编译原理(清华)第七章LR分析法

第7章LR分析法学习目标：掌握：LR（0）分析，SLR（1）分析理解：活前缀，可归前缀了解：LR(1)、LALR(1)分析思想7.1LR分析概述7.2LR(0)分析7.3SLR(1)分析7.4LR(1)、LALR(1)分析思想回顾：自底向上分析实现的基本思想——“移进－归约”方法(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d判断输入串abbcde#是否为该文法的句子归约（S→aAcBe）##aAcBe10）接受##S11）移进ee##aAcB9）归约（B→d）e##aAcd8）移进dde##aAc7）归约（A→Ab）cde##aAb5）移进ccde##aA6）移进bbcde##aA4）归约（A→b）bcde##ab3）移进bbbcde##a2）移进aabbcde##1）动作输入符号串符号栈步骤1.LR分析法：根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的K个（K=0）符号就可唯一地确定句柄。LR(K)的含义：L表示从左到右扫描输入串R表示最左规约（即最右推导的逆过程）K表示向右查看输入串符号的个数当K=1时，能满足当前绝大多数高级语言编译程序的需要，所以着重介绍LR(0),SLR(1),LR(1),LALR(1)方法7.1LR分析概述LR分析的特点：是规范归约适用范围广，适用于大多数上下文无关文法描述的语言分析速度快，能准确定位错误缺点：LR分析器的构造工作量大2.LR分析器的组成1)总控程序：所有LR分析器总控程序相同。2)分析表：不同文法有不同的分析表同一文法采用的LR分析器不同，分析表也不同分析表分为ACTION表（动作表）和GOTO表（状态转换表）。3)分析栈：包括状态栈S和文法符号栈X。分析表是LR分析器的核心3.LR分析表：列标题为状态，行标题为文法符号GOTO表示当前状态面临文法符号时应转向的下一个状态。ACTION表示当前状态面临输入符号时应采取的动作ACTIONGOTOacebd#acebd#SAB0S211acc2SS133r2r2r2r2r2r2为了节省空间，将ACTION和GOTO中关于终结符号的各列合并起来ACTIONGOTOacebd#acebd#SAB0S211acc2SS133r2r2r2r2r2r2ACTIONGOTOacebd#SAB0S211acc2S1S33r2r2r2r2r2r2ACTION表中的动作有4种：1)移进(Sk)：把状态k移入状态栈，若当前状态是i，且k=GOTO[i,a]，把a移入符号栈2)归约(rk)：用第k条产生式进行归约，此时栈顶形成了句柄β，文法中第k条产生式为A-β，且|β|=r，归约时从状态栈和符号栈中弹出r个符号，把A移入符号栈，j=GOTO[i,A]移入状态栈，其中状态i为修改指针后的栈顶状态3)接受(acc)：当符号栈只剩文法开始符S，并且当前输入符为‘＃’，则分析成功4)报错：当状态栈顶的状态遇到了不应该出现的文法符号，则报错，说明输入串不是该文法的句子LR分析器的工作过程示意图输入串a1a2…an#总控程序ACTION表GOTO表nXn。。。。10X1#SP输出状态栈文法符号栈栈指针LR分析器：在分析的每一步，通用的总控程序按照状态栈栈顶状态i和当前输入符号a查LR分析表，并执行其中ACTION和GOTO规定的操作。LR分析例（LR(0)分析）文法G[S]：(1)S-aAcBe(2)A-b(3)A-Ab(4)B-d对输入串abbede＃进行LR分析ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1LR(0)分析表为：对输入串abbcde#的分析过程(1)S-aAcBe(2)A-b(3)A-Ab(4)B-dacc##011R1##aAcBe02357910S9e##aAc02359R4e##aAcd023588S8de##aAc02357S5cde##a026R3cde##aAb02365S6bcde##a024R2bcde##ab0243S4bbcde##a022S2abbcde##01GOTOACTION输入串符号栈状态栈步骤A333A37B71S17.2LR(0)分析使用LR(0)分析表的LR分析器称为LR(0)分析器。LR(0)分析器在分析的过程中只根据符号栈的内容就能确定句柄，不需要向右查看输入符号对文法的限制较大，对绝大多数高级语言的语法分析器不适用构造LR(0)分析表的思想和方法是构造其他LR分析表的基础。例文法：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d判断输入串abbcde#是否为该文法的句子归约（S→aAcBe）##aAcBe10）接受##S11）移进ee##aAcB9）归约（B→d）e##aAcd8）移进dde##aAc7）归约（A→Ab）cde##aAb5）移进ccde##aA6）移进bbcde##aA4）归约（A→b）bcde##ab3）移进bbbcde##a2）移进aabbcde##1）动作输入符号串符号栈步骤LR(k)分析法通过活前缀来帮助确定句柄规范句型的可归约前缀和活前缀(7.2.1)构造文法的识别活前缀及可归前缀的DFA(7.2.2，7.2.3)按DFA构造相应分析表——状态转换表和动作表(7.2.4)按分析表进行LR(k)分析(7.2.5)7.2.1规范句型的可归约前缀和活前缀什么是可归前缀？什么是活前缀？可归前缀和活前缀在LR分析中起什么作用？前缀如果Z=xy是一符号串，则x是Z的前缀，其中x,y为任意符号串（包括空串ε）例：abc的前缀有ε，a，ab，abc。可归前缀规范句型中句柄之前包括句柄在内的串称为可归前缀。例：文法G[S]，其中产生式后[i]是其编号S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]输入串abbcde的最右推导（规范推导）过程：S=aAcBe[1]=aAcd[4]e[1]=aAb[3]cd[4]e[1]=ab[2]b[3]cd[4]e[1]最左归约(规范归约)过程：ab[2]b[3]cd[4]e[1]用产生式[2]归约├aAb[3]cd[4]e[1]用产生式[3]归约├aAcd[4]e[1]用产生式[4]归约├aAcBe[1]用产生式[1]归约├S可归前缀有：ab[2]，aAb[3]，aAcd[4]，aAcBe[1]活前缀定义：形成可归前缀之前(包括可归前缀在内)的所有规范句型（符号栈内部分）的前缀称为活前缀。即规范句型的不含句柄右边符号的前缀称为活前缀。例：规范句型aAbcde(下划线为句柄)的可归前缀为aAb，活前缀为：ε，a，aA，aAb可归前缀和活前缀在LR分析中的作用在LR分析过程中，实际上是把活前缀列出放在符号栈中，一旦在栈中出现可归前缀，即句柄已经形成，就用相应的产生式进行归约，在分析的过程中，只要符号栈中的符号串是一个活前缀，就可保证已被分析过的部分是该文法规范句型的正确部分。归约（S→aAcBe）##aAcBe10）接受##S11）移进ee##aAcB9）归约（B→d）e##aAcd8）移进dde##aAc7）归约（A→Ab）cde##aAb5）移进ccde##aA6）移进bbcde##aA4）归约（A→b）bcde##ab3）移进bbbcde##a2）移进aabbcde##1）动作输入符号串符号栈步骤7.2.2识别活前缀的有穷自动机回顾：有穷自动机——一种识别装置分DFA和NFA0X13104Y151识别1(0|1)*101的NFA用有穷自动机来识别活前缀和可归前缀有穷自动机如何构造？一个特例：构造识别活前缀和可归前缀的有穷自动机由文法的产生式构造识别活前缀和可归前缀的有穷自动机的方法用有穷自动机来识别活前缀和可归前缀有穷自动机的输入字符：终结符和非终结符状态转换：每把一个符号进栈，就看成识别过了该符号，进行状态转换。因为LR分析时栈中始终保持是活前缀，所以有穷自动机识别过的符号串也是活前缀。终态：当识别到可归约前缀（表明在栈中形成句柄），认为到达了识别句柄的终态，执行归约例如：识别可归前缀aAcBe的有穷自动机12aA3c46B5e构造识别活前缀和可归约前缀的有穷自动机的一个例子：由句子规范推导的逆过程直观的看出它的活前缀和可归前缀按活前缀和可归前缀构造识别它们的有穷自动机例文法G：S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]拓广文法为：S’-S[0]S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]拓广原因：文法开始符S可能出现在产生式的右部，在归约过程中，不能判断是归约到文法的最初开始符，还是归约到在产生式右部出现的开始符，S’只在产生式左部出现，确保不会混淆。S’-S[0]S→aAcBe[1]A→b[2]A→Ab[3]B→d[4]输入串abbcde的最右推导过程：S’=S[0]=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]，S[0]输入串abbcde的可归前缀有：S[0]，ab[2]，aAb[3]，aAcd[4]，aAcBe[1]识别其活前缀和可归前缀的NFA为：X025914εεεεε1S*3a4b6aA78b10aA11c1213d15aA16c1719B18e识别活前缀和可归前缀的NFA所有的状态都是活前缀的识别状态终态是句柄的识别态带“*”号的状态既是句柄识别态又是句子识别态，句子识别态仅有一个符号栈输入串动作#abbcde#移进a#abbcde#移进b#abbcde#归约(A-b)#aAbcde#移进b#aAbcde#归约(A-Ab)#aAcde#移进c#aAcde#移进d#aAcde#归约(B-d)#aAcBe#移进e#aAcBe#归约(S-aAcBe)#S#接受X2a1*SA45b3b6c7dB89e识别活前缀和可归前缀的DFA理解识别活前缀和可归前缀的DFA和分析过程的对应将NFA确定化得到：S[0]，ab[2]，aAb[3]，aAcd[4]，aAcBe[1]ACTIONGOTOacebd#SABXS211acc2S343r2r2r2r2r2r24S6S55r3r3r3r3r3r36S787r4r4r4r4r4r48S99r1r1r1r1r1r1对任何一个上下文无关文法只要构造出它的识别活前缀和可归前缀的有穷自动机，就可以构造其相应的分析表（ACTION表和GOTO表），进行LR分析S[0]，ab[2]，aAb[3]，aAcd[4]，aAcBe[1]X2a1*SA45b3b6c7dB89e识别活前缀和可归前缀的DFA以上示例中构造DFA的方法是通过一个句子的归约过程确定可归前缀，但是：对于一个复杂的文法，其可归前缀不是如此简单就能计算出来示例中用一个句子归约过程的所有活前缀和可归前缀构造出的DFA，恰好也是识别整个文法的活前缀和可归前缀的DFA，这仅是一个特殊情况。对一个上下文无关文法需要求出它的所有活前缀和可归前缀后才能构造其识别该文法活前缀的DFA由文法的产生式构造识别活前缀和可归前缀的DFA的方法1.LR(0)项目文法的识别活前缀的有穷自动机以“项目”作为它的状态在文法G中每个产生式的右部适当位置添加一个圆点构成项目例：产生式U→XYZ对应有4个项目[0]U→•XYZ[1]U→X•YZ[2]U→XY•Z[3]U→XYZ•产生式A→ε只有一个项目A→•项目的含义：圆点在最左部（U→•XYZ）表示希望用产生式的右部归约圆点的左部（U→X•YZ）表示分析过程中已识别过的部分圆点的右部（U→X•YZ）表示待识别部分圆点达到最右边（U→XYZ•）表示句柄已形成，可以进行归约。LR(0)项目分类移进项目