(完整版)编译原理[张素琴]第2版-答案-清华大学出版社 下载本文

语法:表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。

语义:表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。

第4 章 词法分析

第5 章 自顶向下语法分析方法

第1 题对文法G[S] S→a|∧|(T) T→T,S|S

(1) 给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。

(2) 对文法G,进行改写,然后对每个非终结符写出不带回溯的递归子程序。 (3) 经改写后的文法是否是LL(1)的?给出它的预测分析表。

(4) 给出输入串(a,a)#的分析过程,并说明该串是否为G 的句子。 答案:(1) 对(a,(a,a)的最左推导为:

S=>(t) => (T,S) => (S,S) => (a,S) => (a,(T)) => (a,(T,S)) => (a,(S,S)) => (a,(a,S)) => (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)

(2) 改写文法为: 0) S→a 1) S→∧ 2) S→( T ) 3) T→S N 4) N→, S N 5) N→ε

非终结符 FIRST 集 FOLLOW 集 S {a,∧,(} {#,,,)} T {a,∧,(} {)}.... N {,,ε} {)}....

对左部为N 的产生式可知: FIRST (→, S N)={,} FIRST (→ε)={ε} FOLLOW (N)={)}

由于SELECT(N →, S N)∩SELECT(N →ε) ={,}∩ { )}= 所以文法是LL(1)的。

预测分析表(Predicting Analysis Table)

也可由预测分析表中无多重入口判定文法是LL(1)的。 (3) 对输入串(a,a)#的分析过程为:

可见输入串(a,a)#是文法的句子。 第3 题

已知文法G[S]:

S→MH|a H→LSo|ε K→dML|ε L→eHf M→K|bLM

判断G 是否是LL(1)文法,如果是,构造LL(1)分析表。 答案:

文法展开为: 0) S→M H 1) S→a 2) H→L S o 3) H→ε

4) K→d M L 5) K→ε 6) L→e H f 7) M→K 8) M→b L M

非终结符 FIRST 集 FOLLOW 集 S {a,d,b,ε,e} {#,o} M {d,ε,b} {e,#,o} H {ε,e} {#,f,o} L {e} {a,d,b,e,o,#} K {d,ε} {e,#,o} 对相同左部的产生式可知:

SELECT(S→M H)∩SELECT(S→a) ={ d,b ,e,#,o }∩ { a }= SELECT(H→L S o)∩SELECT(H→ε) ={ e }∩ { #,f,o }= SELECT(K→d M L)∩SELECT(K→ε) ={ d }∩ { e,#,o }= SELECT(M→K)∩SELECT(M→b L M) ={ d,e,#,o }∩ { b }= 所以文法是LL(1)的。 预测分析表:

由预测分析表中无多重入口也可判定文法是LL(1)的。 第7 题

对于一个文法若消除了左递归,提取了左公共因子后是否一定为LL(1)文法?试对下面 文法进行改写,并对改写后的文法进行判断。

(1)A→baB|ε

B→Abb|a

(2) A→aABe|a B→Bb|d

(3) S→Aa|b A→SB B→ab

答案:(1)先改写文法为:

0) A→baB 1) A→ε 2) B→baBbb 3) B→bb 4) B→a

再改写文法为:

0) A→baB 1) A→ε 2) B→bN 3) B→a 4) N→aBbb 5) N→b

预测分析表:

由预测分析表中无多重入口判定文法是LL(1)的。 (2) 文法: A→aABe|a B→Bb|d

提取左公共因子和消除左递归后文法变为:

0) A→a N 1) N→A B e 2) N→ε 3) B→d N1 4) N1→b N1 5) N1→ε

非终结符 FIRST 集 FOLLOW 集 A {a} {#,d} B {d} {e} N {a,ε} {#,d} N1 {b,ε} {e}

对相同左部的产生式可知:

SELECT(N→A B e)∩SELECT(N→ε) ={ a }∩ {#,d }= SELECT(N1→b N1)∩SELECT(N1→ε) ={ b }∩ { e }= 所以文法是LL(1)的。

预测分析表(Predicting Analysis Table)

也可由预测分析表中无多重入口判定文法是LL(1)的。 (3)文法:

S→Aa|b A→SB B→ab

第1 种改写:用A 的产生式右部代替S 的产生式右部的A 得:

S→SBa|b B→ab

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

非终结符 FIRST 集 FOLLOW 集 S {b} {#} B {a} {a} N {ε,a} {#}

对相同左部的产生式可知:SELECT(N→B a N)∩SELECT(N→ε) ={ a }∩ {# }=