第5章自底向上的语法分析方法

自底向上的分析方法的主要思想是从待分析的输入单词串出发，根据文法规则逐步进行归约，直到归约到文法的开始符号为止。在编译器的语法分析中，存在多种自底向上的分析法，这些方法归根结底都遵循相同的原理，即“移进归约”的思想。


5.1自底向上的语法分析方法

5.1.1“移进归约”分析
自底向上的语法分析方法通常采用“移进归约”的分析过程处理输入串。该过程需要预先设置一个存放文法符号的符号栈和存放输入串的缓冲区，初始化时，栈底存放标记符号#，输入缓冲区也以#作为结尾标记。在分析过程中，自左至右扫描输入串，把输入字符逐一移入符号栈内，当栈顶出现某个产生式的右部时就进行归约，即把栈顶的可归约串弹出，产生式的左部符号入栈，然后继续检查栈顶是否又出现了归约串，若出现，则继续归约，否则从输入缓冲区中继续移进下一个符号，这一过程直到整个输入串扫描完毕。此时若栈顶为文法的开始符号，说明整个输入串最终归约成文法开始符号，则可以确认所分析的符号串是文法的句子，否则，符号串不合法，要报告语法错误。下面通过一个例子说明“移进归约”分析过程。
【例51】设有文法G［S］:

S→aAcBe
A→b｜Ab
B→d
对输入符号串abbcde进行“移进归约”分析，即判定它是否为该文法的句子。
用“移进归约”分析方法对输入符号串abbcde的分析过程如表51所示。符号#作为输入符号串abbcde的左右界符，即输入符号串的开始和结束标志。初始化时，将左界符#首先放入符号栈底，然后从第一个符号开始分析。


表51输入符号串abbcde的分析过程


步骤
符号栈
输入串
分析动作


初始化#abbcde#移进
(1)#abbcde#移进
(2)#abbcde#用A→b归约
(3)#aAbcde#移进
(4)#aAbcde#用A→Ab归约
(5)#aAcde#移进
(6)#aAcde#移进
(7)#aAcde#用B→d归约
(8)#aAcBe#移进
(9)#aAcBe#用S→aAcBe归约
(10)#S#接受（分析成功）

注： 表中第2列“符号栈”左端表示栈底，右端表示栈顶； 第3列“输入串”左端表示当前要读入的输入串的字符，右端是输入串的结束。





从上述分析过程可知，“移进归约”分析过程主要采取的分析动作包括移进、归约、接受或报错，上例因为分析的符号串没有语法错误，所以没有出现“报错”。“报错”通常调用出错处理子程序进行处理。进一步观察表51给出的归约顺序可知，归约的逆过程恰好是从文法开始符号出发，进行最右推导(规范推导)的过程。例如，符号串abbcde的最右推导序列为
SaAcBeaAcdeaAbcdeabbcde

每次归约时呈现在栈顶的要归约的子串称为可归约串。归约时，第一步把最左边的可归约串b归约为A，第二步把最左边的可归约串Ab归约为A，第三步把最左边的可归约串d归约为B，最后一步仍然是把最左边的可归约串aAcBe归约为S。因此最右推导与最左归约对应，互为逆过程。
“移进归约”分析方法之所以采用最左归约是和扫描顺序对应的，因为对输入字符串自左至右逐一扫描，所以很自然地总是对最左边的可归约串进行归约。
5.1.2规范归约与句柄
上述“移进归约”分析实施的是规范归约(最左归约)，每步归约的是最左可归约串，显然，如何定义和确定它是自底向上分析的关键问题。下面介绍一些相关的概念和定义。
定义51短语
已知文法G［S］，S是文法G的开始符号，αβδ是文法G的一个句型，即S*αAδ，若A+β，则β是句型αβδ相对于非终结符A的短语。
定义52直接短语
已知文法G［S］，S是文法G的开始符号，αβδ是文法G的一个句型，若有S*αAδ且Aβ，则β是句型αβδ相对于非终结符A的直接短语。
定义53句柄
一个句型的最左直接短语称为该句型的句柄，句柄是一个重要的概念。“移进归约”分析中的“可归约串”就是当前句型的句柄。如果文法是无二义性的，则规范句型的最右推导是唯一的，也就是说每步归约至多存在一个句柄。
下面通过例子说明短语、直接短语和句柄的概念以及句柄在“移进归约”分析中的作用。
【例52】设有文法G［S］: 
(1) S→aAcBe 
(2) A →b｜Ab 
(3) B →d
符号串abbcde的最右推导序列为SaAcBeaAcdeaAbcdeabbcde，分析每一步推导过程中各句型中的短语、直接短语和句柄。
下面根据短语、直接短语和句柄的定义进行分析，句型aAcBe中，aAcBe是相对S的短语、直接短语，也是句柄，这是因为S S，SaAcBe，且aAcBe是唯一直接短语，因此也是句柄。句型aAcde中，d是相对于B的直接短语，aAcde是相对于S的短语。同理可以分析剩余的两个句型。从定义出发寻找每个句型中的短语、直接短语和句柄不直观，容易遗漏，下面介绍一种简单直观的方法。
在自顶向下分析中，可通过分析树直观地了解从文法开始符号S(树根)到输入串(叶子结点)的推导过程。同样，在自底向上分析中，从输入串(叶子结点)出发，可通过对分析树逐层修剪直到根结点来了解归约过程，从而加深对规范归约、句柄等概念的理解。
下面对例52进行分析，句子abbcde的自底向上归约过程的分析树如图51所示。


图51句子abbcde的自底向上分析分析树的修剪过程



句子abbcde的最左子树是图51(a)中方框勾出的部分。这样子树的叶子结点b即为句子abbcde的句柄，将其剪掉(归约)后如图51(b)所示。图51(b)中方框勾出的部分为句型aAbcde的分析树中的最左子树，其叶子结点Ab为句柄，将其剪掉如图51(c)所示。此时，句型aAcde的句柄为d，将其剪掉得到图51(d)所示的分析树。此时，句型aAcBe的最左子树即为它自身的分析树，它的叶子结点aAcBe为句型aAcBe的句柄，将其剪掉，只剩下根结点S，即文法的开始符号，至此，完成了输入符号串abbcde的分析。

仍然对例52进行分析，可以看出，一个句型的分析树中最左边只有父子两代的子树的所有叶子的自左至右排列形成该句型的句柄。而句型的直接短语是仅有父子两代的子树的所有叶子结点自左至右排列起来所形成的符号串。句型的短语是分析树中子树的所有叶子结点从左到右的排列，形成相对于子树根的短语。
下面对例52每步归约对应的句型进行分析，通过分析树找出短语、直接短语和句柄。各句型的分析树中所有子树用方框标识，如图52所示。句子abbcde的子树是图52(a)中方框勾出的部分，共4棵子树，叶子结点b是相对于子树根A的短语和直接短语，bb是相对于子树根A的短语，因为从A出发经过两步而不是直接推导出bb，d是相对于子树根B的短语和直接短语。句子abbcde的分析树是其自身的子树，因此，abbcde是相对于子树根S的短语，b是分析树中最左那棵只有父子两代的子树的所有叶子自左至右排列形成的符号串，即句柄。句型aAbcde的分析树中包含3棵子树，其中Ab是相对于A的短语、直接短语，也是句柄。d是相对于B的短语和直接短语。aAbcde是相对于子树根S的短语，如图52(b)所示。句型aAcde包含两棵分析树，d和aAcde是短语，d也是直接短语和句柄，如图52(c)所示。句型aAcBe的短语、直接短语和句柄均为aAcBe，如图52(d)所示。


图52各句型的分析树及其子树


从上述例子可以看出，“移进归约”分析方法的关键问题是如何确定可归约串。一是判断栈顶字符串的可归约性，即判断处在栈顶的子串是否是可归约串； 二是确定使用文法中的哪一个规则进行归约，因为一个可归约串可以归约到多个不同的非终结符，即可归约串是不同的产生式的候选式。依照寻找可归约串的策略不同形成了不同的自底向上分析方法。
综上所述，各种自底向上分析方法的共同点是，都采用“移进归约”分析思想，不同点是确定可归约串的方法不同。下面将介绍几种典型的自底向上的分析方法。

5.2LR分析法

LR(k)分析法简称为LR分析法， 1965年由D.Knuth提出，是目前编译程序的语法分析中最常用且有效的自底向上的分析方法，这里的L指自左至右扫描输入符号串，R指分析过程是最右推导的逆过程。k表示根据分析栈当前已移进和归约出的全部文法符号，再向前查看k(k≥0)个输入符号，就可以确定分析器的动作是移进还是归约。LR分析的过程是规范推导的逆过程，因此是一种规范归约过程。采用LR方法构造的语法分析程序统称为LR分析器。
自顶向下的LL(1)分析对文法有较强的限制，而LR分析法对于文法的限制则少得多，因此也更通用，适用于绝大多数上下文无关语言分析，理论上也比较完善，另外这种方法还具有分析速度快、报错准确等优点。其缺点是对于高级程序语言构造一个LR分析器工作量相当大，手工实现困难。因此，需要借助贝尔实验室最早推出的语法分析自动生成器YACC辅助构造来自动生成。
下面重点介绍LR(k)当k≤1时分析器的基本构造原理和方法，其中LR(0)分析器是最简单的一种LR分析法，分析过程中不需要向后看任何符号，但是它对文法的限制较大，对绝大多数高级程序语言不适用，其他LR分析法都是在LR(0)的基础上进行完善的，特别地，当k=1时就能够满足绝大多数高级程序语言语法分析的需要。本节重点讨论LR(0)、SLR(1)、LR(1)和LALR(1)这4种分析器的构造。
1. LR分析器的逻辑结构和工作过程


