资源描述：
《编译原理第四章 习题与答案1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第4章习题1 4-1消除下列文法的左递归性。(1)S→SA
2、AA→SB
3、B
4、(S)
5、()B→[S]
6、[](2)S→AS
7、bA→SA
8、a(3)S→(T)
9、a
10、εT→S
11、T,S4-2对于如下文法，求各候选式的FIRST集和各非终结符号的FOLLOW集。S→aAB
12、bA
13、εA→aAb
14、εB→bB
15、ε4-3验证下列文法是否为LL(1)文法。(1)S→AB
16、CDaA→ab
17、cB→dE
18、εC→eC
19、εD→fD
20、fE→dE
21、ε(2)S→aABbCD
22、εA→ASd
23、εB→SAc
24、eC
25、εC→Sf
26、Cg
27、εD→aBD
28、ε4-4对于如下的文法G[S]
29、：S→Sb
30、Ab
31、bA→Aa
32、a(1)构造一个与G等价的LL(1)文法G′[S]；(2)对于G′[S]，构造相应的LL(1)分析表；(3)利用LL(1)分析法判断符号串aabb是否是文法G[S]的合法句子。4-5设已给文法S→SaB
33、bBA→S
34、aB→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产生式的右部代入产
35、生式S→A中，得到与原文法等价的文法G′[S]：S→SA
36、SB
37、B
38、(S)
39、()A→SB
40、B
41、(S)
42、()B→[S]
43、[]文法G′[S]中的S是直接左递归的非终结符号，则消除S产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法G"[S]：S→BS′
44、(S)S′
45、()S′S′→AS′
46、BS′
47、εA→SB
48、B
49、(S)
50、()B→[S]
51、[](2)文法G[S]中的S，A都是间接左递归的非终结符号。将A产生式代入产生式S→AS中，得到与原文法等价的文法G′[S]：S→SAS
52、aS
53、bA→SA
54、a文法G′[S]中的S是直接左
55、递归的非终结符号，则消除S产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法G"[S]：S→aSS′
56、bS′S′→ASS′
57、εA→SA
58、a(3)文法G[S]中的T是直接左递归的非终结符号。则消除T产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法G′[S]：S→(T)
59、a
60、εT→ST′T′→,ST′
61、ε4-2解：文法G[S]的各候选式的FIRST集和各非终结符号的FOLLOW集如答案表4-2所示。答案表4-2文法G[S]的各个FIRST集和FOLLOW集产生式FIRSTFOLLOWS→aABS→
62、bAS→ε{a}{b}{ε}{#}A→aAbA→ε{a}{ε}[b,#}B→bBB→ε{b}{ε}{#}4-3解：(1)因为D产生式的两个候选式fD和f的FIRST集交集为f,不为空，所以该文法不是LL(1)的。(2)因为文法中含有左递归的非终结符号A，故此文法具有左递归性，不是LL(1)的。4-4解：(1)文法中含有直接左递归的非终结符号S和A，则消除直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法G′[S]：：S→AbS′
63、bS′S′→bS′
64、εA→aA′A′→aA′
65、ε文法G′[S]的各候选式的FIRST集和各非
66、终结符号的FOLLOW集如答案表4-4-(1)所示:答案表4-4-(1)文法G′[S]的各个FIRST集和FOLLOW集产生式FIRSTFOLLOWS→AbS′S→bS′{a}{b}{#}S′→bS′S′→ε{b}{ε}{#}A→aA′{a}{b}A′→aA′A′→ε{a}{ε}{b}下面来验证文法G′[S]是否是LL(1)文法。对于文法G′[S]，因为有：对于产生式S→AbS′
67、bS′，有FIRST(AbS′)∩FIRST(bS′)={a}∩{b}=Æ；对于产生式S′→bS′
68、ε，有FIRST(bS′)∩FOLLOW(S′)={
69、b}∩{#}=Æ；对于产生式A′→aA′
70、ε，有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)分析表ab#SS→AbS′S→bS′S′S′→bS′S′→εAA→aA′A′A′→aA′A′→ε(3)对符号串aabb进行LL(1)分析的过程如答案表4-4-(3)所示。答案表4-4-(3)对aabb进行LL(1)分析的过程步骤分析栈余留输入串所用产生式1#
71、Saabb#S→AbS′2#S′bAaabb#A→aA′3#S′bA′aaabb#4#S′bA′abb#A′→aA′5#S′bA′aabb#6#S′bA′bb#A′→ε7#S′bbb#8#S′b#S′→bS′9#S′bb#10#S′#S′→ε11#
