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

1、第第7 7章分析法章分析法 l教学要求：教学要求：要求理解可归约串、有效项目的基本要求理解可归约串、有效项目的基本 概念；掌握分析方法。概念；掌握分析方法。 l教学重点：教学重点：LRLR族文法、分析表的构造。族文法、分析表的构造。 语法分析方法语法分析方法: : 1 1、预测分析法（仅限于、预测分析法（仅限于LLLL（1 1）文法）文法） 2 2、算符优先分析法（仅限于算符优先文法）、算符优先分析法（仅限于算符优先文法） 3 3、LRLR分析法（适用范围广；分析速度快；报错分析法（适用范围广；分析速度快；报错 准确）准确） 7.1 7.1 分析概述分析概述 一、一、LRLR分析法含义分析法含

2、义 L L：从左到右扫描输入串：从左到右扫描输入串 R R：最右推导的逆过程：最右推导的逆过程( (即最左归约）即最左归约） LR(K)LR(K)分析法分析法: :根据当前分析栈中的符根据当前分析栈中的符 号串和向右顺序查看输入串的号串和向右顺序查看输入串的K K个（个（ K0K0） 符号唯一地确定分析器的动作是移进还是符号唯一地确定分析器的动作是移进还是 归约和用哪个产生式归约。归约和用哪个产生式归约。 （2 2）动作（动作（ACTIONACTION）表：）表： ACTIONi,aACTIONi,a规定当前状态规定当前状态 i i遇到输入符号遇到输入符号a a应执行的动作。应执行的动作。 a

3、)a)移进移进S Sj j：符号：符号a a、状态、状态j j分别进入符号栈和状态栈。分别进入符号栈和状态栈。 b)b)归约归约r rj j：栈顶形成句柄为栈顶形成句柄为时时, ,有产生式有产生式A(A(第第j j个产生个产生 式）式）,|=n,|=n,两个栈均出栈两个栈均出栈n n项项, ,状态栈顶为状态栈顶为i i;然后符号然后符号A A和状态和状态 k=GOTOik=GOTOi,A,A分别进栈。分别进栈。 c)c)acc:acc:接受接受 d)d)报错报错 a a1 1aai iaan n# # LRLR主控主控 程序程序 动作表动作表 actionaction 转移表转移表 gotog

4、oto 产生式产生式 序列序列 状态状态/ /符号符号 输入缓冲区输入缓冲区 分析表分析表 S Sm m S Sm-1 m-1 S S1 1 0 0 X Xm m X Xm-1 m-1 X X1 1 # # （1 1）状态转换（状态转换（GOTOGOTO）表：）表： GOTOi ,X=jGOTOi ,X=j规定当前状态规定当前状态i i遇遇 到文法符号为到文法符号为X X时转换到状态时转换到状态j j 。 输入串（单词系列）输入串（单词系列）LR分析程序分析程序 action表和表和goto表表 输出信息输出信息 文法文法 本章学习思路本章学习思路 分析程序算法分析程序算法 构造构造 置置ip

5、ip指向输入串指向输入串w w的第一个符号；的第一个符号；0 0和和# #分别进栈；分别进栈； 令令S S为栈顶状态；为栈顶状态；a a是是ipip指向的符号；指向的符号； BeginBegin if ACTIONS,a=S if ACTIONS,a=Sj j then then begin j begin j、 、a a分别进栈； 分别进栈；ipip指向下一输入符号；指向下一输入符号； endend a a1 1aai iaan n# # LRLR主控主控 程序程序 动作表动作表 actionaction 转移表转移表 gotogoto 产生式产生式 序列序列 状态状态/ /符号符号 输入缓

6、冲区输入缓冲区 分析表分析表 S Sm m S Sm-1 m-1 S S1 1 0 0 X Xm m X Xm-1 m-1 X X1 1 # # else if ACTIONS,a=relse if ACTIONS,a=rj j ( (第 第j j条产生式为条产生式为A A) ) then begin then begin 出栈出栈| | | |项；项； 令当前栈顶状态为令当前栈顶状态为SS，A A和和GOTOS,AGOTOS,A分别进栈；分别进栈； endend else if ACTIONS,aelse if ACTIONS,a=acc then return (=acc then ret

