第2章 LR分 析 法 LR分析法是一种自下而上进行规范归约的语法分析方法，LR指“自左向右扫描和自下而上进行归约”。LR分析法比递归下降分析法、LL(1)分析法和算符优先分析法对文法的限制要少得多，对大多数用无二义的上下文无关文法描述的语言都可以用LR分析器予以识别，而且速度快，并能准确、及时地指出输入串的任何语法错误及出错位置。LR分析法的一个主要缺点是，若用手工构造分析器则工作量相当大，因此必须求助于自动产生LR分析器的产生器。 返回目录

2.1.1 LR分析器的工作原理 我们知道，规范归约(最左归约，即最右推导的逆过程)的关键问题是寻找句柄。LR分析法的基本思想是：在规范归约过程中，一方面记住已移进和归约出的整个符号串，即记住“历史”；另一方面根据所用的产生式推测未来可能遇到的输入符号，即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶端时，我们希望能够根据所记载的“历史”和“展望”以及“现实”的输入符号等三方面的材料，来确定栈顶的符号是否构成相对某一产生式的句柄。

LR分析器结构示意

一个LR分析器实质上是一个带先进后出存储器(栈)的确定有限状态自动机。我们将把“历史”和“展望”材料综合抽象成某些“状态”，而分析栈(先进后出存储器)则用来存放这些状态；栈里的每个状态概括了从分析开始直到某一归约阶段的全部“历史”和“展望”资料。任何时候，栈顶的状态都代表了整个“历史”和已推测出的“展望”。LR分析器的每一步工作都是由栈顶状态和现行输入符号所惟一决定的。为了有助于明确归约手续，我们把已归约出的文法符号串也同时放在栈中(实际上可不必进栈)。栈的每一项内容包括状态s和文法符号X两部分。(s0，#)为分析开始前预先放入栈里的初始状态和句子括号；栈顶状态为sm，符号串X1X2…Xm是至今已移进归约出的文法符号串。

LR分析表是LR分析器的核心部分。一张LR分析表包括两部分：一部分是“动作”(ACTION)表，另一部分是“状态转换”(GOTO)表；它们都是二维数组。ACTION[s,a]规定了当状态s面临输入符号a时应采取什么动作，而GOTO[s, X]规定了状态s面对文法符号X(终结符或非终结符)时的下一状态是什么。显然，GOTO[s, X]定义了一个以文法符号为字母表的DFA。 每一项ACTION[s, a]所规定的动作是以下四种情况之一： (1) 移进：使(s, a)的下一状态s'=ACTION[s, a]和输入符号a进栈(注：对终结符a来说，

下一状态s'=GOTO[s, a]的值实际上是放在ACTION[s, a]中的)，下一输入符号变成现行输入符号。 (2) 归约：指用某一产生式A→β进行归约。假若β的长度为γ，则归约的动作是去掉栈顶的γ个项，即使状态sm-γ变成栈顶状态，然后使(sm-γ,A)的下一状态s'=GOTO[sm-γ,A] 和文法符号(非终结符)A进栈。归约的动作不改变现行输入符号，执行归约的动作意味着呈现于栈顶的符号串Xm-γ+1…Xm是一个相对于A的句柄。 (3) 接受：宣布分析成功，停止分析器的工作。

(4) 报错：报告发现源程序含有错误，调用出错处理程序。 LR分析器的总控程序本身的工作十分简单，它的任何一步只需按分析栈的栈顶状态s和现行输入符号a执行ACTION[s,a]所规定的动作即可。 例如，表达式文法G[E]如下，它对应的LR分析表见表2.13，则语句i+i*i的LR分析过程如表2.14所示：

G[E]: (1) E→E+T (2) E→T (3) T→T*F (4) T→F (5) F→(E) (6) F→i

表2.13 LR分析表 状态 ACTION GOTO i + * ( ) # E T F s5 s4 1 2 3 s6 acc r2 s7 s5   s4 1 2 3 s6 acc r2 s7 r4 4 8 5 r6 6 9 7 10 s11 r1 r3 11 r5

其中，sj指把下一状态j和现行输入符号a移进栈；rj指按文法的第j个产生式进行归约；acc表示分析成功；空白格为出错。 表2.14 i+i*i的LR分析过程 步骤 状态栈 符号栈 输入串 动 作 说 明 1 # i+i*i# ACTION[0,i]=s5，即状态5入栈 2 0 5 # i +i*i# r6: 用F→i归约且GOTO(0,F)=3入栈 3 0 3 # F r4: 用T→F归约且GOTO(0,T)=2入栈 4 0 2 # T r2: 用E→T归约且GOTO(0,E)=1入栈 5 0 1 # E ACTION[1,+]=s6，即状态6入栈 6 0 1 6 # E+ i*i# ACTION[6,i]=s5，即状态5入栈

7 0 1 6 5 # E+i *i# r6: 用F→i归约且GOTO(6,F)=3入栈 8 0 1 6 3 # E+F r4: 用T→F归约且GOTO(6,T)=9入栈 9 0 1 6 9 # E+T ACTION[9,*]=s7，即状态7入栈 10 0 1 6 9 7 # E+T* i# ACTION[7,i]=s5，即状态5入栈 11 0 1 6 9 7 5 # E+T*i # r6: 用F→i归约且GOTO(7,F)=10入栈 12 0 1 6 9 7 10 # E+T*F r3: 用T→T*F归约且GOTO(6,T)=9入栈 13 r1: 用E→E+T归约且GOTO(0,E)=1入栈 14 0 1 # E Acc: 分析成功

我们主要关心的问题是如何由文法构造LR分析表。对于一个文法，如果能够构造一张分析表，使得它的每个入口均是惟一确定的，则称这个文法为LR文法。对于一个LR文法，当分析器对输入串进行自左至右扫描时，一旦句柄呈现于栈顶，就能及时对它实行归约。 在有些情况下，LR分析器需要“展望”和实际检查未来的k个输入符号才能决定应采取什么样的“移进—归约”决策。一般而言，一个文法如果能用一个每步最多向前检查k个输入符号的LR分析器进行分析，则这个文法就称为LR(k)文法。

对于一个文法，如果它的任何“移进—归约”分析器都存在这样的情况：尽管栈的内容和下一个输入符号都已了解，但仍无法确定是“移进”还是“归约”，或者无法从几种可能的归约中确定其一，则该文法是非LR(1)的。注意，LR文法肯定是无二义的，一个二义文法决不会是LR文法；但是，LR分析技术可以进行适当修改以适用于分析一定的二义文法。

我们在后面将介绍四种分析表的构造方法，它们是： (1) LR(0)表构造法：这种方法局限性很大，但它是建立一般LR分析表的基础； (2) SLR(1)表(即简单LR表)构造法：这种方法较易实现又极有使用价值； (3) LR(1)表(即规范LR表)构造法：这种表适用大多数上下文无关文法，但分析表体积庞大； (4) LALR表(即向前LR表)构造法：该表能力介于SLR(1)和LR(1)之间。

2.1.2 LR(0)分析表的构造 我们希望仅由一种只概括“历史”资料而不包含推测性“展望”材料的简单状态就能识别呈现在栈顶的某些句柄，而LR(0)项目集就是这样一种简单状态。 在讨论LR分析法时，需要定义一个重要概念，这就是文法规范句型的“活前缀”。字的前缀是指该字的任意首部，例如字abc的前缀有ε、a、ab或abc。所谓活前缀，是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。在LR分析工作过程中的任何时候，栈里的文法符号(自栈底而上)X1X2…Xm应该构成活前缀，

把输入串的剩余部分匹配于其后即应成为规范句型(如果整个输入串确为一个句子的话)。因此，只要输入串的已扫描部分保持可归约成一个活前缀，就意味着所扫描的部分没有错误。 对于一个文法G[S]，首先要构造一个NFA，它能识别G[S]的所有活前缀。这个NFA的每个状态就是一个“项目”，文法G[S]中每一个产生式的右部添加一个圆点，称为G[S]的一个LR(0)项目(简称项目)。

例如，产生式A→XYZ对应有四个项目： A→·X Y Z A→ X·Y Z A→ X Y·Z A→ X Y Z· 但是产生式A→ε只对应一个项目A→·。一个项目指明了在分析过程的某个时刻我们看到产生式的多大一部分。可以使用这些项目状态构造一个NFA用来识别文法的所有活前缀。

使用讲义讲述的子集方法，就能够把识别活前缀的NFA确定化，使之成为一个以项目集合为状态的DFA，这个DFA就是建立LR分析算法的基础。构成识别一个文法活前缀的DFA的项目集(状态)的全体称为这个文法的LR(0)项目集规范族。这个规范族提供了建立一类LR(0)和SLR(1)分析器的基础。注意，凡圆点在最右端的项目，如A→α· ，称为一个“归约项目”；对文法的开始符号S'的归约项目(S'的含义见下面的叙述)，如S'→α· ，称为“接受”项目；形如A→α·aβ的项目(其中a为终结符)，称为“移进”项目；形如A→α·Bβ的项目(其中B为非终结符)，称为“待约”项目。

