《编译原理》课程简介 (39).pdf
编 译 原 理C O M P I L A T I O N P RIN C IP LE 第五章 语法分析自下而上分析5.3.5 由DFA构造LR(0)分析表5.3.5 由DFA构造LR(0)分析表v LR(0)分析表的构造LR(0)分析表由两部分组成动作表表示当前状态下面临输入符号应做的动作是移进、归约、接受或出错；状态转换表表示在当前状态下面临文法符号时应转向的下一个状态。5.3.5 由DFA构造LR(0)分析表vLR(0)分析表的构造n构造原则：设有文法GS，则LR(0)分析表的构造规则为：对于A XSi，GOTO(Si,X)=Sj若X Vt，则置actionSi,X=Sj若X Vn，则置gotoSi,X=j对于A Si，若A 是文法的第j个产生式，则对所有的xVt，均置actionSi,x=rj 若S Si，则置actionSi,#=acc其他均置出错。5.3.5 由DFA构造LR(0)分析表vLR(0)分析表的构造n假定C=I0,I1,In，令每个项目集Ik的下标k 为分析器的一个状态，因此，G 的LR(0)分析表含有状态0，1，n。令那个含有项目SS的Ik的下标k为初态。ACTION和GOTO可按如下方法构造：u若项目Aa属于Ik且GO(Ik,a)=Ij,a为终结符，则置ACTIONk,a为“把状态j和符号a移进栈”，简记为“sj”;u若项目A属于Ik,那么，对任何终结符a,置ACTIONk,a为“用产生式A进行规约”，简记为“rj”;其中，假定A为文法G的第j个产生式；u若GO(Ik,A)=Ij,A为非终结符，则置GOTO(k,A)=j;u若项目SS属于Ik,则置ACTIONk,#为“接受”，简记为“acc”;u分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”5.3.5 由DFA构造LR(0)分析表v例子：文法G为：(0)S E (1)E aA (2)E bB (3)A cA (4)A d (5)B cB (6)B dn该文法的状态描述序列见下表5.3.5 由DFA构造LR(0)分析表状态项目集后继符号后继状态S0S EE aAE bBEabS1S2S3S1S E#S12S2Ea A A cAA dAcdS6S4S10S3EbB B cBB dBcdS7S5S115.3.5 由DFA构造LR(0)分析表状态项目集后继符号后继状态S4A c AA cAA dAcdS8S4S10S5Bc BB cBB dBcdS9S5 S11S6EaA#EaA S12S7EbB#EbB S12S8A cA#A cAS125.3.5 由DFA构造LR(0)分析表状态项目集后继符号后继状态S9BcB#BcBS12S10Ad#AdS12S11Bd#BdS12S12 n根据状态描述序列和分析表的构造规则得到的LR(0)分析表如下：5.3.5 由DFA构造LR(0)分析表状态ACTIONGOTOabcd#EABS0S2S31S1accS2S4S106S3S5S117S4S4S108S5S5S119S6r1r1r1r1r1S7r2r2r2r2r2S8r3r3r3r3r3S9r5r5r5r5r5S10r4r4r4r4r4S11r6r6r6r6r65.3.5 由DFA构造LR(0)分析表状态栈符号栈产生式输入符actiongoto说明S0#bccd#S3b和S3进栈S0S3#bccd#S5c和S5进栈S0S3S5#bccd#S5c和S5进栈S0S3S5S5#bccd#S11d和S11进栈S0S3S5S5S11#bccdB d#r69d和S11退栈B和S9进栈S0S3S5S5S9#bccBB cB#r59S0S3S5S9#bcBB cB#r57S0S3S7#bBE bB#r21S0S1#E#acc接受|编译原理谢 谢Thanks