7、urn (成功）成功） else errorelse error end.end. a a1 1aai iaan n# # LRLR主控主控 程序程序 动作表动作表 actionaction 转移表转移表 gotogoto 产生式产生式 序列序列 状态状态/ /符号符号 输入缓冲区输入缓冲区 分析表分析表 S Sm m S Sm-1 m-1 S S1 1 0 0 X Xm m X Xm-1 m-1 X X1 1 # # GS: Sif S else S (1) Sif S (2) SS;S (3) Sa (4) 输入串输入串if a else a;a#的分析过程的分析过程 状态状态 符号符号

8、输入串输入串 01 #S # 03578 #if S else S # 0357846 #if S else S;S # 0357842 #if S else S;a # 035784 #if S else S; a# 03578 #if S else S ;a# 03572 #if S else a ;a# 0357 #if S else a;a# 035 #if S else a;a# 032 #if a else a;a# 03 #if a else a;a# 0 # if a else a;a# 1 1、符号栈中的内容加上余留的输入串的内、符号栈中的内容加上余留的输入串的内 容构成规范

9、句型。容构成规范句型。 2 2、是规范的规约、是规范的规约( (是规范推导的逆过程是规范推导的逆过程) )。 3 3、分析决策依据、分析决策依据: :栈顶状态和现行输入符栈顶状态和现行输入符 号号 l四种技术四种技术 lLR(0) SLR(1) LR(1) LALR(1)LR(0) SLR(1) LR(1) LALR(1) 为了介绍为了介绍LR分析过程，在这里直接给出该文分析过程，在这里直接给出该文 法的分析表，之后再介绍如何生成该表。法的分析表，之后再介绍如何生成该表。 ri表示按第表示按第i个产生个产生 式进行归约式进行归约 Si表示把当前输入符表示把当前输入符 号移进栈，且转第号移进栈，

10、且转第i 个状态，即第个状态，即第i个状个状 态进状态栈。态进状态栈。 i表示转第表示转第i个状态，个状态， 即第即第i个状态进状个状态进状 态栈态栈。 空白表示分析空白表示分析 动作出错。动作出错。 l自底向上分析法的关键问题是在分析自底向上分析法的关键问题是在分析 过程中如何确定过程中如何确定句柄句柄。LRLR方法中的句方法中的句 柄是通过求柄是通过求可归前缀可归前缀而求得。而求得。 1 1、符号串、符号串S S的前缀：移走符号串的尾部的零个或多的前缀：移走符号串的尾部的零个或多 个符号所得到的一个符号串。个符号所得到的一个符号串。 例：例：banban是是bananabanana的一个前

11、缀。的一个前缀。 2 2、符号串、符号串S S的后缀：删去符号串的头部的零个或多的后缀：删去符号串的头部的零个或多 个符号所得到的一个符号串。个符号所得到的一个符号串。 例：例：nananana是是bananabanana的一个后缀。的一个后缀。 3 3、可归前缀：如果一个句型含有这样一个前缀，这、可归前缀：如果一个句型含有这样一个前缀，这 个前缀的后缀是该句型的句柄，则这个前缀称为个前缀的后缀是该句型的句柄，则这个前缀称为 该句型的该句型的可归前缀可归前缀。 例：例：S SaAcBe 1aAcBe 1 A Ab 2b 2 A AAb 3Ab 3 B Bd 4d 4 输入串：输入串：abbcd

12、eabbcde。 规范推导过程为：规范推导过程为： 逆过程逆过程: :( (分析栈，输入流分析栈，输入流) ) (- (-，abbcde)abbcde) (a(a，bbcde)bbcde) (ab(ab，bcdebcde) ) (aA(aA，bcde) bcde) ( (用用22归约归约) ) (aAb(aAb，cdecde) ) (aA(aA，cde) cde) ( (用用33归约归约) ) (aAc(aAc，de)de) (aAcd(aAcd，e)e) (aAcB(aAcB，e) e) ( (用用44归约归约) ) (aAcBe(aAcBe，-)-) (S(S，-) -) ( (用用11归

13、约归约) ) S SaAcBeaAcBe1 1 aAcdaAcd4 4e e11 aAbaAb3 3cd cd4 4e e11 abab2 2b b33cd cd4 4e e11 问题问题: :在归约过程中在归约过程中, ,那些是可归前缀那些是可归前缀? ? 4 4、活前缀：、活前缀：G=(Vn,Vt,P,S), G=(Vn,Vt,P,S), 若有若有 S SAA, A A(是句柄是句柄,是可归前缀是可归前缀),), 是是的前缀的前缀, ,则称则称是文法是文法G G的活前缀的活前缀. . 即，形成可归约前缀之前，包括可归约前缀即，形成可归约前缀之前，包括可归约前缀 在内的所有规范句型的前缀称为

