编译原理7-LR(0).ppt

《编译原理7-LR(0).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章LR分析7.1概述7.2LR(0)分析7.3SLR(1)分析7.4LR(1)分析7.5LALR(1)分析7.6二义性文法在LR分析中的应用重点讲解内容LR分析概述能力强几乎所有CFG的语言结构都能用LR分析不需要对文法附加条件难点几乎不可能用手工编写LR分析器现实有LR分析器的生成器LR分析属于自下而上的分析方法移进-归约可归约串及相关概念：短语；直接短语；最左素短语；句柄；规范归约——选择“可归约串”为句型的句柄自下而上分析：通用模型总控程序output…产生式表Input$(#)移进归

2、约依据表符号栈自下而上的分析：LR分析器模型总控程序output…产生式表Input$(#)LR分析表符号栈LR分析L从左到右扫描输入串R构造最右推导(最左归约)LR分析表主要包括ACTION表和GOTO表这两张表的含义分别什么？LR分析使用两张表ACTION表的作用告诉分析器在栈顶状态为S,当前输入符号是a时做什麽(下面是几种可能动作)ACTION[S,a]=SjACTION[S,a]=rj(第j条产生式为A)ACTION[S,a]=accACTION[S,a]=errorGOTO表的作用

3、告诉分析器在栈顶状态为S，归约之后的非终结符為A时，要放到栈顶的新状态自下而上语法分析：例设有文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d对输入串abbcde使用移进-归约的方法分析它是否为上述文法的句子先看自上而下的推导过程：SaAcBeaAcdeaAbcdeabbcdeSaAcBeaAcdeaAbcdeabbcde…………续：普通自下而上分析过程步骤符号栈输入符号串动作(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)##a

4、#ab#aA#aAb#aA#aAc#aAcd#aAcB#aAcBe#Sabbcde#bbcde#bcde#bcde#cde#cde#de#e#e###移进移进归约(A→b)移进归约(A→Ab)移进移进归约(B→d)移进归约(S→aAcBe)接受ACTION表和GOTO表ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1StepstatesTherestofi

5、nputactiongoto10abbcde#s2202bbcde#s43024bcde#r2goto(2,A)4023bcde#s650236cde#r3goto(2,A)6023cde#s570235de#s8802358e#r4goto(5,B)902357e#s910023579#r1goto(0,S)1101#acc续：LR分析过程步骤符号栈输入符号串动作1）#abbcde#移进0S22）#abbcde#移进02S44）#aAbcde#移进023S66）#aAcde#移进023S57）

6、#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个产生式归约，同时

7、状态栈与符号栈退出相应个符号，并把GOTO表相应状态和第i个产生式的左部非终结符入栈。LR分析ACTION表表达如此含义，即栈顶状态为S,当前输入符号是a的时候采取什麽动作---?有穷狀态自动机特征规范的符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号分析决策依据――栈顶状态和现行输入符号。识别规范句型特定前缀(就到句柄为止)的DFA四种技术LR(0)SLR(1)LR(1)LALR(1)前缀相关的几个概念LR(0)分析表构造思想和方法是其他LR分析表构造的基础先认识一下前缀问题可归前缀子

8、前缀活前缀前缀问题回到前例的归约过程：SaAcBe[1]aAcd[4]eaAb[3]cdeab[2]bcde其每次归约时句型的前部分别为：ab[2]所有可能前缀：,a,abaAb[3]所有可能前缀：,a,aA,aAbaAcd[4]所有可能前缀：,a,aA,aAc,aAcdaAcBe[1]所有可能前缀：,a,aA,aAc,aAcd,aAcBe…………文法的拓广文法的开始符号可以出现在右部，也就可能作为前缀的一个部分出现。为了保证文法的开始符号只出现在产生式的左部，对原有文法进行简单