本节书摘来自华章出版社《编译与反编译技术》一书中的第3章，第3.4节自下而上的语法分析，作者庞建民，陶红伟，刘晓楠，岳峰，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
3.4 自下而上的语法分析
所谓自下而上的语法分析就是从左向右扫描输入串，逐步进行“归约”，直到文法的开始符号，或者从树末端开始，自下而上为输入串构造语法分析树。这里的归约是指根据文法的产生式规则，把产生式的右部替换成左部符号。
3.4.1 移进与归约
自下而上的语法分析法是一种“移进–归约”法，移进–归约的基本思想是用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成（归约为）该产生式的左部符号。移进–归约分析程序的结构与预测分析程序的结构类似，也是采用表驱动的方式实现。其包含一个输入缓冲区、一个输出缓冲区、一个符号栈、一个分析表和一个总控程序。
1）输入缓冲区用来存放待分析的符号串，它以界符“#”作为结束标志。
2）输出缓冲区用来存放分析结果，通常是产生式序列或者语法分析树。
3）分析栈中存放分析过程中的文法符号，栈底符号为“#”，分析开始时栈里面只含有“#”。当分析栈中仅剩“#”和文法的开始符号S，输入串指针也指向输入串尾的“#”时，分析成功。
4）分析表用来存放不同情况下的分析动作，分析动作有四种：
① 移进：将下一输入符号移入栈。
② 归约：用产生式左侧的非终结符替换栈顶的可归约串（某产生式右部）。
③ 接受：分析成功。
④ 出错：出错处理。
5）移进–归约分析的总控程序按照如下方式进行工作：把输入符号自左至右逐个移进分析栈，并且边移入边分析，一旦栈顶的符号串形成某个句型的可归约串时就进行一次归约，即用相应产生式的左部非终结符替换当前可归约串。接下来继续查看栈顶是否形成新的可归约串，若为可归约串则再进行归约；若栈顶不是可归约串则继续向栈中移进后续输入符号。不断重复这一过程，直到将整个输入串处理完毕。若此时分析栈只剩有“#”和文法的开始符号则分析成功，即确认输入串是文法的一个句子；否则，即认为分析失败。如图3-6所示为移进–归约语法分析器模型。
移进–归约的关键是识别可归约串，如果归约的过程中每次都选择某个句型的句柄作为可归约串，则这样的归约称为规范归约，下面为规范归约的形式化定义。
定义3.13（规范归约） 假定α是文法G的一个句子，我们称序列
αn，αn-1，…，α0
是一个规范归约，如果此序列满足：
1）αn=α；
2）α0为文法的开始符号，即α0=S；
3）对任何i，0 ≤ i ≤ n，αi-1是从αi经将句柄替换成为相应产生式左部符号而得到的。
规范归约是关于α一个最右推导的逆过程，因此规范归约也称为最左归约。无二义文法的最右推导的逆过程一定是规范归约。对于规范句型而言句柄的后面只能出现终结符。
例3.26 考虑式（3.2）文法，对输入串i1*i2+i3进行规范归约的过程如表3-3所示。
表3-3 对输入串i1*i2+i3进行规范归约的过程
步骤 符号栈 输入串 动作 步骤 符号栈 输入串 动作
0 # i1*i2+i3# 预备 8 #E +i3# 用E→T归约
1 #i1 *i2+i3# 移进 9 #E+ i3# 移进
2 #F *i2+i3# 用F→i归约 10 #E+i3 # 移进
3 #T *i2+i3# 用T→F归约 11 #E+F # 用F→i归约
4 #T* i2+i3# 移进 12 #E+T # 用T→F归约
5 #T*i2 +i3# 移进 13 #E # 用E→E+T归约
6 #T*F +i3# 用F→i归约 14 #E # 接受
7 #T +i3# 用T→T*F归约
3.4.2 LR分析
本小节介绍一种有效的自下而上的语法分析方法，称为LR分析法，其中，L表示从左到右扫描输入符号，R表示为输入串构造一个最右推导的逆过程，实现LR分析法的程序称为LR分析程序，又称为LR分析器。LR分析法比LL(1)分析法对文法的限制都要少得多。对大多数用无二义的上下文无关文法所描述的语言都可以用LR分析器予以识别，而且速度快，并能准确、及时地指出输入串的任何语法错误及出错位置。LR分析法的一个主要缺点是，若用手工构造分析器则工作量相当大，因此必须求助于自动产生LR分析器的产生器（典型的产生器是YACC）。
LR分析方法的基本思想是在规范归约过程中，一方面记住已移进和归约出的整个符号串，即记住“历史”；另一方面根据所用的产生式推测未来可能遇到的输入符号，即对未来进行“展望”；当一串貌似句柄的符号串呈现于分析栈的顶端时，根据所记载的“历史”和
“展望”，以及“现实”的输入符号三方面的材料，来确定栈顶的符号是否构成相对某一产生式的句柄，从而确定应该采用的分析动作。
LR分析程序作为一种特殊的移进–归约程序，其同样由五部分组成，也即：一个输入缓冲区、一个输出缓冲区、一个符号栈、一张LR分析表和一个LR分析程序的总控程序，如图3-7所示。
1）输入缓冲区用来存放待分析的符号串，它以界符"#"作为结束标志。
2）输出缓冲区用来存放LR分析总控程序对输入串进行分析过程中所采用的动作序列。
3）符号栈的每一项都分为两栏，分别包括状态s和文法符号X两部分。栈里的每个状态概括了从分析开始直到某一归约阶段的全部“历史”和“展望”资料。（s0，#）为分析开始前预先放入栈里的初始状态s0和句子括号#；任何时候，栈顶的状态sm都代表了整个“历史”和已推出的“展望”，栈中自下而上所包含的符号串X1X2…Xm是至今已移进归约出的文法符号串。
4）一张LR分析表包括两部分，一部分是“动作” （ACTION）表，另一部分是“状态转换”(GOTO)表；它们都是二维数组。ACTION[s，a]规定了当状态s面临输入符号a时应采取什么动作，而GOTO[s，X]规定了状态s面对文法符号X（终结符或非终结符）时的下一状态是什么。每一项ACTION[s，a]所规定的动作是以下四种情况之一：
① 移进：使（s，a）的下一状态s'= GOTO[s，a]和输入符号a进栈，下一输入符号变成现行输入符号。
② 归约：指用某一产生式A→β进行归约。假若β的长度为γ，则归约的动作是去掉栈顶的γ个项，即，使状态sm-γ变成栈顶状态，然后使（sm-γ，A）的下一状态s'=GOTO[sm-γ，A]和文法符号（非终结符）A进栈。归约的动作不改变现行输入符号，执行归约的动作意味着呈现于栈顶的符号串Xm-γ+1…Xm是一个相对于A的句柄。
③ 接受：宣布分析成功，停止分析器的工作。
④ 报错：报告发现源程序含有错误，调用出错处理程序。
5）LR分析器的总控程序本身的工作十分简单，它的任何一步只需按分析栈的栈顶状态s和现行输入符号a执行ACTION[s，a]所规定的动作即可。
在实际实现时，文法符号不必存放在栈里，但为了有助于明确归约过程，仍然把已归约出的文法符号串也同时放在栈中。对于不同的LR分析器，其总控程序都一样，不同的是LR分析表，构造LR分析表的方法不同就形成各种不同的LR分析法。后面将介绍四种分析表的构造方法，它们是：
1）LR(0)分析表构造法：这种方法局限性很大，但它是建立一般LR分析表的基础。
2）SLR(1)分析表（即简单LR分析表）构造法：这种方法较易实现又极有使用价值。
3）LR(1)分析表（即规范LR分析表）构造法：这种表适用大多数上下文无关文法，但分析表体积庞大。
4）LALR(1)分析表（即向前LR分析表）构造法：该表能力介于SLR(1)分析表和LR(1)分析表之间。
一个LR分析器的工作过程可看成栈里的状态序列、已归约串和输入串所构成的三元组的变化过程。分析开始时初始三元组为
（s0，#，a1a2 … an #）
其中，s0为分析器的初始状态；第一个#为句子的左括号；a1a2 … an为输入串，其后的#为结束符（句子的右括号）。以后每步的结果可以表示为：
（s0 s1 … sm，# X1 … Xm，aiai+1 … an #）
分析器根据ACTION(sm，ai)确定下一步动作：
1）若ACTION(sm，ai)为移进，且s=GOTO(sm，ai)，则三元组变为：
（s0 s1 … sm s，# X1 … Xm ai，ai+1 … an #）
2）若ACTION(sm，ai)为按A→β归约，三元组变为：
（s0 s1 … sm-r s，# X1 … Xm-rA ，aiai+1 … an #）
此处，s=GOTO(sm-r， A)，r为β的长度，β= Xm-r+1… Xm。
3）若ACTION(sm，ai)为“接受”，则三元组不再变化，变化过程终止，宣布分析成功。
4）若ACTION(sm，ai)为“报错”，则三元组变化过程终止，报告错误。
一个LR分析器的工作过程就是一步一步地变化三元组的过程，直到执行接受或报错动作为止。上面讨论的分析思想可用算法3.7来描述。
算法3.7 LR分析算法
输入：文法G的LR分析表和输入串w
输出：如果w∈L(G)，则输出w的自下而上分析，否则报错
步骤：
1. 将#和初始状态s0压入栈，将w#放入输入缓冲区；
2. 令输入指针ip指向w#的第一个符号；
3. 令s是栈顶状态，a是ip所指向的符号；
4. repeat
5. if ACTION[s，a]= =sj then /* sj表示将下一个状态j和现行的输入符号a移进栈*/
6. { 把状态j和符号a分别压入栈；
7. 令ip指向下一输入符号；}
8. else if ACTION[s，a ]=rj then /* rj表示按第j个产生式A→β归约 */
9. { 从栈顶弹出|β|个符号；
10. 令s'是现在的栈顶状态；
11. 把GOTO[s'，A]和A先后压入栈中；
12. 输出产生式 A→β；}
13. else if ACTION[s，a]= acc then
14. return；
15. else
16. error()；例3.27 考虑式（3.2）文法，其LR分析表如表3-4所示。表中所引用的记号的意义是：acc表示接受，空白符表示出错。另外，若a为终结符，则GOTO[s，a]的值已列在ACTION[s，a]的sj之中（即状态j），因此GOTO表仅对所有非终结符（比如A）列出GOTO[s，A]的值。假定输入串为i1+i2*i3，则LR分析器的工作过程如表3-5所示。
表3-4 式（3.2）文法的LR分析表
状态 ACTION GOTO
i + * ( ) # E T F状态 ACTION GOTO
i + * ( ) # E T F0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
表3-5 i+i*i的LR分析过程
步骤 状态 符号 输入串 动作说明
1 0 # i1+i2*i3# s5: 状态5和i1入栈
2 0 5 # i1 +i2*i3# r6: 用F→i归约且GOTO(0，F)=3入栈
3 0 3 # F +i2*i3# r4: 用T→F归约且GOTO(0，T)=2入栈
4 0 2 # T +i2*i3# r2: 用E→T归约且GOTO(0，E)=1入栈
5 0 1 # E +i2*i3# s6: 状态6和+入栈
6 0 1 6 # E+ i2*i3# s5: 状态5和i2入栈
7 0 1 6 5 # E+i2 *i3# r6: 用F→i归约且GOTO(6，F)=3入栈
8 0 1 6 3 # E+F *i3# r4: 用T→F归约且GOTO(6，T)=9入栈
9 0 1 6 9 # E+T i3# s7: 状态7和入栈
10 0 1 6 9 7 # E+T* i3# s5: 状态5和i3入栈
11 0 1 6 9 7 5 #E+T*i3 # r6: 用F→i归约且GOTO(7，F)=10入栈
12 0 1 6 9 7 10 # E+TF # r3: 用T→TF归约且GOTO(6，T)=9入栈
13 0 1 6 9 # E+T # r1: 用E→E+T归约且GOTO(0，E)=1入栈
14 0 1 # E # acc：分析成功
定义3.14（LR文法） 对于一个给定的文法G(S)，如果能够构造一张上述的LR分析表，使得它的每个入口均是唯一确定的，则称该文法为LR文法。
对于一个LR文法，当分析器对输入串进行自左至右扫描时，一旦句柄呈现于栈顶，就能及时对它实行归约。
定义3.15（LR(k)文法） 对于一个给定的文法G(S)，如果能用一个每步顶多向前检查k个输入符号的LR分析器进行分析，则称该文法为LR(k)文法。
对于多数语言而言，k=0或1就够了。LR文法肯定是无二义的，一个二义文法决不会是LR文法；但是，LR分析技术可以进行适当修改以适用于分析一定的二义文法。
3.4.3 LR(0)分析
采用LR(0)分析表进行语法分析的方法称为LR(0)分析方法，LR(0)分析方法不需要向前查看输入符号，分析器根据当前的栈顶状态即可确定下一步所应采取的动作。
在未讨论LR(0)分析表的构造之前，首先需要定义一些相关概念。
定义3.16（活前缀） 活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。也就是说，对于规范句型αβδ，β为句柄，如果αβ=u1u2…ur，则符号串ε，u1u2…ui（1≤i≤r）是αβδ的活前缀（δ必为终结符串）。
之所以称为活前缀，是因为在其右边增添一些终结符号之后，就可以使它成为一个规范句型。活前缀与句柄之间有如下关系之一：
1）活前缀不含有句柄的任何符号，期望从剩余输入串中能够看到由某产生式A→α的右部α所推导出的符号串。
2）活前缀只含有句柄的部分符号，某产生式A→α1α2的右部子串α1已经出现在栈顶，期待从剩余的输入串中能够看到α2推导出的符号串。
3）活前缀已经含有句柄的全部符号，某一产生式A→α的右部符号串α已经出现在栈顶，用该产生式进行归约。
LR分析法分析过程中，只要已分析的符号串是正确的，符号栈里的文法符号由底到顶就构成规范句型的一个活前缀，当这个活前缀包含句柄时就归约，否则移进。因此，只要能识别出所有活前缀，识别活前缀是否包含句柄，就能决定什么时候移进，什么时候归约。下面的问题就是，给定一个文法，如何识别该文法的所有活前缀以及活前缀与句柄之间的关系。为此，引入LR(0)项目的概念。
定义3.17（LR(0)项目） 给定一个文法G(S)，右部某个位置上标有圆点的产生式称为该文法的一个LR(0)项目。其中，圆点在产生式最右端的LR(0)项目称为归约项目；对文法开始符号的归约项目又称接受项目；圆点后第一个符号为非终结符号的LR(0)项目称为待约项目；圆点后第一个符号为终结符号的LR(0)项目称为移进项目。
注意：产生式A→ε只有一个LR(0)归约项目“A→·”。LR(0)项目中的圆点符分割已获取的内容和待获取的内容，点的左边代表历史信息，右边代表展望信息。直观地讲，LR(0)项目表示在分析过程的某一阶段，已经看到了产生式的多大部分以及希望看到的部分。
例3.28 产生式S→bBB对应有4个LR(0)项目
S→·bBB
S→b·BB
S→bB·B
S→bBB·
其中，
1）S→·bBB是移进项目，表示活前缀不包含句柄，分析过程中应将b移进符号栈。
2）S→b·BB是待约项目，表示活前缀不包含句柄，期待在继续分析过程中进行归约而得到B。
3）S→bB·B也是待约项目，表示活前缀不包含句柄，期待在继续分析过程中进行归约而得到B。
4）S→bBB·是归约项目，表示已从输入串看到能由bBB推导出的符号串，联系到可将bBB归约为S，bBB是句柄，此时活前缀包含句柄。
为了保证文法开始符号只出现在一个产生式的左边，亦即保证分析器只有一个接受状态，对该文法进行拓广，构造其拓广文法。便会有一个仅含项目S'→S·的状态，这就是唯一的“接受”态。
定义3.18（拓广文法） 假定文法G是一个以S为开始符号的文法，构造一个文法G'，它包含了整个G，但它引进了一个不出现在G中的非终结符S'，并加进一个新产生式S'→S，而这个S'是G'的开始符号。那么，称G'是G的拓广文法。
下面介绍识别文法所有活前缀的方法，算法3.8给出了利用DFA来识别文法所有活前缀的方法。
算法3.8 构造识别文法所有活前缀的DFA方法
输入：文法G=(VT，VN，P，S)的拓广文法G'
输出：识别文法G'所有活前缀的DFA
步骤：
1.拓广文法的每个项目表示一个状态，规定包含拓广文法开始符号的待归约项目所对的状态为初态，其余的任何状态均可认为是NFA的终态（活前缀识别态）。
2.状态之间转换关系的确定方法如下：
① 若状态i为X→X1 … Xi-1·Xi … Xn，状态j为X→X1 … Xi-1Xi·Xi+1 … Xn，则从状态i画一条标志为Xi的有向边到状态j；
② 若状态i为X→α·Aβ，A为非终结符，则从状态i画一条ε边到所有状态A→·γ。
3.把识别文法所有活前缀的NFA确定化，就可以得到一个以项目集合为状态的识别文法G'所有活前缀的DFA。
定义3.19（LR(0)项目集规范族） 构成识别一个文法活前缀的DFA的项目集(状态)的全体称为文法的LR(0)项目集规范族。
例3.29 已知文法G(A)：
A→aA
A→b
构造识别该文法所有活前缀的DFA。
解：先对G(A)进行拓广，拓广后的文法G'(S')为
S'→A
A→aA
A→b（3.12）
G'(S')的LR(0)项目有
（1）S'→·A
（2）A→·aA
（3）A→a·A
（4）A→·b
（5）A→b·
（6）S'→A·
（7）A→aA·
依据算法3.8可以得到识别文法G'(S')活前缀的NFA，如图3-8所示。
对图3-8中的NFA进行确定化，得到识别文法G'(S')的活前缀的DFA，如图3-9所示。
图3-8 识别例3.29中文法G'(S')的 图3-9 识别例3.29中文法G'(S')的
活前缀的NFA 活前缀的DFA从而可以得到，文法G'(S')的LR(0)项目集规范族C为：
C = {{S'→·A，A→·aA，A→·b}，{A→a·A，A→·aA，A→·b}，
{A→b·}，{S'→A·}，{A→aA·}}
通过列出拓广文法的所有LR(0)项目，进而构造识别活前缀的NFA，再确定化为DFA的方法，工作量较大，不实用，实用的方法是直接构造以项目集为状态的识别活前缀的DFA。在未介绍这个方法之前先介绍几个概念。
定义3.20 （LR(0)项目集的闭包(CLOSURE)） 假定I是文法G的任一LR(0)项目集合，定义I的闭包CLOSURE(I)如下：
1）I的任何项目都属于CLOSURE(I)。
2）若A→α·Bβ属于CLOSURE(I)，那么，对任何关于B的产生式B→γ，项目B→·γ也属于CLOSURE(I)。
3）重复执行上述两步骤直至CLOSURE(I)不再增大为止。
为了识别活前缀，还需要定义一个状态转换函数GO。
定义3.21 （LR(0)项目集的转换函数GO） 假定I是文法G的一个LR(0)项目集，X是文法G的一个文法符号，函数值GO(I，X)定义为：
GO(I，X)=CLOSURE(J)
其中J={任何形如A→αX·β的项目| A→α·Xβ属于I}。GO(I，X)称为转移函数，项目A→αX·β称为A→α·Xβ的后继。
通过CLOSURE和GO函数很容易构造文法G的拓广文法G'的LR(0)项目集规范族，具体见算法3.9。
算法3.9 构造文法的LR(0)项目集规范族
输入：文法G=(VT，VN，P，S)的拓广文法G'
输出：G'的LR(0)项目集规范族C
步骤：
- C:={CLOSURE({S'→·S})}；
- repeat
- for C中每个项目集I和G'的每个符号X
- if GO(I，X)非空且不属于C then
- 把GO(I，X)放入C族中；
- until C不再增大
转换函数GO把LR(0)项目集规范族C中项目集连接成一个DFA转换图。
例3.30 对式（3.12）文法，利用算法3.9计算其LR(0)项目集规范族。
解：I0= CLOSURE ({S'→·A})={S'→·A，A→·aA，A→·b}
GO(I0，a)= CLOSURE ({A→a·A})={A→a·A，A→·aA，A→·b}=I1
GO(I0，b)= CLOSURE ({A→b·})={A→b·}=I2
GO(I0，A)= CLOSURE ({S'→A·})={S'→A·}=I3
GO(I1，a)= CLOSURE ({A→a·A})=I1
GO(I1，b)= CLOSURE ({A→b·})={A→b·}=I2
GO(I1，A)= CLOSURE ({A→aA·})={A→aA·}=I4
由于I2、I3 和I4都是归约项目，所以计算结束，故G'(S')的LR(0)项目集规范族C={I0，I1，I2，I3，I4}。
我们希望从识别文法活前缀的DFA建立LR分析器。因此需要研究这个DFA的每个项目集中项目的不同作用。
定义3.22（LR(0)有效项目） 项目A→β1·β2对活前缀γ=αβ1是有效的，如果存在一个规范推导：
S?αAω ? αβ1β2ω，ω∈VT
一个项目可能对好几个活前缀都是有效的（当一个项目出现在LR(0)项目集规范族的好几个不同的项目集合中时便是这种情形）。若归约项目A→ β1·对活前缀αβ1是有效的，则它告诉我们应把符号串β1归约为A，即把活前缀αβ1变为αA。若移进项目A→ β1·β2对活前缀αβ1是有效的，则它告诉我们句柄尚未形成，因此下一步动作应是移进。但是，可能存在如下情形，即对同一个活前缀存在不止一个有效项目，并且有的是移进项目，有的是归约项目，这就有可能存在冲突，这种冲突通过向前多看几个输入符号或许能够获得解决。
若项目A→α·Bβ对活前缀γ=δα是有效的，并且B→η是一个产生式，则项目
B →·η对γ=δα也是有效的。那是因为如果A→α·Bβ对γ=δα是有效的，则存在规范推导
S?δAω?δαBβω，ω∈VT
假定存在规范推导βω?φω，φω∈VT，则对任意的B→η，有规范推导
S?δAω?δαBβω?δαBφω?δαhφω
由定义3.22可知，项目B →·η对γ=δα也是有效的。依据该结论，对于每个活前缀，就可以构造它的有效项目集。实际上，一个活前缀γ的有效项目集就是从上述DFA的初态出发，沿着标记为γ的路径到达的那个项目集（状态）。也即，在任何时候，分析栈里的活前缀X1X2…Xm的有效项目集正是栈顶状态Sm所代表的那个集合。这是LR分析理论的一个基本定理，我们不打算在这里证明该定理，而是通过一个例子对其进行说明。
例3.31 考虑式（3.12）文法及图3-9中它的识别活前缀自动机。符号串aa是一个活前缀，这个自动机在读出aa后到达的状态包含有三个项目，它们分别是
A→a·A
A→·aA
A→·b
下面说明这三个项目都对aa有效。考虑下面三个规范推导
S'?A ? aA ? aaA
S'? A ? aA ? aaA ? aaaA
S'? A ? aA ? aaA ? aab
第一个推导表明A→a·A的有效性，第二个推导表明A→·aA的有效性，第三个推导表明A→·b的有效性。显然对活前缀aa不再存在其他有效项目了。
定义3.23（LR(0)文法） 对于一个给定的文法G，假若识别其拓广文法G'活前缀的自动机中的每个状态（项目集）不存在下述情况：
1）既含有移进项目又含有归约项目。
2）含有多个归约项目。
则称G是一个LR(0)文法。
对于LR(0)文法，我们可直接从它的项目集规范族C和识别活前缀自动机的状态转换函数GO构造出LR分析表。算法3.10是构造LR(0)分析表的算法。
由于假定LR(0)文法规范族的每个项目集不含冲突项目，因此按上述方法构造的分析表的每个入口都是唯一的（即不含多重定义）。我们称如此构造的分析表是一张LR(0)分析表，使用LR(0)分析表的分析器叫做LR(0)分析器。
算法3.10 构造LR(0)分析表
输入：文法G=(VT，VN，P，S)的拓广文法G'(S')
输出：文法G'的LR(0)分析表
步骤：
1.构造G'的LR(0)项目集规范族C={I0，I1，…，In}和识别活前缀自动机的状态转换函数GO，令每个项目集Ik的下标k作为分析器的状态，包含项目S'→·S的集合Ik的下标k为分析器的初态。
2.ACTION子表的构造：
① 若项目A→α·aβ∈Ik且GO(Ik，a)=Ij，a为终结符，则置ACTION[k，a]为sj，表示将(j，a)移进栈。
② 若项目A→α·∈Ik，则对任何终结符a（或结束符#），置ACTION[k，a]为rj，表示用产生式A→α进行归约，其中j是产生式的编号，即A→α是文法G'(S')的第j个产生式。
③ 若项目S'→S·∈Ik，则置ACTION[k，#]为acc表示分析成功。
3.GOTO子表的构造：
若GO(Ik，A)=Ij，A为非终结符，则置GOTO[k，A]=j。
4.分析表中凡不能用规则2～3填入的空白格均置为“出错标志”。
例3.32 对于式（3.12）文法，依据算法3.10可以得到其LR(0)分析表如表3-6所示。
并不是所有的上下文无关文法都是LR(0)文法，实际上只有很少的一部分上下文无关文法是LR(0)文法。
例3.33 判断式（3.2）文法是否为LR(0)文法？
解：首先对式（3.2）文法进行拓广，得到如下拓广文法G'(S')：
（1）S'→E
（2）E→E+T
（3）E→T
（4）T→T*F
（5）T→F
（6）F→(E)
（7）F→i（3.13）
图3-10是识别该拓广文法所有活前缀的DFA。因为I1、I2和I9都含有“移进–归约”冲突，所以，式（3.2）文法不是LR(0)文法。
由例3.33的计算结果可知，算术表达式（3.2）文法不是LR(0)文法，所以不能采用LR(0)分析方法对其进行分析。但是根据算术表达式文法的定义可知，在项目I1对应的状态，只有遇到输入的结束符号“#”时才表明整个表达式归约完成，这时候才执行acc，当遇到“+”时，表明表达式还在形成过程中，所以应该移进，不能归约；在项目集I2对应的状态，遇到“ ”时表示项还没有完全形成，所以需要移进“”，只有遇到“+”、“）”或“#”才能进行归约；在项目集I9对应的状态也有类似的情况。而这里出现冲突的原因是LR(0)分析表的构造中，无论后面遇到什么符号都进行归约，这是不合理的。所以，可以采用向前查看一个输入符号的办法来解决一些冲突。下面将介绍一种通过向前查非终结符的FOLLOW集中的符号来解决冲突的方法，也即SLR(1)分析方法。
3.4.4 SLR(1)分析
LR(0)文法是一类非常简单的文法，其特点是该文法的活前缀识别自动机的每一状态（项目集）都不含冲突性项目。但是，由例3.33可知，即使是定义算术表达式这样的简单文法也不是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）此外，报错。
这种冲突性动作的解决办法称为SLR(1)分析法。
基于SLR(1)解决办法的思想，对任给的一个文法G(S)，我们可用算法3.11构造它的SLR(1)分析表。
算法3.11 构造SLR(1)分析表
输入：文法G=(VT，VN，P，S)的拓广文法G'
输出：文法G'的SLR(1)分析表
步骤：
1.构造G'的LR(0)项目集规范族C={I0，I1，…，In}和识别活前缀自动机的状态转换函数GO，令每个项目集Ik的下标k作为分析器的状态，包含项目S'→·S的集合Ik的下标k为分析器的初态。
2.ACTION子表的构造：
① 若项目A→α·aβ∈Ik且GO(Ik，a)=Ij，a为终结符，则置ACTION[k，a]为sj ，表示将(j，a)移进栈。
② 若项目A→α·∈Ik，则对任何终结符a，a∈FOLLOW(A)，置ACTION[k，a]为rj，其中，假定A→α为文法G'的第j个产生式。
③ 若项目S'→S·∈Ik，则置ACTION[k，#]为acc表示分析成功。
- GOTO子表的构造：
若GO(Ik，A)=Ij，A为非终结符，则置GOTO[k，A]=j。
4.分析表中凡不能用规则2～3填入的空白格均置为“出错标志”。
定义3.24（SLR(1)文法和SLR(1)分析器） 对于一个给定的文法G，如果按算照3.11构造出的ACTION与GOTO表不含多重入口，则称该文法为SLR(1)文法。数字“1”的意思是，在分析过程中顶多只要向前看一个符号。使用SLR(1)表的分析器称为SLR(1)分析器。
例3.34 构造式（3.2）文法的SLR(1)分析表。
解：例3.33已给出识别式（3.2）文法的拓广文法所有活前缀的DFA，见图3-10。其中项目集I1、I2和I9都含有“移进–归约”冲突。
首先考虑I1中的项目
S'→E·
E→E·+T
因为FOLLOW(S')={#}，所以I1第一个项目产生ACTION[1, #]=acc；而第二个项目ACTION[1, +]=s7
再考虑I2中的项目
E→T·
T→T·*F
因为FOLLOW(E)={#, ), +}，所以第一个项目使得ACTION[2, #]=r2, ACTION[2, )]=r2，ACTION[2, +]=r2；第二个项目使得ACTION[2, *]=s6。从而I2的冲突可以解决。同理，I9的冲突也可以解决。最后得到式（3.2）文法的SLR(1)分析表如表3-7所示。
每一个SLR(1)文法都是无二义的文法，但并非无二义的文法都是SLR(1)文法。
表3-7 式（3.2）文法的SLR(1)分析表
状态 ACTION GOTO
i + * ( ) # E T F状态 ACTION GOTO
i + * ( ) # E T F0 s5 s4 1 2 3
1 s7 acc
2 r2 s6 r2 r2
3 r4 r4 r4 r4
4 s5 s4 10 2 3
5 r6 r6 r6 r6
6 s5 s4 8
7 s5 s4 9 3
8 r3 r3 s11
9 r1 s6 r1 r1
10 s7 s11
11 r5 r5 r5 r5
例3.35 文法G(S)具有如下产生式：
S→L=R
S→R
L→*R
L→id
R→L（3.14）
该文法为无二义性，对其进行拓广，得到拓广文法G'( S')的产生式如下：
（0）S'→S
（1）S→L=R
（2）S→R
（3）L→*R
（4）L→id
（5）R→L（3.15）
构造文法G'(S')的识别活前缀的DFA，如图3-11所示。考虑I2，第一个项目使ACTION[2，=]=s6；而第二个项目由于“=”属于FOLLOW(R)，所以将使ACTION[2，=]=r5，因此含有“移进–归约”冲突，并且这种冲突不能用SLR(1)解决办法消解，因此不是SLR(1)文法。
因为式（3.14）文法不是SLR(1)文法，从而不能用SLR(1)分析方法进行分析。而实际上根据式（3.14）文法的定义可知，由于这个文法不存在以“R=”为前缀的规范句型，因此，当状态2处于栈顶，面临输入符号“=”时，不能用R→L对栈顶的L进行归约。“=”属于FOLLOW(R)是因为存在以“*R=”为前缀的规范句型，但不存在以“R=”为前缀的规范句型，FOLLOW函数不能区分这两种情况。究其原因，SLR(1)分析方法只是孤立地考察了输入符号是否属于归约项目A→α·所关联的FOLLOW(A)，而没有考察符号串α在规范句型中的上下文，因而具有一定的片面性。
所以当试图用某一产生式A→α归约栈顶符号串α时，不仅要向前扫描一个输入符号，还要查看栈中的所有符号串δα，只有当δA加上后续的符号a的确构成文法某一规范句型的活前缀时，才能用A→α归约。但是，怎样确定δAa是否是文法某一规范句型的活前缀？下面将介绍一种对于产生式A→α的归约，考虑不同使用位置的A会要求不同的后继符号的方法，也即LR(1)分析方法。
3.4.5 LR(1)分析
在SLR(1)分析方法中，若项目集Ik含有A→α·，那么在状态k时，只要所面临的输入符号a∈FOLLOW(A)，就确定采取“用A→α归约”的动作。但在某种情况下，当状态k呈现于栈顶时，栈里的符号串所构成的活前缀δα未必允许把α归约为A，因为可能没有一个规范句型含有前缀δAa。因此，在这种情况下用A→α进行归约未必有效。为了解决这一问题，对LR(0)项目进行分裂，使得LR分析器的每个状态能确定地指出，当α后紧跟哪些终结符时，才允许把α归约为A。为此，我们需要重新定义项目，使得每个项目都附带有k个终结符。
定义3.25（LR(k)项目） LR(k)项目一般形式为[A→α·β，a1a2…ak]，其中A→α·β是一个LR(0)项目，ai （i=1，2，…，k）是终结符号。项目中的 a1a2…ak 称为它的向前搜索符串（或展望串）。
向前搜索符串仅对归约项目[A→α·，a1a2…ak]有意义。对于任何移进或待约项目[A→α·β，a1a2…ak]，β ≠ ε，搜索符串 a1a2…ak 没有作用。归约项目[A→α·，a1a2…ak]意味着当它所属的状态呈现在栈顶且后续的k个输入符号为 a1a2…ak 时，才可以把栈顶上的α归约为A。我们只对k≤1的情形感兴趣，向前搜索（展望）一个符号就多半可以确定“移进”或“归约”。
与LR(0)文法类似，识别文法全部活前缀的DFA的每一状态也是用一个LR(1)项目集来表示，为保证在分析时每一步都在栈中得到规范句型的活前缀，应使每一个LR(1)项目集仅由对相应活前缀有效的项目组成。下面是LR(1)有效项目的定义。
定义3.26（LR(1)有效项目） 称一个LR(1)项目[A→α·β，a]对活前缀γ=δα是有效的，如果存在一个规范推导：
S?* δAω ? δαβω
其中ω的第一个符号为a，或者ω=ε且a=#。
若项目[A→α·Bβ，a]对活前缀γ=δα是有效的，并且B→η是一个产生式，则对任何b∈FIRST(βa)，项目[B→·η，b]对活前缀γ=δα也是有效的。那是因为如果[A→α·Bβ，a]对γ=δα有效，则存在规范推导：
S?*δAax?δαBβax
假定βax?*by，则对任意的B→η，有规范推导
S? δAax?δαBβax?δαBby?δαηby
由定义3.26可知，项目[B→·η，b]对活前缀γ=δα也是有效的。
定义3.27（LR(1)有效项目集和LR(1)项目集规范族） 文法G的某个活前缀γ的所有LR(1)有效项目组成的集合称为γ的LR(1)有效项目集。文法G的所有LR(1)有效项目集组成的集合称为G的LR(1)项目集规范族。
构造LR(1)项目集规范族的办法本质上与构造LR(0)项目集规范族的办法是一样的，也需要两个函数：CLOSURE和GO。
定义3.28（LR(1)项目集的闭包(CLOSURE)） 设I是文法G的一个LR(1)项目集，定义I的闭包CLOSURE(I)如下：
1）I的任何项目都属于CLOSURE(I)。
2）若项目[A→α·Bβ，a]属于CLOSURE(I)，B→η是一个产生式，那么，对于FIRST(βa)中的每个终结符b，如果[B→·η，b]原来不在CLOSURE(I)中，则把它加进去。
3）重复执行步骤2，直至CLOSURE(I)不再增大为止。
定义3.29（LR(1)项目集的转移函数(GO)） 设I是文法G一个LR(1)项目集，X是文法G一个文法符号，函数GO(I，X)定义为：
GO(I，X)=CLOSURE(J)
其中J={任何形如[A→αX·β，a]的项目| [A→α·Xβ，a]∈I}。项目[A→αX·β，a]称为[A→α·Xβ，a]的后继。
若I中项目[A→α·Xβ，a]对活前缀γ=δα是有效的，则由定义3.26可知，存在规范推导
S?*δAω ?δαXβax
这个推导同样说明J中的项目[A→αX·β，a]是活前缀γX的有效项目。所以若I是某个活前缀γ的有效项目集，则GO(I，X)便是活前缀γX的有效项目集。
算法3.12 构造文法的LR(1)项目集规范族
输入：文法G=(VT，VN，P，S)的拓广文法G'
输出：G'的LR(1)项目集规范族
步骤：
- C:={CLOSURE({[S'→·S，#]})}；
- repeat
- for C中每个项目集I和G'的每个符号X
- if GO(I，X)非空且不属于C then
- 把GO(I，X)加入C中
- until C不再增大
例3.36 依据算法3.12构造式（3.15）文法的LR(1)项目集规范族C，并给出基于LR(1)项目识别该文法所有活前缀的DFA。
解：I0 = CLOSURE({[S'→·S，#]})
= { [S'→·S，#]，[S→·L=R，#]，[S→·R，#]，[L→·*R，=/#]，[L→·i，/#]，
[R→·L，#] }
I1 = GO(I0，S)= CLOSURE({[S'→S·，#]})={[S'→S·，#]}
I2 = GO(I0，L)= CLOSURE({[S →L·=R，#]，[R →L·，#]})
={[S →L·=R，#]，[R →L·，#]}
I3 = GO(I0，R)= CLOSURE({[S→R·，#]})={[S→R·，#]}
I4 = GO(I0，)= CLOSURE({[L →·R，=/#]})
= {[L →·R，=/#]，[R →·L，=/#]，[L →·i，=/#]，[L →·R，=/#]}
I5 = GO(I0，i)= CLOSURE({[L→i·，=/#]})={[L→i·，=/#]}
I6 = GO(I2，=)= CLOSURE({[S →L=·R，#]})
= {[S →L=·R，#]，[R →·L，#]，[L →·*R，#]，[L →·i，#]}
I7 = GO(I4，R)= CLOSURE({[L→R ·，=/#]})={[L→R ·，=/#]}
I8 = GO(I4，L)= CLOSURE({[R→L·，=/#]})={[R→L·，=/#]}
I9 = GO(I6，R)= CLOSURE({[S→L=R·，#]})={[S→L=R·，#]}
I10=GO(I6，L)= CLOSURE({[R→L·，#]})={[R→L·，#]}
I11=GO(I6，i)= CLOSURE({[L→i·，#]})={[L→i·，#]}
I12=GO(I6，)= CLOSURE({[L →·R，#]})
={[L →·R，#]，[R →·L，#]，[L →·R，#]，[L →·i，#]}
I13=GO(I12，R)= CLOSURE({[L→R·，#]})={[L→R·，#]}
综上可得，式（3.15）文法的LR(1)项目集规范族C如表3-8所示。根据该项目集可以得到识别式（3.15）文法所有活前缀的DFA，如图3-12所示。
表3-8 式(3.15)文法的LR(1)项目集规范族C
I0: S'→·S，#
S →·L=R，#
S →·R，#
L →·*R，=/#
L →·i，=/#
R →·L，# I3: S→R·，# I6: S →L=·R，#
R →·L，#
L →·*R，#
L →·i，# I10: R→L·，#
I4: L →*·R，=/#R →·L，=/#
L →·i，=/#
L →·*R，=/# I11: L→i·，#
I12: L →*·R，#R →·L，#
L →·*R，#
L →·i，#
I1: S'→S·，# I5: L→i·，=/# I7: L→R ·，=/# I13: L→R·，#
I2: S →L·=R，#
R →L·，# I8:
I9: R→L·，=/#
S→L=R·，#
图3-12 基于LR(1)项目识别式（3.15）文法所有活前缀的DFA
算法3.13给出根据文法LR(1)项目集规范族C和转换函数GO构造LR(1)分析表的方法。
算法3.13 构造LR(1)分析表
输入：文法G=(VT，VN，P，S)的拓广文法G'
输出：文法G'的LR(1)分析表
步骤：
1.构造G'的LR(1)项目集规范族C={I0，I1，…，In}和识别活前缀自动机的转换函数GO，令每个项目集Ik的下标k作为分析器的状态，包含项目[S'→· S，#]的集合Ik的下标k为分析器的初态。
- ACTION子表的构造：
① 若项目[A→α·aβ，b]∈Ik且GO(Ik，a)=Ij，a为终结符，则置ACTION[k，a]为sj，表示将(j，a)移进栈。
② 若项目[A→α·，a]∈Ik，则ACTION[k，a]为rj，其中，假定A→α为文法G'的第j个产生式。
③ 若项目[S'→S?·?，?#]∈Ik，则置ACTION[k，#]为acc 表示分析成功。
- GOTO子表的构造：
若GO(Ik，A)=Ij，A为非终结符，则置GOTO[k，A]=j。
4.分析表中凡不能用规则2～3填入的空白格均置为“出错标志”。
定义3.30（LR(1)文法和LR(1)分析器） 对于一个给定的文法G，如果按算法3.13构造出的ACTION与GOTO表不含多重入口，则称它是文法G的LR(1)分析表；具有LR(1)分析表的文法称为LR(1)文法；使用LR(1)分析表的分析器称为LR(1)分析器。
例3.37 基于例3.36中的计算结果，利用算法3.13可以得到式（3.15）文法的LR(1)分析表，如表3-9所示。从而可知，式（3.15）文法不能用SLR(1)技术解决冲突，但能用LR(1)技术解决。
表3-9 式（3.15）文法的LR(1)分析表
状态 ACTION GOTO
= * i # S L R0 s4 s5 1 2 3
1 acc
2 s6 r5
3 r2
4 s4 s5 8 7
5 r4 r4
6 s12 s11 10 9
7 r3 r3
8 r5 r5
9 r1
10 r5
11 r4
12 s12 s11 10 13
13 r3
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)分析表的构造更复杂，占用的存储空间也更多。
3.4.6 LALR(1)分析
虽然LR(1)分析法的分析能力比SLR(1)分析方法的能力强，但是LR(1)分析表的规模要比SLR(1)分析表或者LR(0)分析表大很多，比如对于Algol一类语言来说，其SLR(1)分析表只有几百个状态，而LR(1)分析表则有几千个状态。为了克服LR(1)分析方法的缺点，F. DeRemer提出了一种折中方法，也即LALR(1)分析方法，这种方法的基本思想是将LR(1)项目集族中的同心项目集合并，以减少项目集的个数，进而减少状态的数目。所谓同心的LR(1)项目集是指略去搜索符后是相同集合的LR(1)项目集。
例3.38 表3-8中的I4={[ L → ·R，=/#]，[R →·L，=/#]，[L →·i，=/#]，[L →·R，=/#]}，I12={[ L → ·R，/#]，[R →·L，/#]，[L →·i，/#]，[L →·R，/#]}有相同的心{L → ·R，R →·L，L →·i，L →·R}，所以I4和I12是同心项目集。同理，表3-8中的I5和I11、I7和I13、I8和I10也是同心项目集。
若文法是LR(1)文法，同心集的合并不会引起新的移进–归约冲突。假设Ik和Ij为两个具有相同心的LR(1)项目集，其中
Ik: [A→α·，u1]
??[B→β·aγ，b]
Ij: [A→α·，u2]
??[B→β·αγ，c]
因为假设文法是LR(1)，所以不存在移进–归约冲突，也即
{u1}?∩?{a}=?，{u2}?∩?{a}=?
显然合并后有
{u1，u2}?∩?{a}=?
所以同心集的合并不会引起新的移进–归约冲突。
若文法是LR(1)文法，同心集的合并有可能产生新的归约–归约冲突，比如例3.39中所给出的式（3.16）文法。
例3.39 试证明式（3.16）文法是LR(1)文法但不是LALR(1)文法。
S' →S
S →aBc | bCc | aCd | bBd
B → e
C → e（3.16）
证明：利用算法3.12可以得到式（3.16）文法的LR(1)项目集规范族，如表3-10所示。表3-10中的每一个项目集Ii都不含移进–归约冲突或者归约–归约冲突，因此式（3.16）文法是LR(1)文法。
表3-10 式（3.16）文法的LR(1)项目集规范族
I0: S'→·S，# S→a·Cd，# I4: S→aB·c，# I9: B→e·，d
S→·aBc，# B→·e，c I5: S→aC·d，# C→e·，c
S→·bCc，# C→·e，d I6: B→e·，c I10: S→aBc·，#
S→·aCd，# I3: S→b·Cc，# C→e·，d I11: S→aCd·，#
S→·bBd，# S→ b·Bd，# I7: S→bC·c，# I12: S→bCc·，#I1: S'→S·，# C→·e，c I8: S→bB·d，# I13: S→bBd·，#
I2: S→a·Bc，# B→·e，d
I6和I9是同心集，合并后为
I6/9: {[C→e·，c/d]，[B→e·，d/c]}
出现了新的归约–归约冲突。因为无论当前的符号是d或c，既可以用C→e进行归约，也可用B→e进行归约，因而可判断式（3.16）文法不是LALR(1)文法。
下面给出构造LALR(1)分析表的算法，其基本思想是，首先构造LR(1)项目集规范族，如果它不存在冲突，就把同心集合并在一起，若合并后的项目集规范族不存在归约–归约冲突，就按这个项目集规范族构造分析表。算法3.14描述了构造LALR(1)分析表的方法。
算法3.14 构造LALR(1)分析表
输入：文法G=(VT，VN，P，S)的拓广文法G'(S')
输出：文法G'(S')的LALR(1)分析表
步骤：
1.构造文法G'的LR(1)项目集族C={I0，I1，…，In }和基于LR(1)项目识别活前缀自动机的状态转换函数GO。
2.把所有的同心集合并在一起，记C'={ J0，J1，…，Jm }为合并后的新族，令每个项目集Jk的下标k作为分析器的状态，含有项目[S'→·S，#]的集合Jk的下标k为分析表的
初态。
3.从C'构造ACTION表。
① 若[A→α·aB，b]∈Jk且GO(Jk，a)= Jj，a为终结符，则置ACTION[k，a]为sj，表示将(j，a)移进栈。
② 若[A→α·，a]∈Jk，则置ACTION[k，a]为rj，其中，假定A→α为文法G'的第j个产生式。
③ 若[S'→S·，# ]∈Jk，则置ACTION[k，#]为acc，表示分析成功。
- GOTO表的构造。
假定Jk是Ii1，Ii2，…，Iit合并后的新集，由于所有这些Ii同心，因而GO(Ii1，X)，GO(Ii2，X)，…，GO(Iit，X)也同心。记Jj为所有这些GO函数值合并后的集，那么就有GO(Jk，X)=Jj。于是，若GO(Jk，X)=Jj，则置GOTO[k，X]=j。
5.分析表中凡不能用步骤3～4填入信息的空白格均填上“出错标志”。
定义3.31（LALR(1)文法和LALR(1)分析器） 对于一个给定的文法G，如果按照算法3.14构造出的ACTION与GOTO表不含多重入口，则称它是文法G的LALR(1)分析表；具有LALR(1)分析表的文法称为LALR(1)文法；使用LALR(1)分析表的分析器称为LALR(1)分析器。
对于同一个文法，LALR(1)分析表和LR(0)分析表以及SLR(1)分析表永远具有相同数目的状态。由例3.39可知，LALR(1)分析方法比LR(1)分析方法能力差一点，但它却能对付一些SLR(1)分析方法所不能对付的情况（见例3.40），也即LALR(1)分析方法的能力介于SLR(1)分析方法和LR(1)分析方法之间。
例3.40 由例3.38可知，式（3.15）文法的LR(1)项目集族C中I4和I12、I5和I11、I7和I13、I8和I10为同心集。I4和I12合并同心集后的项目集为
I4/12: {[L→·R，=/#]，[R→·L，=/#]，[L→·i，=/#]，[L→·R，=/#]}
I5和I11合并同心集后的项目集为
I5/11: {[L→i·，=/#]}
I7和I13合并同心集后的项目集为
I7/13: {[L→*R·，=/#]}
I8和I10合并同心集后的项目集为
I8/10: {[R→L·，=/#]}
合并同心集后得到的项目集仍然不含有冲突，所以，式（3.15）文法也是LALR(1)文法。相应的识别式（3.15）文法的所有规范句型活前缀的DFA如图3-13所示。根据这个DFA，利用算法3.14很容易构造出式（3.15）文法的LALR(1)分析表，如表3-11所示。
LALR(1)分析方法与LR(1)分析方法还有一点不同之处，当输入串有误时，LR(1)分析方法能够及时发现错误，而LALR分析方法则可能还需继续做一些不必要的归约动作，但决不会执行新的移进，即LALR(1)分析方法能够像LR(1)分析方法一样准确地指出出错的地点。
图3-13 基于LALR(1)项目识别式（3.15）文法所有活前缀的DFA
表3-11 式（3.15）文法的LALR(1)分析表
状态 ACTION GOTO
= * i # S L R0 s4/12 s5/11 1 2 3
1 acc
2 s6 r5
3 r2
4/12 s4/12 s5/11 8/10 7/13
5/11 r4 r4
6 s4/12 s5/11 8/10 9
7/13 r3 r3
8/10 r5 r5
9 r1
例3.41 假设输入串为i1=i2=#，则表3-9所对应的LR(1)分析器的分析过程如表3-12所示，表3-11所对应的LALR(1)分析器的分析过程如表3-13所示。从表3-12和表3-13中可以看出LALR(1)分析方法多做了一些不必要的归约动作。
表3-12 LR(1)分析器对i1=i2=#的分析过程
步骤 状态 符号 输入串 步骤 状态 符号 输入串
0 0 # i1=i2=# 3 026 #L= i2=#
1 05 #i1 =i2=# 4 02611 #L=i2 =#
2 02 #L =i2=# 5 报错
表3-13 LALR(1)分析器对i=i=#的分析过程
步骤 状态 符号 输入串 步骤 状态 符号 输入串
0 0 # i1=i2=# 4 0265/11 #L=i2 =#
1 05/11 #i1 =i2=# 5 0268/10 #L=L =#
2 02 #L =i2=# 6 0269 #L=R =#
3 026 #L= i2=# 7 报错
3.4.7 分析方法比较
至此，我们已经讨论了常用的语法分析方法，即LL(1)分析方法和LR(k)分析方法。下面我们就这些方法做一个比较。LR分析方法能分析的文法类是LL(1)分析方法能分析的文法类的真超集。对于LR(k)分析方法，分析程序只要求在看见了产生式右部推出的所有符号以及从输入串中预测k个符号后，就能够识别产生式右部的出现。这个要求比LL(k)分析方法的要求弱，LL(k)分析方法要求看见了右部推出的前k个符号后就识别所使用的产生式。所以，LR文法比LL文法能够描述、识别更多的语言。
针对本章所介绍的常用的LR分析方法，LR(0)分析方法不考虑搜索符，SLR(1)分析方法在归约时考虑搜索符，因此，SLR(1)分析方法比LR(0)分析方法的能力强，但是两种方法有相同的状态数，然而SLR(1)分析方法对搜索符所含信息量的利用有限，未考虑栈中内容。LR(1)分析方法考虑对于产生式A→α的归约，不同使用位置的A要求不同的后继符号，所以LR(1)分析方法比SLR(1)分析方法更精确，功能更强，但由于状态的细化，LR(1)分析方法比SLR(1)分析方法和LR(0)分析方法存在更多的状态，代价更高。通过对LR(1)分析方法中LR(1)项目集族的同心项目集进行合并所得到的LALR(1)分析方法，其状态数目与SLR(1)分析法和LR(0)分析方法中的相同，功能比LR(1)分析方法弱但比SLR(1)分析法强。