在逻辑上，LR分析器的结构如图53所示。它有一个输入缓冲区，存放LR分析器处理的字符串，有一个下推分析栈，以及一个LR分析总控程序和LR分析表。



图53LR分析器逻辑结构示意图



(1) 分析栈。包括文法符号栈X［i］和相应的状态栈S［i］两部分(状态是指能识别活前缀的自动机状态,后面会详细说明)，LR分析器通过判断状态栈的栈顶元素和输入符号查询分析表确定下一步分析动作，对符号栈进行相应更新。文法符号栈存放在分析过程中移进或归约的文法符号，类似“移进归约”分析中符号栈的作用。状态栈的栈顶状态概括了栈中位于下边的全部信息，即无须关心状态栈中从开始状态到当前栈顶状态之间经历的一系列状态，仅用当前栈顶状态和输入符号就可以决定下一步的具体工作。换句话说，栈顶状态刻画了分析过程的“历史”情况和“展望”信息。初始化时，符号栈压入初始状态，文法符号栈压入输入串的左界符#。
(2) 总控程序。LR分析器在总控程序的控制下自左至右扫描输入串，根据当前分析栈顶所存放的文法符号状态及当前扫描读入的符号，查询LR分析表完成分析动作。
(3) 分析表。分析表是LR分析器的核心，它与具体文法有关，包括动作表(action)和状态转换表(goto)两部分，均使用二维数组表示，为总控程序提供决策依据。两个表的结构如表52和表53所示。


表52LR分析表的动作表


状态a1
a2
…
an


S0
action［S0, a1］
action［S0, a2］
…
action［S0, an］
S1
action［S1, a1］
action［S1, a2］
…
action［S1, an］
︙
︙
︙
︙
︙
Sn
action［Sn, a1］
action［Sn, a2］
…
action［Sn, an］





表53LR分析表的状态转换表


状态
X1
X2
…
Xn


S0
goto［S0, X1］
goto［S0, X2］
…
goto［S0, Xn］
S1
goto［S1, X1］
goto［S1, X2］
…
goto［S1, Xn］
︙
︙
︙
︙
︙
Sn
goto［Sn, X1］
goto［Sn, X2］
…
goto［Sn, Xn］


其中，状态转换表的元素goto ［Si, Xi］是一个状态，它表示根据状态栈栈顶状态Si和文法符号栈栈顶符号Xi(Xi∈VN)转移到下一个状态。例如，若有goto ［Si, Xi］= Sk，表示当前栈顶状态为Si和符号为Xi时转移到的下一个状态为Sk。
动作表的元素action［Si, ai］表示栈顶当前状态为Si,和当前输入符号为ai(ai∈VT)时完成的分析动作。具体的分析动作可分为4类： 移进、归约、接受或出错。
(1)  移进。
当action［Si, ai］= Sj时(这里Si和Sj中的i、j为状态编号，S表示shift，移进)，即当前栈顶状态为Si，当前缓冲区输入符号为ai时，将Sj移进状态栈，ai移进文法符号栈。“移进”分析动作表示句柄尚未在分析栈顶形成，正期待继续移进符号以形成句柄。
(2)  归约。
当action［Si, ai］= rj时(rj指按文法的第j个产生式进行归约，r表示reduce，归约)，即表示当前栈顶状态为Si，当前输入符号为ai时，用第j个产生式归约。设第j个产生式为A → β，字符串β的长度为r，分析动作为“归约”时，表明当前分析栈的栈顶已形成当前句型的句柄β，要立即进行归约。不仅要把文法符号栈栈顶包含r个符号的句柄β弹出，同时，状态栈也要弹出对应的r个状态，并把A移入文法符号栈，同时查询状态转换表goto［Sm, A］=Sj(Sm表示状态栈弹出r个状态后的栈顶状态)，把Sj移进状态栈，形成当前的新状态。
(3)  接受。
当action［Si, ai］='acc'时('acc'表示accept，接受)，表示当前输入串已经归约到文法的开始符号，即文法符号栈栈顶为开始符号S，输入缓冲区扫描到最后的结尾标记#时，分析成功，终止分析工作。
(4)  报错。
当action［Si, ai］='error' (也可用空白表示)时，分析动作出错，表示当前输入串有语法错误，调用相应的出错处理程序。


算法51给出了LR分析过程的具体描述。
算法51LR分析算法
输入： LR分析表和输入符号串
输出： 若输入符号串合法，输出自底向上构造的分析树，否则报错。
算法： 
(1) 初始化，将初始状态S0压入状态栈，输入串左界符#压入文法符号栈。
(2) 循环执行下面的步骤，直至分析成功或报错。
(3) 根据当前状态栈栈顶状态Si以及当前输入符号ai查询动作表。
若action［Si, ai］= Sj，将Sj移进状态栈，ai移进文法符号栈。
若action［Si, ai］= rj，用第j个产生式归约，归约过程如前面所述。
若action［Si, ai］='acc'，分析成功。若action［Si, ai］='error'，进行出错处理。
下面通过具体例子介绍LR分析器的工作过程。
【例53】设有文法G［S ］:
(1) S→L,S  
(2) S→L
(3) L→x
(4) L→y
已知文法G［S ］的LR分析表如表54所示。以输入串“x，y，x”为例，给出LR分析器的分析过程。



表54文法G［S］的LR分析表


状态

action表
goto表

x
y
,
#
S
L


0
S3
S4


1
2
1



acc


2


S5
r2


3


r3
r3


4


r4
r4


5
S3
S4


6
2
6



r1





输入串“x，y，x”的LR分析过程如表55所示。



表55输入串“x,y,x”的LR分析过程




步骤
栈中状态
栈中符号
输入符号串
分 析 动 作


1
0
#
x,y,x#
S3移进“x”，状态转到3(3入栈)
2
03
#x
,y,x#
r3(用第三个产生式L→x归约)
3
02
#L
,y,x#
S5移进“，”，状态转到5(5入栈)
4
025
#L，
y,x#
S4移进“y”，状态转到4(4入栈)
5
0254
#L,y
,x#
r4(用第四个产生式L→y归约)
6
0252
#L,L
,x#
S5移进“，”，状态转到5(5入栈)
7
02525
#L,L,
x#
S3移进“x”，状态转到3(3入栈)
8
025253
#L,L,x
#
r3(用第三个产生式L→x归约)
9
025252
#L,L,L
#
r2(用第二个产生式S→L归约)
10
025256
#L,L,S
#
r1(用第一个产生式S→L ,S归约)
11
0256
#L,S
#
r1(用第一个产生式S→L ,S归约)
12
01
#S
#
acc



从表55所示的分析过程可看出，根据归约的顺序依次归约的句柄是“x”“y”“x”“L”“L，S”“L,S”。刚好构成了最右推导(规范推导)的逆过程，即上述分析过程每一行的符号栈的文法符号和输入缓冲区的所有符号加在一起，刚好构成文法的一个右句型，因此，LR的分析过程是(最左归约)规范归约的过程。
对于例53，本书预先给出了LR分析表，实际上，LR分析法的关键恰恰是分析表的构造。对于不同的文法，LR分析算法都是不变的，唯一的区别是LR分析表构造的方法不同。
2. LR文法

定义54LR文法

一个文法G，若构造出的LR分析表不含多重定义，即它的每一入口的动作都是唯一确定的，则文法G称为LR文法。
定义55LR(k)文法
一个文法G，若使用LR方法进行分析，分析过程中的每一步最多向前查看k个输入符号，就能唯一确定当前分析动作，即可以构造出无多重定义的LR(k)分析表，则称文法G为LR(k)文法。
LR(k)是从分析过程需要利用输入字符数目的角度来定义的。对于当前流行的大多数程序设计语言来说，k=1就可以满足它们LR分析的需要。根据定义不难推出，任何LR(k)文法都是无二义性的文法，任何二义性文法都不是LR(k)文法。对于二义性文法而言，可通过对二义性文法进行修改或者施加一些限制来克服分析表中出现的冲突动作，从而使LR分析适用于这些二义性文法。
当k=0时对应的LR(0)分析是最简单的一种LR分析法，仅适用于LR(0)文法。LR(0)分析仅根据状态栈当前状态即可决定当前符号栈是否已构成句柄，而不需要查看下一个输入符号，即只根据状态就可以确定是否归约。值得注意的是，这里的向前看一个符号的作用主要是确定是否归约，因为移进动作总是需要向前看一个符号，也就是说，每个LR(k)分析法确定移进动作时肯定需要向前看一个符号，但是确定是否归约时就有区别了，LR(0)不需要向前看任何符号，
SLR(1)找出所有跟在句柄后可能的第一个终结符，LR(1)找出规范句型中跟在句柄之后可能的第一个终结符。
各种LR分析的实现思想和分析过程是相同的，区别仅在于LR分析表中确定归约动作的方法不同，下面从LR(0)分析作为出发点，逐步展开对LR分析的讨论。首先引入一些重要的概念、术语和定义。
定义56规范句型的活前缀
规范句型的一个前缀若不含句柄之后的任何符号，则称为该句型的一个活前缀。活前缀的形式化定义为： 设有文法G［S］，S αAw αβw是文法G的一个规范推导(α, β∈V+,w∈V*T,A∈VN)，若γ是符号串αβ的前缀，则称γ是G的一个活前缀，如果符号串γ是含句柄的活前缀，则称γ是G的可归前缀(最长的活前缀)。
需要注意的是，活前缀所在句型一定是规范句型。从例53中对输入串“x,y,x”的分析过程可以看出，在分析的每一步，若将符号栈中的全部文法符号与扫描剩余的输入串连接起来，刚好构成语法的一个规范句型。符号栈中全部文法符号刚好是某一规范句型的活前缀。