14、在内的所有规范句型的前缀称为活前缀活前缀。 （可归前缀的前缀称为活前缀）（可归前缀的前缀称为活前缀） 其中其中SS是对原文法扩充是对原文法扩充(S(SS)S)增加的非终结符增加的非终结符. . l在在LRLR分析过程中，实际上是把分析过程中，实际上是把的前缀的前缀 （即文法（即文法G G的活前缀）列出放在符号栈中，的活前缀）列出放在符号栈中， 一旦在栈中出现一旦在栈中出现（形成可归前缀），（形成可归前缀）， 即句柄已经形成，则用产生式即句柄已经形成，则用产生式A A进行归进行归 约。约。 l对任何一个上下文无关文法，只要能构造对任何一个上下文无关文法，只要能构造 出它的识别可归前缀的有限自动机

15、，就可出它的识别可归前缀的有限自动机，就可 以构造其相应的分析表（状态转换表和动以构造其相应的分析表（状态转换表和动 作表）。作表）。 LRLR分析方法的核心问题是首先从给定的文法构造一分析方法的核心问题是首先从给定的文法构造一 个识别该文法所有活前缀的确定的有限自动机个识别该文法所有活前缀的确定的有限自动机(DFA)(DFA)， 然后根据然后根据DFADFA去构造它的分析表。去构造它的分析表。 1 1、LRLR（0 0）项目）项目 项目：文法项目：文法G G的每个产生式的每个产生式( (规则规则) )的右部添加一的右部添加一 个圆点就构成一个项目。个圆点就构成一个项目。 A xyz A xy

16、z Axyz Axyz Axyz LR(0)LR(0)项目说明项目说明 1 1）一个产生式可对应的项目数为它的右部符号串长度加）一个产生式可对应的项目数为它的右部符号串长度加 1 1。 2 2）每个项目的含义与圆点位置有关，圆点的左部表示已）每个项目的含义与圆点位置有关，圆点的左部表示已 识别过的部分，右部表示待识别的部分。识别过的部分，右部表示待识别的部分。 3 3）对于）对于AA的的LR(0)LR(0)项目只有项目只有AA 项目分类：项目分类： 移进项目：移进项目：形如形如X Xa a （在归约过程中将把（在归约过程中将把a a移入栈移入栈 中）中） 待约项目：待约项目：形如形如X XA

17、A （期待在分析过程中把余留（期待在分析过程中把余留 的符号归约而得到的符号归约而得到A A） 归约项目：归约项目：形如形如X X（ 已在栈顶，可以归约）已在栈顶，可以归约） 接受项目：接受项目：形如形如SSS S。 1 1、拓广文法、拓广文法: :增加产生式增加产生式SSS S，并令，并令SSS S为初态项目为初态项目. . ( (保证文法开始符号不出现在任何产生式右部且只在一保证文法开始符号不出现在任何产生式右部且只在一 个产生式中出现个产生式中出现) ) 2 2、SSS S 称为句子识别态或接受项目；称为句子识别态或接受项目； 3 3、转换关系：项目、转换关系：项目i i为为X XX X

18、1 1XXi-1 i-1X Xi iX Xn n, , 项目项目j j为为X XX X1 1X Xi i X Xi i 1 1X Xn n， 则从项目则从项目i i画一弧线射向画一弧线射向j j，标记为，标记为X Xi i； 4 4、若项目、若项目i i为为X XA A ，其中，其中A A是非终结符，则从是非终结符，则从i i项目画项目画 弧射向所有弧射向所有A A 的项目，的项目，V V* * 例例:G:SaAc AAb Ab:G:SaAc AAb Ab 2 2、由项目构造识别文法活前缀的、由项目构造识别文法活前缀的NFANFA 1) 1)构造出的构造出的NFANFA是包含有是包含有 串的串

