第6讲 LR分析法.ppt

《第6讲 LR分析法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六讲LR分析法LR分析概述LR(0)分析SLR(1)分析LR(1)分析LALR(1)分析二义性文法在LR分析中的应用复习：移进-归约分析文法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

2、]的句子对输入串abbcde#的移进-规约分析过程SaAcBeaAcdeaAbcdeabbcde在步骤3中，用A→b归约在步骤5中，用A→Ab归约问题：何时移进？何时归约？用哪个产生式归约？3）#abbcde#归约(A→b)5）#aAbcde#归约(A→Ab)4）#aAbcde#移进6）#aAcde#移进分析：已分析过的部分在栈中的前缀不同，而且移进和归约后栈中的状态会发生变化引入一个新的状态栈来表示符号栈中的符号目前状态；用LR分析表来表示不同状态对各输入符号应采取的动作。LR分析器工作过程示意图总控程序ACTION表GOTO表S0S1#X1...Sn...XnSP输出a

3、1a2……ai#……an输入串状态栈符号栈LR分析表步骤符号栈输入符号串动作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)

4、S→aAcBe(2)A→b(3)A→Ab(4)B→dSi:移进，并将状态i进栈ri:用第i个产生式归约，同时状态栈与符号栈退出相应个符号，根据GOTO表将相应状态入栈S8S9问题：对于一个文法，状态集是如何确定的？LR分析表是如何得到的？可归前缀与活前缀文法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]规范句型的这种前部分符

5、号串称为可归前缀把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为活前缀,a,ab,a,aA,aAb,a,aA,aAc,aAcd,a,aA,aAc,aAcB,aAcBe活前缀（ViablePrefixes）定义：S’A是文法G中的一个规范推导，如果符号串γ是的前缀，则称γ是G的一个活前缀。LR分析需要构造识别活前缀的有穷自动机把文法的终结符和非终结符都看成有穷自动机的输入符号，每次把一个符号进栈看成已识别过了该符号，同时状态进行转换，当识别到可归前缀时，相当于在栈中形成句柄，认为达到了识别句柄的终态。步骤符号栈输入符号串动作1）#abbcde#移进0

6、S22）#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*步骤符号栈输入符号串动作1）#abbcde#移进0S2对输入串abbcde#的LR

7、分析过程状态栈ACTIONGOTO014235769SabAbcBed8*步骤符号栈输入符号串动作1）#abbcde#移进0S22）#abbcde#移进02S4对输入串abbcde#的LR分析过程状态栈ACTIONGOTO014235769SabAbcBed8*步骤符号栈输入符号串动作1）#abbcde#移进0S22）#abbcde#移进02S4对输入串abbcde#的LR分析过程3）#abbcde#归约(A→b)024r23状态栈ACTIONGOTO014235