编译原理 之 LR分析程序及其构造.ppt

《编译原理 之 LR分析程序及其构造.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第7章ＬＲ分析程序及其构造自下而上分析及其LR分析概述LR(0)分析SLR(1)分析LR（1）分析LALR分析使用二义文法自底向上分析方法是一种移进--归约过程.分析栈的栈顶符号形成句柄时--归约.自底向上分析方法的关键问题--确定句柄.LR分析的归约过程是规范（最右）推导的逆过程.LR分析过程是一种规范（最左）归约过程.LR分析方法对文法的限制少，速度快.LR分析器的构造工作量大.7.1自下而上的语法分析概述例：文法G：S→cAdA→abA→a识别输入串w=cabd是否该文法的句子SAAcabdcabdcd归约过程构造的推导：cAdc

2、abdScAd(1)S→cAd(2)A→ab(3)A→a识别输入串w=cabd是否为该文法的句子自下而上的语法分析对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么在cAbd中无法找到一个可归约串了，最终就达不到归约到S的结果，因而也无从知道cabd是一个句子.在自下而上的分析方法中如何识别可归约串？在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”cAbda文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→dabb

3、cde步骤栈余留输入符号串动作1）#abbcde#移进2）#abbcde#移进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abbcde刻画“可归约串”文法G[S]句型的短语SαAδ且Aβ，则称β是句型αβδ相

4、对于非终结符A的短语句型的直接短语若有Aβ，则称β是句型αβδ相对于非终结符A的直接短语句型的句柄一个句型的最左直接短语称为该句型的句柄例：i*i+i的短语、直接短语和句柄EE+TTFT*Fi3短语：i1*i2+i3，i1*i2，Fi2i1，i2，i3。i1直接短语：i1，i2，i3。句柄：i1G[E]：E→E+T

5、TT→T*F

6、FF→(E)

7、i句型：i*i+i自下而上的语法分析在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”算符优先－选择“可归约串”是最左素短语（至少含有一个终结

8、符的最左边的短语，且这个短语不包含别的短语）规范归约－选择“可归约串”是句型的句柄G[E]：E→E+T

9、TT→T*F

10、FF→(E)

11、i句型i*i+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ＬＲ分析器模型总控程序outputInput×××#SnXm…S1…X1S0#栈状态文法符号ACTIONGOTOLR分析表产生式表L

12、R分析使用两张表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时，要放到栈顶的新状态步骤符号栈输入符号串动作1）#abbcde#移进0action[0,a]=S22）#abbcde#移进02S44）#aAbcde#移进023S66）#aAcde#移进023S57）#aAcde#移进0235S89）#

13、aAcBe#移进02357S911）#S#接受01acc对输入串abbcde#的LR分析过程3）#abbcde#归约(A→b)024r2goto[2,A]=35）#aAbcde#归约(A→Ab)0236r3goto[2,A]=38）#aAcde#归约(B→d)02358r4goto[5,B]=710）#aAcBe#归约(S→aAcBe)023579r1goto[0,S]=1状态栈ACTIONGOTO文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→dSi:移进，将状态i和输入符进栈ri:归约，用第i个产生式归约，同

14、时状态栈与符号栈退出相应个符号，并把GOTO表相应状态和第i个产生式的左部非终结符入栈。7.2LR(0)分析构造DFA识别规范句型特定前缀(就到句柄为止).LR(0)项目集规范族的构造LR(0