第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→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→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集 产 生 式 S→aAB S→bA S→ε A→aAb A→ε B→bB B→ε
4-3 解：
(1) 因为D产生式的两个候选式fD和f的FIRST集交集为f,不为空，所以该文法不是LL(1)的。
(2) 因为文法中含有左递归的非终结符号A，故此文法具有左递归性，不是LL(1)的。
4-4 解：
(1) 文法中含有直接左递归的非终结符号S和A，则消除直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法G′[S]：：
S→AbS′|bS′
FIRST {a} {b} {ε} {a} {ε} {b} {ε} {#} [b,#} FOLLOW {#}