第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

预测分析表：