例如，如表56所示，句子“x,y,x”分析的第3步，符号栈中的文法符号串是“L”，剩余字符串为“,y,x”，连接在一起刚好形成文法一个规范句型“L,y,x”。该句型的句柄为“y”，栈中符号串为“L”，则此句型的活前缀为“ε”“L”“L,”“L，y”，最长活前缀“L,y”恰好含有句柄“y”。但是在第3步还没有把“y”移入符号栈，因此，需要把输入符号串的字符继续逐一移入符号栈，在第5步句柄“y”出现在栈顶时，把“y”归约为“L”。从这个例子可以看出，符号栈中的符号串是当前规范句型的活前缀，如果还没有包括句柄，则继续移入符号，当把句柄完全移入后产生了最长的活前缀，然后紧接着进行归约。因此，我们最关心的是最长活前缀，因为最长活前缀刚好包含句柄。不难看出，活前缀的特点是它不含句柄之右的任何符号。


表56规范句型的活前缀


步骤
栈中状态
栈中符号
输入符号串
活前缀
最长活前缀


1
0
#
x,y,x#
εx
x
2
03
#x
,y,x#
εx
x
3
02
#L
,y,x#
εLL,L,y
L,y
4
025
#L，
y,x#
εLL,L,y
L,y
5
0254
#L,y
,x#
εLL,L,y
L,y
6
0252
#L,L
,x#
εLL,L,LL,L,L,L,x
L,L,x
7
02525
#L,L,
x#
εLL,L,LL,L,L,L,x
L,L,x
8
025253
#L,L,x
#
εLL,L,LL,L,L,L,x
L,L,x
9
025252
#L,L,L
#
εLL,L,LL,L,L,L,L
L,L,L
10
025256
#L,L,S
#
εLL,L,LL,L,L,L,S
L,L,S
11
0256
#L,S
#
εLL,L,S
L,S
12
01
#S
#


上例也说明，一个LR分析器的“移进归约”工作过程其实是符号栈逐步产生文法G的规范句型的活前缀的过程。当生成最长活前缀时，此时分析栈顶部形成句柄，可立即归约。
这就为确定分析动作提供了依据，若能找出文法所有的活前缀，并且确定当前分析句型中最长的活前缀，那么就可以在活前缀生长到最长时归约，在其余状态时移进或报错。
5.2.1LR(0)
如前所述，找出文法所有的活前缀并确定最长的活前缀是确定分析动作的关键，为此，首先分析活前缀与句柄的关系，然后提出识别文法所有活前缀的方法。
在一个规范句型的活前缀中，决不会含有句柄右边的任何符号。因此，活前缀与句柄间的关系有3种情况： 
(1) 活前缀中不包含句柄的任何符号。
(2) 活前缀中只含有句柄的一部分符号。
(3) 活前缀中已含有句柄的全部符号，即最长活前缀，通常也称为可归前缀。
第一种情况表明，句柄中的文法符号没有一个出现在栈顶，期望从输入符号串中移进某一产生式A→β中的β符号串。第二种情况意味着形如产生式A→ β1β2的子串β1已出现在栈顶，下一步准备从输入串中移进由β2推出的符号串。第三种情况表明，某一产生式A→ β的右部β已完全出现在栈顶，下一步分析动作应是用该产生式进行归约。为了刻画分析过程中文法的每一个产生式的右部符号已有多大一部分被识别(出现在栈顶)，很自然地可以在产生式的右部加上一个圆点指示位置。 
(1) A→ ·β表示当前句型活前缀中不包含句柄β的任何符号。
(2) A→ β1·β2表示当前句型活前缀中只含有句柄的一部分符号β1。
(3) A→ β·表示当前句型活前缀中已含有句柄的全部符号。
因此，需要定义LR(0)项目来描述这些情况。
定义57LR(0)项目

为了描述分析状态，在文法G的每个产生式的右部符号串的任何位置上添加一个圆点所构成的每个产生式称为LR(0)项目。
特别地，若产生式形为A→ε，则其LR(0)项目为A→· 。
【例54】已知文法G(S):
S→aAcBe
A→Ab|b
B→d
找出其所有LR(0)项目。
G(S)的LR(0)项目有： 
S→·aAcBe，S→a·AcBe，S→aA·cBe， S→aAc·Be，S→aAcB·e，S→aAcBe·,
A→ ·Ab，A→ A·b，A→ Ab·,A→·b,A→b·,
B→ ·d，B→d ·

从直观意义上讲，一个LR(0)项目对应一种分析状态，即在分析过程中分析到了圆点所在的位置，圆点可看成是符号栈栈顶与输入串当前输入符号的分界点，圆点左边为已进入符号栈的部分，右边是当前需要分析的符号串。
根据LR(0)项目的定义，圆点所在不同位置反映了分析栈的不同情况。因此根据不同的位置可以把LR(0)项目分为4类，表示4种不同状态。
(1) 移进项目。
形式： A→α·aβ(a∈VT)
这类LR(0)项目表示α出现在符号栈中，活前缀包含句柄的部分符号，为构成可归前缀，需继续将圆点后的终结符号a移进符号栈。因此这种形式的LR(0)项目称为移进项目，它对应的状态为移进状态。
(2) 待约项目。
形式： A→α·Bβ(B∈VN)
这类LR(0)项目表示α出现在符号栈中，活前缀包含句柄的部分符号，为构成可归前缀，期待着把当前输入字符串中的相应内容先归约到B。因此这种形式的LR(0)项目称为待约项目，它对应的状态为待约状态。
(3) 归约项目。
形式： A→α·
这类LR(0)项目表示句柄α刚好出现在符号栈栈顶，活前缀刚好包含句柄，即当前符号栈中的符号串正好为可归前缀，应按A→α进行归约。因此这种形式的LR(0)项目称为归约项目，它对应的状态为归约状态。
(4) 接受项目。
对任何文法G，在G中加进一个新的符号S′和一个产生式S′→S，并以S′代替S作为文法的开始符号，这样得到的一个与G等价的文法G′称为G的拓广文法。对于拓广文法G［S′］,有项目S′→S ·，它是一个特殊的归约项目，我们称它为接受项目，它所对应的状态为接受状态。引入拓广文法的目的在于，拓广文法G′的接受项目是唯一的，即S′→S·。下面举一个例子，例如，已知文法G(S): S→aS|b，若分析句子ab，当把b归约为S时，好像是归约到了文法的开始符号S，整个分析就结束了，但实际上还需要进一步归约，因此，引入拓广文法就可以避免这一问题。
对例54的文法进行拓广，引入一个新的开始符号S′，则拓广后的文法为G(S′): S′→S，S→aAcBe，A→Ab|b，B→d，对其所有LR(0)项目进行编号： 
(1) S→·S′(2) S→ S′·(3) S→·aAcBe(4) S→a·AcBe(5) S→aA·cBe
(6) S→aAc·Be(7) S→aAcB·e(8) S→aAcBe·(9) A→·Ab(10) A→ A·b
(11) A→ Ab·(12) B→ ·d(13) B→d ·(14) A→·b(15) A→b·

其中(2)、(8)、(11)、(13)、(15)为归约项目，(2)为接受项目，(1)、(4)、(6)、(9)为待约项目，(3)、(5)、(7)、(10)、(12)、(14)为移进项目。
前面已经提到，找出文法所有的活前缀并确定最长的活前缀是确定分析动作的关键，在给出LR(0)项目的定义和分类之后，可以定义文法的所有LR(0)项目，每个项目对应一个分析状态。因此，利用这些LR(0)项目，可以构造能识别文法所有可归前缀的有限自动机。具体地，构造有限自动机可以从初始LR(0)项目出发，通过引入闭包运算和GO转移函数来实现。
定义58LR(0)项目集的闭包运算

