编译原理教程课后习题答案 - 第三章

第三章 语法分析

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所示的两棵语法树。 SS

aSbSb

aSbaSb SbaSb

bb

图3-1 句子aabbbb对应的两棵不同语法树

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

SS

SaSSaS

SaS??SaS ????(a)(b)

图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]如下： A G[S]：S→aA|bB

ba A→aS|bC|b

B→bS|aC|a C→bA|aB|ε

aSbBbabCa图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)、

S(b)所示。

SaAcB

aAcB AaBbScA bScABdc图3-4 习题3.6的语法树

Bdc b (a ) (b ) (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所示。

S

(L)

L,S

S(L)图3-5 句型(S,(a))的语法树

Sa(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 DT→int|long|short

DTLL→idL

TLintaL′

intL,c,bL′

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

a?(a)(b) (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 预测分析表 a b l d # A A→aA′ A′ A′→ABl A′→ε A′→ε B B→dB′ B′ B′→bB′ B′→ε

(3) 输入串aadl的分析过程见表3-2。 表3-2 输入串aadl的分析过程 符号栈 当前输入符号 输入串 说 明 a adl# 弹出栈顶符号A并将A→aA′产生式右部反序压栈 #A a a adl# 匹配，弹出栈顶符号a并读出下一个输入符号a #A′a dl# 弹出栈顶符号A′并将A′→ABl产生式右部反序压栈 #A′ a dl# 弹出栈顶符号A并将A→aA′产生式右部反序压栈 #lBA #lBA′a a dl# 匹配，弹出栈顶符号a并读出下一个输入符号d

#lBA′ d l# 由A′→ε仅弹出栈顶符号A′

#lB d l# 弹出栈顶符号B并将B→dB′产生式右部反序压栈

#lB′d d l# 匹配，弹出栈顶符号d并读出下一个输入符号l

#lB′ l # 由B′→ε仅弹出栈顶符号B′ #l l # 匹配，弹出栈顶符号l并读出下一个输入符号# # # 匹配，分析成功

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的优先关系表 + * i + ? ? ?

* ? ? ?

i ? ?

用关系图构造优先函数的方法是：对所有终结符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。

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

＋*i

+ * i

f 2 4 4

g 1 3 5

13gg*5gi＋

图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 优先函数的计算过程表

迭代次数 函数 + * i

f 1 1 1 0(初值) g 1 1 1

f 2 3 3 1 g 1 2 4

f 2 3 3 2 g 1 3 4

f 2 4 4

3 g 1 3 5 f 2 4 4 4 g 1 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的算符优先关系表

a b ( ) d #

a ? ? ? b ? ? ? ( ? ? ? ? ) ? ? ?

d ? ? ? ? ?

# ? ? ?

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

(A)

SdA SdA

SdASdA

SS图3-8 句型(SdSdS)的语法树 .(＜.d.＜.d＞.)＞##＜由图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)# 移进 #( adb)# 移进 #(a db)# 用S→a归约 #(S db)# 移进 #(Sd b)# 移进 #(Sdb )# 用S→b归约 #(SdS )# 用A→S归约 #(SdA )# 用A→SdA归约 #(A )# 移进 #(A) # 用S→(A)归约 #S # 分析成功 为便于分析，同时给出了(adb)#的语法树，如图3-10所示。

S

(A) SdA

aS

b图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 优先关系表 a b c a ? ? ? ? b ? ? c ? ?

(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所示。

S I：S→bAS·BBA I3：S→bA·SBb I6 I：S′→·S I8：S→bASB·0 S→bA·2：S→b·ASB B→·cAa S→·bASB S→b·A S→·bASB B→·c S→·bA A→·dSab S→·bA A→·ecSe eA I：A→e·5 I：B→cA·adb I11 I9：B→c·Aa1：S′→S·S B→c·a I I：A→d·Sa7：A→dS·a4 A→·dSa S→·bASB a I：B→cAa· A→·e12 S→·bA I：A→dSa· 10d 图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)分析表

ACTION GOTO 状态 a b c d e # S A B 0 s2 1 1 acc 2 s4 s5 3

3 r2 s2 r2 r2 6

4 s2 7

5 r4 r4 r4 r4

6 s9 8 7 s10 8 r1 r1 r1 9 r6 r6 s4 s5 r6 11

10 r3 r3 r3 r3

11 s12

12 r5 r5 r5

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)、SLR(1)多。 (4) LALR从本质上讲与LR(1)相同，只不过它把那些栈顶符号串相同但现行输入符号不同(即认为这个相同的栈顶符号串为同心)的判断合一(使状态数又减少到与LR(0)、SLR(1)一样)，只有输入符号跟在栈顶符号串后面形成一规范句型前缀时，才认为栈顶的这个符号串为句柄而进行归约。 对于同心的栈顶符号串而言，由于面对不同的输入符号将形成不同规范句型的前缀，这就给归约带来一些困难；也即，当输入串有误时，LR(1)能够及时地发现错误，而LALR则可能还继续执行一些多余的归约动作，但决不会执行新的移进，即LALR能够像LR(1)一样准确地指出出错的地点。此外，LALR这种同心集的合并有可能带来新的“归约”/“归约”冲突。 3.21 请指出图3-12中的LR分析表(a)、(b)、(c)分属LR(0)、SLR(1)和LR(1)中的哪一种，并说明理由。

【解答】 我们知道，LR(0)、SLR(1)和LR(1)分析表构造的主要差别是构造算法(2)。其区别如下： (1) 对LR(0)分析表来说，若项目A→α·属于Ik(状态)，则对任何终结符a(或结束符#)，置ACTION[k,a]为“用产生式A→α进行归约(A→α为第j个产生式)”，简记为“rj”。表现在ACTION子表中，则是每个归约状态所在的行全部填满“rj”；并且，同一行的“rj”其下标j相同，而不同行的“rj”其下标j是不一样的。

ACTIONGOTO 状态b#SBACTIONGOTOACTIONGOTO 状态状态0s312ab#Tik#P

0s2s310s1s321acc

2s451accg1s1s3

3r22s2s32acc

4r23r2r2r23r2

5r14r1r1r14r1

(a)(b)(c)

图3-12 LR分析表

(2) 对SLR(1)分析表来说，若项目A→α·属于Ik，则对任何输入符号a，仅当a∈FOLLOW(A)时置ACTION[k,a]为“用产生式A→α进行归约(A→α为第j个产生式)”，简记为“rj”。表现在ACTION子表中，则存在某个归约状态所在的行并不全部填满rj，并且不同行的“rj”其下标j不同。

(3) 对LR(1)来说，若项目[A→α·,a]属于Ik(状态)，则置ACTION[k,a]为“用产生式A→α进行归约”，简记为“rj”。LR(1)是在SLR(1)状态(项目集)的基础上，通过状态分裂的办法(即分裂成更多的项目集)，使得LR分析器的每个状态能够确切地指出当α后跟哪些终结符时才容许把α归约为A。例如，假定[A→α·,a]属于Ik(状态)，则置ACTION[k,a]栏目为rj(A→α为第j个产生式)；而[A→α·,b]属于Im(状态)，则同样置ACTION[m,b]栏目为rj。表现在ACTION子表中，则在不同的行(即不同的状态)里有相同的rj存在。

因此，图3-12(a)的分析表为LR(1)分析表(在不同行有相同的r2存在)；图3-12(b)为LR(0)分析表(有rj的行是每行都填满了rj且同一行rj的j相同，不同行rj的j不同)；而图3-12(c)为LR(0)分析表(存在并不全部填满rj的行，且不同行rj的j不同)。 3.22 文法G(S)的产生式集为 S→(EtSeS) | (EtS) | i =E E→+EF | F F→*Fi | i 构造文法G的SLR(1)分析表，要求先画出相应的DFA。 【解答】 将文法G拓广为文法G[S′]：(0)S′→S (1) S→(EtSeS) (2) S→(EtS) (3) S→i=E (4) E→+EF (5) E→F (6) F→*Fi (7) F→i

列出LR(0)的所有项目： 1. S′→·S 9. S→ (EtSeS·) 17. S→·i=E 25. E→·F 2. S′→S· 10. S→ (EtSeS)· 18. S→i·=E 26. E→F· 3. S→·(EtSeS) 11. S→·(EtS) 19. S→i=·E 27. F→·*Fi 4. S→ (·EtSeS) 12. S→ (·EtS) 20. S→i=E· 28. F→*·Fi 5. S→ (E·tSeS) 13. S→ (E·tS) 21. E→·+EF 29. F→*F·i 6. S→ (Et·SeS) 14. S→ (Et·S) 22. E→+·EF 30. F→*Fi· 7. S→ (EtS·eS) 15. S→ (EtS·) 23. E→+E·F 31. F→·i 8. S→ (EtSe·S) 16. S→ (EtS)· 24. E→+EF· 32. F→i· 用ε_CLOSURE方法构造文法G[S′]的LR(0)项目集规范族： I0: S′→·S I5: S→ (EtS·eS) I13: E→+·EF S→·(EtSeS) S→ (EtS·) E→·+EF S→·(EtS) I6: S→ (EtSe·S) E→·F S→·i=E S→·(EtSeS) I14: E→+E·F I1: S′→S· S→·(EtS) F→·*Fi I2: S→ (·EtSeS) S→·i=E F→·i S→ (·EtS) I7: S→ (EtSeS·) I15: E→+EF· E→·+EF I8: S→ (EtSeS)· I16: E→F· E→·F I9: S→ (EtS)· I17: F→*·Fi I3: S→(E·tSeS) I10: S→i·=E F→·*Fi S→(E·tS) I11: S→i=·E F→·i I4: S→ (Et·SeS) E→·+EF I18: F→*F·i

S→ (Et·S) E→·F I19: F→*Fi· S→·(EtSeS) I12: S→i=E· I20: F→i· S→·(EtS) S→·i=E 文法G[S′]的DFA如图3-13所示。

( I：S′→S·1 I：6 ( S→(EtSe·S)S I 5： S→·(EtSeS) S→(EtS·eS) I： I：S S→·(EtS)I It3E 2：40：e S→(EtS·) S→(E·tSeS) S→(Et·SeS) S→·i＝ES′→·S( S→(·EtSeS) S→(E·tS) S→(Et·S)S→·(EtSeS) S→(·EtS))S S→·(EtSeS) S→·(EtS) E→·＋EFi＋ I：S→(EtS)· S→·(EtS)9S→·i＝E E→·F i I：S→(EtSeS·)7 S→·i＝E )Fi I8：S→(EtSeS)· F* I：E→F·＝ I1611：S→i·＝E ＝· S→iEiF E→· I I： ＋EF＋20：F→i·17 E→·F F→*·Fi I：13 * F→·*Fi E→＋·EFFE I：F→*F·i I：E1814 F→·i E→·＋EF E E→＋E·F I：S→i12i ＝E· E→·F F→·*FiF F→·i I：E→＋EF· I：F→*Fi· 1519＋ 图3-13 习题3.22的DFA

构造SLR(1)分析表必须先求出所有形如“A→α·”的FOLLOW(A)，即由FOLLOW集的构造方法求得G[S′]的FOLLOW集如下： (1) FOLLOW(S′)={#}； (2) 由S→(EtSeS)得FIRST(′t′) ? FOLLOW(E)，即FOLLOW(E)={t}； FIRST(′e′) ? FOLLOW(S)，即FOLLOW(S)={e}； FIRST(′) ′) ? FOLLOW(S)，即FOLLOW(S)={e,)}； 由F→*Fi得FIRST(′i′) ? FOLLOW(F)，即FOLLOW(F)={i}； 由E→+EF得FIRST(′F′)/{ε}? FOLLOW(E)，即 FOLLOW(E)={t,i}； (3) 由S′→S得FOLLOW(S′) ? FOLLOW(S)，即FOLLOW(S)={e,),#}； 由S→i=E得FOLLOW(S) ? FOLLOW(E)，即FOLLOW(E)={t,i,e,),#}； 由E→F得FOLLOW(E) ? FOLLOW(F)，即FOLLOW(F)={t,i,e,),#}。 最后得到SLR(1)分析表，见表3-10。

表3-10 习题3.22的SLR(1)分析表

ACTION GOTO

状态 t + e ( ) * = i # S E F

0 s10 1

1 acc

2 s13 3 16 3 s4 4 s2 s10 5 5 s6 s9 6 s2 s10 7

7 s8

8 r1 r1 r1

9 r2 r2 r2

10 s11 11 s13 12 16 12 r3 r3 r3 13 s13 14 16

14 s17 15

15 r4 r4 r4 r4 r4

16 r5 r5 r5 r5 r5

17 s17 s20 18 18 s19 19 r6 r6 r6 r6 r6 20 r7 r7 r7 r7 r7

3.23 为二义文法G[T]构造一个LR分析表(详细说明构造方法)。其中终结符“，”满足右结合性，终结符“；”满足左结合性，且“，”的优先级高于“；”的优先级。 G[T]: T→TAT | bTe | a A→, | ; 【解答】 首先将文法G[T]拓广为文法G[S]：(0) S→T

(1) T→TAT (2) T→bTe (3) T→a (4) A→， (5) A→；

下面列出LR(0)的所有项目： 1．S→·T 5．T→TA·T 9．T→bT·e 13．A→·， 2．S→T· 6．T→TAT· 10．T→bTe· 14．A→，· 3．T→·TAT 7．T→·bTe 11．T→·a 15．A→·; 4．T→T·AT 8．T→b·Te 12．T→a· 16．A→; · 用ε_CLOSURE方法构造文法G[S]的LR(0)项目集规范族，并根据转换函数GO构造出文法G[S]的DFA，如图3-14所示。

I：S→·T0 T→·TAT T→·bTe T→·abT I3：S→T· T→T·AT A→·， A→·；，；Ab I4：T→TA·Ta T→·TAT T→·bTe T→·aTA IT·8：T→TA， T→T·AT A→·， A→·；， I5：A→，·；a I6：A→；·； I1：T→a·a I2：T→b·Te T→·TAT T→·bTeT T→·ab图3-14 习题3.23中文法G[S]的DFA

；A I：T→bT·e7 T→T·AT A→·，e A→·； I：T→bTe·9已知文法G[S]为二义文法，故必然存在冲突。逐一检查各状态，得知I8存在“移进”/“归约”

冲突(因为T→TAT·要求归约，而T→T·AT却要求移进)。在此，LR(0)已不能满足要求，因为LR(0)分析表中的ACTION子表在某归约状态下(即某一行)的所有栏目全被“rj”占满，但由于存在“移进”/“归约”冲突，即在此状态下，有些栏目应填为“Sj”(即归约)。为了减少冲突，最好采用SLR(1)、LR(1)或LALR分析表。这里采用SLR(1)分析表。 下面，构造文法G[S]中非终结符的FIRST集和FOLLOW集如下： FIRST(S)=FIRST(T)={a,b}; FIRST(A)={“，”,“；”} FOLLOW(S)={#}；FOLLOW(T)={“，”,“；”,e,#}； FOLLOW(A)={a,b} 因为T→TAT·要求归约，而T→T·AT要求移进，即对T要求归约而对A要求移进，则有： FOLLOW(T)∩FIRST(A)={“，”,“；”,e,#}∩{“，”,“；”}={“，”,“；”}≠Φ 也即冲突字符为“，”和“；”。 下面分析“，”与“；”的具体情况。因为“，”的优先级高且有右结合，故不论是“，”还是“；”，遇见“，”其后的“，”一定移进；类似地，“；”优先级低且有左结合，则无论是“，”还是“；”，遇见其后的“；”一定归约。由此可得到SLR(1)分析表，见表3-11。 从分析表中可以看到，本应该对在状态8对应ACTION子表中的字符集{e,“，”,“，”,#}都执行用r1归约，但“，”和“；”存在“移进”/“归约”冲突，由于“，”的优先级高且有右结合，故对应ACTOIN[8, “，”]栏改为s5，即移进；由于“；”满足左结合性，即应归约，所以ACTION[8,“，”]栏仍为r1。

表3-11 习题3.23的SLR(1)分析表 ACTION GOTO

状态 a b E ， ; # A T s1 s2 3 0

r3 r3 r3 r3 1

s1 s2 7 2

s5 s6 acc 4 3

s1 s2 8 4 r4 r4 5 r5 r5 6 7 8 9 s9 r1 r2 s5 s5 r2 s6 r1 r2 r1 r2 4 4

注意，如果将条件改为“，”的优先级高且满足左结合，则将无法构造分析表。这是因为“，”在遇见其后的“，”时要求归约；而“；”在遇见其后的“，”时则要求移进；这时ACTION[8,“，”]栏就无法确定是放“r1”还是放“s5”了。 3.24 文法G[T]及其SLR(1)分析表(见表3-12)如下，给出串bibi的分析过程。 G[T]:(1) T→EbH (2) E→d (3) E→ε (4) H→i

(5) H→Hbi (6) H→ε

表3-12 习题3.24的SLR(1)分析表 ACTION GOTO 状态 b d i # T E H

0 r3 s3 1 2

1 acc

2 s4

3 r2

4 r6 s6 r6 5

5 s7 r1 6 r4 r4 7 s8 8 r5 r5 【解答】 对句子bibi，先构造它的语法树，如图3-15所示。 T

EbH

?Hbi i图3-15 句子bibi的语法树

bibi的分析过程参考该语法树进行，见表3-13。 表3-13 bibi的分析过程

输入串 状态 归约产生式 符号

0 r3 # bibi# 02 #E bibi# 024 #Eb ibi# 0246 r4 #Ebi bi# 0245 #EbH bi# 02457 #EbHb i# 024578 r5 #EbHbi # 0245 r1 #EbH #

01 #T #

acc

3.25 给出文法G[S]及图3-16所示的LR(1)项目集规范族中的0、1、2、3、4。 G[S]: S→S;B | B B→BaA | A

A→b(S) 01 S →·S, #′2

3

4

图3-16 习题3.25的部分项目集

【解答】 首先求出G[S]中所有非终结符的FOLLOW集。 已知FOLLOW(S′)={#}；则： 由S′→S得FOLLOW(S′) ?FOLLOW(S)，即FOLLOW(S)={#}； 由S→S;…得FOLLOW(S)={#,;}； 由A→…S)得FOLLOW(S)={#,;,)}； 由B→Ba…得FOLLOW(B)={a}；

由S→B得FOLLOW(S) ?FOLLOW(B)，即FOLLOW(B)={#,;,),a}； 由B→A得FOLLOW(B) ?FOLLOW(A)，即FOLLOW(A)={#,;,),a}。 LR(1)的闭包CLOSURE(I)可按如下方法构造： (1) I的任何项目都属于CLOSURE(I)。 (2) 若项目[A→α·Bβ,a]属于CLOSURE(I)，B→γ是一个产生式，对FIRST(βa)中的每个终结符b，如果[B→·γ,b]原来不在CLOSURE(I)中，则把它加进去。 (3) 重复执行步骤(2)，直至CLOSURE(I)不再增大为止。 注意，b可能是从β推出的第一个符号，若β推出ε，则b就是a。 我们先构造LR(1)项目集族的I0。 由FOLLOW(S)={#}可知[S′→·S,#]∈CLOSURE(I0)。此时β=ε，故b=a=“#”，即有： [S→·S;B,#]∈CLOSURE(I0) [S→·B,#]∈CLOSURE(I0) 此时对B→·γ而言，因β=ε，即b=a=“#”。 对[S→·S;B,#]，由于β≠ε，而FIRST(β)=FIRST(′;B′)={;}；则有： [S→·S;B,#/;]∈CLOSURE(I0) [S→·B,#/;]∈CLOSURE(I0) 同时有： [B→·BaA,#/;]∈CLOSURE(I0) [B→·A,#/;]∈CLOSURE(I0) 此时对A→·γ而言，因β=ε，即b=a=“#/;”。 对[B→·BaA,#]，由于β≠ε，而FIRST(β)=FIRST(′aA′)={a}；则有： [B→·BaA,#/;/a]∈CLOSURE(I0) [B→·A,#/;/a]∈CLOSURE(I0) 同时有：[A→·b(S),#/;/a]∈CLOSURE(I0)

S1 S →S·,#′′ S →·S,#0 S→S·;B,#/; S→·S;B,#/; B2 S→B·,#/; S→·B,#/; B→B·aA,#/;/a B→·BaA,#/;/a

A3 B→A·,#/;/a B→·A,#/;/ab4

A→b·(S),#/;/a A→·b(S),#/;/a

图3-17 习题3.25的LR(1)部分项目集

3.26 一个非LR(1)的文法如下： L→MLb | a M→ε 请给出所有“移进”/“归约”冲突的LR(1)项目集，以说明该文法确实不是LR(1)的。 【解答】 先将文法G[L]拓广为G[L′]：(0) L′→L 1) L→MLb (2) L→a (3) M→ε 如果按LR(1)方法构造分析表时出现“移进”/“归约”冲突，则项目集规范族中一定包含如下形式的项目： [A→α·bβ,a] 和 [A→α·,b] 即移进符号与向前搜索符号相同。 在构造LR(1)项目集族之前，我们先求出G[L′]中所有非终结符的FIRST集和 FOLLOW集：

FIRST(L′)=FIRST(L)={a, ε} FIRST(M)={ ε} 由FOLLOW集构造方法知FOLLOW(L′)={#}； 由L→…Lb 得FIRST(′b′) ? FOLLOW(L)，即FOLLOW(L)={b}； 由L→ML… 得FIRST(L)\\{ ε}? FOLLOW(M)，即FOLLOW(M)={a}； 由L′→L得FOLLOW(L′) ? FOLLOW(L)，即FOLLOW(L)={#,b}。 LR(1)闭包CLOSURE(I)构造方法如下： (1) I的任何项目都属于CLOSURE(I)。 (2) 若项目[A→α·Bβ,a]属于CLOSURE(I)，B→γ是一个产生式，对FIRST(βa)中的每个终结符b，如果[B→·γ,b]原来不在CLOSURE(I)中，则把它加进去。 (3) 重复执行步骤(2)，直至CLOSURE(I)不再增大为止。 注意，b可能是从β推出的第一个符号，若β推出ε，则b就是a。 令[L′→·L,#]∈CLOSURE(I0)，求得项目集如下： I0：L′→·L,# I2：L→M·Lb,# I4：L→M·Lb,b L→·MLb,# L→·MLb,b L→·MLb,b L→·a,# L→·a,b L→·a,b M→·, a M→·, a M→·, a I1：L′→L·,# I3：L→ML·b,# I5：L→MLb·,# 如果一个项目中含有m个移进项目： A1→α·a1β1, A2→α·a2β2, …,Am→α·amβm

同时I中含有n个归约项目： B1→α·, B2→α·, …, Bn→α· 如果集合{a1, …,am}，FOLLOW(B1), …,FOLLOW(Bn)两两相交，则必然存在“移进”/“归约”冲突。 由I0中L→·a, #和M→·,a 可知{a}∩FOLLOW(M)={a}∩{a}≠Φ(在此α=ε)； 由I2中L→·a,b和M→·,a 可知{a}∩FOLLOW(M)≠Φ； 由I4中L→·a,b和M→·,a 可知{a}∩FOLLOW(M)≠Φ； 也即，I0 、I2 、I4三个项目集存在“移进”/“归约”冲突。 3.27 试证明任何一个SLR(1)文法一定是一个LALR(1)文法。 【解答】 我们知道，在求闭包ε_CLOSURE(I)时，构造有效的LR(1)项目集与构造LR(0)项目集是有区别的。如果A→α·Bβ属于CLOSURE(I)，且关于B的产生式是B→γ，则对LR(0)来说，项目B→·γ也属于CLOSURE(I)；而对LR(1)(假定A→α·Bβ的后续一个字符为a)，则要求对FIRST(βa)中的每个终结符b，有项目[B→·γ,b]属于CLOSURE(I)。 LR(1)、LR(0)以及SLR(1)方法的区别也仅在上述构造分析表的算法上。也即若项目 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)的要求(即限制)也比SLR(1)严格。但是对LR(1)来说，其中的一些状态(项目集)除了向前搜索符不同外，其核心部分都是相同的，也即LR(1)比SLR(1)和LR(0)存在更多的状态，但是每个LR(0)文法、SLR(1)文法都是LR(1)文法。

如果两个LR(1)项目集除去搜索符之后是相同的，则称这两个LR(1)项目集具有相同的心。当把所有同心的LR(1)项目集合并为一时，则会看到一个心就是LR(0)项目集(同时也是SLR(1)项目集)，这种LR分析法称为LALR方法。 假定有一个LR(1)文法，它的LR(1)项目集不存在动作冲突，如果我们把同心集合并为一，就可能导致冲突存在。但是这种冲突不会是“移进”/“归约”间的冲突。因为若存在这种冲突，则意味着面对当前的输入符号a，有一个项目[A→α·,a]要求采取归约动作；同时又有另一项目[B→β·aγ,b]要求把a移进。

这两个项目既然同处在合并之后的一个集合中，就意味着在合并之前必然有某个c使得[A→α·,a]和[B→β·aγ,c]同处于(合并之前的)某一集合中，然而这又意味着原来的LR(1)项目集已经存在着“移进”/“归约”冲突了，同时也意味着SLR(1)项目集也已经存在着“移进”/“归约”冲突(因为SLR(1)与合并后的LALR项目集相同。) 但是，同心集的合并有可能产生新的“归约”/“归约”冲突。假定有对活前缀ac有效的项目集为{[A→c·,d], [B→c·,e]}，对bc有效的项目集为{[A→c·,e], [B→c·,d]}，这两个集合都不含冲突，它们是同心的，但合并后就变成{[A→c·,d/e], [B→c·,d/e]}，显然这是一个含有“归约”/“归约”冲突的集合。由于SLR(1)与LALR同心(项目集相同),故在SLR(1)文法中必然存在“归约”/“归约”冲突。由此可知,任何一个SLR(1)文法一定是一个LALR(1)文法。 注意，LALR项目集族总是与同一文法的SLR(1)项目集的心相同，并且实现LALR分析对文法的要求比LR(1)严但比SLR(1)宽，而开销比SLR(1)大却远小于LR(1)。 3.28 已知文法G[S]: S→aAd | ;Bd | aB↑| ;A↑ A→a B→a

(1) 试判断G[S]是否为LALR(1)文法。 (2) 当一个文法是LR(1)而不是LALR(1)时，那么LR(1)项目集的同心集合并后会出现哪几种冲突，请说明理由。

【解答】 (1) 将文法G[S]拓广为文法G[S′]：(0) S′→S (1) S→aAd (2) S→;Bd (3) S→aB↑ (4) S→;A↑ (5) A→a (6) B→a

判断G[S]是否为LALR(1)文法的方法是：首先构造LR(1)项目集族，如果它不存在冲突，就把同心集合并在一起；若合并后的集族不存在“归约”/“归约”冲突(即不存在同一个项目集中有两个像A→c·和B→c·这样具有相同搜索符的产生式)，则表明G[S]是LALR(1)文法。 在构造LR(1)项目集族之前，先求出G[S′]中所有非终结符的FIRST集和FOLLOW集如下： FIRST(S′)= FIRST(S)={a,;} FIRST(A)={a} FIRST(B)={a} 由FOLLOW集构造方法知FOLLOW(S′)={#}； 由S′→S得FOLLOW(S′) ?FOLLOW(S)，即FOLLOW(S)={#}； 由S→…Ad和S→…A↑得FOLLOW(A)={d,↑}； 由S→…Bd和S→…B↑得FOLLOW(B)={d,↑}。 LR(1)的闭包CLOSURE(I)可按如下方法构造： ① I的任何项目都属于CLOSURE(I)； ② 若项目[A→α·Bβ,a]属于CLOSURE(I)，B→γ是一个产生式，对FIRST(βa)中的每一个终结符b，如果[B→·γ,b]原来不在CLOSURE(I)中，则把它加进去。 ③ 重复执行步骤②，直至CLOSURE(I)不再增大为止。 注意，b可能是从β推出的第一个符号，若β推出ε，则b就是a。 LR(1)项目集族构造如下： 由FOLLOW(S)={#}知S的向前搜索字符为“#”，即[S′→·S,#]。令[S′→·S,#] ∈CLOSURE(I0)，我们来求出属于I0的所有项目。已知[S′→·S,#]∈CLOSURE(I0)，由LR(1)闭包CLOSURE(I)步骤①知β=ε，也即对产生式S→aAd、S→;Bd、S→aB↑、S→;A↑都有b=a=“#”。由此得到项目集I0如下： I0：S′→·S,#

S→·aAd,# S→·;Bd,# S→·aB↑,# S→·;A↑,# 同理求得其他项目： I1: S′→S·,# I4: S→aA·d,# I10: S→aAd·,# I2: S→a·Ad,# I5: S→aB·↑,# I11: S→aB↑·,# S→a·B↑,# I6: A→a·,d I12: S→;Bd·,# A→·a,d B→a·,↑ I13: S→;A↑·,# B→·a,↑ I7: S→;B·d,# I3: S→;·Bd,# I8: S→;A·↑,#

S→;·A↑,# I9: A→a·,↑ A→·a,↑ B→a·,d B→·a,d 根据LR(1)项目集族，将同心集合并(即去掉向前搜索符后两个项目的产生式相同)。经检查，只有I6与I9同心，即将I6和I9合并为I69： I69：A→a·,↑/d B→a·,↑/d 此时出现了“归约”/“归约”冲突，即对“↑”或“d”不知是用A→a·归约，还是用B→a·归约，故G[S]不是LALR文法。 (2) 当一个文法是LR(1)而不是LALR时，那么LR(1)项目集的同心集合并后只可能出现“归约”/“归约”冲突，而不会是“移进”/“归约”冲突。因为如果存在这种冲突，则意味着面对当前输入符号a，有一个项目[A→α·,a]要求采取归约动作，同时又有另一项目[B→β·aγ,b]要求把a移进。这两个项目既然同处在合并之后的一个集合中，就意味着在合并前必有某个c使得[A→α·,a]和[B→β·aγ,c]同处于(合并之前的)某一集合中，然而这又意味着原来的LR(1)项目集已经存在着“移进”/“归约”冲突了。因此，同心集的合并不会产生新的“移进”/“归约”冲突(因为是同心合并，所以只改变了搜索符，而并没有改变“移进”或“归约”操作，故不可能存在“移进”/“归约”冲突)。

但是，同心集的合并有可能产生新的“归约”/“归约”冲突。例如本题中，对活前缀aa有效的项目集为I6：{[ A→a·,d],[ B→a·,↑]}，对活前缀 ,a有效的项目集为I9：{[ A→a·,↑],[ B→a·,d]}，这两个集合都不含冲突，它们是同心的，但合并之后就变成{[ A→a·,↑/d],[ B→a·, ↑/d]}，显然这是一个含有“归约”/“归约”冲突的集合，因为当面临“↑”或“d”时我们不知道该用A→a还是B→a进行归约。

3.29 给定文法G[A]: A→(A)|a。 (1) 证明：LR(1)项目[A→(A·),]]对活前缀“((a”是有效的； (2) 画出LR(1)项目识别所有活前缀的DFA； (3) 构造LR(1)分析表； (4) 合并同心集，构造LALR(1)分析表。 【解答】 (1) 证明：首先将文法D[A]拓广为 G[A′]：(0) A′ → A (1) A → (A) (2) A → a

其次，构造文法G[A′]的FOLLOW集如下: ① FOLLOW(A′)={#}； ② 由A→…A)得FIRST(′)′)\\{ε}?FOLLOW(A)，即FOLLOW(A)={)}； ③ 由A′→A得，FOLLOW(A′) ?FOLLOW(A)，即FOLLOW(A)={),#}。 下面构造LR(1)项目集规范族，其构造方法如下： ① I的任何项目都是属于CLOSURE(I)的； ② 若项目[A→α·Bβ,a]属于CLOSURE(I)，B→γ是一个产生式，对FIRST(βa)中的每个终结符b，如果[B→·γ,b]原来不在CLOSURE(I)中，则把它加进去； ③ 重复执行步骤②，直至CLOSURE(I)不再增大为止。 注意，b可能是从β推出的第一个符号；若β推出ε，则b就是a。 由此得到文法G[A′]的LR(1)项目集规范族如下(项目集I0由A′→·A，#开始)： I0: A′→·A,# I4: A→(A·),# A′→·(A),# I5: A→(A)·,#

A→·a,# I6: A→(·A),) I1: A′→A·,# A→·(A),) I2: A→(·A),# A→·a,) A→·(A),) I7: A→(A·),) A→ ·a,) I8: A→(A)·,) I3: A→a·,# I9: A→a·,) LR(1)识别所有活前缀的DFA如图3-18所示。 而项目[A→(A·),]]对应图3-18中的I7，即由I0到达I7的活前缀(即由I0到达I7道路上的字符组成)为“(…(A”，其中“(…(”至少有两个“(”。由此得到项目[A→(A·),])对活前缀“((A”有效。 (2) LR(1)项目识别所有活前缀的DFA如图3-18所示。 (3) 构造的LR(1)分析表见表3-14。 A′ →A·,# I 1：A A) I I′ →·A,#4：A→(A·),#5：A→(A)·,# I I：A→(·A),#0：A2( ′ →·(A),# A A→·(A),)( A→·a,# A→·a,) I6：A→(·A),)A A→·(A),) I7：A→(A·),) aa A→·a,)( )a I：A→(A)·,)8 I I 3：A→a·,#9：A→a·,)图3-18 识别活前缀的DFA

表3-14 习题3.29的LR(1)分析表 ACTION GOTO 状态 ( ) a # A 0 s2 s3 I 1 acc 2 s6 s9 4 3 r2 4 s5 5 r1 6 s6 s9 7 7 s8 8 r1 9 r2 将I3、I9合并成I39：[A→a· ，)/#]； 将I2、I6合并成I26：[A→(·A)，)/#]，[A→·(A)，)]，[A→·a，)]； 将I4、I7合并成I47：[A→(A·)，)/#]； 将I5、I8合并成I58：[A→(A)· ，)/#]。 由此得到合并后集族所构成的LALR分析表，见表3-15。 表3-15 合并后集族所构成的LALR分析表

ACTION GOTO 状态 ( ) a # A

0 s26 s39 1

1 acc

26 s26 s39 47

39 r2 r2 47 s58

58 r1 r1 3.30 下述文法G[S]是哪类LR文法？构造相应LR分析表。 G[S]: (1) S→L=R (2) S→R (3) L→*R (4) L→i (5) R→L

【解答】 首先将文法G[S]拓广为G[S′]：(0) S′→S (1) S→L=R (2) S→R (3) L→*R (4) L→i (5) R→L 构造文法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集含有“#”)，则要解决隐含在I中的动作冲突，可检查现行输入符号a属于上述n+1个集合中的哪个集合，这就是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)={=,#}。 由I2的移进项目S→L·=R和归约项目R→L·得到：

{=}∩FOLLOW(L)={=}∩{=,#}={=}≠Φ 所以文法G[S]不是SLR(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·,=

此时，I2的移进项目[S→L·=R,#]和归约项目[R→L·,#]有： {=}∩{#}=Φ 故文法G[S]是LR(1)文法。最后得到LR(1)分析表，见表3-16。 表3-16 习题3.30的LR(1)分析表

ACTION GOTO

状态 = * i # S L R

0 s4 s5 1 2 3

1 acc

2 s6 r5

3 r2

4 s4 s5 8 7

5 r4

6 s11 s12 10 9 7 r3 8 r5 9 r1 10 r5 11 s11 s12 10 13 12 r4

13 r3

3.31 已知布尔表达式的文法G[B]如下：

G[B]: B→AB︱OB︱not B︱(B)︱i rop i︱i A→B and O→B or 试为G[B]构造LR分析表。 【解答】 将文法G[B]拓广为文法G[S′]：(0) S′→B (1) B→i

(2) B→i rop I (3) B→(B) (4) B→not B (5) A→B and (6) B→AB (7) O→B or (8) B→OB

列出LR(0)的所有项目： 1. S′→·B 8. B→i rop i· 15. B→not B 22. O→·B or 2. S′→B· 9. B→·(B) 16. A→·B and 23. O→B·or 3. B→·i 10. B→(·B) 17. A→B·and 24. O→B or · 4. B→i· 11. B→(B·) 18. A→B and· 25. B→·OB 5. B→·i rop i 12. B→(B)· 19. B→·AB 26. B→O·B 6. B→i· rop i 13. B→·not B 20. B→A·B 27. B→OB· 7. B→i rop ·i 14. B→not ·B 21. B→AB· 用ε_CLOSURE方法构造出文法G[S′]的LR(0)项目集规范族，并根据状态转换函数GO画出文法G[S′]的DFA，如图3-19所示。

9 or I10： ropi I I I：B→i·2：B→i rop·i3：B→i ropi·i1 B→i ·rop i′0：S →·B I B→·ii B→·i rop i B→·(B)( I：B→(·B) B→·not B4 I12：B→(B)· B→·i B→·AB I：B→(B·)11and B→·OB B→·i rop iB A→B·and I9： B→·(B) A→·B and O→B·or( O→·B or B→·not BO I10： B→·AB O B→·OBOA A→·B and Anot O→·B or (not I5：B→not·B B→·inot B→·i rop i O B→·(B) B→·not Bi B→·ABA B→·OB B→·B and B→·B or Band I I：B→not B·9：A→B and·6 A→B·and O C→B·or I10：O→B or· O I7：B→A·B B→·iandB I14：B→AB· B→·i rop i A→B·and B→·(B) O→B·or B→·not B not B→·AB B→·OB A( A→·B and O→·B or i OA Inot8：B→O·B B→·i ( B→·i rop i B→·(B)i B→·not B B→·ABandO I I：B →OB·9： B→·OB15B A→B·and A→·B andor O→B·or I： O→·B or10

图3-19 习题3.31中文法G[S′]的DFA 下面，对文法G[S′]中形如“A→α·”的项目： I13 ： S′→B· I12 ： B→(B)· I14 ： B→AB· I1 ： B→i· I6 ： B→not B· I10 ： O→B or· I3 ： B→i rop i· I9 ： A→B and· I15 ： B→OB· 求FOLLOW集。根据FOLLOW集构造方法，构造文法G[S′]中非终结符的FOLLOW集如下：

① 对文法开始符S′，#∈FOLLOW(S′)，即FOLLOW(S′)={#}。 ② 由B→…B)得FIRST(′) ′)\\{ε}?FOLLOW(B)，即FOLLOW(B)={ )}； 由B→B and得FIRST(′and′)\\{ε}?FOLLOW(B)，即FOLLOW(B)={ )，and};

B I13：S →B· A→B·and O→B·orand I： 由O→B or得FIRST(′or′)\\{ε}?FOLLOW(B)，即FOLLOW(B)={)，and,or}; 由B→AB得FIRST(B)\\{ε}?FOLLOW(A)，即FOLLOW(A)={ i，(,not) (注：FIRST(B)={ i，(,not)}；

由B→OB得FIRST(B)\\{ε}?FOLLOW(O)，即FOLLOW(O)={ i，(,not)。 ③ 由S′→B得FOLLOW(S′)?FOLLOW(B)，即FOLLOW(B)={ )，and，or,#}，由此得到FOLLOW(B)={ )，and，or,#}，FOLLOW(A)=FOLLOW(O)={ i，(,not)。 分析图3-19，可知I1、I6、I14、I15存在矛盾。I1的“移进”/“归约”矛盾可以在SLR(1)下得到解决，因为FOLLOW(B)={ )，and，or,#}，而移进仅是在字符“rop”下进行的，即有FOLLOW(B)∩{ rop }=Φ，故移进与归约不发生矛盾(归约是在字符“)”、“and”、“or”或“#”下进行的)。 而I6、I14和I15的“移进”/“归约”矛盾无法得到解决(在字符“and”和“or”下既要“移进”又要“归约”)，故文法G[S′]是一个二义文法。经分析，当B遇到后面的“and”或“or”时应移进，故服从右结合规则。由此得到布尔表达式的SLR(1)分析表见表3-17。

表3-17 习题3.31的布尔表达式的SLR(1)分析表 状ACTION GOTO 态 i rop ( ) not and or # B A O 0 s1 s4 s5 13 7 8

1 s2 r1 r1 r1 r1

2 s3

3 r2 r2 r2 r2

4 s1 s4 s5 11 7 8

5 s1 s4 s5 6 7 8

6 r4 s9 s10 r4

7 s1 s4 s5 14 7 8 8 s1 s4 s5 15 7 8 9 r5 r5 r5 10 r7 r7 r7 11 s12 s9 s10

12 r3 r3 r3 r3

13 s9 s10 acc

14 r6 s9 s10 r6

15 r8 s9 s10 r8 3.32 给出文法G[S]: S→SaS∣SbS∣cSd∣eS∣f。 (1) 请证实这是一个二义文法； (2) 给出什么样的约束条件可构造无冲突的LR分析表？请证实你的论点。 【解答】 (1) 对于语句fafbf，该文法存在两棵不同的语法树，如图3-20所示。

SS

SaSSbS

fSbSSaSf图3-20 语句fafbf的两棵不同语法树

ffff 因此，G[S]是二义文法。 (2) 首先将文法G[S]拓广为G[S′]：(0) S′→S (1) S→SaS (2) S→SbS (3) S→cSd (4) S→eS (5) S→f 该文法G[S′]的DFA如图3-21所示。 ef S′ I：S →S· I′ I：S →·S I：S→Sa·S19：S→SaS·Sa05 S→S·aS S→S·aS S→·SaS S→·SaSa S→·SbS S→S·bS S→S·bS S→·SbS S→·cSdb S→·cSdbc S→·eS S→·eS c S→·f Ie S→·f2：S→c·Sd S→·SaS S→·SbSaf S→·cSd f S→·eSc I：S→f· I：S→Sb·S4 S→·f6S S→·SaSS I：S→SbS·10 S→·SbS S→S·aSecc S→·cSdb S→S·bS e S→·eS f S→·f I3：S→e·Sf S→·SaS b S→·SbS I7：S→cS·d S→·cSdd S→S·aS I11：S→cSd· S→·eSae S→·f S→S·bS a IS8：S→eS· S→S·aSb S→S·bS 图3-21 习题3.32中G[S′]的DFA

状态I1、I8、I9和I10存在“移进”/“归约”冲突。计算G[S′]中所有非终结符的 FOLLOW集： FOLLOW(S′)={#} FOLLOW(S)={a,b,d,#} ① 对于I1：S′→S· S→S·aS S→S·bS 可以采用SLR(1)解决冲突，即当LR分析器处于状态1时，如果下一个输入符号是“#”，则按S′→S·执行归约；如果下一个输入符号是“a”或“b”，则执行移进。 ② 对于I8：S→eS· S→S·aS S→S·bS 该冲突无法采用SLR(1)解决，我们给出约束条件：让e的优先级比a和b高，则

当LR分析器处于状态8时，若下一输入符号是FOLLOW(S)中的符号，就按S→eS·执行归约。 ③ 对于I9：S→SaS· S→S·aS S→S·bS 该冲突无法采用SLR(1)解决，我们给出约束条件：让a的优先级比a和b高，即实行左结合，则当LR分析器处于状态9时，若下一输入符号是FOLLOW(S)中的符号，就按S→SaS·执行归约。 ④ 对于I10：S→SbS· S→S·aS S→S·bS 此时也给出约束条件：让b的优先级比a和b高，即实行左结合，则当LR分析器处于状态10时，若下一输入符号是FOLLOW(S)中的符号，就按S→SbS·执行归约。

综上所述，统一给出构造无冲突的LR分析表的约束条件是：左边终结符的优先级比右边终结符高，即实行左结合。另外，我们也看到，消除左递归有助于解决LR分析表中的冲突。 3.33 根据下面所给文法G[S′]和表3-18分析ia;iaea# 的语义加工过程。 G[S′]：(0) S′→S (1) S→iSeS (2) S→iS (3) S→S;S (4) S→a

【解答】 ia;iaea# 的语义加工过程见表3-19。 表3-18 习题3.33的SLR(1)分析表 ACTION GOTO 状态 i e ; a # S 0 s2 s3 1 1 s4 acc

2 s2 s3 5

3 r4 r4 r4

4 s2 s3 6

5 s7 r2 r2

6 r3 r3 r3

7 s2 s3 8

8 r1 r1 r1

表3-19 ia;iaea# 的语义加工过程

步 骤 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 02 023 025 01 014 0142 01423 01425 014257 状 态 栈 符 号 栈 # # i # ia # iS # S # S; # S;i # S;ia # S;iS # S;iSe # S;iSea # S;SeS #S;S # S 输 入 串 ia;iaea# a;iaea# ;iaea# ;iaea# ;iaea# iaea# aea# ea# ea# a# # # # # 0142573 0142578 0146 01 acc

本文来源：https://www.bwwdw.com/article/rci5.html