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

第4章 习题1

4-1 消除下列文法的左递归性。

(1) S→SA|A A→SB|B|(S)|( ) B→[S]|[ ] (2) S→AS|b A→SA|a (3) S→(T)|a|ε T→S|T,S

4-2 对于如下文法，求各候选式的FIRST 集和各非终结符号的FOLLOW 集。 S→aAB|bA|ε A→aAb|ε B→bB|ε

4-3 验证下列文法是否为LL(1)文法。

(1) S→AB|CDa A→ab|c B→dE|ε

C →eC|ε D→fD|f E→dE|ε

(2) S→aABbCD|ε A→ASd|ε B→SAc|eC|ε

C →Sf|Cg|ε 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 设已给文法

S→SaB|bB A→S|a B→Ac

(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]：

S→BS ′|(S)S′|( )S′ S ′→AS ′|BS′|ε

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

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

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

S→SAS|aS|b

A →SA|a

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

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

(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 集

4-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 集

下面来验证文法G ′[S]是否是LL(1)文法。对于文法G ′[S]，因为有： 对于产生式S→AbS ′|bS′，有FIRST(AbS′)∩FIRST(bS′)={a}∩{b}=∅； 对于产生式S ′→bS ′|ε，有FIRST(bS′)∩FOLLOW(S′)={b}∩{#}=∅； 对于产生式A ′→aA ′|ε，有FIRST(aA′)∩FOLLOW(A′)={a}∩{b}=∅； 所以文法G ′[S]即为所求的与G 等价的LL(1)文法。

(2) 文法G ′[S]的LL(1)分析表如答案表4-4-(2)所示:

答案表4-4-(2) 文法G ′[S]的LL(1)分析表

(3) 对符号串aabb 进行LL(1)分析的过程如答案表4-4-(3)所示。

答案表4-4-(3) 对aabb 进行LL(1)分析的过程

因为分析成功，所以符号串aabb 是文法G[S]的合法句子。

4-5 解：

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

S→bBS ′ S ′→aBS ′|ε A →S|a B →Ac

文法G ′[S]的各候选式的FIRST 集和各非终结符号的FOLLOW 集如答案表4-5-(1)所示:

答案表4-5-(1) 文法G ′[S]的各个FIRST 集和FOLLOW 集

下面来验证文法G ′[S]是否是LL(1)文法。对于文法G ′[S]，因为有： 对于产生式S ′→aBS ′|ε，有FIRST(aBS′)∩FOLLOW(S′)={a}∩{#,c}=∅； 对于产生式A →S|a，有FIRST(S)∩FIRST(a)={b}∩{a}=∅； 所以文法G ′[S]即为所求的与G 等价的LL(1)文法。

(2) 文法G ′[S]的LL(1)分析表如答案表4-5-(2)所示:

答案表4-5-(2) 文法G ′[S]的LL(1)分析表

(3) 对符号串bacabc 进行LL(1)分析的过程如答案表4-5-(3)所示。

答案表4-5-(3) 对bacabc 进行LL(1)分析的过程

因为LL(1)分析表中B 行c 列元素为空，即为“出错”，故分析失败，所以符号串bacabc 不是文法G[S]的合法句子。