假定I是文法G的任一LR(0)项目集，I的项目集闭包closure(I)通过以下步骤生成： 
(1) I中的每一个LR(0)项目皆属于closure(I)。
(2) 若项目A → α·Bβ∈closure(I)(B∈VN)，则把文法G中形如B→η对应的LR(0)项目B → ·η加进closure( I )中。
(3) 重复执行(2)直到closure(I)不再增大为止。
LR(0)项目集的闭包运算的含义是把项目集当中所有形如A → α·Bβ和B → ·η的LR(0)项目放在一起，因为A → α·Bβ和B → ·η对应的分析状态是相同的，A → α·Bβ表示将要开始识别B，马上要进行分析，B → ·η也表示还没有分析B能推导出的η，两个LR(0)项目均表示当前要分析B，因此它们表示同一种状态，使用闭包运算来合并这些相同含义的状态。
【例55】已知文法G(S):

S→ABC
A→Aa|a
B→b|bB
C→c


假设I1={S→·ABC}，I2={S→A·BC}求I1和I2的LR(0)项目集闭包。
根据定义不难求出： 

closure(I1)={ S→·ABC，A→·Aa，A→·a }
closure(I2)={ S→A·BC，B→·bB，B→·b }

定义59GO转移函数

若I是G的一个LR(0)项目集, X ∈{VT∪VN}，则

GO(I, X)=closure(J)，J={A→αX·β| A→α·Xβ ∈ I}

GO(I, X)称为转移函数，项目A→αX·β称为A→α·Xβ的后继。 
转移函数用来刻画不同LR(0)项目集状态之间的关系，或者说从一个状态如何转移到下一个状态。例如，例55中的I1和I2之间的关系可以使用GO转移函数表示： 

GO(I1, B)=closure (I2)=closure({ S→A·BC})={ S→A·BC，B→·bB，B→·b }


结合LR(0)项目集闭包的定义，可以很好地理解这两个定义的作用，即LR(0)项目集闭包首先把表示相同状态的LR(0)项目合并在一起形成LR(0)项目集，然后利用转移函数建立不同LR(0)项目集之间的跳转关系，从而形成识别文法所有可归前缀的有限自动机。
定义510LR(0)项目集规范族

识别文法G可归前缀的DFA中的所有LR(0)项目集的全体称为文法G的LR(0)项目集规范族。
根据定义510，构造出了识别文法所有可归前缀的DFA，也就构造出了LR(0)项目集规范族。下面给出LR(0)项目集规范族的构造算法。

算法52文法G［S］的LR(0)项目集规范族的构造算法
输入： 文法G［S］的拓广文法G′
输出： 文法G［S］的LR(0)项目集规范族C
算法： 
/*通过加入S′→S对文法进行拓广形成拓广文法G′，从而使接受状态易于识别*/
BEGIN
C={closure(S′ → ·S) };
DO
FORI∈C和X ∈{VT ∪VN} 
把go(I,X)加入到C中
WHILE C不再增大
END;

算法52从文法的初始LR(0)项目S′ → ·S开始求其闭包I，再通过GO函数求其所有的后继项目集，然后逐步扩展，且将其各项目集连成一个DFA，最终求得的所有项目集C即为文法G′的LR(0)项目集规范族。
需要注意的是，用前述方法所构造的LR(0)项目集中可能包括多个LR(0)项目，每个LR(0)项目表征了在分析过程中一个特定的分析动作，因此每个项目集中的各项目应是相容的，即没有冲突的。下面从项目集相容的角度出发，对LR(0)文法加以定义。
定义511LR(0)文法
若一个文法G的识别可归前缀的DFA的每个状态对应的项目集均不存在以下情况： 
(1) 既含移进项目又含归约项目。
(2) 含有多个归约项目。