1．LR(0)项目集规范族的构造 我们用所引进的ε_CLOSURE(闭包)来构造一个文法G[S]的LR(0)项目集规范族。为了使“接受”状态易于识别，总是将文法G[S]进行拓广。假定文法G[S]以S为开始符号，我们构造一个G'[S']，它包含了整个G[S]并引进了一个不出现在G[S]中的非终结符S'，同时加进了一个新产生式S'→S，这个S'是G'[S']的开始符号。称G'[S']是G[S]的拓广文法，并且会有一个仅含项目S'→S·的状态，这就是惟一的“接受”态。

假定I是文法G'[S']的任一项目集，则定义和构造I的闭包CLOSURE(I)的方法是： (2) 若A→α·Bβ属于CLOSURE(I)，那么对任何关于B的产生式B→γ，其项目B→·γ也属于CLOSURE(I)(设A→α·Bβ的状态为i，则i到所有含B→·γ的状态都有一条ε有向边，即此规则仍与第二章的ε_CLOSURE(I)定义一样)； (3) 重复执行上述(1)～(2)步直至CLOSURE(I)不再增大为止。

在构造CLOSURE(I)时请注意一个重要的事实，那就是对任何非终结符B，若某个圆点在左边的项目B→·γ进入到CLOSURE(I)，则B的所有其它圆点在左边的项目B→·β也将进入同一个CLOSURE集。 此外，我们设函数GO为状态转换函数，GO(I,X)的第一个变元I是一个项目集，第二个变元X是一个文法符号(终结符或非终结符)，函数GO(I,X)定义为 GO(I,X)=CLOSURE(J)

其中，如果A→α·Xβ属于I，则J=｛任何形如A→αX·β的项目｝。如果由I项目集发出的字符为X的有向边，则到达的状态即为CLOSURE(J)(这也类同于第二章Ia=ε_CLOSURE(J)的定义，但这里相当于输入的字符是X)。直观上说，若I是对某个活前缀γ有效的项目集(状态)，则GO(I,X)就是对γX有效的项目集(状态)。

通过函数CLOSURE和GO很容易构造一个文法G[S]的拓广文法G'[S']的LR(0)项目集规范族。如果已经求出了I的闭包CLOSURE(I)，则用状态转换函数GO可以求出由项目集I到另一项目集状态必须满足的字符(即转换图有向边上的字符)；然后，再求出有向边到达的状态所含的项目集，即用GO(I,X)=CLOSURE(J)求出J，再对J求其闭包CLOSURE(J)，也就是有向边到达状态所含的项目集。以此类推，最终构造出拓广文法G'[S']的LR(0)项目集规范族。