19、的NFANFA，可以使用子集法，可以使用子集法 使之确定化，使之成为一个以项目集为状态的使之确定化，使之成为一个以项目集为状态的DFADFA， 这个这个DFADFA就是建立就是建立LRLR分析算法的基础。分析算法的基础。 2)2)相应相应DFADFA的每个状态是一个项目集，称作的每个状态是一个项目集，称作LR(0)LR(0)项目项目 集，整个状态集称为集，整个状态集称为LR(0)LR(0)项目集规范族。项目集规范族。 3)3)在在DFADFA的一个状态对应的项目集内，每个项目是的一个状态对应的项目集内，每个项目是 “等价等价”的，即从的，即从期待归约期待归约的角度看相同。的角度看相同。 注：注

20、： 3 3、 LR(0)LR(0)项目集规范族的自动构造项目集规范族的自动构造 1 1）拓广文法）拓广文法G G 增加增加SSS S 产生式。产生式。 2 2）定义和构造项目集的闭包）定义和构造项目集的闭包 设设I I是拓广文法是拓广文法G G的一个项目集（开始时仅包含的一个项目集（开始时仅包含 S SSS），如下定义和构造），如下定义和构造I I的闭包的闭包CLOSURE(I)CLOSURE(I)： a)Ia)I的任何项目都属于的任何项目都属于CLOSURE(I)CLOSURE(I)； b)b)若若A AB B 属于属于CLOSURE(I),BCLOSURE(I),B是非终结符，则对任何是非

21、终结符，则对任何 关于关于B B的产生式的产生式B B，项目，项目B B 也属于也属于CLOSURE(I);CLOSURE(I); c)c)重复执行步骤重复执行步骤b)b)直到直到CLOSURE(I)CLOSURE(I)不再扩大为止。不再扩大为止。 说明：说明： CLOSURE(I)CLOSURE(I)即为所求的一个项目子集，将即为所求的一个项目子集，将 其作为其作为DFADFA的一个状态。的一个状态。 3 3）定义状态转换函数）定义状态转换函数GOGO（产生新的项目集产生新的项目集） GO(I,X)GO(I,X)定义为定义为CLOSURE(J)CLOSURE(J)，其中，其中I,JI,J都是

22、项目都是项目 集，集，X X ( (V VN NV VT T),J=),J=A AX X | |当当A AX XII。 4 4）构造）构造LR(0)LR(0)项目集规范族的算法项目集规范族的算法 C:=CLOSURE(SC:=CLOSURE(SS S)/)/* *初态项目集初态项目集* */ / DO DO FOR ( FOR (对对C C中每个项目集中每个项目集I I和和G G中每个文法符号中每个文法符号X)X) IF (GO(I,X) IF (GO(I,X)非空且不属于非空且不属于C)C) 把把GO(I,X)GO(I,X)加入加入C C中中 WHILE C WHILE C仍然在扩大仍然在扩

23、大 注：其中注：其中C C是集合，用于存放全部的项目集。是集合，用于存放全部的项目集。 例例 设拓广文法设拓广文法GG的产生式为的产生式为 ： SE EE + T ET Tid T( E ) 求识别此文法的活前缀的求识别此文法的活前缀的DFADFA。 解：这个文法的解：这个文法的LR(0)LR(0)项目有项目有 (1)SE (1)SE (2)SE (2)SE (3)EE+T (4)EE+T(3)EE+T (4)EE+T (5)EE+T (5)EE+T (6)EE+T(6)EE+T (7)ET (8)ET(7)ET (8)ET (9)Tid (9)Tid (10)Tid(10)Tid (11)T

