《LR分析法和LR(k)分析技术.ppt》由会员分享，可在线阅读，更多相关《LR分析法和LR(k)分析技术.ppt（34页珍藏版）》请在三一文库上搜索。
1、4.2.4 LR分析法,1965年D.Knuth提出了分析效率极高的LR(k)分析技术;LR分析: 自左至右扫描的自底向上的分析;在分析的每一步,只须根据分析栈中的已移进的和已归约出的符号,并至多向前扫描k个字符就能确定应采取什么分析动作(移进、归约、接受、报错);LR分析对文法要求很少,效率极高,且能及时发现错误,是目前最广泛使用的方法;一般用CFG描述的语言均可用LR分析法,LR分析综述,计算机理论研究已证明了如下结论:LR(k)文法是无二义性文法;LR(k)文法与LR(1)文法等价.由于常见的程序设计语言均能由LR(1)文法产生,因此我们只讨论k=0,1两种情况;本节中,我们将先介绍LR
2、分析器的逻辑结构及工作原理,再分别介绍几种LR分析器(即LR(0),SLR(1)的构造;LR(0)简单,能力低; SLR(1)能力强于LR(0);,自底向上分析方法是一种移进-归约过程，当分析的栈顶符号串形成句柄时就采取归约动作，因而自底向上分析法的关键问题是在分析过程中如何确定句柄。LR分析法正是给出一种能根据当前分析栈中的符号串(通常以状态表示)和向右顺序查看输入串的K个(K0)符号就可唯一地确定分析器的动作是移进还是归约和用哪个产生式归约，因而也就能唯一地确定句柄。LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程。向前查看0个符号，就是LR(0)分析方法，向前查
3、看1个符号，就是LR(1)方法。,LR分析法,LR分析表的优缺点,优点：比其他“移进-归约”分析法，如算符优先分析法使用更加广泛，识别效率高能用LL(1)分析法分析的所有文法都能使用LR方法来进行分析。LR分析法在自左至右扫描输入串的过程中就能发现其中的任何错误，并能准确地指出出错位置。缺点：手工构造分析表工作量太大。必须使用自动生成器。,自底向上分析法的关键问题是如何确定句柄。LR分析法与算符优先方法一样，LR方法也是通过求句柄逐步归约来进行语法分析。在算符优先分析中，通过算符的优先关系得到句柄，LR方法中句柄是通过求活前缀而求得。,LR分析方法的基本思想是：在规范归约过程中，一方面记住已移
4、进和归约出的整个符号串(历史)，另一方面又根据所用产生式推测未来可能碰到的输入符号(对未来的展望)。当某一符号串类似于句柄出现在栈顶时，需要根据已记载的“历史”、“展望”和“现实”的输入符号三方面的内容来决定栈顶的符号串是否构成了真正的句柄，是否需要归约。一个LR分析器的组成见下图。,1、LR分析方法的逻辑结构,一个LR分析器由3个部分组成：LR分析程序，又称总控程序。所有的LR分析器都是相同的。分析表(分析函数)，不同的文法分析表不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表(ACTION)和状态转换(GOTO)表两个部分，它们都可用二维数组表示。分析栈，包括文法
5、符号栈和相应的状态栈，它们均是先进后出栈。,状态栈：(S0,#)为预先放到栈中的初始状态和符号。,文法符号：X1X2Xm是目前已移进并归约出的句型部分。,分析器实际上是一个带有先进后出栈的确定的有穷自动机。将“历史”和“展望”综合成“状态”，分析栈用来存放状态，状态概括了从分析开始直到某一归约阶段的全部历史和展望资料，不必象算符优先分析法中要翻阅栈中的内容才能决定是否要进行归约。只需根据栈顶状态和输入符号就可以唯一决定下一个动作。,总控程序根据分析表的内容来决定其下一步的处理动作，分析表是根据具体的文法按某种规则构造出来的。LR方法：根据具体文法的分析表对输入串进行分析处理。LR分析过程：在总
6、控程序的控制下，从左到右扫描输入符号串，根据分析栈中的状态和当前输入符号，按分析表中的内容完成相应的分析工作。,2. 分析表的组成：(1) 分析动作表Action是一个二维数组,表中actionSi,aj，指出如果当前栈顶为状态Si，输入符号为aj时应执行的动作。其动作有四种可能，分别为：移进(S)、归约(r)、接受(acc)、出错(error)。,表中gotoSi,xj指出栈顶状态为Si，碰到文法符号为Xj时应转到的下一状态。显然：分析表定义了一个以文法非终结符为字母表的DFA,(2) 状态转换表goto 也是一个二维数组,用三元式: (状态栈，符号栈，输入符号) 表示分析过程中状态栈，符号
7、栈，输入符号的变化。将初始状态S0和#进分析栈。三元式为：(S0, # , a1a2an#)任一时刻的三元式为：(S0S1Sm, #X1X2Xm, aiai+1an#)分析器的下一步动作是由栈顶状态Sm和当前面临的输入符号ai唯一确定的。,LR分析过程：,根据栈顶状态Sm和输入符号ai查action表, 根据表中的内容不同完成不同的动作，若actionSm, ai为：移进：当前输入符号ai进符号栈，下一输入符号变成当前输入符号，将action表中指出的状态S进状态栈。三元式变为： (S0S1SmS, # X1X2Xmai, ai+1an#)归约：按某个产生式A进行归约，若产生式的右端长度为r，
8、则两个栈顶的r个元素同时出栈。将归约后的符号A进符号栈; 根据新栈顶状态Sm-r和归约符号A查GOTO表，S=gotoSm-r, A进状态栈。三元式变为： (S0S1 Sm-r S, # X1X2Xm-rA, aiai+1an #) 接受：分析成功，终止分析。三元式不再变化。 出错：报告出错信息。三元式的变化过程终止。,为了介绍LR分析过程，直接给出该文法的分析表，以后再介绍如何生成,ri表示按第i个产生式进行归约,Si表示把当前输入符号移进栈，第i个状态进状态栈。,i表示转第i个状态，即第i个状态进状态栈。,空白表示分析动作出错,举例说明LR具体分析过程：,(1) E E+T (2) E T
9、 (3) T T*F (4) T F (5) F (E) (6) F i,产生式的序号,设文法为GL：,根据上述分析表，对输入串 i * i + i 的分析过程如下：,1）基本概念字的前缀：指该字的任意首部。活前缀：识别了句柄的一部分就相当于识别了当前的规范句型的左起部分，这部分被识别的符号称为规范规约的活前缀在LR分析的过程中，假定输入串是一个句子，任何时候符号栈里的文法符号都构成某个产生式的活前缀。LR分析器通过一个有限自动机来识别文法G的所有活前缀，这样就可以自动生成LR分析表。,LR(0)项目集族,LR(0)项目：在文法G中每个产生式的右部适当位置添加一个圆点构成项目。例如：产生式 S
10、XYZ 对应有4个项目。 0 SXYZ 1 SXYZ2 SXYZ 3 SXYZ 产生式A 只对应一个项目： A 项目指明了在分析过程的某时刻，已看到的产生式部分 项目集：若干个项目组成的集合称为项目集。 例如：对于上述产生式的4个项目即构成一个项目集。后继符号：在项目中紧跟在符号“”后面的符号称为该项目的后继符号。 后继符号表示下一时刻读到的符号。,后继符号有多种，据此将项目分为多种：后继符号为终结符： A a, 称为移进项目；（注意：终结符都要移进栈中的）(2) 后继符号为非终结符：A B, 称为待归约项目；（注意：在LR分析法中栈里的非终结符都是规约出来的而不是移进去的）(3) 后继符号为
11、空：即圆点在最右边A , 称为归约项目；(4) 归约项目的左边是文法的开始符号S, 称为接受项目(5)后继符号集：项目集中各项目的后继符号所组成的集合称为后继符号集。 例如：项目集 E E T ， F i 的后继符号集为，i,文法：S EE aA | bBA cA | dB cB | d,1. S E 2. S E 3. E aA 4. E aA 5. E aA 6. A cA 7. A c A 8. A cA 9. A d 10. A d11. E bB 12. E bB 13. E bB 14. B cB 15. B cB 16. B cB 17. B d 18. B d,该文法的项目有：
12、,LR(0)项目集规范族：构成识别一个文法活前缀的DFA的项目集的全体。一个项目集I的闭包CLOSURE(I)的计算：I中的任何项目iI都有iCLOSURE(I)(2) 若A BCLOSURE(I), 且B VN则对任何关于B的产生式：B的BCLOSURE(I)，为任意符号串(3) 重复(2)直到CLOSURE(I)不再增加为止。,5、LR(0)项目集规范族的构造：,注意：(2)的条件表示所有项目集中右边为B的状态与B 的状态是等价的，因此，只要B 进入CLOSURE(I)中, 则所有B的圆点在左边的项目B 都应进入同一个CLOSURE(I)中。,定义状态转换函数GO(I,X)：GO(I,X)
13、=CLOSURE(J)=Ij I是一个项目集，X是一个文法符号其中J=AX的项目|AXIGO函数实际就是检查I中的每一个后随符号为X的项目，将这个圆点向后移动一个位置，得到项目集J，再对项目集J求闭包。,1. 拓广文法：若原文法G的开始符号为S，则增加一个非终结符S和一个产生式SS，这样是为了得到唯一的接受状态S S (原因是当存在这样的产生式s aA|A时如果不引进s那么就存在两个接受状态aA.和A.)设项目集规范族C只包含第一个状态S S的闭包，即C = Closure(S S)然后利用GO函数对C中的每个项目集和每个符号X计算其下一状态，并将下一状态GO(I,X)加入到C中，直到C中状态
14、数不再增加C即为文法G的LR(0) 项目集规范族,LR(0)项目集规范族的构造算法：,例：设文法G为：E aA bB A cAd B cBd求该文法的LR(0)分析表。,(0) S E (1) E aA (2) E bB (3) A cA (4) A d (5) B cB (6) B d,第步：拓广文法，并对产生式给予序号：,第步：写出拓广后的文法的项目集：,1. S E 2. S E 3. E aA 4. E a A 5. E aA 6. E bB 7. E b B 8. E bB 9. A cA 10. A c A 11. A cA 12. A d13. A d 14. B cB 15.
15、B c B 16. B cB 17. B d18. B d ,第3步：从S E开始求项目集规范族,由 S0 = S E知：Closure(S0) = S E,E aA, E bB ,由此初值Cclosure(S0)再根据GO函数计算后继状态,由此表明显看出：Go(状态，后继符号)后继状态,LR(0)文法：若一个文法G的拓广文法G的活前缀识别自动机中的每个状态不存在下述情况： 既含移进又含归约的项目； 含有多个归约项目。对LR(0)文法可以直接从它的项目集规范族C和活前缀识别自动机的状态转换函数构造出LR分析表,LR(0)分析表的构造,设有文法G，则LR(0)分析表的构造原则为：对于A XIk，
16、GOTO(Ik,X)=Ij 若XVt，则置actionk,X=Sj ,即把(j,a)移进栈 若XVn，则置gotoIk,X=j对于AIk，则对所有的xVt和#，均置actionk,x=rj (设A 是第j个产生式)，即用A 归约若SSIk，则置actionk,#=acc，即接受其他均置出错。,第4步：根据状态描述构造LR(0)分析表,只有当一个文法G是LR(0)文法，即G的每一个状态不出现冲突时，才能构造出LR(0)分析表。由于大多数适用的程序设计语言的文法不能满足LR(0) 文法的条件，因此使用向前查看一个符号的办法来处理冲突。只对有冲突的状态向前查看一个符号，即查看follow集，以确定做
17、哪个动作，这种分析方法为简单的LR分析法，用SLR表示。如果每个项目都附上k个终结符号，表示要对它进行归约时，后续的k个输入符号与这k个符号相同时，才能对栈顶进行归约。这就是LR(k)分析。,SLR分析表的构造,若一个项目集中既含有移进项目，又含有归约项目，出现了冲突。解决冲突的办法是：分析所有含A、B的句型，根据后继符号即FOLLOW(A)和FOLLOW(B)来判断。当在状态I时面临某输入符号为a时：当a = b，则b应移进；当a follow(A)，则用产生式A 进行归约；当a follow(B)，则用产生式B 进行归约.,I=XbA A B ,SLR(1)解决办法,移进-归约冲突,Fol
18、low(E)=#,),+所以如果当前输入符号为#, ), +时，就使用E T进行归约；如果当前输入符号为*时，就移进；当面临其他输入符号时，出错。,SLR(1)分析表的构造,设有文法G，则SLR(1)分析表的构造方法为： 对于A XIk，GOTO(Ik,X)=Ij 若X Vt，则置actionk,X=Sj ,即把(j,a)移进栈 若X Vn，则置gotoIk,X=j 对于A Ik ，则对所有的x，xfollow(A) ，则置actionk,x=rj (设A 是第j个产生式)，即用A 归约 若S S Ik，则置actionk,#=acc，即接受 其他均置出错。,按照该方法构造的分析表，如果每个入口不含多重定义，则称为SLR表，文法G称为SLR(1)文法。,I0:SSSASBAaAbAcBaBbBd,I1: SS,S,I2: SA,A,I3: SB,B,I4:AaAbAaAbAcBaBbBaBbBd,a,I5: Ac,c,c,I6: Ad,d,d,a,I7: AaAb,I9: BaBb,I8: AaAb,I10: BaBb,B,A,b,b,图4-16 识别GS全部活前缀的DFA,