编译原理教程课后习题答案——第三章.doc

第三章 语法分析
3.1 完成下列选择题：
(1) 文法G：S→xSx|y所识别的语言是 。
a. xyx b. (xyx)*
c. xnyxn(n≥0) d. x*yx*
(2) 如果文法G是无二义的，则它的任何句子α 。 　
a. 最左推导和最右推导对应的语法树必定相同
b. 最左推导和最右推导对应的语法树可能不同
c. 最左推导和最右推导必定相同
d. 可能存在两个不同的最左推导，但它们对应的语法树相同
(3) 采用自上而下分析，必须 。
a. 消除左递 a. 必有ac归 b. 消除右递归
c. 消除回溯 d. 提取公共左因子
(4) 设a、b、c是文法的终结符，且满足优先关系ab和bc，则 。
b. 必有ca
c. 必有ba d. a～c都不一定成立
(5) 在规范归约中，用 来刻画可归约串。
a. 直接短语 b. 句柄
c. 最左素短语 d. 素短语
(6) 若a为终结符，则A→α·aβ为 项目。
a. 归约 b. 移进
c. 接受 d. 待约
(7) 若项目集Ik含有A→α· ，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α· ”动作的一定是 。
a. LALR文法 b. LR(0)文法
c. LR(1)文法 d. SLR(1)文法
(8) 同心集合并有可能产生新的 冲突。
a. 归约 b. “移进”/“移进”
c.“移进”/“归约” d. “归约”/“归约”
【解答】 (1) c (2) a (3) c (4) d (5) b (6) b (7) d (8) d
3.2 令文法G[N]为
G[N]: N→D|ND
D→0|1|2|3|4|5|6|7|8|9
(1) G[N]的语言L(G[N])是什么?
(2) 给出句子0127、34和568的最左推导和最右推导。
【解答】
(1) G[N]的语言L(G[N])是非负整数。
(2) 最左推导： NNDNDDNDDDDDDD0DDD01DD012D0127
NNDDD3D34
NNDNDDDDD5DD56D568
最右推导： NNDN7ND7N27ND27N127D1270127
NNDN4D434
NNDN8ND8N68D68568
3.3 已知文法G[S]为S→aSb|Sb|b，试证明文法G[S]为二义文法。
【解答】 由文法G[S]：S→aSb|Sb|b，对句子aabbbb可对应如图3-1所示的两棵语法树。

图3-1 句子aabbbb对应的两棵不同语法树
因此，文法G[S]为二义文法(对句子abbb也可画出两棵不同语法树)。
3.4 已知文法G[S]为S→SaS|ε，试证明文法G[S]为二义文法。
【解答】 由文法G[S]：S→SaS|ε，句子aa的语法树如图3-2所示。

图3-2 句子aa对应的两棵不同的语法树
由图3-2可知，文法G[S]为二义文法。
3.5 按指定类型，给出语言的文法。
(1) L={aibj|j＞i≥0}的上下文无关文法；
(2) 字母表Σ={a,b}上的同时只有奇数个a和奇数个b的所有串的集合的正规文法；
(3) 由相同个数a和b组成句子的无二义文法。
【解答】 (1) 由L={aibj|j＞i≥0}知，所求该语言对应的上下文无关文法首先应有S→aSb型产生式，以保证b的个数不少于a的个数；其次，还需有S→Sb或S→b型的产生式，用以保证b的个数多于a的个数。因此，所求上下文无关文法G[S]为
G[S]：S→aSb|Sb|b
(2) 为了构造字母表Σ={a,b}上同时只有奇数个a和奇数个b的所有串集合的正规式，我们画出如图3-3所示的DFA，即由开始符S出发，经过奇数个a到达状态A，或经过奇数个b到达状态B；而由状态A出发，经过奇数个b到达状态C(终态)；同样，由状态B出发经过奇数个a到达终态C。
由图3-3可直接得到正规文法G[S]如下：
G[S]：S→aA|bB
A→aS|bC|b
B→bS|aC|a
C→bA|aB|ε