24、(E) (11)T(E) (12)T(E)(12)T(E) (13)T(E) (14)T(E)(13)T(E) (14)T(E) 0 S E E E+T E T T id T ( E ) 1 SE EE +T 3 Tid 5 EE+ T T id T (E) 6 EE+T 2 ET 4 T( E) E E+T E T T id T ( E ) 7 T(E ) EE +T 8 T(E) TT ( id E T id ) E + id ( ( + 设设C=IC=I0 0,I,I1 1,I,In n,以各项目集以各项目集I Ik k(k(k0 0，,n),n)的下标的下标 k k作为状态序号，并以包

25、含作为状态序号，并以包含SSS S的项目集作为初始状态，的项目集作为初始状态， 同时将同时将GG文法的产生式进行编号。然后按下列步骤填写文法的产生式进行编号。然后按下列步骤填写 ACTIONACTION表和表和GOTOGOTO表：表： 1 1、若、若A Aa aI Ik k且且GO(IGO(Ik k,a)=I,a)=Ij j,a,a V VT T，则，则 ACTIONk,a=SACTIONk,a=Sj j。 2 2、若、若A A I Ik k, ,则对任何则对任何a a V VT T( (或或),),则则 ACTIONk,a=rACTIONk,a=rj j; ; 其中其中j j为产生式为产生式

26、A A的编号。的编号。 3 3、若、若SSS S I Ik k, , 则则ACTIONk,ACTIONk,=acc=acc。 4 4、若、若GO(GO(I Ik k，A)=A)=I Ij j,A,A V VN N ，则，则GOTOk,A=j;GOTOk,A=j; 5 5、其余为、其余为“出错标志出错标志”。 例如、构造下面的文法的例如、构造下面的文法的LR(0)LR(0)分析表，假定对分析表，假定对 这个文法的各个产生式给予编号并写成：这个文法的各个产生式给予编号并写成： 0. S E 4.A d 1.E aA 5.B cB 2.E bB 6.B d 3.A cA 0: SE E aA E b

27、B 5: BcB B cB B d 3: EbB B cB B d 2:EaA A cA A d 1: S E 4:AcA A cA A d 8:Ac A 10:A d 6:EaA 7:EbB 11:B d 9:BcB b E a c c c c d d d d A A B B DFA r6r6 r6 r6 r611 r4r4 r4 r4 r410 r5 r5r5 r5 r59 r3r3r3 r3 r38 r2 r2r2r2 r27 r1r1r1r1 r16 9 S11S55 8 S10S44 7S11S5 3 6 S10S42 acc1 1S3S20 BAE# d c b a GOTOACT

28、ION状 态 E T T T P 6 P id 4 E E + T T T P T P P id P (E) 2 T P 3 S E E E + T 1 S E E E+T E T T T P T P P id P (E) 0 T T P P id P (E) 7 T T * P 8 E E+T T T P 10 P (E ) E E +T 11 P(E) 9 E P T id T E ( P P ( E ) E E+T E T T T P T P P id P (E) 5 4 P T 7 id ( ( ) + id P + id 8 ( LR(0)LR(0)分析方法的不足分析方法的不足 如果

29、一个项目集（一个状态）中既有移进项目如果一个项目集（一个状态）中既有移进项目 又含有归约项目，或者一个项目集中含有二个以上又含有归约项目，或者一个项目集中含有二个以上 的归约项目，则称此项目为的归约项目，则称此项目为冲突项目冲突项目。如果由一个。如果由一个 文法构造的识别可归约前缀的文法构造的识别可归约前缀的DFADFA的每个项目集（状的每个项目集（状 态）均不含冲突项目，则称这种文法态）均不含冲突项目，则称这种文法G G为为LRLR（0 0）文）文 法法。 SLR SLR是是LR(0)LR(0)的一种改进，它在归约时的一种改进，它在归约时, , 对有冲突对有冲突 的项目集用向前查看一个符号的

30、办法进行处理的项目集用向前查看一个符号的办法进行处理, ,以解以解 决冲突。决冲突。 例：设文法例：设文法G G的的LR(0)LR(0)项目集规范族中含有如下一个项目集规范族中含有如下一个 项目集（状态）项目集（状态）I I： I=XI=Xb b / /* *移进项目移进项目* */ / A A / /* *归约项目归约项目* */ / B B / /* *归约项目归约项目* */ / 这三个项目告诉我们应做的动作各不相同，出现这三个项目告诉我们应做的动作各不相同，出现 了了移进归约冲突移进归约冲突和和归约归约- -归约归约冲突。这个文法冲突。这个文法 一定不是一定不是LR(0)LR(0)文法

31、。文法。 解决冲突的一种方法解决冲突的一种方法:FOLOW(A), FOLLOW(B):FOLOW(A), FOLLOW(B) 和和bb互不相交时冲突便可解决互不相交时冲突便可解决. . 即即, ,在在I I状态下面输入符状态下面输入符a a时时, ,动作为动作为: : a=ba=b时时, ,则移进则移进. . 若若a a属于属于FOLLOW(A), FOLLOW(A), 则用产生式则用产生式A A 归约归约. . 若若a a属于属于FOLLOW(B), FOLLOW(B), 则用产生式则用产生式B B 归约归约. . 1)1) 此外此外, ,出错出错. . I=XI=Xb b / /* *移

32、进项目移进项目* */ / A A / /* *归约项目归约项目* */ / B B / /* *归约项目归约项目* */ / 构造构造SLRSLR分析表的算法分析表的算法 设设C=IC=I0 0,I,I1 1,I,In n,以各项目集以各项目集I Ik k(k(k0 0，,n),n)的下标的下标k k 作为状态序号，并以包含作为状态序号，并以包含SSS S的项目集作为初始状态，的项目集作为初始状态， 同时将同时将GG文法的产生式进行编号。然后按下列步骤填文法的产生式进行编号。然后按下列步骤填 写写ACTIONACTION表和表和GOTOGOTO表：表： 1 1、若、若A Aa aI Ik k

33、且且GO(IGO(Ik k,a)=I,a)=Ij j,a,a V VT T，则，则 ACTIONk,a=SACTIONk,a=Sj j。 2 2、若、若A A I Ik k, ,则对任何则对任何a a FOLLOW(A)FOLLOW(A), ,则则 ACTIONk,a=rACTIONk,a=rj j; ; 其中其中j j为产生式为产生式A A 的编号。的编号。 3 3、若、若S SS S I Ik k, , 则则ACTIONk,ACTIONk,=acc=acc。 4 4、若、若GO(GO(I Ik k，A)=A)=I Ij j,A,A V VN N ，则，则GOTOk,A=j;GOTOk,A=

34、j; 5 5、其余为、其余为“出错标志出错标志”。 若文法若文法G G按上面算法构造出来的分析表不包含多重定按上面算法构造出来的分析表不包含多重定 义项，则该文法义项，则该文法G G是是SLRSLR文法。文法。 非终结符的非终结符的FOLLOWFOLLOW集为集为: : FOLLOW(FOLLOW(S)=#)=# FOLLOW(E)=#,+,)FOLLOW(E)=#,+,) FOLLOW(T)=#,+,),FOLLOW(T)=#,+,), FOLLOW(P)=#,+,),FOLLOW(P)=#,+,), 1.S1.SE 2.EE 2.EE+TE+T 3.E3.ET 4.TT 4.TT T P

35、P 5.T5.TP 7.PP 7.Pidid 6.P6.P(E)(E) 分析栈分析栈 符号栈符号栈 输入串输入串 分析动作分析动作 转向状态转向状态 0 # id id+id# S5 0,5 #id id+id# R6 4 0,4 #P id+id# R5 7 0,7 #T id+id# S8 0,7,8 #T id+id# S5 0,7,8,5 #T id +id# R6 9 0,7,8,9 #T P +id# R4 7 0,7 #T +id# R3 1 0,1 #E +id# S3 0,1,3 #E+ id# S5 0,1,3,5 #E+id # R6 4 0,1,3,4 #E+P # R

36、5 11 0,1,3,11 #E+T # R2 1 0,1 #E # Acc 例：有如下文法例：有如下文法: 1. SS 2. S L=R 3. S R 4. L *R 5. L i 6. R L FOLLOW(S )=# FOLLOW(S)=# FOLLOW(L)=,# FOLOOW(R)=,# 0: SS S L=R S R L *R L I R L 6: SL=R R L L *R L i 2: SL=R R L 4:L*R R L L *R L i 1: SS 3:SR 7:L*R 8:RL 5:Li 9:SL=R = R * R L i R S * i i L* L 在状态在状态2

37、2中中, ,对于项目对于项目S SL L=R=R和项目和项目R RL L 因为有因为有FOLLOE(L)=FOLLOE(L)= 所以依然出现冲突所以依然出现冲突, ,因此文法不是因此文法不是SLRSLR文法文法 1 1、LR(1)LR(1)项目项目 LR(0) LR(0)方法不依赖输入流，直接判定归约，容易出现冲突。方法不依赖输入流，直接判定归约，容易出现冲突。 SLR(1)SLR(1)方法要求出现冲突项目时方法要求出现冲突项目时, ,向前搜索符号集向前搜索符号集 bb1 1 ,b ,b2 2 ,b ,b3 3 , , ,b,bm m 和和FOLLOW(VFOLLOW(V1 1) )、FOLL

38、OW(VFOLLOW(V2 2) )、 FOLLOW(VFOLLOW(Vn n) )两两互不相交，但并不是所有文法都能满足这一两两互不相交，但并不是所有文法都能满足这一 要求。要求。 解决方法：每个项目中含有更多的展望信息，使得能确切知解决方法：每个项目中含有更多的展望信息，使得能确切知 道何时能进行归约。道何时能进行归约。 (1)LR(1)(1)LR(1)项目：项目： (A(A ,a),a)的二元式称为的二元式称为LR(1)LR(1)项目。其中，项目。其中，A A是文法的是文法的 一个产生式，一个产生式，a a是终结符，称为搜索符。是终结符，称为搜索符。 说明：搜索符说明：搜索符a a只对归

39、约项目只对归约项目(A(A,a),a)有意义，它表示当它有意义，它表示当它 所属的状态处于栈顶，且下一个输入符号为所属的状态处于栈顶，且下一个输入符号为a a时，才可以把时，才可以把 归约为归约为A A。 7.4 LR(1)7.4 LR(1)分析分析 1)I 1)I的项目集的项目集CLOSURE(I)CLOSURE(I) a)I a)I的任何项目都属于的任何项目都属于CLOSURE(I)CLOSURE(I)； b)b)若项目若项目(A(AB B ,a),a)属于属于CLOSURE(I)CLOSURE(I)，B B是是 一个产生式，则对于一个产生式，则对于FIRST(FIRST( a a) )中