2．LR(0)分析表的构造 假若一个文法G[S]的拓广文法G'[S']的活前缀识别自动机中的每个状态(项目集)不存在下述情况：既含移进项目又含归约项目或者含有多个归约项目，则称G[S]是一个LR(0)文法。换言之，LR(0)文法规范族的每个项目集不包含任何冲突项目。 对于LR(0)文法，我们可直接从它的项目集规范族C和活前缀自动机的状态转换函数GO构造出LR分析表。下面是构造LR(0)分析表的算法。

假定C={I0，I1，…，In}。由于我们已经习惯用数字表 示状态，因此令每个项目集Ik的下标k作为分析器的状态，特别地，令包含项目S'→·S(表示整个句子还未输入)的集合Ik的下标k为分析器的初态。分析表的ACTION子表和GOTO子表可按如下方法构造： (1) 若项目A→α·aβ属于Ik且GO(Ik,a)=Ij，a为终结符，则置ACTION[k,a]为“将(j,a)移进栈”，简记为“sj”。

(2) 若项目A→α·属于Ik，则对任何终结符a(或结束符#)，置ACTION[k,a]为“用产生式A→α进行归约”，简记为“rj”(注意：j是产生式的编号，而不是项目集的状态号，即A→α是文法G'[S']的第j个产生式)。 (3) 若项目S'→S·属于Ik(S·表示整个句子已输入并归约结束)，则置ACTION[k,#]为“接受”，简记为“acc”。 (4) 若GO(Ik,A)=Ij，A为非终结符，则置GOTO[k,A]=j。

(5) 分析表中凡不能用规则(1)～(4)填入的空白格均置为“出错标志”。 由于假定LR(0)文法规范族的每个项目集不含冲突项目，因此按上述方法构造的分析表的每个入口都是惟一的(即不含多重定义)。我们称如此构造的分析表是一张LR(0)表，使用LR(0)表的分析器叫做一个LR(0)分析器。 例7.16 已知文法G[S]如下，试构造该文法的LR(0)分析表： G[S]: S→BB B→aB∣b

[解答] 将文法G[S]拓广为文法G'[S']： G'[S']: (0) S'→S (1) S→BB (2) B→aB (3) B→b

列出LR(0)的所有项目： 1．S'→·S 5．S→BB· 9．B→·b 2．S'→S· 6．B→·aB 10．B→b· 3．S→·BB 7．B→a·B 4．S→B·B 8．B→aB·

用ε_CLOSURE办法构造文法G'[S']的LR(0)项目集规范族如下： I0: S'→·S I1: S'→S· I3: B→a·B I5: S→BB· S→·BB I2: S→B·B B→·aB I6: B→aB· B→·aB B→·aB B→·b B→·b B→·b I4: B→b· 根据状态转换函数GO构造出文法G‘[S’]的DFA，如图2–22所示。

图2–22 例3.16文法G'[S']的DFA(即LR(0)项目集和GO函数)

