编译原理课件第6讲LR分析法

1第六讲LR分析法LR分析概述LR(0)分析SLR(1)分析LR(1)分析LALR(1)分析二义性文法在LR分析中的应用2复习：移进-归约分析3文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→dabbcde步骤符号栈输入符号串动作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abbcde4在步骤3中，用A→b归约在步骤5中，用A→Ab归约问题：何时移进？何时归约？用哪个产生式归约？53）#abbcde#归约(A→b)5）#aAbcde#归约(A→Ab)4）#aAbcde#移进6）#aAcde#移进分析：已分析过的部分在栈中的前缀不同，而且移进和归约后栈中的状态会发生变化我们引入一个新的状态栈来表示符号栈中的符号目前状态用LR分析表来表示不同状态下对于各输入符号应采取的动作6LR分析器工作过程示意图总控程序ACTION表GOTO表S0S1#X1...Sn...XnSP输出a1a2……ai#……an输入串状态栈文法符号栈LR分析表分析栈7LR分析使用两张表ACTION表告诉分析器：栈顶状态为S,当前输入符号是a时做什么1.ACTION[S,a]=Sj2.ACTION[S,a]=rj(第j条产生式为A)3.ACTION[S,a]=acc4.ACTION[S,a]=errorGOTO表GOTO[S,A]栈顶状态为S，归约之后的非终结符为A时，要放到栈顶的新状态8步骤符号栈输入符号串动作1）#abbcde#移进0S22）#abbcde#移进02S44）#aAbcde#移进023S66）#aAcde#移进023S57）#aAcde#移进0235S89）#aAcBe#移进02357S911）#S#接受01acc对输入串abbcde#的LR分析过程3）#abbcde#归约(A→b)024r235）#aAbcde#归约(A→Ab)0236r338）#aAcde#归约(B→d)02358r4710）#aAcBe#归约(S→aAcBe)023579r11状态栈ACTIONGOTO文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→dSi:移进，并将状态i进栈ri:用第i个产生式归约，同时状态栈与符号栈退出相应个符号，产生式左部非终结符入符号栈，根据GOTO表将相应状态入栈ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r2576r3r3r3r3r3r378r4r4r4r4r4r49r1r1r1r1r1r1S8S99问题：对于一个文法，状态集是如何确定的？LR分析表是如何得到的？10,a,ab,a,aA,aAb,a,aA,aAc,aAcd,a,aA,aAc,aAcB,aAcBe可归前缀与活前缀文法G[S]：(1)S→aAcBe[1](2)A→b[2](3)A→Ab[3](4)B→d[4]SaAcBe[1]aAcd[4]e[1]aAb[3]cd[4]e[1]ab[2]b[3]cd[4]e[1]每次归约句型的前部分依次为：ab[2]aAb[3]aAcd[4]aAcBe[1]规范句型的这种前部分符号串称为可归前缀我们把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为活前缀1、a,aA,aAc都不只是某一个规范句型的前缀2、活前缀表明已分析过的部分为规范句型的一个正确部分。11活前缀（ViablePrefixes）定义：S’A是文法G中的一个规范推导，如果符号串γ是的前缀，则称γ是G的一个活前缀。其中S’是对原文法扩充(S’S)增加的非终结符.?为使S’不出现在任何产生式的右部.如G=({S},{a},{SSa,Sa},S)则拓广文法G‘=({S，S’},{a},{S’S,SSa,Sa},S’)R*R12LR分析需要构造识别活前缀的有穷自动机我们可以把文法的终结符和非终结符都看成有穷自动机的输入符号，每次把一个符号进栈看成已识别过了该符号，同时状态进行转换，当识别到可归前缀时，相当于在栈中形成句柄，认为达到了识别句柄的终态。13步骤符号栈输入符号串动作1）#abbcde#移进0S22）#abbcde#移进02S44）#aAbcde#移进023S66）#aAcde#移进023S57）#aAcde#移进0235S89）#aAcBe#移进02357S911）#S#接受01acc对输入串abbcde#的LR分析过程3）#abbcde#归约(A→b)024r235）#aAbcde#归约(A→Ab)0236r338）#aAcde#归约(B→d)02358r4710）#aAcBe#归约(S→aAcBe)023579r11状态栈ACTIONGOTO014235769SabAbcBed8*14步骤符号栈输入符号串动作1）#abbcde#移进0S2对输入串abbcde#的LR分析过程状态栈ACTIONGOTO014235769SabAbcBed8*15步骤符号栈输入符号串动作1）#abbcde#移进0S22）#abbcde#移进02S4对输入串abbcde#的LR分析过程状态栈ACTIONGOTO014235769SabAbcBed8*16步骤符号栈输入符号串动作1）#abbcde#移进0S22）#abbcde#移进02S4对输入串abbcde#的LR分析过程3）#abbcde#归约(A→b)024r23状态栈ACTIONGOTO014235769SabAbcBed8*17步骤符号栈输入符号串动作1）#abbcde#移进0S22）#abbcde#移进02S44）#aAbcde#移进023S6对输入串abbcde#的LR分析过程3）#abbcde#归约(A→b)024r23状态栈ACTIONGOTO014235769SabAbcBed8*18步骤符号栈输入符号串动作1）#abbcde#移进0S22）#abbcde#移进02S44）#aAbcde#移进023S6对输入串abbcde#的LR分析过程3）#abbcde#归约(A→b)024r235）#aAbcde#归约(A→Ab)0236r33状态栈ACTIONGOTO014235769SabAbcBed8*19步骤符号栈输入符号串动作1）#abbcde#移进0S22）#abbcde#移进02S44）#aAbcde#移进023S66）#aAcde#移进023S5对输入串abbcde#的LR分析过程3）#abbcde#归约(A→b)024r235）#aAbcde#归约(A→Ab)0236r33状态栈ACTIONGOTO*014235769SabAbcBed820步骤符号栈输入符号串动作1）#abbcde#移进0S22）#abbcde#移进02S44）#aAbcde#移进023S66）#aAcde#移进023S57）#aAcde#移进0235S8对输入串abbcde#的LR分析过程3）#abbcde#归约(A→b)024r235）#aAbcde#归约(A→Ab)0236r33状态栈ACTIONGOTO*014235769SabAbcBed821步骤符号栈输入符号串动作1）#abbcde#移进0S22）#abbcde#移进02S44）#aAbcde#移进023S66）#aAcde#移进023S57）#aAcde#移进0235S8对输入串abbcde#的LR分析过程3）#abbcde#归约(A→b)024r235）#aAbcde#归约(A→Ab)0236r338）#aAcde#归约(B→d)02358r47状态栈ACTIONGOTO014235769SabAbcBed8*22步骤符号栈输入符号串动作1）#abbcde#移进0S22）#abbcde#移进02S44）#aAbcde#移进023S66）#aAcde#移进023S57）#aAcde#移进0235S89）#aAcBe#移进02357S9对输入串abbcde#的LR分析过程3）#abbcde#归约(A→b)024r235）#aAbcde#归约(A→Ab)0236r338）#aAcde#归约(B→d)02358r47状态栈ACTIONGOTO014235769SabAbcBed8*23步骤符号栈输入符号串动作1）#abbcde#移进0S22）#abbcde#移进02S44）#aAbcde#移进023S66）#aAcde#移进023S57）#aAcde#移进0235S89）#aAcBe#移进02357S9对输入串abbcde#的LR分析过程3）#abbcde#归约(A→b)024r235）#aAbcde#归约(A→Ab)0236r338）#aAcde#归约(B→d)02358r4710）#aAcBe#归约(S→aAcBe)023579r11状态栈ACTIONGOTO014235769SabAbcBed8*24步骤符号栈输入符号串动作1）#abbcde#移进0S22）#abbcde#移进02S44）#aAbcde#移进023S66）#aAcde#移进023S57）#aAcde#移进0235S89）#aAcBe#移进02357S911）#S#接受01acc对输入串abbcde#的LR分析过程3）#abbcde#归约(A→b)024r235）#aAbcde#归约(A→Ab)0236r338）#aAcde#归约(B→d)02358r4710）#aAcBe#归约(S→aAcBe)023579r11状态栈ACTIONGOTO014235769SabAbcBed8*25如何构造识别活前缀的有限自动机已经有了活前缀如何构造有限自动机?活前缀及其可归前缀的一般计算方法26文法G‘[S]：S’→S[0]S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]句子abbcde的可归前缀如下：S[0]ab[2]aAb[3]aAcd[4]aAcBe[1]构造识别其活前缀及可归前缀的有限自动机如下：104387131210182591461715161110SabaAbaAcdaAcBe*1*句子识别态i句柄识别态27104387131210182591461715161110SabaAbaAcdaAcBe*X加上开始状态X确定化得DFA014235769SabAbcBed8*识别活前缀的确定的有限自动机28活前缀及其可归前缀的一般计算方法定义(非终结符的左文)：文法G，AVN,LC(A)={|S’A,V*,VT*}对拓广文法的开始符号S’:LC(S’)={}规范推导中在非终结符A左边所有可能出现的符号串的集合。推论：若文法G中有产生式B→A，则有LC(A)LC(B)·{}因为:S’BAR*R*R29文法G’[S]：S’→S[0]S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]由前面的定义与推论我们知：LC(S’)={}LC(S)=LC(S’).{}LC(A)=LC(S).{a}LC(A).{}LC(B)=LC(S).{aAc}化简为：[S’]=[S]=[S’][A]=[S]a+[A][B]=[S]aAc代入法求解方程组可得：[S’]=[S]=[A]=a+[A][B]=aAc[A]=a|[A]=a*=a这样我们求出了每个非终结符在规范推导中用该非终结符的右部替换该非终结符之前，它的左部可能出现的所有前缀，也就是在规范归约过程中用句柄归约成该非终结符之前不包括句柄的活前缀。30不包括句柄的活前缀+句柄=？可归前缀？令LR(0)C(A→)=L