编译原理,清华大学,第2版_第7章 LR分析法

第7章ＬＲ分析法教学要求：要求理解可归约串、有效项目的基本概念；掌握分析方法。教学重点：LR族文法、分析表的构造。语法分析方法:1、预测分析法（仅限于LL（1）文法）2、算符优先分析法（仅限于算符优先文法）3、LR分析法（适用范围广；分析速度快；报错准确）7.1ＬＲ分析概述一、LR分析法含义L：从左到右扫描输入串R：最右推导的逆过程(即最左归约）LR(K)分析法:根据当前分析栈中的符号串和向右顺序查看输入串的K个（K≥0）符号唯一地确定分析器的动作是移进还是归约和用哪个产生式归约。（2）动作（ACTION）表：ACTION[i,a]规定当前状态i遇到输入符号a应执行的动作。a)移进Sj：符号a、状态j分别进入符号栈和状态栈。b)归约rj：栈顶形成句柄为β时,有产生式A→β(第j个产生式）,|β|=n,两个栈均出栈n项,状态栈顶为i′;然后符号A和状态k=GOTO[i′,A]分别进栈。c)acc:接受d)报错a1…ai…an#LR主控程序动作表action转移表goto产生式序列状态/符号输入缓冲区分析表SmSm-1………S10XmXm-1………X1#二、ＬＲ分析器模型（1）状态转换（GOTO）表：GOTO[i,X]=j规定当前状态i遇到文法符号为X时转换到状态j。输入串（单词系列）LR分析程序action表和goto表输出信息文法本章学习思路分析程序算法构造三、LR分析算法置ip指向输入串w的第一个符号；0和#分别进栈；令S为栈顶状态；a是ip指向的符号；BeginifACTION[S,a]=Sjthenbeginj、a分别进栈；ip指向下一输入符号；enda1…ai…an#LR主控程序动作表action转移表goto产生式序列状态/符号输入缓冲区分析表SmSm-1………S10XmXm-1………X1#elseifACTION[S,a]=rj(第j条产生式为A)thenbegin出栈||项；令当前栈顶状态为S’，A和GOTO[S’,A]分别进栈；endelseifACTION[S,a]=accthenreturn(成功）elseerrorend.a1…ai…an#LR主控程序动作表action转移表goto产生式序列状态/符号输入缓冲区分析表SmSm-1………S10XmXm-1………X1#G[S]:S→ifSelseS(1)S→ifS(2)S→S;S(3)S→a(4)输入串ifaelsea;a#的分析过程状态符号输入串01#S#03578#ifSelseS#0357846#ifSelseS;S#0357842#ifSelseS;a#035784#ifSelseS;a#03578#ifSelseS;a#03572#ifSelsea;a#0357#ifSelsea;a#035#ifSelsea;a#032#ifaelsea;a#03#ifaelsea;a#0#ifaelsea;a#1、符号栈中的内容加上余留的输入串的内容构成规范句型。2、是规范的规约(是规范推导的逆过程)。3、分析决策依据:栈顶状态和现行输入符号．四种技术LR(0)SLR(1)LR(1)LALR(1)四、ＬＲ分析说明为了介绍LR分析过程，在这里直接给出该文法的分析表，之后再介绍如何生成该表。状态ACTIONGOTOab,#LES0S3S412S1accS2S5r2S3r3r3S4r4r4S5S3S462S6r1ri表示按第i个产生式进行归约Si表示把当前输入符号移进栈，且转第i个状态，即第i个状态进状态栈。i表示转第i个状态，即第i个状态进状态栈。空白表示分析动作出错。自底向上分析法的关键问题是在分析过程中如何确定句柄。LR方法中的句柄是通过求可归前缀而求得。7.2LR(0)分析一、可归约前缀1、符号串S的前缀：移走符号串的尾部的零个或多个符号所得到的一个符号串。例：ban是banana的一个前缀。2、符号串S的后缀：删去符号串的头部的零个或多个符号所得到的一个符号串。例：nana是banana的一个后缀。3、可归前缀：如果一个句型含有这样一个前缀，这个前缀的后缀是该句型的句柄，则这个前缀称为该句型的可归前缀。例：SaAcBe[1]Ab[2]AAb[3]Bd[4]输入串：abbcde。规范推导过程为：逆过程:(分析栈，输入流)(-，abbcde)(a，bbcde)(ab，bcde)(aA，bcde)(用[2]归约)(aAb，cde)(aA，cde)(用[3]归约)(aAc，de)(aAcd，e)(aAcB，e)(用[4]归约)(aAcBe，-)(S，-)(用[1]归约)SaAcBe[1]aAcd[4]e[1]aAb[3]cd[4]e[1]ab[2]b[3]cd[4]e[1]问题:在归约过程中,那些是可归前缀?4、活前缀：G=(Vn,Vt,P,S),若有S′αAωαβω,A→β(β是句柄,αβ是可归前缀),γ是αβ的前缀,则称γ是文法G的活前缀.即，形成可归约前缀之前，包括可归约前缀在内的所有规范句型的前缀称为活前缀。（可归前缀的前缀称为活前缀）其中S′是对原文法扩充(S′S)增加的非终结符.在LR分析过程中，实际上是把αβ的前缀（即文法G的活前缀）列出放在符号栈中，一旦在栈中出现αβ（形成可归前缀），即句柄已经形成，则用产生式Aβ进行归约。对任何一个上下文无关文法，只要能构造出它的识别可归前缀的有限自动机，就可以构造其相应的分析表（状态转换表和动作表）。二、构造识别可归约前缀的DFALR分析方法的核心问题是首先从给定的文法构造一个识别该文法所有活前缀的确定的有限自动机(DFA)，然后根据DFA去构造它的分析表。1、LR（0）项目项目：文法G的每个产生式(规则)的右部添加一个圆点就构成一个项目。AxyzA·xyzAx·yzAxy·zAxyz·LR(0)项目说明1）一个产生式可对应的项目数为它的右部符号串长度加1。2）每个项目的含义与圆点位置有关，圆点的左部表示已识别过的部分，右部表示待识别的部分。3）对于A→ε的LR(0)项目只有A→·项目分类：移进项目：形如X•a（在归约过程中将把a移入栈中）待约项目：形如X•A（期待在分析过程中把余留的符号归约而得到A）归约项目：形如X•（已在栈顶，可以归约）接受项目：形如S′S•。1、拓广文法:增加产生式S`S，并令S`•S为初态项目.(保证文法开始符号不出现在任何产生式右部且只在一个产生式中出现)2、S′S•称为句子识别态或接受项目；3、转换关系：项目i为XX1…Xi-1•Xi…Xn,项目j为XX1…Xi•Xi＋1…Xn，则从项目i画一弧线射向j，标记为Xi；4、若项目i为X•A，其中A是非终结符，则从i项目画弧射向所有A•的项目，V*例:G:S→aAcA→AbA→b2、由项目构造识别文法活前缀的NFA1)构造出的NFA是包含有串的NFA，可以使用子集法使之确定化，使之成为一个以项目集为状态的DFA，这个DFA就是建立LR分析算法的基础。2)相应DFA的每个状态是一个项目集，称作LR(0)项目集，整个状态集称为LR(0)项目集规范族。3)在DFA的一个状态对应的项目集内，每个项目是“等价”的，即从期待归约的角度看相同。注：3、LR(0)项目集规范族的自动构造1）拓广文法G′增加S′S产生式。2）定义和构造项目集的闭包设I是拓广文法G′的一个项目集（开始时仅包含S′→·S），如下定义和构造I的闭包CLOSURE(I)：a)I的任何项目都属于CLOSURE(I)；b)若A•B属于CLOSURE(I),B是非终结符，则对任何关于B的产生式B，项目B•也属于CLOSURE(I);c)重复执行步骤b)直到CLOSURE(I)不再扩大为止。说明：CLOSURE(I)即为所求的一个项目子集，将其作为DFA的一个状态。3）定义状态转换函数GO（产生新的项目集）GO(I,X)定义为CLOSURE(J)，其中I,J都是项目集，X(VN∪VT),J={AX•|当A•XI}。4）构造LR(0)项目集规范族的算法{C:={CLOSURE(S′•S)}/*初态项目集*/DO{FOR(对C中每个项目集I和G′中每个文法符号X)IF(GO(I,X)非空且不属于C){把GO(I,X)加入C中}}WHILEC仍然在扩大}注：其中C是集合，用于存放全部的项目集。例设拓广文法G'的产生式为：SEEE+TETTidT(E)求识别此文法的活前缀的DFA。解：这个文法的LR(0)项目有(1)S→·E(2)S→E·(3)E→·E+T(4)E→E·+T(5)E→E+·T(6)E→E+T·(7)E→·T(8)E→T·(9)T→·id(10)T→id·(11)T→·(E)(12)T→(·E)(13)T→(E·)(14)T→(E)·0S→EE→E+TE→TT→idT→(E)1S→EE→E+T3T→id5E→E+TT→idT→(E)6E→E+T2E→T4T→(E)E→E+TE→TT→idT→(E)7T→(E)E→E+T8T→(E)TT(idETid)E+id((+设C={I0,I1,…In},以各项目集Ik(k＝0，…,n)的下标k作为状态序号，并以包含S`•S的项目集作为初始状态，同时将G`文法的产生式进行编号。然后按下列步骤填写ACTION表和GOTO表：1、若A•aIk且GO(Ik,a)=Ij,aVT，则ACTION[k,a]=Sj。2、若A•Ik,则对任何aVT(或＃),则ACTION[k,a]=rj;其中j为产生式A的编号。3、若S`S•Ik,则ACTION[k,＃]=acc。4、若GO(Ik，A)=Ij,AVN，则GOTO[k,A]=j;5、其余为“出错标志”。三、LR(0)分析表的构造算法例如、构造下面的文法的LR(0)分析表，假定对这个文法的各个产生式给予编号并写成：0.S`E4.Ad1.EaA5.BcB2.EbB6.Bd3.AcA0:S`•EE•aAE•bB5:Bc•BB•cBB•d3:Eb•BB•cBB•d2:Ea•AA•cAA•d1:S`E•4:Ac•AA•cAA•d8:AcA•10:Ad•6:EaA•7:EbB•11:Bd•9:BcB•bEaccccddddAABBDFAr6r6r6r6r611r4r4r4r4r410r5r5r5r5r59r3r3r3r3r38r2r2r2r2r27r1r1r1r1r169S11S558S10S447S11S536S10S42acc11S3S20BAE#dcbaGOTOACTION状态一个文法例:GE:S→E[1]E→E+T[2]E→T[3]T→TP[4]T→P[5]P→id[6]P→(E)[7]E→TT→TP6P→id4E→E+TT→TPT→PP→idP→(E)2T→P3S→EE→E+T1S→EE→E+TE→TT→TPT→PP→idP→(E)0T→TPP→idP→(E)7T→T*P8E→E+TT→TP10P→(E)E→E+T11P→(E)9EPTidTE(PP→(E)E→E+TE→TT→TPT→PP→idP→(E)54PT7id(()+idP+id8(LR(0)分析方法的不足LR(0)方法对文法的要求严格。LR(0)方法容易出现冲突状态。四、LR(0)文法如果一个项目集（一个状态）中既有移进项目又含有归约项目，或者一个项目集中含有二个以上的归约项目，则称此项目为冲突项目。如果由一个文法构造的识别可归约前缀的DFA的每个项目集（状态）均不含冲突项目，则称这种文法G为LR（0）文法。SLR是LR(0)的一种改进，它在归约时,对有冲突的项目集用向前查看一个符号的办法进行处理,以解决冲突。7.3SLR分析例：设文法G的LR(0)项目集规范族