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

第4章习题14-1消除下列文法的左递归性。(1)S→SA|AA→SB|B|(S)|()B→[S]|[](2)S→AS|bA→SA|a(3)S→(T)|a|εT→S|T,S4-2对于如下文法，求各候选式的FIRST集和各非终结符号的FOLLOW集。S→aAB|bA|εA→aAb|εB→bB|ε4-3验证下列文法是否为LL(1)文法。(1)S→AB|CDaA→ab|cB→dE|εC→eC|εD→fD|fE→dE|ε(2)S→aABbCD|εA→ASd|εB→SAc|eC|εC→Sf|Cg|εD→aBD|ε4-4对于如下的文法G[S]：S→Sb|Ab|bA→Aa|a(1)构造一个与G等价的LL(1)文法G′[S]；(2)对于G′[S]，构造相应的LL(1)分析表；(3)利用LL(1)分析法判断符号串aabb是否是文法G[S]的合法句子。4-5设已给文法S→SaB|bBA→S|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产生式的右部代入产生式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|bA→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集产生式FIRSTFOLLOWS→aABS→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′|bS′S′→bS′|εA→aA′A′→aA′|ε文法G′[S]的各候选式的FIRST集和各非终结符号的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′|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)分析表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#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##分析成功因为分析成功，所以符号串aabb是文法G[S]的合法句子。4-5解：(1)文法中含有直接左递归的非终结符号S，则消除直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法G′[S]：：S→bBS′S′→aBS′|εA→S|aB→Ac文法G′[S]的各候选式的FIRST集和各非终结符号的FOLLOW集如答案表4-5-(1)所示:答案表4-5-(1)文法G′[S]的各个FIRST集和FOLLOW集产生式FIRSTFOLLOWS→bBS′{b}{#,c}S′→aBS′S′→ε{a}{ε}{#,c}A→SA→a{b}{a}{c}B→Ac{a,b}{#,a,c}下面来验证文法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)分析表abc#SS→bBS′S′S′→aBS′S′→εS′→εAA→aA→SBB→AcB→Ac(3)对符号串bacabc进行LL(1)分析的过程如答案表4-5-(3)所示。答案表4-5-(3)对bacabc进行LL(1)分析的过程步骤分析栈余留输入串所用产生式1#Sbacabc#S→bBS′2#S′Bbbacabc#3#S′Bacabc#B→Ac4#S′cAacabc#A→a5#S′caacabc#6#S′ccabc#7#S′abc#S′→aBS′8#S′Baabc#9#S′Bbc#B→Ac10#S′cAbc#A→S11#S′cSbc#S→bBS′12#S′cS′Bbbc#13#S′cS′Bc#分析失败因为LL(1)分析表中B行c列元素为空，即为“出错”，故分析失败，所以符号串bacabc不是文法G[S]的合法句子。