图3-3 习题3.5的DFA
(3) 我们用一个非终结符A代表一个a(即有A→a)，用一个非终结符B代表一个b(即有B→b)；为了保证a和b的个数相同，则在出现一个a时应相应地出现一个B，出现一个b时则相应出现一个A。假定已推导出bA，如果下一步要推导出连续两个b时，则应有bAbbAA。也即为了保证b和A的个数一致，应有A→bAA；同理有B→aBB。此外，为了保证递归地推出所要求的ab串，应有S→aBS和S→bAS。由此得到无二义文法G[S]为
G[S]：S→aBS|bAS|ε
A→bAA|a
B→aBB|b
3.6 有文法G[S]: S→aAcB|Bd
A→AaB|c
B→bScA|b
(1) 试求句型aAaBcbbdcc和aAcbBdcc的句柄；
(2) 写出句子acabcbbdcc的最左推导过程。
【解答】 (1) 分别画出对应句型aAaBcbbdcc和aAcbBdcc的语法树如图3-4的(a)、(b)所示。

图3-4 习题3.6的语法树

(a) aAaBcbbdcc; (b) aAcbBdcc
对树(a)，直接短语有3个：AaB、b和c，而AaB为最左直接短语(即为句柄)。对树(b)，直接短语有两个：Bd和c，而Bd为最左直接短语。
能否不画出语法树，而直接由定义(即在句型中)寻找满足某个产生式的候选式这样一个最左子串(即句柄)呢？例如，对句型aAaBcbbdcc，我们可以由左至右扫描找到第一个子串AaB，它恰好是满足A→AaB右部的子串；与树(a)对照，AaB的确是该句型的句柄。是否这一方法始终正确呢？我们继续检查句型aAcbBdcc，由左至右找到第一个子串c，这是满足A→C右部的子串，但由树(b)可知，c不是该句型的句柄。由此可知，画出对应句型的语法树然后寻找最左直接短语是确定句柄的好方法。
(2) 句子acabcbbdcc的最左推导如下：
SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcA
　　　acabcbbdcAacabcbbdcc
3.7 对于文法G[S]: S→(L)|aS|a
L→L,S|S
(1) 画出句型(S,(a))的语法树；
(2) 写出上述句型的所有短语、直接短语、句柄、素短语和最左素短语。
【解答】 (1) 句型(S, (a))的语法树如图3-5所示。

图3-5 句型(S,(a))的语法树
(2) 由图3-5可知：
短语：S、a、(a)、S,(a)、(S,(a))；
直接短语：a、S；
句柄：S；
素短语：素短语可由图3-5中相邻终结符之间的优先关系求得，即：
#⋖ (⋖，⋖ (⋖a⋗)⋗)⋗#
因此，素短语为a。
3.8 下述文法描述了C语言整数变量的声明语句：
G[D]: D→TL
T→int|long|short
L→id|L,id
(1) 改造上述文法，使其接受相同的输入序列，但文法是右递归的；
(2) 分别用上述文法G[D]和改造后的文法G[D′]为输入序列int a,b,c构造分析树。
【解答】 (1) 消除左递归后，文法G[D′]如下：
D→TL
T→int|long|short
L→idL

图3-6 两种文法为int a,b,c构造的分析树

