《编译原理》课后习题答案第5章.pdf
文本预览下载声明
《编译原理》课后习题答案第五章
第 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)
计算机咨询网（ ）陪着您 1
《编译原理》课后习题答案第五章
(((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 ）
a ∧ ( ) , #
S →a →∧ →(T)
T →S N →S N →S N
N →ε →, S N
也可由预测分析表中无多重入口判定文法是 LL(1) 的。
(3) 对输入串（a,a ）
显示全部