40、的每个终结符中的每个终结符b b， 如果如果( (B B ,b),b)原来不在原来不在CLOSURE(I)CLOSURE(I)中，则把它中，则把它 加进去；加进去； c)c)重复步骤重复步骤b)b)直到直到CLOSURE(I)CLOSURE(I)不再扩大为止。不再扩大为止。 2 2、构造、构造LR(1)LR(1)项目集规范族的算法项目集规范族的算法 2)GO2)GO函数函数 令令I I是一个项目集，是一个项目集，X X是一个文法符号，函数是一个文法符号，函数 GO(I,X)GO(I,X)定义为：定义为：GO(I,X)=CLOSURE(J)GO(I,X)=CLOSURE(J)，其中，其中: :

41、J=(A J=(AX X ,a)|(A,a)|(AX X ,a),a) II 注：注：在执行转换函数在执行转换函数GOGO时，搜索符并不改变。时，搜索符并不改变。 3)3)构造拓广文法构造拓广文法GG的的LR(1)LR(1)项目集族项目集族C C的算法的算法 C=CLOSURE(S C=CLOSURE(S S,#);S,#); DOFOR C DOFOR C中的每个项目集中的每个项目集I I和每个文法符号和每个文法符号X X IF GO(I,X) IF GO(I,X)非空且不属于非空且不属于C C 把把GO(I,X)GO(I,X)加入加入C C中；中； WHILE CWHILE C依然扩大；依

42、然扩大； 设设C=IC=I0 0,I,I1 1,I,In n,以各项目集以各项目集I Ik k(k(k0 0，,n),n)的下的下 标标k k为分析表中的状态，并以包含为分析表中的状态，并以包含(S(SS,S,) )的项的项 目的状态为分析表初态。按下列步骤填写目的状态为分析表初态。按下列步骤填写ACTIONACTION表表 和和GOTOGOTO表：表： 1)1)若项目若项目(A(Aa a ,b),b)属于属于I Ik k，且，且GO(IGO(Ik k,a)=I,a)=Ij j, a, a为终为终 结符，则置结符，则置ACTIONk,a=SACTIONk,a=Sj j; ; 2)2)若项目若项目(A(A,a),a)属于属于I Ik k，则置，则置ACTIONk,a=rACTIONk,a=rj