(a) 文法G(D)； (b) 文法G′(D)
3.9 考虑文法G[S]: S→(T) | a+S | a
T→T,S | S
消除文法的左递归及提取公共左因子，然后对每个非终结符写出不带回溯的递归子程序。
【解答】 消除文法G[S]的左递归：
S→(T) | a+S | a
T→ST′
T′→,ST′| ε
提取公共左因子：
S→(T) | aS′
S′→+S | ε
T→ST′
T′→,ST′| ε
改造后的文法已经是LL(1)文法，不带回溯的递归子程序如下：
void match (token t)
{
if ( lookahead==t)
lookahead=nexttoken;
else error ( );
}
void S ( )
{
if ( lookahead==′a′)
match (′a′);
else if ( lookahead==′(′)
{
match (′(′);
T ( );
void S′( )
{
if ( lookahead==′+′)
{
match (′+′);
S ( );
}
}
void T ( )
{
S ( );
T′( );
}
void T′ ( )
{
if ( lookahead==′, ′)
{
match (′, ′);
S ( );
T′ ( );
}
}
3.10 已知文法G[A]: A→aABl|a
B→Bb|d
(1) 试给出与G[A]等价的LL(1)文法G[A′]；
(2) 构造G[A′]的LL(1)分析表；
(3) 给出输入串aadl#的分析过程。
【解答】 (1) 文法G[A]存在左递归和回溯，故其不是LL(1)文法。要将G[A]改造为LL(1)文法，首先要消除文法的左递归，即将形如P→Pα | β的产生式改造为
P→βP′
P→αP′| ε
来消除左递归。由此，将产生式B→Bb|d改造为
B→dB′
B′→bB′| ε
其次，应通过提取公共左因子的方法来消除G[A]中的回溯，即将产生式A→aABl|a改造为
A→aA′
A′→ABl | ε
最后得到改造后的文法为
G[A′]：A→aA′
A′→ABl | ε
B→dB′
B′→bB′| ε
求得：
FIRST(A)={a} FIRST(A′)={a, ε}
FIRST(B)={d} FIRST(B′)={b, ε}
对文法开始符号A，有FOLLOW(A)={#}。
由A′→ABl得FIRST(B)\{ ε}ÌFOLLOW(A)，即FOLLOW(A)={#,d}；
由A′→ABl得FIRST(′l′) ÌFOLLOW(B)，即FOLLOW(B)={l}；
由A→aA′得FOLLOW(A) ÌFOLLOW(A′)，即FOLLOW(A′)={#,d}；
由B→dB′得FOLLOW(B) ÌFOLLOW(B′)，即FOLLOW(B′)={l}。
对A′→ABl来说，FIRST(A)∩FOLLOW(A′)={a}∩{#,d}=Φ，所以文法G′[A]为所求等价的LL(1)文法。
(2) 构造预测分析表的方法如下：
① 对文法G[A′]的每个产生式A→α执行②、③步。
② 对每个终结符a∈FIRST(A)，把A→α加入到M[A,a]中，其中α为含有首字符a的候选式或为唯一的候选式。
③ 若ε∈FIRST(A)，则对任何属于FOLLOW(A)的终结符b，将A→ε加入到M[A,b]中。把所有无定义的M[A,a]标记上“出错”。
由此得到G[A′]的预测分析表，见表3-1。
表3-1 预测分析表

(3) 输入串aadl的分析过程见表3-2。
表3-2 输入串aadl的分析过程

3.11 将下述文法改造为LL(1)文法：
G[V]: V→N | N[E]
E→V | V+E
N→i
【解答】 LL(1)文法的基本条件是不含左递归和回溯(公共左因子)，而文法G[V]中含有回溯，所以先消除回溯，得到文法G[V′]：
G [V′]：V→NV′
V′→ε | [E]
E→VE′
E′→ε | +E
N→i
一个LL(1)文法的充要条件是：对每一个终结符A的任何两个不同产生式A→α|β有下面的条件成立：
(1) FIRST(α)∩FIRST(β)=Φ；
(2) 假若βε，则有FIRST(α)∩FOLLOW(A)= Φ。
即求出G[V′]的FIRSTVT和LASTVT集如下：
FIRST(N)=FIRST(V)=FIRST(E)={i}
FIRST(V′)={[, ε}
FIRST(E′)={+, ε}
FOLLOW(V)={#}
由V′→…E]得FIRST(′)′) ÌFOLLOW(E)，即FOLLOW(E)={ ]}；
由V→NV′得FIRST(V′)\{ ε} Ì FOLLOW(N)，即FOLLOW(N)={ [}；
由E→VE′得FIRST(E′)\{ ε}ÌFOLLOW(V)，即FOLLOW(V)={#,+}；
由V→NV′得FOLLOW(V) ÌFOLLOW(V′)，即FOLLOW(V′)={#,+}；
由V→NV′，且V′→ε得FOLLOW(V) ÌFOLLOW(N)，即FOLLOW(N)={[,#,+]；
由E→VE′得FOLLOW(E) ÌFOLLOW(E′)，即FOLLOW(E′)={ ]}；
则，对V′→ε |[E]有：FIRST(ε)∩FIRST(′[′]= Φ；
对E′→ε | +E有：FIRST(ε)∩FIRST(′+′)= Φ；
对V′→ε | [E]有： FIRST(′[′)∩FOLLOW(V′)={[]∩{#,+}=Φ；
对E′→ε | +E有： FIRST(′+′)∩FOLLOW(E′)={+}∩{}}=Φ。
故文法G[V′]为LL(1)文法。
3.12 对文法G[E]: E→E+T|T
T→T*P|P
P→i
(1) 构造该文法的优先关系表(不考虑语句括号#)，并指出此文法是否为算符优先文法；
(2) 构造文法G的优先函数。

【解答】 FIRSTVT集构造方法：
① 由P→a…或P→Qa…，则a∈FIRSTVT(P)。
② 若a∈FIRSTVT(Q)，且P→Q…，则a∈FIRSTVT(P)，也即FIRSTVT(Q)ÌFIRSTVT(P)。
由①得：由E→E+…得FIRSTVT(E)={+}；
由T→T*…得FIRSTVT(T)={*}；
由P→i得FIRSTVT(P)={i}。
由②得：由T→P得FIRSTVT(P)ÌFIRSTVT(T)，即FIRSTVT(T)={*，i}；
由E→T得FIRSTVT(T)ÌFIRSTVT(E)，即FIRSTVT(T)={+，*，i}。
LASTVT集构造方法：
① 由P→…a或P→…aQ, 则a∈LASTVT(P)。
② 若a∈LASTVT(Q)，且P→…Q，则a∈LASTVT(P)，也即LASTVT(Q)ÌLASTVT(P)。
由①得：E→…+T，得LASTVT(E)={+}；
T→…*P，得LASTVT(T)={*}；
P→i，得LASTVT(P)={i}。
由②得：由T→P得LASTVT(P)ÌLASTVT(T)，即LASTVT(T)={*，i}；
由E→T得LASTVT(T)ÌLASTVT(E)，即LASTVT(E)={+，*，i}。
优先关系表构造方法：
① 对P→…ab…或P→…aQb…，有ab；
② 对P→…aR…而b∈FIRSTVT(R)，有a⋖b；
③ 对P→…Rb…而a∈LASTVT(R)，有a⋗b。
解之无①。
由②得：E→…+T，即+⋖FIRSTVT(T)，有+⋖*，+⋖i；
　　T→…*P，即*⋖FIRSTVT(P)，有*i。
由③得：E→E+…，即LASTVT(E)⋗+，有+⋗+，*⋗+，i⋗+；
T→T*…，即LASTVT(T)⋗*，有*⋗*，i⋗*。
得到优先关系表见表3-3。
由于该文法的任何产生式的右部都不含两个相继并列的非终结符，故属算符文法，且该文法中的任何终结符对(见优先关系表)至多满足、⋖和⋗三种关系之一，因而是算符优先文法。

表3-3 习题3.12的优先关系表

用关系图构造优先函数的方法是：对所有终结符a用有下脚标的fa、ga为结点名画出全部终结符所对应的结点。若存在优先关系a⋗b或ab，则画一条从fa到ga的有向弧；若a⋖b或ab，则画一条从g b到f a的有向弧。最后，对每个结点都赋一个数，此数等于从该结点出发所能到达的结点(包括出发结点)的个数，赋给fa的数作为f(a)，赋给gb的数作为g(b)。用关系图法构造本题的优先函数，如图3-7所示。
得到优先函数见表3-4。

表3-4 习题3.12的优先函数表

图3-7 习题3.12关系图构造
该优先函数表经检查与优先关系表没有矛盾，故为所求优先函数。
也可由定义直接构造优先函数，其方法是：对每个终结符a，令f(a)=g(a)=1；如果a⋗b，而f(a)≤g(b)，则令f(a)=g(b)+1；如果a⋖b，而f(a)≥g(b)，则令g(b)=f(a)+1；如果ab，而f(a)≠g(b)，则令 min{f(a),g(b)}=max{f(a),g(b)}。重复上述过程，直到每个终结符的函数值不再变化为止。如果有一个函数值大于2n(n为终结符个数)，则不存在优先函数。
优先函数的计算过程如表3-5所示。
表3-5 优先函数的计算过程表

计算最终收敛，并且计算得出的优先函数与关系图构造得出的优先函数是一样的。
3.13 设有文法G[S]: S→a|b|(A)
A→SdA|S
(1) 构造算符优先关系表；
(2) 给出句型(SdSdS)的短语、简单短语、句柄、素短语和最左素短语；
(3) 给出输入串(adb)#的分析过程。
【解答】(1) 先求文法G[S]的FIRSTVT集和LASTVT集：
由S→a|b|(A)得FIRSTVT(S)={a,b,(}；
由A→Sd…得FIRSTVT(A)={d}，又由A→S…得FIRSTVT(S) ÌFIRSTVT(A)，即FIRSTVT(A)={d,a,b, ( }；
由S→a|b|(A)得LASTVT(S) ={a,b,)}；
由A→…dA得LASTVT(A)={d}，又由A→S得LASTVT(S) ÌLASTVT(A)，即LASTVT(A)={d,a,b,)}。
构造优先关系表方法如下：
① 对P→…ab…或P→…aQb…，有ab；
② 对P→…aR…而b∈FIRSTVT(R)，有a⋖b；
③ 对P→…Rb…而a∈FIRSTVT(R)，有a⋗b。
由此得到：
① 由S→(A)得()；
② 由S→(A…得(⋖FIRSTVT(A)，即(⋖d,(⋖a,(⋖b,(⋖(；
由A→…dA得d⋖FIRSTVT(A)，即d⋖d,d⋖a,d⋖b,d⋖ (；
③由S→…A)得LASTVT(A)⋗)，即d⋗),a⋗),b⋗),)⋗)；
由A→Sd…得LASTVT(S)⋗d，即a⋗d,b⋗d,)⋗d；
此外，由#S#得##；
由#⋖FIRSTVT(S)得 #⋖a,# ⋖b, # ⋖ (；
由LASTVT(S)⋗#得a⋗#, b⋗#, )⋗#。
最后得到算符优先关系表，见表3-6。
表3-6 习题3.13的算符优先关系表

由表3-6可以看出，任何两个终结符之间至多只满足、⋖、⋗三种优先关系之一，故G[S]为算符优先文法。
(2) 为求出句型(SdSdS)的短语、简单短语、句柄，我们先画出该句型对应的语法树，如图3-8所示。

图3-8 句型(SdSdS)的语法树
由图3-8得到：
短语：S，SdS，SdSdS，(SdSdS) 注意，句型中的素短语具有如下形式：
aj-1⋖ajaj+1…ai⋗ai+1
而最左素短语就是该句型中所找到的最左边的那个素短语，即最左素短语必须具备三个条件：
① 至少包含一个终结符(是否包含非终结符则按短语的要求确定)；
② 除自身外不得包含其他素短语(最小性)；
③ 在句型中具有最左性。
图3-9 句型(SdSdS)的优先关系
简单短语(即直接短语)：S
句柄(即最左直接短语)：S
可以通过分析图3-8的语法树来求素短语和最左素短语，即找出语法树中的所有相邻终结符(中间可有一个非终结符)之间的优先关系。确定优先关系的原则是：
① 同层的优先关系为；
② 不同层时，层次离树根远者优先级高，层次离树根近者优先级低(恰好验证了优先关系表的构造算法)；
③ 在句型ω两侧加上语句括号“#”，即#ω#，则有#⋖ω和ω⋗#，由此我们得到句型(SdSdS)的优先关系如图3-9所示。
因此，由图3-9得到SdS为句型(SdSdS)的素短语，它同时也是该句型的最左素短语。
(3) 输入串(adb)#的分析过程见表3-7。
表3-7 输入串(adb)#的分析过程

为便于分析，同时给出了(adb)#的语法树，如图3-10所示。

图3-10 (adb)的语法树
3.14 在算符优先分析法中，为什么要在找到最左素短语的尾时才返回来确定其对应的头，能否按扫描顺序先找到头后再找到对应的尾，为什么？
【解答】 设句型的一般形式为N1a1N2a2…NnanNn+1。其中，每个ai都是终结符，而Ni则是可有可无的非终结符。对上述句型可以找出该句型中的所有素短语，每个素短语都具有如下形式：
…aj-1⋖ajaj+1…ai⋗ai+1…
如果某句型得到的优先关系如下：
…⋖…⋖……⋗…⋗

则当从左至右扫描到第一个“⋗”时，再由此从右至左扫描到第一个“⋖”时，它们之间(当然不包含第一个“⋖”前一个终结符和第二个“⋗”后一个终结符)即为最左素短语。
如果由左至右扫描到第一个“⋖”，可以看出这并不一定是最左素短语的开头，因为由它开始并不一定是素短语(在其内部还可能包含其他更小的素短语)，所以，在算符优先分析算法中，只有先找到最左素短语的尾(即“⋗”)，才返回来确定与其对应的头(即“⋖”)；而不能按扫描顺序先找到头然后再找到对应的尾。
3.15 试证明在算符文法中，任何句型都不包含两个相邻的非终结符。
【解答】 设文法G=(VT,VN,S, ξ)，其中VT是终结符集；VN是非终结符集；ξ为产生式集合；S是开始符号。
对句型的推导长度n作如下归纳：
(1) 当n=1时，S⇒α，则存在一条产生式S→α属于ε，其中a∈(VT∪VN) *。由于文法是算符文法，所以α中没有两个相邻非终结符，故归纳初始成立。
(2) 设n=k时结论成立，则对任何k+1步推导所产生的句型必为
Sα∪β⇒α∨β
其中，α、β∈(VT∪VN) *，U∈VN，而U→V是一条产生式。
由归纳假设，U是非终结符，设α=α1α2…αn，β=β1β2…βm，其中αi、βj ∈(VT∪VN) (1≤i≤n-1,2≤j≤m) ；但αn和βm必为位于U两侧的终结符。
设V=V1V2…Vr，由于它是算符文法的一个产生式右部候选式，因此V1V2…Vr中不会有相邻的非终结符出现。又因为αnV1和Vrβ1中的αn、β1为终结符，也即在推导长度为k+1时所产生的句型
α1α2…αnV1V2…Vrβ1β2…βm
不会出现相邻的非终结符，故n=k+1时结论成立。显然，在α或β为空时结论也成立。
3.16 给出文法G[S]: S→aSb∣P
P→bPc∣bQc
Q→Qa∣a
(1) 它是Chomsky哪一型文法？
(2) 它生成的语言是什么？
(3) 它是不是算符优先文法？请构造算符优先关系表证实之；
(4) 文法G[S]消除左递归、提取公共左因子后是不是LL(1)文法？请证实。
【解答】 (1) 根据Chomsky的定义，对任何形如A→β的产生式，有A∈VN，β∈(VT∪VN)*时为2型文法。而文法G[S]恰好满足这一要求，故为Chomsky 2型文法。
(2) 由文法G[S]可以看出：S推出串的形式是ai P bi(i≥0)，P推出串的形式是bjQcj(j≥1)，Q推出串的形式是ak(k≥1)。因此，文法G[S]生成的语言是L={aibjakcjbi|i≥0, j≥1, k≥1}。
(3) 求出文法G[S]的FIRSTVT集和LASTVT集：
FIRSTVT(S)={a,b} FIRSTVT(P)={b}
FIRSTVT(Q)={a}
LASTVT(S)={b,c} LASTVT(P)={c}
LASTVT(Q)={a}
构造优先关系表如表3-8所示。
由于在优先关系中同时出现了a⋖a和a⋗a以及b⋖b和b⋗b，故文法G[S]不是算符优先文法。
表3-8 优先关系表

(4) 消除文法G[S]的左递归：
S→aSb | P
P→bPc | bQc
Q→aQ′
Q′→aQ′| ε
提取公共左因子后得到文法G′[S]:
S→aSb | P
P→bP′
P′→Pc | Qc
Q→aQ′
Q′→aQ′| ε
求每个非终结符的FIRST集和FOLLOW集如下：
FIRST(S)={a,b} FIRST(P)={b}
FIRST(P′)={a,b} FIRST(Q)={a}
FIRST(Q′)={a, ε}
FOLLOW(S)={b,#} FOLLOW(P)={b,c,#}
FOLLOW(P′)={b,c,#} FOLLOW(Q)={c}
FOLLOW(Q′)={c}
通过检查G′[S]可以得到：
① 每一个非终结符的所有候选式首符集两两不相交；
② 存在形如A→ε的产生式Q′→aQ′| ε，但有
FIRST(aQ′)∩FOLLOW(Q′)={a}∩{c}=Φ
所以文法G′[S]是LL(1)文法。

**3.17 LR分析器与优先关系分析器在识别句柄时的主要异同是什么？
【解答】 如果S⇒aAδ且有A⇒β，则称β是句型αβδ相对于非终结符A的短语。特别的，如果有A⇒β，则称β是句型αβδ相对于规则A→β的直接短语。一个句型的最左直接短语称为该句型的句柄。规范归约是关于α的一个最右推导的逆过程，因此，规范归约也称最左归约。请注意句柄的“最左”特征。
LR分析器用规范归约的方法寻找句柄，其基本思想是：在规范归约的过程中，一方面记住已经归约的字符串，即记住“历史”；另一方面根据所用的产生式推测未来可能碰到的输入字符串，即对未来进行“展望”。当一串貌似句柄的符号串呈现于栈顶时，则可根据历史、展望以及现实的输入符号等三方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。事实上，规范归约的中心问题恰恰是如何寻找或确定一个句型的句柄。给出了寻找句柄的不同算法也就给出了不同的规范归约方法，如LR(0)、SLR(1)、LR(1)以及LALR就是在归约方法上进行区别的。
算符优先分析不是规范归约，因为它只考虑了终结符之间的优先关系，而没有考虑非终结符之间的优先关系。此外，算符优先分析比规范归约要快得多，因为算符优先分析跳过了所有单非产生式所对应的归约步骤。这既是算符优先分析的优点，同时也是它的缺点，因为忽略非终结符在归约过程中的作用存在某种危险性，可能导致把本来不成句子的输入串误认为是句子，但这种缺陷容易从技术上加以弥补。为了区别于规范归约，算符优先分析中的“句柄”被称为最左素短语。
3.18 什么是规范句型的活前缀？引进它的意义何在？
【解答】 在讨论LR分析器时，需要定义一个重要概念，这就是文法的规范句型的“活前缀”。
字的前缀是指该字的任意首部，例如，字abc的前缀有ε、a、ab或abc。所谓活前缀，是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。之所以称为活前缀，是因为在其右边增添一些终结符号后，就可以使它成为一个规范句型。
引入活前缀的意义在于它是构造LR(0)项目集规范族时必须用到的一个重要概念。
对于一个文法G，首先要构造一个NFA，它能识别G的所有活前缀，这个NFA的每个状态即为一个“项目”。文法G每一个产生式的右部添加一个圆点称为G的一个LR(0)项目(简称项目)，可以使用这些项目状态构造一个NFA。我们能够把识别活前缀的NFA确定化，使之成为一个以项目集为状态的DFA，这个DFA就是建立LR分析算法的基础。构成识别一个文法活前缀的DFA项目集(状态)的全体称为这个文法的LR(0)项目集归范族。
3.19 试构造下述文法的SLR(1)分析表。
G[S]: S→bASB | bA
A→dSa | e
B→cAa | c
【解答】 首先将文法G[S]拓广为G[S′]:
G[S′]： (0) S′→S
(1)  S→bASB
(2)  S→bA
(3)  A→dSa
(4)  A→e
(5)  B→cAa
(6)  B→c
构造文法G[S′]的LR(0)项目集规范族如下：
  I0: S′→·S I5: A→e·
S→·bASB I6: S→bAS·B
S→·bA B→·cAa
I1: S′→S· B→·c
I2: S→b·ASB I7: A→dS·a
S→b·A I8: S→bASB·
A→·dSa I9: B→c·Aa
A→·e B→c·
I3: S→bA·SB A→·dSa
S→bA· A→·e
S→·bASB I10: A→dSa·
S→·bA I11: B→cA·a
I4: A→d·Sa I12: B→cAa·
S→·bASB
S→·bA
文法G[S′]的DFA如图3-11所示。

图3-11 文法G[S′]的DFA
注意，在比较熟练的情况下，也可以不构造LR(0)项目集规范族而直接画出文法G[S′]的DFA。
由于I3和I9既含有移进项目又含有归约项目，故文法G[S]不是LR(0)文法。我们构造文法G[S′]的FOLLOW集如下：
(1) FOLLOW(S′)={#}；
(2) 由S→…AS…得FIRST(S)\{ ε}FOLLOW(A)；即FOLLOW(A)={b}；
由S→…SB得FIRST(B)\{ ε}FOLLOW(S)；即FOLLOW(S)={c}；
由A→…Sa得FIRST(′a′)\{ ε}FOLLOW(S)；即FOLLOW(S)={a,c}；
(3) 由S′→S得FOLLOW(S′)FOLLOW(S)，即FOLLOW(S)={a,c,#}；
由S→…B得FOLLOW(S)FOLLOW(B)，即FOLLOW(B)={a,c,#}；
由S→…A得FOLLOW(S)FOLLOW(A)，即FOLLOW(A)={a,b,c,#}；
对I3有：{b}∩FOLLOW(S)={b}∩{a,c,#}=Φ
对I9有：{d,e}∩FOLLOW(B)={d,e}∩{a,c,#}= Φ
故文法G[S]是SLR(1)文法。最后得到SLR(1)分析表见表3-9。
表3-9 SLR(1)分析表

3.20 LR(0)、SLR(1)、LR(1)及LALR有何共同特征？它们的本质区别是什么？
【解答】 LR(0)、SLR(1)、LR(1)及LALR的共同特征是都用规范归约的方法寻找句柄，即LR分析器的每一步工作都是由栈顶状态和现行输入符号所唯一决定的。它们的本质区别是寻找句柄的方法不同。如果当前的栈顶状态为归约状态(即有形如A→α·的项目属于栈顶状态)，则：
(1) 对LR(0)来说，无论现行输入符号是什么，都认为栈顶的符号串为句柄而进行归约。
(2) 对SLR(1)来说，则对现行输入符号加了一点限制，即该输入符号必须属于允许跟在句柄之后的字符范围内，才认为栈顶的符号串为句柄而进行归约。
(3) 对LR(1)来说，对现行输入符号的限制则更加严格，它在该输入符号跟在栈顶符号串后形成一个规范句型的前缀时，才认为栈顶的这个符号串为句柄，从而进行归约。由于要对不同的输入符号进行判断，因此LR(1)的状态数要比LR(0