LR分析法和LR(k)分析技术

1、o1965年D.Knuth提出了分析效率极高的LR(k)分析技术; : 自左至右扫描的自底向上的分析; o在分析的每一步,只须根据分析栈中的已移进的和已归约出的符 号,并至多向前扫描k个字符就能确定应采取什么分析动作(移进、移进、 归约、接受、报错归约、接受、报错); oLR分析对文法要求很少,效率极高,且能及时发现错误,是目前最 广泛使用的方法;一般用CFG描述的语言均可用LR分析法分析法 LR o计算机理论研究已证明了如下结论: oLR(k)文法是无二义性无二义性文法; oLR(k)文法与LR(1)文法等价等价. o由于常见的程序设计语言均能由LR(1)文法产生,因此我们只讨 论k=0,1

2、两种情况; o本节中,我们将先介绍LR分析器的逻辑结构及工作原理,再分别 介绍几种LR分析器(即LR(0),SLR(1)的构造; oLR(0)简单,能力低; SLR(1)能力强于LR(0); 自底向上分析方法是一种移进-归约过程，当分析的栈 顶符号串形成句柄时就采取归约动作，因而自底向上 分析法的关键问题是在分析过程中如何确定句柄。LR 分析法正是给出一种能根据当前分析栈中的符号串(通 常以状态表示)和向右顺序查看输入串的K个(K0)符号 就可唯一地确定分析器的动作是移进还是归约和用哪 个产生式归约，因而也就能唯一地确定句柄。LR分析 法的归约过程是规范推导的逆过程，所以LR分析过程 是一种规

3、范归约过程。 向前查看0个符号，就是LR(0)分析方法，向前查看1个 符号，就是LR(1)方法。 LR分析法分析法 LR分析表的优缺点 优点： 比其他“移进-归约”分析法，如算符优先分 析法使用更加广泛，识别效率高 n能用LL(1)分析法分析的所有文法都能使用LR 方法来进行分析。 nLR分析法在自左至右扫描输入串的过程中就 能发现其中的任何错误，并能准确地指出出错 位置。 o缺点： n手工构造分析表工作量太大。必须使用自动生 成器。 o自底向上分析法的关键问题是如何确定句柄。LR分 析法与算符优先方法一样，LR方法也是通过求句柄 逐步归约来进行语法分析。 o在算符优先分析中，通过算符的优先关

4、系得到句柄， LR方法中句柄是通过求活前缀而求得。 LR分析方法的基本思想基本思想是：在规范归约过程中， 一方面记住已移进和归约出的整个符号串(历史)， 另一方面又根据所用产生式推测未来可能碰到的 输入符号(对未来的展望)。 当某一符号串类似于句柄出现在栈顶时，需要根 据已记载的“历史”、“展望”和“现实”的输 入符号三方面的内容来决定栈顶的符号串是否构 成了真正的句柄，是否需要归约。 一个LR分析器的组成见下图。 1、LR分析方法的逻辑结构分析方法的逻辑结构 一个一个LR分析器由分析器由3个部分组成：个部分组成： LR分析程序，又称总控程序。所有的分析程序，又称总控程序。所有的LR分析器都是

5、相同的。分析器都是相同的。 分析表分析表(分析函数分析函数)，不同的文法分析表不同，同一个文法采用的，不同的文法分析表不同，同一个文法采用的LR 分析器不同时，分析表也不同，分析表又可分为动作表分析器不同时，分析表也不同，分析表又可分为动作表(ACTION)和和 状态转换状态转换(GOTO)表两个部分，它们都可用二维数组表示。表两个部分，它们都可用二维数组表示。 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 状态栈：(S0,#)为预先 放到栈中的初始状态 和符号。 文法符号：X1X2Xm是 目前已移进并归约出的句 型部分。

6、 分析器分析器实际上是一个带有先进后出栈的确定的 有穷自动机。将“历史”和“展望”综合成 “状态状态”，分析栈用来存放状态，状态概括了 从分析开始直到某一归约阶段的全部历史和展 望资料，不必象算符优先分析法中要翻阅栈中 的内容才能决定是否要进行归约。只需根据栈根据栈 顶状态和输入符号就可以唯一决定下一个动作顶状态和输入符号就可以唯一决定下一个动作。 总控程序根据分析表的内容来决定其下一步的处理总控程序根据分析表的内容来决定其下一步的处理 动作，分析表是根据具体的文法按某种规则构造出动作，分析表是根据具体的文法按某种规则构造出 来的。来的。 LR方法：方法：根据具体文法的分析表对输入串进行分析处

7、根据具体文法的分析表对输入串进行分析处 理。理。 LR分析过程：分析过程：在总控程序的控制下，从左到右扫描输在总控程序的控制下，从左到右扫描输 入符号串，根据分析栈中的状态和当前输入符号，入符号串，根据分析栈中的状态和当前输入符号， 按分析表中的内容完成相应的分析工作。按分析表中的内容完成相应的分析工作。 2. 分析表的组成：分析表的组成： (1) 分析动作表分析动作表Action是一个是一个二维数组 符号符号 状态状态 a1a2at S0actionS0 , a1 actionS0 , a2actionS0 , at S1actionS1 , a1 actionS1 , a2actionS1

8、 , at SnactionSn , a1 actionSn , a2actionSn , at 表中actionSi,aj，指出如果当前栈顶为状态Si，输入 符号为aj时应执行的动作。其动作有四种可能，分别为： 移进(S)、归约(r)、接受(acc)、出错(error)。 符号符号 状态状态 x1x2xt S0 gotoS0 , x1 gotoS0 , x2gotoS0 , xt S1 gotoS1 ,x1 gotoS1 , x2gotoS1 , xt Sn gotoSn , x1 gotoSn , x2gotoSn , xt 表中gotoSi,xj指出栈顶状态为Si，碰到文法符号为Xj时应

9、转 到的下一状态。 显然：分析表定义了一个以文法非终结符为字母表的显然：分析表定义了一个以文法非终结符为字母表的 DFA (2) 状态转换表状态转换表goto 也是一个二维数组也是一个二维数组 用三元式用三元式: (状态栈，符号栈，输入符号状态栈，符号栈，输入符号) 表示分析过程中状态栈，符号栈，输入符号的变化。表示分析过程中状态栈，符号栈，输入符号的变化。 将初始状态将初始状态S0和和#进分析栈。三元式为：进分析栈。三元式为： (S0, # , a1a2an#) 任一时刻的三元式为：任一时刻的三元式为： (S0S1Sm, #X1X2Xm, aiai+1an#) 分析器的下一步动作是由栈顶状态

10、分析器的下一步动作是由栈顶状态Sm和当前面临的和当前面临的 输入符号输入符号ai唯一确定的。唯一确定的。 LR分析过程：分析过程： o根据栈顶状态Sm和输入符号ai查action表, 根据表中的内容不同完成 不同的动作，若actionSm, ai为： 移进：移进：当前输入符号ai进符号栈，下一输入符号变成当前输入 符号，将action表中指出的状态S进状态栈。三元式变为： (S0S1SmS, # X1X2Xmai, ai+1an#) 归约：归约：按某个产生式A进行归约，若产生式的右端长度为 r，则两个栈顶的r个元素同时出栈。将归约后的符号A进符号 栈; 根据新栈顶状态Sm-r和归约符号A查GO

11、TO表， S=gotoSm-r, A进状态栈。三元式变为： (S0S1 Sm-r S, # X1X2Xm-rA, aiai+1an #) 接受：接受：分析成功，终止分析。三元式不再变化。 出错：出错：报告出错信息。三元式的变化过程终止。 为了介绍为了介绍LR分析过分析过 程，直接给出该文法程，直接给出该文法 的分析表，以后再介的分析表，以后再介 绍如何生成绍如何生成 状状 态态 ACTIONGoTo i+*()#ETF 0 0 S5S4123 1 1 S6ac c 2 2 r2S7r2r2 3 3 r4r4r4r4 4 4 S5S4823 5 5 r6r6r6r6 6 6 S5S4r193 7

12、 7 S5S410 8 8 S6S1 9 9 r1S7r1r1 1010 r3r3r3r3 1111 r5r5r5r5 ri表示按第i个产 生式进行归约 Si表示把当前输入 符号移进栈，第i个 状态进状态栈。 i表示转第i个状 态，即第i个状 态进状态栈。 空白表示分 析动作出错 举例说明举例说明LR具体具体 分析过程：分析过程： (1) E E+T (2) E T (3) T T*F (4) T F (5) F (E) (6) F i 产生式产生式 的序号的序号 设文法为设文法为GL： 根据上述分析表，对输入串根据上述分析表，对输入串 i * i + i 的分析过程如下：的分析过程如下： 序

13、号序号状态栈状态栈符号栈符号栈产生式产生式输入串输入串说明说明 10#i*i+i# 0和和#进栈进栈 205#i*i+i# i和和S5进栈进栈 303#FFi*i+i# i和和S5退栈退栈, F和和S3进栈进栈 402#TTF*i+i# F和和S3退栈退栈, T和和S2进栈进栈 5027#T*i+i# *和和S7进栈进栈 60275#T*i+i# i和和S5进栈进栈 702710#T*FFi+i# i和和S5退栈退栈, F和和S10进栈进栈 802#TTT*F+i# F*T和和S10,7,2退栈退栈, T和和S2进栈进栈 901#EET+i# T和和S2退栈退栈, E和和S1进栈进栈 1001

14、6#E+i# +和和S6进栈进栈 110165#E+i# i和和S5进栈进栈 120163#E+FFi# i和和S5退栈退栈, F和和S3进栈进栈 130169#E+TTF#F和和S3退栈退栈, T和和S9进栈进栈 1401#EE E+T#T+E和和S9,6,1退栈退栈, E和和S1进栈进栈 1）基本概念）基本概念 字的前缀：字的前缀：指该字的任意首部。 活前缀：活前缀：识别了句柄的一部分就相当于识别了当前 的规范句型的左起部分，这部分被识别的符号称为 规范规约的活前缀活前缀 在LR分析的过程中，假定输入串是一个句子，任何 时候符号栈里的文法符号都构成某个产生式的活前 缀。 LR分析器通过一个

15、有限自动机来识别文法G的所有 活前缀，这样就可以自动生成LR分析表。 LR(0)项目集族项目集族 LR(0)项目：项目：在文法G中每个产生式的右部右部适当位置 添加一个圆点构成项目。 例如：产生式 SXYZ 对应有4个项目。 0 SXYZ 1 SXYZ 2 SXYZ 3 SXYZ 产生式产生式A 只对应一个项目：只对应一个项目： A 项目项目指明了在分析过程的某时刻，已看到的产生式 部分 项目集：项目集：若干个项目组成的集合称为项目集。 例如： 对于上述产生式的4个项目即构成一个项目集。 后继符号：后继符号：在项目中紧跟在符号“”后面的符号 称为该项目的后继符号项目的后继符号。 后继符号表示下

16、一时刻读 到的符号。 后继符号有多种，据此将项目分为多种：后继符号有多种，据此将项目分为多种： 后继符号为终结符： A a, 称为移进项目；移进项目； （注意：终结符都要移进栈中的）（注意：终结符都要移进栈中的） (2) 后继符号为非终结符：A B, 称为待归约项目；待归约项目； （注意：在（注意：在LR分析法中栈里的非终结符都是规约出来的分析法中栈里的非终结符都是规约出来的 而不是移进去的）而不是移进去的） (3) 后继符号为空：即圆点在最右边A , 称为归约项归约项 目；目； (4) 归约项目的左边是文法的开始符号S, 称为接受接受 项目项目 (5)后继符号集：项目集中各项目的后继符号所组

17、成的集 合称为后继符号集后继符号集。 例如：项目集 E E T ， F i 的后继符号 集为，i 文法： S E E aA | bB A cA | d B 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 d 11. E bB 12. E bB 13. E bB 14. B cB 15. B cB 16. B cB 17. B d 18. B d 该文法的项目有：该文法的项目有： oLR(0)项目集规范族：构成识别一个文法活前缀的DFA 的项目集的全体。 o一个项目集I的闭包CL

18、OSURE(I)的计算：的计算： I中的任何项目中的任何项目i I都有都有i CLOSURE(I) (2) 若若A BCLOSURE(I), 且且B VN则对任何关于则对任何关于B 的产生式：的产生式：B的的B CLOSURE(I)，为任意符号串为任意符号串 (3) 重复重复(2)直到直到CLOSURE(I)不再增加为止。不再增加为止。 5、LR(0)项目集规范族的构造：项目集规范族的构造： 注意注意：(2)的条件表示所有项目集中右边为B的状态与B 的状态是等价的，因此，只要B 进入CLOSURE(I) 中, 则所有B的圆点在左边的项目B 都应进入同一个 CLOSURE(I)中。 o定义状态转

19、换函数GO(I,X)： GO(I,X)=CLOSURE(J)=Ij I是一个项目集，是一个项目集，X是一个文法符号是一个文法符号 其中其中J=AX 的项目的项目|AXI oGO函数实际就是检查I中的每一个后随符号为X 的项目，将这个圆点向后移动一个位置，得到 项目集J，再对项目集J求闭包。 o1. 拓广文法：若原文法G的开始符号为S，则增加一个 非终结符S和一个产生式SS，这样是为了得到唯一唯一 的接受状态的接受状态S S o(原因是当存在这样的产生式原因是当存在这样的产生式s aA|A时如果不引进时如果不引进s 那么就存在两个接受状态那么就存在两个接受状态aA.和和A.) o设项目集规范族C

20、只包含第一个状态S S的闭包， 即C = Closure(S S) o然后利用GO函数对C中的每个项目集和每个符号X计算 其下一状态，并将下一状态GO(I,X)加入到C中，直到 C中状态数不再增加 oC即为文法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 第步：拓广文法，并第步：拓广文法，并 对产生式给予序号：对产

21、生式给予序号： 第步：写出拓广后的第步：写出拓广后的 文法的项目集：文法的项目集： 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 d 13. A d 14. B cB 15. B c B 16. B cB 17. B d18. B d 状态状态项目集项目集后继符号后继符号后继状态后继状态 S0 S E E aA E bB E a b S1 S2 S3 S1 S E #接受态接受态 S2 Ea A A cA A d A c d S6 S4 S10 S

22、3 EbB B cB B d B c d S7 S5 S11 S4 A c A A cA A d A c d S8 S4 S10 S5 Bc B B cB B d B c d S9 S5 S11 S6 EaA #归约归约 S7 EbB #归约归约 A cA #归约归约 第第3步：从步：从S E开开 始始求项目集规范族求项目集规范族 由 S0 = S E知：知： Closure(S0) = S E, E aA, E bB 由此初值Cclosure(S0)再根 据GO函数计算后继状态 由此表明显看出：由此表明显看出： Go(状态，后继符号状态，后继符号)后继状态后继状态 LR(0)文法：若一个文法

23、文法：若一个文法G的拓广文法的拓广文法G的活前缀识的活前缀识 别自动机中的每个状态不存在下述情况：别自动机中的每个状态不存在下述情况： 既含移进又含归约的项目；既含移进又含归约的项目； 含有多个归约项目。含有多个归约项目。 对对LR(0)文法可以直接从它的项目集规范族文法可以直接从它的项目集规范族C和活前和活前 缀识别自动机的状态转换函数构造出缀识别自动机的状态转换函数构造出LR分析表分析表 LR(0)分析表的构造分析表的构造 设有文法设有文法G，则，则LR(0)分析表的构造原则为：分析表的构造原则为： 对于对于A XIk，GOTO(Ik,X)=Ij 若若X Vt，则置，则置actionk,X

24、=Sj ,即把即把(j,a) 移进栈移进栈 若若X Vn，则置，则置gotoIk,X=j 对于对于A Ik，则对所有的，则对所有的x Vt和和#，均置，均置 actionk,x=rj (设设A 是第是第j个产生式个产生式)，即，即 用用A 归约归约 若若SS Ik，则置，则置actionk,#=acc，即接受，即接受 1. 其他均置出错。其他均置出错。 状状 态态 ACTIONGOTO abcd#EAB S0S2S31 S1acc S2S4S106 S3S5S117 S4S4S108 S5S5S119 S6r1r1r1r1r1 S7r2r2r2r2r2 S8r3r3r3r3r3 S9r5r5r

25、5r5r5 S10r4r4r4r4r4 S11r6r6r6r6r6 第第4步：步： 根据状态根据状态 描述构造描述构造 LR(0)分分 析表析表 只有当一个文法只有当一个文法G是是LR(0)文法，即文法，即G的每一个状的每一个状 态不出现冲突时，才能构造出态不出现冲突时，才能构造出LR(0)分析表。分析表。 由于大多数适用的程序设计语言的文法不能满足由于大多数适用的程序设计语言的文法不能满足 LR(0) 文法的条件，因此使用向前查看一个符号文法的条件，因此使用向前查看一个符号 的办法来处理冲突。的办法来处理冲突。 只对有冲突的状态向前查看一个符号，即查看只对有冲突的状态向前查看一个符号，即查看 follow集，以确定做哪个动作，这种分析方法为简集，以确定做哪个动作，这种分析方法为简 单的单的LR分析法，用分析法，用SLR表示。表示。 如果每个项目都附上如果每个项目都附上k个终结符号，表示要对它进个终结符号，表示要对它进 行归约时，后续的行归约时，后续的k个输入符号与这个输入符号与这