第7章 LR分析法(lly)3.ppt

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

1、第七章LR分析法考查重点：LR(0)、SLR(1)、LR(1)，LALR(1)项目集规范族的构造，识别活前缀的DFA的构造，分析表的构造，及输入串的分析。LR(0)、SLR(1)、LR(1)、LALR(1)文法及其关系和区别文法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）#

2、aAcde#归约(B→d)9）#aAcBe#移进11）#S#接受S10）#aAcBe#归约(S→aAcBe)分析符号串abbcde是否G[S]的句子对输入串abbcde#的移进-规约分析过程SaAcBeaAcdeaAbcdeabbcde在步骤3中，用A→b归约在步骤5中，用A→Ab归约问题：何时移进？何时归约？用哪个产生式归约（如何找当前句柄归约）？3）#abbcde#归约(A→b)5）#aAbcde#归约(A→Ab)4）#aAbcde#移进6）#aAcde#移进分析：已分析过的部分在栈中的前缀不同，而且移进和归约后栈中

3、的状态会发生变化我们引入一个新的状态栈来表示符号栈中的符号目前状态用LR分析表来表示不同状态下对于各输入符号应采取的动作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）#aAcd

4、e#归约(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表将相应状态入栈S8S9问题：对于一个文法，状态集是如何确定的？LR分析表是如何得到的？答案：需要构造识别可归前缀的有穷自动机可归前缀与活前缀文法G[S]：(1)S→aAcBe[1](2)A→b[2](3)A→Ab[3](4)B→d

5、[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]规范句型的这种前部分符号串称为可归前缀我们把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为活前缀,a,ab,a,aA,aAb,a,aA,aAc,aAcd,a,aA,aAc,aAcB,aAcBe活前缀定义：S’A是文法G中的一个规范推导，如果符号串γ是的前缀，则称γ是G的一个活前缀。（

6、在当前句型中，不包含句柄右边的前缀）LR分析需要构造识别可归前缀的有穷自动机把文法的终结符和非终结符都看成有穷自动机输入符号，每次把一个符号进栈看成已识别过了该符号，同时状态进行转换，当识别到可归前缀（栈中形成句柄）时，认为达到了识别句柄的终态。注：在符号栈中，始终存放当前句型的活前缀8014235769SabAbcBed*S8S9句子abbcde的可归前缀：ab[2]aAb[3]aAcd[4]aAcBe[1]文法G[S]：(1)S→aAcBe[1](2)A→b[2](3)A→Ab[3](4)B→d[4]1句子识

7、别态i句柄识别态*如何构造识别可归前缀的有限自动机已经有了可归前缀如何构造有限自动机?活前缀及其可归前缀的一般计算方法文法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句柄识别态104387131210182591461715

8、161110SabaAbaAcdaAcBe*X加上开始状态X确定化X13246859SabAbcBed7*识别活前缀的确定的有限自动机活前缀及其可归前缀的一般计算方法定义：文法G，AVN,LC(A)={

9、S’A,V*,VT*}规范推