精品文档

第五章 习题参考答案

1、(1) 对(a,(a,a)的最左推导为：S(a,(a,S))((S,S,S),S)

(a,(a,a))

(T)

(T,S)

(S,S)

((T),S)

((T,S),S)

((T,S,S),S)(((a,a),∧,S),S)

(((T),S,S),S)

(((T,S),S,S),S)(((a,a),∧,(S)),S)

(((S,S),S,S),S)(((a,a),∧,(a)),S)

(((a,S),S,S),S)

(((a,a),S,S),S)

(T)

(T,S)

(S,S)

(a,S)

(a,(T))

(a,(T,S))

(a,(S,S))

对(((a,a),∧,(a)),a) 的最左推导为：S(((a,a),∧,(T)),S)

(((a,a),∧,(a)),a)

对((( a, a ), ?, ( a )), a )的最左推导为：S ? ( T ) ? ( T, S ) ? ( S, S ) ? (( T ), S ) ? (( T, S ), S )

?(( T, S, S ), S )

? (( S, S, S ), S ) ? ((( T ), S, S ), S ) ? ((( T, S ), S, S ), S ) ? ((( S, S ), S, S ), S ) ? ((( a, S ), S, S ), S ) ? ((( a, a ), S, S ), S ) ? ((( a, a ), ?, S ), S ) ? ((( a, a ), ?, ( T )), S ) ? ((( a, a ), ?, ( S )), S ) ? ((( a, a ), ?, ( a )), S ) ? ((( a, a ), ?, ( a )), a )

对((( a, a ), ?, ( a )), a )的最左推导为：S ? ( T ) ? ( T, S ) ? ( T, a ) ? ( S, a ) ? (( T ), a ) ? (( T, S ), a )? (( T, ( T )), a ) ? (( T, ( S )), a ) ? (( T, ( a )), a ) ? (( T, S, ( a )), a ) ? (( T, ?, ( a )), a ) ? (( S, ?, ( a )), a ) ? ((( T ), ?, ( a )), a ) ? ((( T, S ), ?, ( a )), a ) ? ((( T, a ), ?, ( a )), a ) ? ((( S, a ), ?, ( a )), a ) ? ((( a, a ), ?, ( a )), a )

(2) 改写文法为：

0) S→a 1) S→∧ 2) S→( T ) 3) T→S N 4) N→, S N 5) N→ε

S: T: 入口 入口 N: 入口 N

a

Y S Y ， Read(w) N ^ N Y N ( Y N

出口 S Read(w) 出错 N T

出口 N ) 精品文档

精品文档

Read(w) 出口 (3) 非终结符 S T N 对左部为N的产生式可知：

SELECT(S→a)∩SELECT(S→∧) ∩SELECT(S→( T ))= SELECT(N →, S N)∩SELECT(N →ε) ={，}∩ { )}= 所以文法是LL(1)的。 预测分析表

FIRST集 {a,∧,(} {a,∧,(} {,,ε}. FOLLOW集 {#,,,)} {)}.... {)}.... S T N a →a →S N ∧ ( →(T) →S N ) →ε , →, S N # →∧ →S N 也可由预测分析表中无多重入口判定文法是LL(1)的。 (4) 对输入串（a,a）#的分析过程为：

栈（STACK） 当前输入符（CUR_CHAR） 剩余输入符（INOUT_STRING） 所用产生式（OPERATION） #S #)T( #)T #)NS #)Na #)N #)NS, #)NS #)Na #)N #) # ( ( a a a , , a a ) ) # a,a)#... a,a)#... ,a)#... ,a)#... ,a)#... a)#... a)#... )#... )#... #... #... .. S→(T) . T→SN S→a . N→,SN . S→a . N→ε 可见输入串（a,a）#是文法的句子。

精品文档

精品文档

6.(2) 不是LL(1)文法

以A的产生式代入S，以D的产生式代入B中，提取左公共因子并删除多余产生式得文法： S→BC 分析表为 S B C F a BC F aB ε b BC F b d BC dF # BC F ε ε C→aB|ε

B→dF|F F→b|ε

结论：经改写之后的文法Ｇ是ＬＬ（１）文法。 递归下降分析器如同题1，从略

6.(4)消除左递归为： S→i E F S S→(E)

+ +SF

E→SF

- -SF F→+SF

i SF i F→-SF

F→ε ( SF (E) ) ε ﹟ 分析表为：

结论：经改写之后的文法Ｇ是ＬＬ（１）文法。 递归下降分析器如同题1，从略

7.(1)文法不存在左递归

第一种改法：以A的产生式替入B 产生式中 B→baBbb B→bC B C B→bb

B→a

B→a

b bC b # 消除左公共因子：

C→aBbb C→b

a a aBbb 改写之后的文法的分析表：

改写之后的文法是LL(1)文法

第二种改法：以B的产生式替入A产生式中 A→baAbb A→ε

A→baa

A→ε

C→a

消除左公共因子后为

A→baC

C→Abb

SELECT(A→baC) ∩ SELECT(A→ε) ={ b}∩ {# ,b }≠ 所以，改写之后的文法不是LL(1)文法

7.(3)第1种改写：用A的产生式右部代替S的产生式右部的A得：

精品文档

精品文档

S→SBa|b B→ab 消除左递归后文法变为： 0) S→b N 1) N→B a N 2) N→ε 3) B→a b

非终结符 S B N FIRST集 {b}... {a}... {ε,a} FOLLOW集 {#} {a} {#} SELECT(N→B a N)∩SELECT(N→ε) ={ a }∩ {# }= 所以文法是LL(1)的。 预测分析表

S B N a →a b →B a N b →b N # →ε 第2种改写：用S的产生式右部代替A的产生式右部的S得： S→Aa|b

A→AaB|bB B→ab

消除左递归后文法变为：

0) S→A a 1) S→b 2) A→b B N 3) N→a B N 4) N→ε 5) B→a b

非终结符 S A B N FIRST集 {b}... {b}... {a}... {a,ε}

FOLLOW集 {#} {a} {a} {a} SELECT(S→A a)∩SELECT(S→b) ={ b }∩ { b }={ b }≠SELECT(N→a B N)∩SELECT(N→ε) ={ a }∩ { a }={ a }≠所以文法不是LL(1)的。

7.(5)以A、B的产生式代入S的产生式中的A、B，得新文法： S→aC S→aC S→aC S→aC

C→Ab|b|a

A→aA|a

A→aA|a

以A的产生式代入C中提取左公共因子得：

C→aD|b D→Ab|b|ε C→aD|b D→aE|ε C→aD|b D→aE|ε

以A的产生式代入D中提取左公共因子得：

E→Ab|b A→aA|a E→aF

F→Ab|b A→aA|a

以A的产生式代入E中提取左公共因子得：

精品文档