第5章 自顶向下语法分析方法
第1题
对文法g[s]
s
t
(1)
(2) 子程序。
(3)
(4)
→a||(t)∧ →t,s|s 给出(a,(a,a))和(((a,a),,(a)),a)∧的最左推导。 对文法g，进行改写，然后对每个非终结符写出不带回溯的递归经改写后的文法是否是ll(1)的?给出它的预测分析表。 给出输入串(a,a)#的分析过程，并说明该串是否为g的句子。 答案：
也可由预测分析表中无多重入口判定文法是ll(1)的。
可见输入串（a,a）#是文法的句子。
第3题
已知文法g[s]：
s→mh|a
h→lso|ε
k→dml|ε
l→ehf
m→k|blm
判断g是否是ll(1)文法，如果是，构造ll(1)分析表。
第7题
对于一个文法若消除了左递归，提取了左公共因子后是否一定为ll(1)文法?试对下面文法进行改写，并对改写后的文法进行判断。
(１)a→bab|ε
b→abb|a
(2) a→aabe|a
b→bb|d
(3) s→aa|b
a→sb
b→ab
答案：
(１)先改写文法为：
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
（2） 文法： a→aabe|a b→bb|d
提取左公共因子和消除左递归后文法变为：
1) n→a b e
→a n 0) a
2) n→ε
3) b→d n1
4) n1→b n1
5) n1→ε
（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
也可由预测分析表中无多重入口判定文法是ll(1)的。 第2种改写：
b→ab
0) s
1) s
2) a
3) n
4) n
5) b
用s的产生式右部代替a的产生式右部的s得：消除左递归后文法变为： →a a →b →b b n →a b n →ε →a b →aa|b a→aab|bb s
预测分析表：