编译原理6-LR0.ppt

《编译原理6-LR0.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章ＬＲ分析自下而上的语法分析特定的一种shift-reduce实现技术能力强几乎所有CFG的语言结构都能用LR分析不需要对文法附加条件难点几乎不可能用手工编写LR分析器现实有LR分析器的生成器第六章ＬＲ分析6.1概述自下而上的语法分析LR分析器6.2LR(0)分析6.3SLR(1)分析技术，二义文法的应用6.4LR(1)和LALR(1)分析6.1概述自下而上的语法分析例：文法G：S→cAdA→abA→a识别输入串w=cabd是否该文法的句子SAAcabdcabdcd归约过程构造的推导：cAdcabdScAd(1)S→cAd(2)A→ab(3)A→a识别输入串w=c

2、abd是否为该文法的句子自下而上的语法分析对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么在cAbd中无法找到一个可归约串了，最终就达不到归约到S的结果，因而也无从知道cabd是一个句子在自下而上的分析方法中如何识别可归约的串？在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”cabdcAbda刻画“可归约串”文法G[S]句型的短语S=>*αAδ且A=>+β，则称β是句型αβδ相对于非终结符A的短语句型的直接短语若有Aβ，则称β是句型αβδ相对于非终结符A的直接短语句型的句柄

3、一个句型的最左直接短语称为该句型的句柄例：i*i+i的短语、直接短语和句柄EE+TTFT*Fi3短语：i1*i2+i3，i1*i2，Fi2i1，i2，i3。i1直接短语：i1，i2，i3。句柄：i1G[E]：E→E+T

4、TT→T*F

5、FF→(E)

6、i句型：i*i+i自下而上的语法分析在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”选择“可归约串”是最左素短语（至少含有一个终结符的最左边的短语，且这个短语不包含别的短语）选择“可归约串”是句型的句柄－规范归约G[E]：E→E+T

7、TT→T*F

8、FF→(E)

9、i句型i*i+

10、i的自下而上分析，总是归约当前句型的句柄形成的规范推导序列：EE+TE+FE+iT+iT*F+iT*i+iF*i+ii*i+i句型i*i+i的自下而上分析总是归约当前句型的最左素短语形成的推导：ET+FT+iF*F+iF*i+ii*i+i自下而上的分析模式移进－归约模式Shift:移进，输入符进栈reduce:归约，用第i个产生式归约总控程序output…产生式表Input$(#)…移进归约依据表文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→dabbcde步骤栈余留输入符号串动作1）#abbcde#移进2）#abbcde#

11、移进A3）#abbcde#归约(A→b)4）#aAbcde#移进A5）#aAbcde#归约(A→Ab)6）#aAcde#移进7）#aAcde#移进B8）#aAcde#归约(B→d)9）#aAcBe#移进11）#S#接受S10）#aAcBe#归约(S→aAcBe)符号串abbcde是否是G[S]的句子对输入串abbcde#的移进-归约分析过程SaAcBeaAcdeaAbcdeabbcde6.1概述ＬＲ分析特定的一种shift-reduce实现技术L从左到右扫描输入串R构造最右推导ＬＲ分析器模型总控程序outputInput$(#)…栈LR分析表产生式表LR分析表(1)S

12、aAcBe(2)Ab(3)AAb(4)BdLR分析表ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1LR分析使用两张表ACTION表告诉分析器：栈顶状态为S,当前输入符号是a时做什麽1.ACTION[S,a]=Sj2.ACTION[S,a]=rj(第j条产生式为A)3.ACTION[S,a]=acc4.ACTION[S,a]=errorGOTO表GOTO[S,A]栈顶状态为S，归约之后的非终结符為A时，要放到栈顶的新状态ＬＲ

13、分析G[S]:(1)SaAcBe(2)Ab(3)AAb(4)Bdw=abbcde#Stepstates..Therestofinputactiongoto10abbcde#s2202bbcde#s43024bcde#r2goto(2,A)4023bcde#s650236cde#r3goto(2,A)6023cde#s570235de#s8802358e#r4goto(5,B)902357e#s910023579#r1goto(0,S)1101#acc1)E–>E+T2)E–>T3)T–>(E