资源描述：
《安徽大学编译原理课件第七章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、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）#aAcde#归约(B→d)9）#aAcBe#移进11）#S#接受S10）#aAcBe#归约(S→aAcBe)分析符号串abbcde是否G[S]的句子对输入串abbcde#的移进-规约分析过程SaAcBeaAcdeaAbcdeabbcde2在步骤3中，用A→b归约在步
2、骤5中，用A→Ab归约问题：何时移进？何时归约？用哪个产生式归约（如何找当前句柄归约）？33）#abbcde#归约(A→b)5）#aAbcde#归约(A→Ab)4）#aAbcde#移进6）#aAcde#移进分析：已分析过的部分在栈中的前缀不同，而且移进和归约后栈中的状态会发生变化我们引入一个新的状态栈来表示符号栈中的符号目前状态用LR分析表来表示不同状态下对于各输入符号应采取的动作4LR分析器工作示意图5步骤符号栈输入符号串动作1）#abbcde#移进0S22）#abbcde#移进02S44）#aAbcde#移进023S66）#aAcde#移进023S57）#aAcde#移进0235
3、S89）#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表将相应状态入栈S8S96问题：对于一个文法，状态集是如何确定的？LR分析表是如
4、何得到的？答案：需要构造识别可归前缀的有穷自动机7可归前缀与活前缀文法G[S]： (1)S→aAcBe[1] (2)A→b[2] (3)A→Ab[3] (4)B→d[4]SaAcBe[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,aAcBe8活
5、前缀定义：S’A是文法G中的一个规范推导，如果符号串γ是的前缀，则称γ是G的一个活前缀。（在当前句型中，不包含句柄右边的符号）LR分析需要构造识别可归前缀的有穷自动机把文法的终结符和非终结符都看成有穷自动机输入符号，每次把一个符号进栈看成已识别过了该符号，同时状态进行转换，当识别到可归前缀（栈中形成句柄）时，认为达到了识别句柄的终态。注：在符号栈中，始终存放当前句型的活前缀98014235769SabAbcBed*S8S9句子abbcde的可归前缀：ab[2] aAb[3] aAcd[4] aAcBe[1]文法G[S]： (1)S→aAcBe[1] (2)A→b[2]
6、 (3)A→Ab[3] (4)B→d[4]1句子识别态i句柄识别态*10如何构造识别可归前缀的有限自动机已经有了可归前缀如何构造有限自动机?活前缀及其可归前缀的一般计算方法11文法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]构造识别其活前缀及可归前缀的有限自动机如下：10141516S**1043871312182596171110abaAbaAcdaAcBe1句子识别态i句柄识别态1210438713121018259146171516
7、1110SabaAbaAcdaAcBe*X加上开始状态X确定化X13246859SabAbcBed7*识别活前缀的确定的有限自动机该文法特殊13活前缀及其可归前缀的一般计算方法定义：文法G，AVN,LC(A)={
8、S’A,V*,VT*}规范推导中在非终结符A左边所有可能出现的符号串的集合(不包括句柄的活前缀?)推论：若文法G中有产生式B→A，则有LC(A)LC(B)·{}左文Proveit?14文法G’[S]： S’→