表2.15 例2.16的LR(0)分析表 状态 ACTION GOTO a b # S B s3 s4 1 2 acc 5 3 6 4 r3 s3 s4   1 2 acc 5 3 6 4 r3 r1 r2

3.5.3 SLR(1)分析表的构造 LR(0)文法是一类非常简单的文法，其特点是该文法的活前缀识别自动机的每一状态(项目集)都不含冲突性的项目。但是，即使是定义算术表达式这样的简单文法也不是LR(0)的，因此，需要研究一种简单“展望”材料的LR分析法，即SLR(1)法。 实际上，许多冲突性的动作都可以通过考察有关非终结符的FOLLOW集(即紧跟在该非终结符之后的终结符或“#”)而获得解决。

一般而言，假定LR(0)规范族的一个项目集I中含有m个移进项目： A1→α·a1β1，A2→α·a2β2，…，Am→α·amβm 同时含有n个归约项目： B1→α·, B2→α·, …, Bn→α·如果集合｛a1,…,am｝、FOLLOW(B1)、…、FOLLOW(Bn)两两不相交(包括不得有两个FOLLOW集含有“#”)，则隐含在I中的动作冲突可通过检查现行输入符号a属于上述n+1个集合中的哪个集合而获得解决，

即： (1) 若a是某个ai，i=1,2,…,m，则移进； (2) 若a∈FOLLOW(Bi)，i=1,2,…,n，则用产生式Bi→α进行归约； (3) 对(1)、(2)项以外的情况，报错。 冲突性动作的这种解决办法叫做SLR(1)解决办法。 对任给的一个文法G[S]，我们可用如下办法构造它的SLR(1)分析表：先把G[S]拓广为G'[S']，对G'[S']构造LR(0)项目集规范族C和活前缀识别自动机的状态转换函数GO，然后再使用C和GO按下面的算法构造G'[S']的SLR(1)分析表。

假定C={I0，I1，…，In}，令每个项目集Ik的下标k为分析器的一个状态，则G'[S']的SLR(1)分析表含有状态0，1，…，n。令那个含有项目S'→·S的Ik的下标k为初态，则函数ACTION和GOTO可按如下方法构造: (1) 若项目A→α·aβ属于Ik且GO(Ik，a)=Ij，a为终结符，则置ACTION[k,a]为“将状态j和符号a移进栈”，简记为“sj”。

(2) 若项目A→α·属于Ik，那么对任何输入符号a，a∈FOLLOW(A)，置ACTION[k,a]为“用产生式A→α进行归约”，简记为“rj”。其中，j是产生式的编号，即A→ α是文法G ' [S ' ]的第j个产生式。 (3) 若项目S'→S·属于Ik，则置ACTION[k,#]为“接受”，简记为“acc”。 (4) 若GO(Ik，A)=Ij，A为非终结符，则置GOTO[k,A]=j。 (5) 分析表中凡不能用规则(1)～(4)填入信息的空白格均置上“出错标志”。

按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G[S]的一张SLR(1)表，具有SLR(1)表的文法G[S]称为一个SLR(1)文法。数字“1”的意思是在分析过程中最多只要向前看一个符号(实际上仅是在归约时需要向前看一个符号)，使用SLR(1)表的分析器叫做一个SLR(1)分析器。 若按上述算法构造的分析表存在多重定义的入口(即含有动作冲突)，则说明文法G[S]不是SLR(1)的；在这种情况下，不能用上述算法构造分析器。

例3.18 试构造例3.16所示文法G[S]的SLR(1)分析表。 [解答] 构造SLR(1)分析表必须先求出所有形如“A→α· ”的FOLLOW(A)，即对文法G'[S']的归约项目： B→b· S→BB· B→aB· 求FOLLOW集，由FOLLOW集的构造方法得：