则称项目集是相容的，称G是一个LR(0)文法。
项目集是相容的也称为项目集是没有冲突的，而不相容的项目集一定包含“移进归约”冲突或者“归约归约”冲突。根据定义511可以得出： 对任何一个LR(0)文法对应的LR(0)分析表一定不含多重定义。
至此，已经完成了所有构造LR(0)分析表的准备工作，当识别其所有可归前缀的DFA构造出来以后，可以方便地构造出LR(0)分析表及相应的LR分析器，因为从DFA中可以清楚地确定每个状态的含义，即确定是移进、归约、接受或者报错。所以LR分析器实质是一个带栈的确定的有限自动机，也称为下推自动机(关于下推自动机的定义不再介绍，读者可以参考可计算理论的相关内容)。
下面给出从识别可归前缀的DFA构造LR(0)分析表的算法。
算法53利用识别可归前缀的DFA构造LR(0)分析表
输入： 文法G； 文法G的识别可归前缀的DFA
输出： 文法G的LR(0)分析表
算法： 
(1) 对于A→α·xβ∈Si ，GO(Si,x)=Sj ： 若x∈VT ，则置action［Si,x］=Sj； 若x∈VN ，则置goto［Si,x］=j； 
(2) 对于A→α· ∈Si ，若A→α是G中第k个产生式，则对所有输入符号x∈VT(包括#)，均置action［Si,x］=rk。
(3) 若S′→S·∈Si ，则置action［Si,#］=acc(#表示输入串右界符)。
(4) 其他情况均置错。 
算法53构造的分析表称为LR(0)分析表，使用LR(0)分析表的LR分析器称为LR(0)分析器。下面举例说明LR(0)分析表的构造过程。
【例56】已知文法G［E］： 
E→aA|bB
A→cA|d
B→cB|d
构造该文法的LR(0)分析表。
首先对文法进行拓广，并对产生式进行编号： 

(0) S′→E(1) E→aA(2) E→bB(3) A→cA(4) A→d(5) B→cB(6) B→d 

根据算法52，从S′→·E出发，构造识别文法所有可归前缀的DFA，如图54所示。



图54识别文法G［E］所有可归前缀的DFA


再根据算法53，构造文法G［E］的LR(0)分析表如表57所示。



表57文法G［E］的LR(0)分析表


状态

action
goto
a
b
c
d
#
E
A
B


0
S2
S3



1


1




acc



2


S4
S10


6

3


S5
S11



7
4


S4
S10


8

5


S5
S11



9
6
r1
r1
r1
r1
r1



7
r2
r2
r2
r2
r2



8
r3
r3
r3
r3
r3



9
r5
r5
r5
r5
r5



10
r4
r4
r4
r4
r4



11
r6
r6
r6
r6
r6





下面以句子acd为例，对表57进行说明。DFA初始状态0经过终结符a到达状态2，所以在action［0,a］位置填写S2，表示当读入a时，分析器的动作为移进，把a移进符号栈，状态2压入状态栈。接着从状态2出发，经过终结符c到达状态4，所以在action［2,c］位置填写S4，表示当读入c时，继续移进，c移进符号栈，状态4压入状态栈。同理，在action［4,d］位置填写S10，状态10中对应归约项目A→d· ，其编号为4，所以在action表中状态10所在的行填入r4，说明栈顶出现了句柄，需要进行归约，因此，d从符号栈弹出，10从状态栈弹出，然后A入栈。此时说明A已经产生，当前状态栈栈顶状态为4，说明状态应该从状态4转到识别出A之后到达的状态8，因此，在goto表的goto［4,A］填入状态8。分析表其他位置的元素也都是根据DFA进行构造。特别地，action［1,#］=acc，这是因为状态1对应LR(0)项目S′→E·，说明要把E归约为S′，如果缓冲区当前扫描到输入串右界符#，说明句子合法，分析动作为接受。
5.2.2SLR(1)
LR(0)文法是一类非常简单的文法，它的项目集规范族中的每一项目集均不包含冲突，但是对于高级程序设计语言来说，构造出的项目集中往往包括“移进归约”或者“归约归约”冲突，因此LR(0)分析的适用性受到很大的限制。下面通过例子进行说明。
【例57】设有文法G［S］:
S→rD
D→D,i|i

试构造文法G的LR(0)分析表。
首先将文法进行拓广，并对产生式进行编号： 
(0) S′→S(1) S→rD(2) D→D,i(3) D→i
构造项目集规范族和识别文法可归前缀的DFA,如图55所示。



图55识别文法G［S］所有可归前缀的DFA


从图55中可看到，在项目集S3中，既有移进项目(D→D·,i)，又有规约项目(S→rD·)，按照LR(0)分析表的构造方法，在分析表中必有元素action［3,，］={S5，r1}，出现多重定义,如表58所示。这说明当分析到状态3时，下一个输入符号如果是“，”，或者将“，”移进符号栈，或者按文法的第一个产生式S→rD进行归约。于是出现了“移进归约”冲突。其他项目集中没有出现冲突，所以要解决含有冲突动作的项目集S3的问题，就可以使用LR分析方法。下面首先对LR(0)分析表构造算法进行分析，找出不足，然后稍加修改，使其仍能适用于出现冲突的文法。其解决方法就是下面要研究的SLR(1)分析法(即简单的LR(1)分析法)。




表58文法G［S］的LR(0)分析表


状态

action
goto

r
,
i
#
S
D



0
S2



1

1



acc


2


S4


3
3
r1
r1,S5
r1
r1


4
r3
r3
r3
r3


5


S6



6
r2
r2
r2
r2



LR(0)分析表构造算法的问题在于，对于A→α· ∈Si ，若A→α是G中第k个产生式，则对所有输入符号x∈VT(包括#)，均置action［Si,x］=rk ，也就是说，不管当前输入符号是什么， action表中相应于状态Si的那一行的元素都指定为rk。这是不合理的，因为只有当输入缓冲区中出现了紧跟在A之后的终结符号时才应该归约，因此，LR(0)分析法并没有进一步确定哪些符号紧跟在A之后，所以有可能即使出现了错误的句子，仍然进行归约。SLR(1)分析法的改进就是，对于归约项目A→α·，要确定紧跟在A之后的终结符号，即计算FOLLOW(A)。 
下面对这一处理过程进行描述，假定一个LR(0)的规范族中存在如下含有冲突的项目集： 

Si={x→α·bβ,A→γ·,B→δ·,α,β,γ,δ∈V*,b∈VT}


显然，项目集中含有一个移进项目和两个归约项目。出现了“移进归约”和“归约归约”冲突。为解决冲突，对于归约项目A→γ·和B→δ· ，分别求FOLLOW(A)和FOLLOW(B) 。若FOLLOW(A)、FOLLOW(B)和{b}互不相交，则冲突可以解决，即对下一个输入符号a有： 
(1) 当a=b时，置action［Si,b］=“移进”。
(2) 当a∈FOLLOW(A)时，置action［Si,a］={按产生式A→γ归约}。
(3) 当a∈FOLLOW(B)时，置action［Si,a］={按产生式B→δ归约}。
(4) 当a不属于上述3种情况时，置action［Si,a］=“error”。
上述方法仅对出现冲突的数据集进行处理，在冲突的地方简单地向前看一个符号，因此称为简单的LR(1)分析法，即SLR(1)方法。
下面给出从识别可归前缀的DFA构造SLR(1)分析表的算法。
算法54利用识别可归前缀的DFA构造SLR(1)分析表
输入： 文法G； 文法G的识别可归前缀的DFA
输出： 文法G的SLR(1)分析表
算法： 
(1) 对于A→α·xβ∈Si，GO(Si,x)=Sj： 若x∈VT ，则置action［Si,x］=Sj； 若x∈VN ，则置goto［Si,x］=j。
(2) 对于归约项目A→α·∈Si，若A→α为文法的第j个产生式，则对于任意输入符号a,若a∈FOLLOW(A),则置action［Si,a］=rj。
(3) 若S′→S·∈Si ，则置action［Si,#］=acc (#表示输入串右界符)。
(4) 其他情况均置错。
比较LR(0)和SLR(1)分析表的构造算法可以看出，后者仅仅对于归约项目A→α·进行了进一步处理，计算FOLLOW(A)。具体地，对于例57，需要计算FOLLOW(S)，FOLLOW(S)={#}，与{，}不相交，所以冲突可以解决。构造出的SLR(1)分析表如表59所示。



表59文法G［S］的SLR(1)分析表


状态

action
goto

r
,
i
#
S
D


0
S2



1

1



acc


2


S4


3
3

S5

r1


4
r3
r3
r3
r3


5


S6



6
r2
r2
r2
r2



从表59可以看出，SLR(1)分析方法比LR(0)分析方法更确定，报错更及时。例如，在状态3下，下一个输入符号如果是r或者i，则直接报错，而LR(0)分析表(表58)中对应的动作却是归约，因此，错误可能在若干步之后才会发现。
定义512SLR(1)文法
文法G按照SLR(1)方法构造的分析表称为SLR(1)分析表。如果每个入口不含多重定义，则文法G称为SLR(1)文法。使用SLR(1)分析表的LR分析器称为SLR(1)分析器。
下面进一步讨论LR(0)文法与SLR(1)文法之间的关系。
【例58】已知文法G［E］： 

E→aA|bB
A→cA|d
B→cB|d
构造该文法的SLR(1)分析表。
首先对文法进行拓广，并对产生式进行编号： 
(0) S′→E(1) E→aA(2) E→bB(3) A→cA(4) A→d(5) B→cB(6) B→d 
根据算法52，从S′→·E出发，构造识别文法所有可归前缀的DFA，如图56所示。


图56识别文法G［E］所有可归前缀的DFA



状态I6、I7、 I8 、I9 、I10和I11中含有归约项目，计算FOLLOW(E)、FOLLOW(A)
和FOLLOW(B)，FOLLOW(E)=FOLLOW(A)=FOLLOW(B)={#}。

再根据算法54，构造文法G［E］的SLR(1)分析表，如表510所示。对比文法的LR(0)分析表(表57)可以看出，文法G［E］的SLR(1)分析表删除了一些归约动作，说明SLR(1)分析报错更及时。同时，这个例子也说明，一个文法如果是LR(0)文法，那么也一定是SLR(1)文法； 反之，一个文法是SLR(1)文法，则不一定是LR(0)文法。



表510文法G［E］的SLR(1)分析表


状态

action
goto

a
b
c
d
#
E
A
B


0
S2
S3



1


1




acc



2


S4
S10


6

3


S5
S11



7
4


S4
S10


8

5


S5
S11



9


6




r1



7




r2



8




r3



9




r5



10




r4



11




r6



5.2.3LR(1)
SLR(1)分析法是一种较为实用的方法。大多数程序设计语言基本上都可以用SLR(1)文法来描述。在SLR(1)分析法中，对于某状态Si，其项目集若不相容时，可根据SLR(1)分析表的构造规则来解决冲突。然而，也确实存在许多无二义的文法，其项目集中的“移进归约”和“归约归约”冲突不能由SLR(1)分析法解决，下面举例说明。
【例59】有文法G［S′］： 
S′→S
S→A=B
S→B
A→*B
A→id
B→A
判断该文法是否为SLR（1）文法。
首先从S′→·S出发，构造识别文法所有可归前缀的DFA，如图57所示。


图57识别文法G［S′］所有可归前缀的DFA

其中，状态S2出现了移进归约冲突，根据SLR(1)分析法计算FOLLOW(B)，FOLLOW(B)={=，#}，与状态S2中的移进符号{=}相交不为空集，冲突仍然没有解决，这说明SLR(1)方法存在不足之处。
下面分析SLR(1)方法存在的问题。SLR(1)分析法对于归约项目A→α·，要确定紧跟在A之后的终结符号，即计算FOLLOW(A)。通俗地讲，就是要找出所有句型中紧跟在A之后的终结符号，因此，这就带来一个问题，分析过程中的一个状态往往只对应一个句型，我们关心的是在当前句型下紧跟在A之后的终结符号，而不是所有句型中紧跟在A之后的终结符号。例如，分析一下状态S2，S2是由初始状态S0识别了A到达的，而S0中有两个句型识别A之后到达S2。S2中的S→A·=B对应的是句型SA=B，S2中的B→A·对应句型S=>A而不是句型SA=B。SLR(1)方法的含义是在S2状态下计算FOLLOW(B)，既考虑句型A=B中紧跟在A之后的=，又考虑句型A中紧跟在B之后的=,也就是说SLR(1)方法仍然不够精确，没有细化到当前状态对应的句型。以上的分析说明，我们不仅关心紧跟在A之后的终结符号，更关心对当前状态有效的句型中紧跟在A之后的终结符号，因此，需要进一步确定FOLLOW(A)中哪些终结符号对当前状态的具体句型有效。对状态S2有效的句型是SA，因此在状态S2下，只有下一个输入符号出现了#才进行归约，如果有效句型是SA=B,出现=时则移进，冲突可以解决。因此，通过把LR(0)项目与有效的句型绑定，就可以设计出比SLR(1)更有效的LR分析方法。
通过以上分析可知，问题的关键点在于如何确定当前句型中紧跟在A之后的终结符号。对于当前分析状态Si:S→α·Aw，A→·γ(假定w推导不出ε)，把FIRST(w)作为用产生式A→γ进行归约的搜索符，用于替代SLR(1)分析法中的FOLLOW(A)，并把搜索符号的集合放在项目的后面(［A→.γ,a］ a∈FIRST(w))。这种处理方法称为LR(1)分析法。
定义513LR(1)项目

在LR(0)项目中放置一个向前搜索的符号a，成为［A→α·β,a］。A→α·β是一个LR(0)项目，a是一个终结符号，这种形式的项目称为LR(1)项目，a称为向前搜索符。 
向前搜索符仅对归约项目［A→α·，a］有意义，当前输入符号是a时，才能用A→α进行归约。
定义514LR(1)项目对活前缀的有效性
若文法G的一个LR(1)项目［A→α·β,a］对活前缀γ是有效的，当且仅当存在规范推导
S δAw δαβw (w∈V*T,A∈VN)，γ= δα，a∈FIRST(w)或a='#'(w=ε)。
定义514的本质在于把A→α·β与句型δAw对应起来，或者说进行绑定，这样就可以确定当前分析状态下的搜索符，即当前句型紧跟在A之后的终结符号。因此，必须准确计算出每个LR(1)项目的向前搜索符，即构造出的每一个LR(1)项目对活前缀(即对应一个句型)都必须是有效的。例59中，S0状态中的B→·A对应的是句型S=>A，所以称［B→·A，#］对活前缀A是有效的，换句话说，［B→·A，#］对句型A也是有效的。因此，定义514的目的是更好地增强LR分析的处理冲突的能力。
与LR(0)分析的情况相类似，识别文法全部可归前缀的DFA的每一个状态也用一个LR(1)项目集来表示，故构造LR(1)项目集规范族的方法和构造LR(0)项目集规范族的方法在本质上是一样的，同样需要用到函数closure(I)和GO(I,X)。
定义515LR(1)项目集的闭包运算

假定I是文法G的任一LR(1)项目集，I的项目集闭包closure(I)通过以下步骤生成： 
(1) I中的每一个LR(1)项目皆属于closure(I)。
(2) 若项目［A → α·Bβ,a］ ∈closure(I)(B∈VN)，则把文法G中形如B→η对应的LR(1)项目［B→·η，b］ (b∈FIRST(βa))加进closure(I)中。
(3) 重复执行(2)直到closure(I)不再增大为止。

定义516GO转移函数
若I是G的一个LR(1)项目集,X∈{VT∪VN}，则

GO(I, X)=closure(J)

其中，J={［A→ α X·β,a］|当［A→α·Xβ,a］∈I}，GO(I, X)称为转移函数。项目A→αX·β称为A→α·Xβ的后继。 
定义517LR(1)项目集规范族

识别文法G可归前缀的DFA中的所有LR(1)项目集的全体称为文法G的LR(1)项目集规范族。
下面给出LR(1)项目集规范族的构造算法。

算法55文法G［S］的LR(1)项目集规范族的构造算法
输入： 文法G［S］的拓广文法G′
输出： 文法G［S］的LR(1)项目集规范族C
算法： 
/*通过加入S′→S对文法进行拓广形成拓广文法G′，从而使接受状态易于识别*/
BEGIN
C={closure({［S′ → ·S，#］}) };
DO
FORI∈C和X ∈{VT ∪VN} 
把go(I,X)加入到C中
WHILE C不再增大
END;

【例510】有文法G［S′］： 
（0） S′→S
（1） S→A=B
（2） S→B
（3） A→*B
（4） A→id
（5） B→A
构造该文法的LR(1)项目集规范族。
根据算法55，从［S′ → ·S，#］出发，构造初始项目集，然后逐步扩展生成文法的LR(1)项目集规范族，如图58所示。


图58文法G［S′］的LR(1)项目集规范族和识别可归前缀的DFA


对于给定文法，当LR(1)项目集规范族和识别可归前缀的DFA构造出来以后，可以方便地构造出文法的LR(1)分析表。
算法56LR(1)分析表的构造

输入： 文法G的LR(1)项目集规范族和识别可归前缀的DFA
输出： 文法G的LR(1)分析表
算法： 
(1) 对于［A→α·xβ,b］∈Si ，GO(Si,x)=Sj : 若x∈VT ，则置action［Si,x］=Sj； 若x∈VN，则置goto［Si,x］=j。
(2) 对于［A→α·,a］∈Si ，若A→α是G中第k个产生式，则置action［Si,a］=rk。
(3) 若［S′→S·,#］∈Si ，则置action［Si,#］=acc (#表示输入串右界符)。
(4) 其他情况均置错。 
算法56构造的分析表称为LR(1)分析表，若一个文法构造出的LR(1)分析表不含多重定义，则该文法称为LR(1)文法，使用LR(1)分析表的LR分析器称为LR(1)分析器。下面举例说明LR(1)分析表的构造过程。

【例511】有文法G［S′］：  
(0) S′→S
(1) S→A=B
(2) S→B
(3) A→*B
(4) A→id
(5) B→A
构造该文法的LR(1)分析表。
在图58的基础上，根据算法56，构造文法G［S′］的LR(1)分析表，如表511所示。与LR(0)和SLR(1)相比较，构造LR(1)分析表最大的不同在于算法的第二步，即利用归约项目中的向前搜索符就可以准确确定归约动作，也就是说，LR(1)分析法中，每一个LR(1)项目都对应向前看一个符号，向前搜索符虽然对非归约项目暂时没有作用，但它是为后面出现的归约项目提前做准备的，因此每一步都向前看一个符号，而不是出现冲突了才向前看一个符号。


表511文法G［S′］的LR(1)分析表



状态
actiongoto

=*id#SAB

0S4S5123
1acc
2S6r5
3r2
4S4S587
5r4r4
6S11S12109
7r3r3
8r5r5
9r1
10r5
11S11S121013
12r4
13r3


前面已经说明，一个文法如果是LR(0)文法，那么也一定是SLR(1)文法，这是因为SLR(1)分析比LR(0)分析多计算了归约项目A→α·的FOLLOW(A)集合，相当于删除了LR(0)分析表中的一些归约动作。同理，一个文法如果是SLR(1)文法，那么也一定是LR(1)
文法，这是因为LR(1)分析进一步确定了FOLLOW(A)中的对当前分析句型有效的终结符号，即向前搜索符。因此，LR(1)分析进一步确定了在FOLLOW(A)中哪些终结符号有效，哪些无效，即LR(1)分析表进一步删除了SLR(1)分析表中的一些归约动作。若一个文法的SLR(1)分析表中没有多重定义，则该文法的LR(1)分析表更不会有多重定义。
3种LR分析法的最大的区别就在于分析表的构造不同，是一个逐步确定化和细化的过程，它们之间的关系如表512所示。



表5123种LR分析法的对比


LR分析法
优点
缺点


LR(0)分析法
无任何冲突，所以分析表构造最简单
所有终结符号均归约，查错慢，仅限于LR(0)文法
SLR(1)分析法
对FOLLOW(A)中的终结符号才归约，查错较快
没有考虑当前分析的句型，查错较LR(1)慢，仅限于SLR(1)文法

LR(1)分析法
对FOLLOW(A)中的对当前分析句型有效的终结符号才归约，每一步都求出这种终结符号，查错最快
构造LR(1)项目集规范族较复杂，识别可归前缀的DFA状态数较多

5.2.4LALR(1)

前面已经提到，LR(1)分析法通过向前搜索符确切地指出归约时FOLLOW集中哪些终结符号有效，但向前搜索符的引入会带来状态数的增加。例如，假设SLR(1)中存在一个项目集［A→α ·］ ，则在LR(1)中可能对应两个项目集［A→α ·,a］和［A→α ·,b］，优点是使分析更加确定，缺点是增加了状态。若对高级程序构造对应的LR(1)分析表，一般是比较庞大的，在机器的存储方面会遇到问题，从而影响到它的应用和推广。
LALR(1)分析法(LookAhead LR)是对LR(1)分析法的一种简化和改进，它的思想是对LR(1)中能够合并的项目集进行合并，从而减少状态。对同一个文法，合并LR(1)项目集之后得到的LALR(1)分析表比LR(1)分析表状态数少，具有和SLR(1)分析表相同数目的状态，但却能胜任SLR(1)所不能解决的问题。对目前常用的各类程序设计语言，LALR(1)分析法基本能够适用，但是缺点是状态的减少导致其比LR(1)报错要慢一点，所以从本质上讲，LALR(1)分析法是一种介于SLR(1)和LR (1)之间的折中的方法。
因此，LALR(1)分析法的关键问题在于LR(1)中哪些项目集能够合并，为此，给出如下同心集的定义。
定义518同心集
若LR(1)的两个项目集的LR(0)项目全部相同，则称两个LR(1)项目集具有相同的心。具有相同心的项目集称为同心集。

【例512】有文法G［S′］：  
(0)  S′→S
(1) S →CC
(2) C→cC
(3) C →d
构造该文法的LR(1)项目集规范族，并合并同心集。
从［S′ → ·S，#］出发，构造初始项目集，然后逐步扩展生成文法的LR(1)项目集规范族，如图59所示。不难看出，I4和I7、I3和I6、I8和I9是同心集，LALR(1)分析的思想就是在文法LR(1)项目集规范族的基础上，将同心的项目集进行合并，合并之后得到的项目集规范族称为LALR(1)项目集规范族。文法G［S′］的LALR(1)项目集规范族如图510所示。



图59文法G［S′］的LR(1)项目集规范族和识别可归前缀的DFA





图510文法G［S′］的LALR(1)项目集规范族和识别可归前缀的DFA




一般来说，对于某个LR(1)文法，若把同心项目集合并，可能会导致冲突，这种冲突不会是“移进归约”冲突，仅可能产生新的“归约归约”冲突。例如，假定Ik和Ij是两个同心集，如下所示： 

Ik:{［A→α·,u1］  ［B→η·,u2］  ［C→β·aγ,b］ }a∩u1=a∩u1=
Ij:{［A→α·,u2］  ［B→η·,u1］  ［C→β·aγ,c］}a∩u2=a∩u1=


则合并之后的项目集Ikj如下： 

Ikj:［A→α·,u1/u2］［ B→η·,u1/u2］［C→β·aγ,b/c］a∩{u1, u2}=


因为原有项目集中假定没有“移进归约”冲突，所以合并之后也不会出现“移进归约”冲突，即a∩{u1, u2}=。但是出现了“归约归约”冲突。例如，下一个输入符号若是u1或u2，均无法确定使用A→α·还是B→η·进行归约。



若合并后的LALR(1)项目集规范族不存在“归约归约”冲突，则可按这个项目集规范族构造LALR(1)分析表。构造LALR(1)分析表的算法如下。
算法57LALR(1)分析表的构造
输入： 文法G的LALR(1)项目集规范族和识别可归前缀的DFA
输出： 文法G的LALR(1)分析表
算法： 
设C={S0，S1，…，Sn}为文法G的LALR(1)项目集规范族。
(1) 对于［A→α·xβ,b］∈Si，GO(Si,x)=Sj： 若x∈VT，则置action［Si,x］=Sj； 若x∈VN，则置goto［Si,x］=j。
(2) 对于［A→α·,a］∈Si，若A→α是G中第k个产生式，则置action［Si,a］=rk。
(3) 若［S′→S·,#］∈Si，则置action［Si,#］=acc(#表示输入串右界符)。
(4) 其他情况均置错。 
在LALR(1)项目集规范族基础上，LALR(1)分析表的构造算法和LR(1)分析表的构造完全相同，按上述算法构造的LALR(1)分析表若无多重定义，则称文法G是LALR(1)文法。使用LALR(1)分析表的分析器叫LALR(1)分析器。
例512的LALR(1)项目集规范族中没有冲突，按上述算法对其构造的LALR(1)分析表如表513所示。如前所述，LALR(1)分析表中的状态进行了合并，优点是减少了状态和存储空间，缺点是分析不够确定，报错较LR(1)慢。





表513例512的LALR(1)分析表


状态

action
goto

c
d
#
S
C


0
S36
S47

1
2
1


acc


2
S36
S47


5
36
S36
S47


89
47
r3
r3
r3


5


r1


89
r2
r2
r2



上面介绍的4种LR分析法对应4种LR文法和LR分析器。那么假定给出任意一个无二义文法G，如何判断G属于哪一类LR文法呢？可以通过一个流程图给出判别的过程，如图511所示。




图511判定文法G属于何种LR文法的流程图



文法的谱系如图512所示。下面不加证明地给出不同文法之间的关系。



图512文法的谱系



LL(k)和LR(k)(k≥0)文法均是无二义文法，LL(k)文法一定是LR(k)文法。一个文法如果是LR(0)文法，则一定是SLR(1)、LALR(1)、LR(1)和LR(k)(k＞1)文法。一个文法如果是SLR(1)文法，则一定是LALR(1)、LR(1)和LR(k)(k＞1)文法。一个文法如果是LALR(1)文法，则一定是LR(1)和LR(k)(k＞1)文法。

5.3语法分析程序自动生成器YACC


本节介绍一个著名的语法分析器自动生成工具——YACC/Bison。它是以有限自动机理论为基础建立的。
1.  YACC综述与应用
YACC(Yet Another CompilerCompiler)是一个LALR(1)分析器自动生成器。YACC与Lex一样，是贝尔实验室在UNIX上首先实现的，而且与Lex有直接的接口，是UNIX的标准应用程序。GNU工程推出Bison，是对YACC的扩充，同时也与YACC兼容。目前，YACC/Bison与Lex/Flex一样，可以在UNIX、Linux、MSDOS等环境运行，鉴于YACC/Bison的兼容，后面讨论中仅针对YACC进行介绍。
YACC的功能是，为上下文无关文法自动生成基于LALR(1)的方法的语法语义分析器(简称分析器)，该分析器是使用C语言实现的。
YACC自动构造分析器的模式及YACC的作用如图513所示。YACC编译器接受YACC源程序，由YACC编译器处理YACC源程序，产生一个分析器作为输出。在UNIX环境中，YACC编译器的输出是一个具有标准文件名y.tab.c的C程序，经过C编译器产生a.out文件，a.out是一个实际可以运行的分析器。



图513YACC自动构造分析器的模式及作用



使用YACC的步骤如图514所示。


图514使用YACC的步骤



(1) 编辑YACC源程序(例如，生成文本格式的关于PAS语言语法的YACC源程序文件PAS.y)。
(2) 使用命令yacc PAS.y运行YACC，若正确则输出y.tab.c。
(3) 调用C编译器编译y.tab.c,并与其他C语言模块连接产生执行文件。调试执行文件，直至获得正确输出。
为了使LALR(1)分析表少占空间，可以用紧凑技术压缩分析表的大小。即使用命令

cc y.tab.c -ly

编译y.tab.c，其中的ly表示使用LR分析器的库(名字ly随系统而定)。

用BNF对语言(设语言为L1)的语法规则进行描述，然而BNF实际输入的是用YACC语言书写的源程序L1.y，y经YACC编译器翻译生成识别语言L1的语法分析器y.tab.c，此分析器即能对L1源程序实现语法分析。
YACC体系包括YACC语言和YACC编译器两部分。

2. YACC语言

YACC语言及YACC源程序是对语言的语法规则的描述，以解决文法规则的输入。YACC语言作为分析器自动构造的专用语言。YACC源程序由3部分组成，其结构如下： 

说明部分

％％

翻译规则

％％

辅助过程

其中，说明部分通常包含两部分内容。一部分为通常的C语言程序的说明，该部分说明用一对符号％{和％}括起来； 另一部分内容为文法符号(一般为终结符号)和文法规则的说明，以及对文法规则说明的一些限定规则和条件的说明。该部分的每一项均以%开头，其形式如下： 


%说明


翻译规则部分是YACC源程序的主体部分，它以一对百分号%%标志该部分的开始，其内容是文法的全部规则及与每一文法规则相关的语义动作描述。对文法中某一文法规则： 

<左部文法符号>→<候选式1>|<候选式2>|…|<候选式n>


用YACC描述的一般形式为
<左部文法符号>： <候选式1>｛语义动作1｝

|<候选式2>｛语义动作2｝

︙

|<候选式n>｛语义动作n｝

;



其中文法规则描述的候选式中，对文法的终结符号要用单引号括起来，以示与非终结符号的区别。该部分描述的第一个左部文法符号是开始符号。语义动作是完成语义处理的C语言程序。语义动作中的符号$$表示与文法规则的左部非终结符号相关的属性值，而$i表示其右部候选式中的第i个文法符号的值。在分析过程中，每当选用某个产生式进行规约后，其产生式后的语义动作子程序即被执行，完成相应的语法范畴的翻译。
例如，对简单的表达式文法

E→E+T|T

其YACC源程序的翻译规则描述部分可表示为 

%%

E： E'+'T    {$$=$1+$3}

|T

； 


YACC程序的第三部分，即辅助过程部分，是若干个C语言函数构成的，其中词法分析程序及错误诊断程序都是必不可少的。
【例513】设文法G(A)： 
A →E+E｜E*E|NUMBER


文法G(A)的YACC源程序如下： 
%｛

#include <ctype.h>

#include <stdio.h>

%｝

%token number

%%

lines:lines expr '＼n'  {printf("%g＼n",$2);}

;

expr:expr '+' expr    {$$=$1+$3}

|expr '*' expr     {$$=$1*$3}

;

%%

…/*辅助过程*/




程序中省略了YACC程序的第三部分。在实际使用YACC时，这部分可根据YACC的使用说明及对文法翻译的具体要求编写所需要的辅助程序。
对于上述YACC说明的文法二义性，LALR(1)算法将产生分析动作的冲突。YACC会报告产生的分析动作的冲突数目。项目集和分析冲突的描述可以在调用YACC时加v选择项得到。这个选择产生一个附加的文件y.output，它包括分析时发现的项目集的心以及对LALR(1)算法产生的分析动作冲突的描述。
带有冲突的LR分析表显然无法正确实施语法分析。考虑YACC的适用性，下面讨论YACC对二义性文法的处理。

3. YACC处理二义性文法

YACC自动生成的分析程序采用的是LALR(1)分析法。按照LR分析应用于二义性文法的思想，即对二义性文法施加某些限定，YACC同样可以适用于二义性文法分析器的自动生成。在YACC源程序的说明部分对规则进行描述，则YACC对二义性文法也可以产生LR分析器。
对例513的台式计算器文法G(A)扩大其表达功能，给出如下文法G(A)′:

A→E+E|E-E|E*E|E/E|(E)|-E|NUMBER
该文法是二义性文法，但只要对其中的终结符号+、—、*、/、NUMBER规定优先级和结合规则，并在YACC源程序的说明部分中加以说明，YACC就能自动生成文法G(A)产生LR分析器。
G(A)′的YACC源程序如下： 

%｛

#include<ctype.h>

#include<stdio.h>

#define YYSTYPE double

%｝

%token NUMBER

%LEFT  '+'  '-'

%LEFT  '*'  '/'

%RIGHT  UMINUS

%%

 lines:lines expr '＼n'  {printf("%g＼n",$2);}

|line  '＼n'

|/*ε*/

;

 expr:  expr '+'{$$=$1+$3;}

|expr  '-'expr       { $$=$1-$3;}

|expr  '*' expr        { $$=$1*$3;}

|expr  '/' expr        { $$=$1/$3;}

|'(' expr ')'            {$$=$2;}

|'-'expr %&prec UMINUS {$$=-$2;}

|NUMBER

;

%%

yylex()

int c;

while((c=getchar())==''){

if((c=='.')||(isdigit(c))  {

ungetc(c,stdin);

scanf("%if",&yylval);

return NUMBER;

}

return c;

}





该YACC程序的声明部分为终结符号规定了优先级和结合性。声明

%terminal '+'  '-'  LEFT

%terminal '*'  '/'   LEFT



使得+和-有同样的优先级且为左结合。*和/也是如此。
记号的优先级按它们在声明部分出现的次序确定，先出现的记号的优先级低，同一声明中的记号有相同的优先级，这样，上述YACC程序的声明中


%RIGHT UMINUS

使得UMINUS的优先级高于前面5个终结符号。

习题

1.  选择题。
(1) 文法识别符号经过任意步推导得到的结果是()。 

A. 句型 
B. 句柄 
C. 句子 
D. 短语 
(2) 在自底向上的规范归约中，可归约串用()来刻画。 
A. 直接短语 
B. 句柄 
C. 终结符号串
D. 最左短语
(3) 下面对自底向上分析描述错误的是()。
A. 自底向上分析过程是对句子实施归约的过程 
B. 自底向上分析是从给定的输入串#开始，逐步进行“归约”，直至归约到文法的开始符号 
C. 各种自底向上分析方法的共同点是都采用移进归约的思想,区别是确定可归约串的方法不同
D. 自底向上分析是规范归约的过程

(4) 下面()不是自底向上的语法分析文法。
① LR(1)② LALR(1)③ 递归下降分析法④ LL(1)⑤ SLR(1)⑥ LR(0)
A. ①②③④B.③④C.①②⑤⑥D.③⑤⑥
(5) 若状态j含有项目“X→α· ”，且仅当输入符号b∈FOLLOW(X)时，才用规则“X→α”归约的语法分析方法是()。
A. LALR分析法
B. LR(0)分析法
C. LR(1)分析法
D. SLR(1)分析法
(6) 若b为终结符，则X→α·bβ为()项目。
A. 归约
B. 移进
C. 接受
D. 待约
(7) 若Y为非终结符，则X→α·Yβ为()项目。
A. 归约
B. 移进
C. 接受
D. 待约
(8) 同心集合并之后若不是LALR(1)文法，则会出现的情况是()。
A. 产生二义性冲突B. 产生移进移进冲突
C. 产生移进归约冲突D. 产生归约归约冲突
(9) 当分析文法G的某一个含有错误的符号串时，LALR(1)分析速度比LR(1)分析速度要慢，主要原因是()。
A. 合并同心集后做了不必要的移进动作
B. 合并同心集后做了不必要的归约动作
C. 合并同心集后做了不必要的移进与归约动作
D. 以上都不对
(10) 关于LR分析表，说法正确的是()。

A.  LR分析表中的状态转换表指出了当状态Si面临输入符号a时，移进之后转移到的新状态
B.  LR分析表中分析动作表指出了当状态Si面临文法符号X时，应转移到的下一个状态
C.  LR分析表中的状态转换表指出了当状态Si面临输入符号a时，应使用哪个规则进行归约
D.  LR分析表中分析动作表中符号为acc时，表示当前分析栈中只剩下开始符号S′和待分析串结束符#，表明分析成功
(11) 关于LR分析器，说法错误的是()。
A.  LR分析器的每一步动作，都是由栈顶状态和现行输入符号所唯一确定的
B.  LR分析器的动作包括移进、归约、接受、报错四种动作
C. 不同的LR分析器，其总控程序也不同
D.  LR分析表包括分析动作表和状态转换表两部分，都是二维数组
(12) 关于文法规范句型的活前缀，说法错误的是()。
A. 规范句型的活前缀不包含句柄右边的任何符号
B.  LR分析栈中的符号为规范句型的活前缀
C. 当LR分析栈中的栈顶符号串形成可归前缀，归约之后，栈中剩余符号不再是规范句型的活前缀
D. 活前缀可以是一个或者是若干个规范句型的前缀
(13) 设一个LR(0)项目集I={A→α·bβ, B→γ·}，该项目集可能含有的冲突项目是()。
A. 移进归约冲突B. 归约归约冲突
C. 移进接受冲突D. 不存在冲突
(14) 设LR(1)项目集I={［A→α·bβ,a］,［B→γ·,a］}，说法正确的是()。
A. 存在移进归约冲突B. 存在归约归约冲突
C. 存在移进接受冲突D. 不存在冲突
(15) 关于二义性文法与LR类文法，说法错误的是()。
A. 任何一个二义性文法绝不是LR类文法
B. 在LR分析表中加入无二义性规则，仍然无法构造出无多重定义的LR分析表
C. 对于二义性的算术表达式文法， 在LR分析表中加入运算符的优先级及运算符的结合性可构造出无多重定义的LR分析表
D. 可以通过消除二义性文法中的二义性，从而使得文法可以满足LR类文法
(16) LR(1)文法都是()。
A. 既不存在二义性，也不存在文法左递归
B. 可以是二义性的，但是没有左递归
C. 不可以是二义性的，但是可以存在左递归
D. 可以是二义性的，还可以存在左递归
2. 填空题。
(1) “移进归约”分析过程主要采取的分析动作包括()、()、()和()。
(2) LR(k)分析法中，L指()，R指分析过程是()的逆过程,其中最简单的是()分析法。
(3) LR文法指构造出的分析表()。
(4) 可归前缀指活前缀中已经包含句柄的()。
(5) 向前搜索符只对()项目有意义，对()项目没有影响。表示()与向前搜索符相同时，进行()。
(6) LR分析表是LR分析器的核心部分，包括()和()两部分组成，均使用()表示。
(7) 同心集是指两个LR(1)项目集的()相同，当同心集合并后，可能会产生新的()，而不可能产生新的()。
(8)  对于文法G［E］： E→T|E+TT→F|T*FF→(E)|i，句型E+T*F+T*F+T*i的句柄是()。
3. 分析应用题。
(1)  文法G［E］为： 
E→T | EiT 
T→F| T+F
F→)E* |( 
试给出句型Ei)E*i( 的短语、简单(直接)短语、句柄。
(2)  文法G［S］为： 
S→SdE | E
E→E<T | T
T→(S) |a
试给出句型(SdE)dT<a的短语、简单(直接)短语、句柄。
(3) 已知文法G(S)： 
S→a|(T)|* 
T→T,S|S 
①   给出(a,(a,a))和(((a,a),,(a)),a)*的最左和最右推导。
②   指出(((a,a),,(a)),a)∧的规范归约及每一步的句柄。根据这个规范归约，给出“移进归约”的过程，并给出它的语法树自底向上的构造过程。
(4)  设有文法G［S］： 
S→a|(T)|* 
T→T,S|S 
①  构造此文法的LR(0)项目集规范族，并给出识别活前缀的DFA。
②  构造其LR(0)分析表。
(5) 给定文法G［Z］： 
①   Z→CS
②   C→if E then
③   S→A=E
④   E→E∧A
⑤  E→A
⑥  A→i
其中： Z、C、S、A、E∈VN 
if、then、＝、∧、i∈VT
①  构造此文法的LR(0)项目集规范族，并给出识别活前缀的DFA。
②  构造其SLR(1)分析表。
(6)  已知文法
A→aAcd|aAb|ε
判断该文法是否是SLR(1)文法，若是，构造相应的分析表，并对输入串ab#给出分析过程。
(7)  设文法G(S)如下：  
E→E + T|T
T→T F|F
F→F/| a|b 

①  构造其SLR分析表。
②  构造其LALR分析表。
③   假定输入串为a/b+b，请给出SLR(1)分析过程(即按照步骤给出状态、符号、输入串的变化过程)。
④   假定输入串为a/b+b，请给出LALR(1)分析过程(即按照步骤给出状态、符号、输入串的变化过程)。
(8)  若有定义二进制数的文法如下： 
S→L.L|L
L→LB|B
B→0|1
①  构造其SLR分析表。
②  假定输入串101.110 ，请给出SLR(1)分析过程(即按照步骤给出状态、符号、输入串的变化过程)。
(9) 给定文法G(S):
S→bAd|Aa|bc|BB
A→a
B→Bb|c
构造其LALR分析表。
(10) 设已构造出文法G(S)： 
①   S→AA
②   A→aA
③   A→b
要求： 
①  构造LR(1)分析表。
②  假定输入串为aabab，请给出LR(1)分析过程(即按照步骤给出状态、符号、输入串的变化过程)。
(11) 证明下面的文法是LL(1)的,但不是SLR(1)的。
S→AaAb|BbBaA→εB→ε
(12) 证明下列文法是LR(1)的，但不是SLR(1)的。
S→Aa|bAc|Bc|bBa
A→d
B→d
(13) 考虑文法S→AS|aA→SA|b
①   列出这个文法的所有LR(0)项目。
②   构造这个文法的LR(0)项目集规范族及识别活前缀的DFA。
③   这个文法是SLR的吗？若是，构造出它的SLR分析表。
④   这个文法是LALR或LR(1)的吗？