蒋立源编译原理第三版第四章-习题与答案1

第4章 习题1

4-1 消除下列文法的左递归性。(1) S→SA|A (2) S→AS|b (3) S→(T)|a|ε

A→SB|B|(S)|( )

A→SA|a

T→S|T,S

B→[S]|[ ]

4-2 对于如下文法，求各候选式的FIRST集和各非终结符号的FOLLOW集。

S→aAB|bA|ε

A→aAb|ε

B→bB|ε

4-3 验证下列文法是否为LL(1)文法。(1) S→AB|CDa C→eC|ε

A→ab|c

B→dE|ε

D→fD|f E→dE|ε

B→SAc|eC|ε

(2) S→aABbCD|ε C→Sf|Cg|ε

A→ASd|ε D→aBD|ε

4-4 对于如下的文法G[S]：S→Sb|Ab|b A→Aa|a

(1) 构造一个与G等价的LL(1)文法G′[S]；(2) 对于G′[S]，构造相应的LL(1)分析表；

(3) 利用LL(1)分析法判断符号串aabb是否是文法G[S]的合法句子。

4-5 设已给文法

A→S|a

B→Ac

S→SaB|bB

(1) 构造一个与G等价的LL(1)文法G′[S]；(2) 对于G′[S]，构造相应的LL(1)分析表；

(3) 利用LL(1)分析法判断符号串bacabc是否是文法G[S]的合法句子。

第4章 习题答案

4-1 解：

(1) 文法G[S]中的S，A都是间接左递归的非终结符号。将A产生式的右部代入产生式

S→A

中，得到与原文法等价的文法G′[S]：

S→SA|SB|B|(S)|( )

A→SB|B|(S)|( ) B→[S]|[ ]

文法G′[S]中的S是直接左递归的非终结符号，则消除S产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法G\：

S→BS′|(S)S′|( )S′ S′→AS′|BS′|εA→SB|B|(S)|( ) B→[S]|[ ]

(2) 文法G[S]中的S，A都是间接左递归的非终结符号。将A产生式代入产生式

S→AS

中，得到与原文法等价的文法G′[S]： A→SA|a

文法G′[S]中的S是直接左递归的非终结符号，则消除S产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法G\：

S→aSS′|bS′ S′→ASS′|εA→SA|a

S→SAS|aS|b

(3) 文法G[S]中的T是直接左递归的非终结符号。则消除T产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法G′[S]：S→(T)|a|ε T→ST′T′→,ST′|ε4-2 解： 文法G[S]的各候选式的FIRST集和各非终结符号的FOLLOW集如答案表4-2所示。答案表4-2 文法G[S]的各个FIRST集和FOLLOW集产 生 式S→aABS→bAS→εA→aAbA→ε B→bB B→εFIRST{a}{b}{ε}{a}{ε}{b}{ε}{#} [b,#}{#}FOLLOW4-3 解：(1) 因为D产生式的两个候选式fD和f的FIRST集交集为f,不为空，所以该文法不是LL(1)的。(2) 因为文法中含有左递归的非终结符号A，故此文法具有左递归性，不是LL(1)的。4-4 解： (1) 文法中含有直接左递归的非终结符号S和A，则消除直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法G′[S]：：S→AbS′|bS′ S′→bS′|ε A→aA′ A′→aA′|ε 文法G′[S]的各候选式的FIRST集和各非终结符号的FOLLOW集如答案表4-4-(1)所示:答案表4-4-(1) 文法G′[S]的各个FIRST集和FOLLOW集产 生 式S→AbS′S→bS′FIRST{a}{b}FOLLOW{#}