① FOLLOW(S')=｛#｝； ②FIRST(B)FOLLOW(B)，即FOLLOW(B)=｛a,b｝； ③ 由S'→S得FOLLOW(S')  FOLLOW(S)，即FOLLOW(S)=｛#｝；由S→BB得FOLLOW(S)FOLLOW(B)，即FOLLOW(B)=｛a,b,#｝。 根据SLR(1)分析表的构造方法得文法G'[S']的SLR(1)分析表见表2.17。

表2.17 例3.18的SLR(1)分析表 状 态 ACTION GOTO a b # S B s3 s4 1 2 acc 5 3 6 4 状 态 ACTION GOTO a b # S B s3 s4   1 2 acc 5 3 6 4 r3 r1 r2

2.2.1 LR(1)分析表的构造 在SLR(1)方法中，若项目集Ik含有A→α·，那么在状态k时，只要所面临的输入符号a∈FOLLOW(A)，就确定采取“用A→α归约”的动作。但在某种情况下，当状态k呈现于栈顶时，栈里的符号串所构成的活前缀βα未必允许把α归约为A，因为可能没有一个规范句型含有前缀βAa。因此，在这种情况下，用A→α进行归约未必有效。

可以设想让每个状态含有更多的“展望”信息，这些信息将有助于克服动作冲突和排除那种用A→α所进行的无效归约，在必要时对状态进行分裂，使得LR分析器的每个状态能够确切地指出当α后跟哪些终结符时才允许把α归约为A。 我们需要重新定义项目，使得每个项目都附带有k个终结符。现在每个项目的一般形式为 [A→α·β，a1a2…ak] 此处，A→α·β是一个LR(0)项目，每一个a都是终结符。这样的一个项目称为一个LR(k)项目，项目中的a1a2…ak称为它的向前搜索符串(或展望串)。

向前搜索符串仅对归约项目 [A→α·，a1a2…ak]有意义。对于任何移进或待约项目[A→α·β，a1a2…ak]，β≠ε，搜索符串a1a2…ak不起作用。归约项目[A→α·，a1a2…ak]意味着当它所属的状态呈现在栈顶且后续的k个输入符号为a1a2…ak时，才可以把栈顶的α归约为A。这里，我们只对k≤1的情形感兴趣，因为对多数程序语言的语法来说，向前搜索(展望)一个符号就基本可以确定“移进”或“归约”。 构造有效的LR(1)项目集族的办法本质上和构造LR(0)项目集规范族的办法是一样的,也需要两个函数：CLOSURE和GO。

假定I是一个项目集，它的闭包CLOSURE(I)可按如下方式构造： (2)若项目 [A→α·Bβ，a] 属于CLOSURE(I)，B→γ是 一个产生式，那么对于FIRST(βa)中的每个终结符b，如果[B→·γ, b]原来不在CLOSURE(I)中，则把它加进去。 (3) 重复执行步骤(2)，直到CLOSURE(I)不再增大为止。

下面根据文法LR(1)项目集族C构造分析表。假定C=｛I0，I1，…，In｝，令每个Ik的下标k为分析表的状态，令那个含有[S'→· S,#]的Ik的k为分析器的初态。动作ACTION和状态转换GOTO可按如下方法构造： (1) 若项目[A→α·aβ，b]属于Ik且GO(Ik,a)=Ij，a为终结符，则置ACTION[k,a]为“将状态j和符号a移进栈”，简记为“sj”； (2) 若项目[A→α·,a]属于Ik，则置ACTION[k,a]为“用产生式A→α归约”，简记为“rj”；其中，j是产生式的编号，即A→α是文法G'[S']的第j个产生式；

(3) 若项目[S'→S·，#]属于Ik，则置ACTION[k，#]为“接受”，简记为“acc”； (4) 若GO(Ik, A)=Ij，A为非终结符，则置GOTO(Ik, A)=j； (5) 分析表中凡不能用规则(1)～(4)填入信息的空白栏均填上“出错标志”。

LR(1)与LR(0)及SLR(1)方法的区别也体现在构造分析表算法的步骤(2)上。若项目A→α· 属于Ik，则当用产生式A→α归约时，LR(0)无论面临什么输入符号都进行归约动作；SLR(1)则是仅当面临的输入符号a∈FOLLOW(A)时进行归约动作，而不判断栈里的符号串所构成的活前缀βα是否存在着把α归约为A的规范句型——其前缀是βAa；LR(1)则明确指出了当α后跟终结符a(即存在规范句型其前缀为βAa)时，才容许把α归约为A。因此，LR(1)比SLR(1)更精确，解决的冲突也多于SLR(1)。

但对LR(1)来说，其中的一些状态(项目集)除了向前搜索符不同外，其核心部分都是相同的；也即LR(1)比SLR(1)和LR(0)存在更多的状态。因此，LR(1)的构造比LR(0)和SLR(1)更复杂，占用的存储空间也更多。 例2.19 试构造例7.16所示文法G[S]的LR(1)分析表。 [解答] 由FOLLOW集构造方法知FOLLOW(S')=｛#｝；且由S'→S知FOLLOW(S')  FOLLOW(S)，即FOLLOW(S)=｛#｝；也即S的向前搜索字符为“#”(实际上可直接看出)，即[S'→·S,#]。令[S'→·S,#]∈CLOSURE(I0)，我们根据LR(1)闭包CLOSURE(I)的构造方法求出属于I0的所有项目。

① 已知[S'→·S,#]∈CLOSURE(I0)，S→BB是一个产生式，且由构造方法“β=ε得到b=a=“#””求得[S→·BB,#]∈CLOSURE(I0)； ② 已知[S→·BB,#]∈CLOSURE(I0)，B→aB是一个产生式，又FIRST(B)=｛a,b｝(此处的B是指S→·BB中的第二个B)，即有[B→·aB,a/b]∈CLOSURE(I0)； ③ 已知[S→·BB,#]∈CLOSURE(I0)，B→b是一个产生式，且FIRST(B)=｛a,b｝，即有[B→·b,a/b]∈CLOSURE(I0)。

由此可以得到项目集I0如下： I0：S→·S,# S→·BB,# B→·aB,a/b B→·b,a/b 同理可求得全部CLOSURE(I)，再根据状态转换函数GO的算法构造出文法G‘[S’]的DFA如图2–24所示。

图2–24 例2.19文法G'[S']的DFA

LR(1)分析表构造与LR(0)和SLR(1)的主要区别是构造算法步骤(2)，即仅当归约时搜索符才起作用。根据LR(1)分析表的构造算法得到LR(1)分析表见表2.18。

表2.18 例2.19的LR(1)分析表 状 态 ACTION GOTO a b # S B s3 s4 1 2 acc s6 s7 5 3 状 态 ACTION GOTO a b # S B s3 s4   1 2 acc s6 s7 5 3 8 4 r3 r1 6 9 7 r2

例2.20 判断下述文法G[S]是哪类LR文法。 G[S]: (1) S→L=R (2) S→R (3) L→*R (4) L→i (5) R→L

[解答] 首先将文法G[S]拓广为G'[S']： G'[S']: (0) S'→S (1) S→L=R (2) S→R (3) L→*R (4) L→i (5) R→L

I0: S'→·S I2: S→L·=R I5: S→R· S→·L=R R→L· I6: S→L=·R S→·R 构造文法G'[S']的LR(0)项目集规范族如下： I0: S'→·S I2: S→L·=R I5: S→R· S→·L=R R→L· I6: S→L=·R S→·R I3: L→*·R R→·L L→·*R R→·L L→·*R L→·I L→·*R L→·I R→·L L→·i I7: S→L=R· I1: S'→S· I4: L→i· I8: L→*R·

我们知道，如果每个项目集中不存在既含移进项目又含归约项目或者含有多个归约项目的情况，则该文法是一个LR(0)文法。检查上面的项目集规范族，发现I2存在既含移进项目S→L·=R又含归约项目R→L·的情况，故文法G[S]不是LR(0)文法。 假定LR(0)规范族的一个项目集I中含有m个移进项目，即 A1→α·a1β1, A2→α·a2β2, …, Am→α·amβm 同时I中含有n个归约项目，即 B1→α·, B2→α·, …, Bn→α·

如果集合{a1,…,am}、FOLLOW(B1)、…、FOLLOW(Bn)任何两个出现相交的情况(包括存在两个FOLLOW集含有“#”)，则该文法不是SLR(1)文法。

因此，构造文法G'[S']的FOLLOW集如下： (1) FOLLOW(S')={#}； (2) 由S→L=… 得FIRST('=')\{ ε} FOLLOW(L)，即FOLLOW(L)={=}； (3) 由S'→S得FOLLOW(S') FOLLOW(S)，即FOLLOW(S)={#}； 由S→R得FOLLOW(S) FOLLOW(R)，即FOLLOW(R)={#}； 由L→…R得FOLLOW(L) FOLLOW(R)，即FOLLOW(R)={=,#}；由R→L得FOLLOW(R) FOLLOW(L)，即FOLLOW(L)={=,#}。

判断是否是LR(1)文法则首先要构造LR(1)项目集规范族。因此，构造文法G'[S']的LR(1)项目集规范族如下(项目集I0由S'→·S,#开始)： I0: S'→·S,# I6: S→L=·R,# S→·L=R,# R→·L,# S→·R,# L→·*R,# L→·*R,= L→·i,# L→·i,= I7: L→*R·,= R→·L,# I8: R→L·,=

I1: S'→S·,# I9: S→L=R·,# I2: S→L·=R,# I10: R→L·,# R→L·,# I11: L→*·R,# I3: S→R·,# R→·L,# I4: L→*·R,= L→·*R,# R→·L,= L→·i,# L→·*R,= I12: L→i·,# L→·i,= I13: L→*R·,# I5: L→i·,=

2.5.5 LALR分析表的构造 对LR(1)来说，存在着某些状态(项目集)，这些状态除向，前搜索符不同外，其核心部分都是相同的，能否将核心部分相同的诸状态合并为一个状态，这种合并是否会产生冲突?下面将对此进行讨论。

两个LR(1)项目集具有相同的心是指除去搜索符之后这两个集合是相同的。如果把所有同心的LR(1)项目集合并为一，将看到这个心就是一个LR(0)项目集，这种LR分析法称为LALR方法。对于同一个文法，LALR分析表和LR(0)以及SLR分析表永远具有相同数目的状态。LALR方法本质上是一种折中方法，LALR分析表比LR(1)分析表要小得多，能力也差一点，但它却能对付一些SLR(1)所不能对付的情况。

由于GO(I,X)的心仅仅依赖于I的心，因此LR(1)项目集合并之后的转换函数GO可通过GO(I,X)自身的合并而得到，因而在合并项目集时无需考虑修改转换函数问题(假定I1与I2的心相同，即项目集相同，则GO(I1,X) =GO(I2,X)，但这里的项目集是不包括搜索符的)。但是，动作ACTION必须进行修改，使之能够反映被合并的集合的既定动作。

假定有一个LR(1)文法，它的LR(1)项目集不存在动作冲突，但如果把同心集合并为一，就可能导致产生冲突。这种冲突不会是“移进”/“归约”间的冲突，因为若存在这种冲突，则意味着面对当前的输入符号a，有一个项目[A→α·,a]要求采取归约动作，而同时又有另一项目[B→β·aγ,b]要求把a移进；这两个项目既然同处于(合并之前的)某一个集合中，

则意味着在合并前必有某个c使得[A→α·,a]和[B→β·aγ,c]同处于(合并之前的)某一集合中，然而这又意味着原来的LR(1)项目集已经存在着“移进”/“归约”冲突了。因此，同心集的合并不会产生新的“移进”/“归约”冲突(因为是同心合并，所以只改变搜索符，而不改变“移进”或“归约”操作，故不可能存在“移进”/“归约”冲突)。同时，这也说明，如果原LR(1)存在着“移进”/“归约”冲突，则LALR必定也有“移进”/“归约”冲突。

但是，同心集的合并有可能产生新的“归约”/“归约”冲突。例如，假定有对活前缀ac有效的项目集为｛[A→c·,d],[B→c·,e]｝，对bc有效的项目集为｛[A→c·,e],[B→c·,d]｝。这两个集合都不含冲突，它们是同心的，但合并后就变成｛[A→c·,d/e],[B→c·,d/e]｝，显然这已是一个含有“归约”/“归约”冲突的集合了，因为当面临e或d时，我们不知道该用A→c还是用B→c进行归约。

下面给出构造LALR分析表的算法，其基本思想是首先构造LR(1)项目集族，如果它不存在冲突，就把同心集合并在一起。若合并后的集族不存在“归约”/“归约”冲突(即不存在同一个项目集中有两个像A→c·和B→c·这样的产生式具有相同的搜索符)，就按这个集族构造分析表。构造分析表算法的主要步骤如下： (1) 构造文法G[S]的LR(1)项目集族C=｛I0, I1, …, In｝。 (2) 把所有的同心集合并在一起，记C'=｛J0, J1, …, Jm｝为合并后的新族，那个含有项目[S'→·S,#]的Jk为分析表的初态。

(3) 从C'构造ACTION表。 ① 若[A→α·aB,b]∈Jk且GO(Jk,a)= Jj，a为终结符，则置ACTION[k,a]为“sj”； ② 若[A→α·,a]∈Jk，则置ACTION[k,a]为“用A→α归约”，简记为“rj”，其中，j是产生式的编号，即A→α是文法G'[S']的第j个产生式； ③ 若[S'→S·,# ]∈Jk，则置ACTION[k,#]为“接受”，简记为“acc”。 （4) GOTO表的构造。假定Jk是Ii1、Ii2、…、Iit合并后的新集，由于所有这些Ii同心，因而GO(Ii1,X)、GO(Ii2,X)、…、GO(Iit,X)也同心；

记Ii为所有这些GO合并后的集(即合并后为第Ji个状态(项目集))，那么就有GO(Jk,X)=Ji。于是，若GO(Jk,A)=Ji，则置GOTO[k,A]=j(此时的Ji已是同心集合并后的状态编号)。 (5) 分析表中凡不能用(3)、(4)填入信息的空白格均填上“出错标志”。 经上述步骤构造的分析表若不存在冲突，则称它为文法G[S]的LALR分析表，存在这种分析表的文法称为LALR文法。

LALR与LR(1)的不同之处是当输入串有误时，LR(1)能够及时发现错误，而LALR则可能还继续执行一些多余的归约动作，但决不会执行新的移进，即LALR能够像LR(1)一样准确地指出出错的地点。就文法的描述能力来说，有下面的结论： LR(0) SLR(1) LR(1) 无二义文法

例2.21 试根据例2.19中的LR(1)项目集族构造LALR分析表。 [解答] 根据LR(1)项目集族将同心集合并在一起，即将图7-24中的I3与I6、I4与I7以及I8与I9分别合并成： I36: [B→a·B,a/b/# ] I47: [B→b·,a/b/# ] [B→·aB,a/b/# ] I89: [B→aB·,a/b/# ] [B→·b,a/b/# ] 由合并后的集族按照LALR分析表的构造算法得到LALR分析表如表2.19所示。

表2.19 例3.21的LALR分析表 状 态 ACTION GOTO a b # S B s36 s47 1 2 acc 5 36 89 状 态 ACTION GOTO a b # S B s36 s47   1 2 acc 5 36 89 47 r3 r1 r2

2.5.6 二义文法的应用 任何二义文法决不是一个LR文法，因而也不是SLR(1)或LALR文法，这是一条定理。但是，某些二义文法是非常有用的。如算术表达式的二义文法远比无二义文法简单，因为无二义文法需要定义算符优先级和结合规则的产生式，这就需要比二义文法更多的状态。但是，二义文法的问题是因其没有算符优先级和结合规则而产生了二义性。因此，我们要讨论的是使用LR分析法的基本思想，凭借一些其它条件来分析二义文法所定义的语言。下面介绍通常处理二义文法的方法。

如果某文法的拓广文法的LR(0)项目集规范族存在“移进(或接受)”/“归约(或接受)”冲突时，可采用SLR(1)的FOLLOW集的办法予以解决。如果无法解决，则只有借助其它条件，如使用算符的优先级和结合规则的有关信息。 此外，还可以赋予每个终结符和产生式以一定的优先级。假定在面临输入符号a时碰到“移进”/“归约”(假定用A→α归约)的冲突，那么就比较终结符a和产生式A→α的优先级。若A→α的优先级高于a的优先级，则执行归约，反之则执行移进。

假如对产生式A→α不特别赋予优先级，就认为A→α和出现在α中的最右终结符具有相同的优先级。自然，那些不涉及冲突的动作将不理睬赋予终结符和产生式的优先级信息。特别重要的是，只给出终结符和产生式的优先级往往不足以解决所有冲突，这时可以规定结合性质，使“移进”/“归约”冲突得以解决。实际上，左结合意味着打断联系而实行归约，右结合意味着维持联系而实行移进。对于“归约”/“归约”冲突，一种极为简单的解决办法是：优先使用列在前面的产生式进行归约，也即列在前面的产生式具有较高的优先性。

例2.22 已知算术表达式文法G[E]如下，试构造该文法的LR分析表： G[E]: E→E+E︱E*E︱(E)︱i [解答] 将文法G拓广为文法G'[S']: (0)S'→E (1)E→E+E (2)E→E*E (3)E→(E) (4)E→i

列出LR(0)的所有项目： 1．S'→·E 5．E→E+·E 9．E→E*·E 13．E→(E·) 2．S'→E· 6．E→E+E· 10．E→E*E· 14．E→(E)· 3．E→·E+E 7．E→·E*E 11．E→·(E) 15．E→·i 4．E→E·+E 8．E→E·*E 12．E→(·E) 16．E→i· 用ε_CLOSURE方法构造出文法G‘[S’]的LR(0)项目集规范族，并根据状态转换函数GO画出文法G‘[S’]的DFA，如图2–25所示。

图2–25 算术表达式文法G'[S']的DFA

下面我们对文法G'[S']中形如“A→α·”的项目求FOLLOW集。 I1 ：S'→E· I7 ：E→E+E· I8 ：E→E*E· I9 ：E→(E)· I3 ：E→i·

根据FOLLOW集构造方法，构造文法G'[S']中非终结符的FOLLOW集如下： (1) 对文法开始符S'，有#∈FOLLOW(S')，即FOLLOW(S')=｛#｝； (2) 由E→E+…得FIRST(‘+’)\｛ε｝FOLLOW(E)，即FOLLOW(E)={+}；由E→E*…得FIRST(‘*’)\｛ε｝ FOLLOW(E)，即FOLLOW(E)={+，*}；由E→…E)得FIRST(‘)’)\｛ε｝ FOLLOW(E)，即FOLLOW(E)={+，*，)}；

(3) 由S'→E得FOLLOW(S') FOLLOW(E)，即FOLLOW(E)={+，*，),#}。 分析图2–25可知I7 和I8存在矛盾：一方面它们存在“移进”/“归约”矛盾；另一方面，不论是“+”或“*”都属于FOLLOW(E)。这说明文法G'[S']是二义文法，即这种“移进”/“归约”冲突只有借助其它条件才能得到解决，这个条件就是使用算符“+”和“*”的优先级和结合规则的有关信息。

由于“. ”的优先级高于“+”，则“+”遇见其后的“. ”应移进，而“ 由于“*”的优先级高于“+”，则“+”遇见其后的“*”应移进，而“*”遇见其后的“+”应归约。此外，因服从左结合，则“+”遇见其后的“+”应归约，“*”遇见其后的“*”也应归约(注意，服从左结合则实行归约，服从右结合则实行移进)。 对于I7，因为是由活前缀…+E转入I7的(见图2-25，由I0开始到达I7的有向边序列上形成的字符序列即为活前缀)，则其后遇到“#”应该归约，遇到“+”也应归约，但遇到“*”则应移进。 对于I8，因为是由活前缀…*E转入I8的，则其后遇到“#”应该归约，遇到“+”也应归约，遇到“*”同样应该归约。

表2.20 算术表达式的SLR(1)分析表 状 态 ACTION GOTO i + * ( ) # E s3 s2 1 s4 s5 acc s3   s2 1 s4 s5 acc 2 6 3 r4 4 7 5 8 s9 r1 r2 9 r3