编译原理第四章 习题与答案1.doc

1、第 4章 习题 14-1 消除下列文法的左递归性。(1) SSA|A ASB|B|(S)|( ) BS| (2) SAS|b ASA|a(3) S(T)|a| TS|T,S4-2 对于如下文法，求各候选式的 FIRST集和各非终结符号的 FOLLOW集。SaAB|bA| AaAb| BbB| 4-3 验证下列文法是否为 LL(1)文法。(1) SAB|CDa Aab|c BdE|CeC| DfD|f EdE|(2) SaABbCD| AASd| BSAc|eC|CSf|Cg| DaBD| 4-4 对于如下的文法 GS：SSb|Ab|b AAa|a(1) 构造一个与 G等价的 LL(1)文法 G

2、S；(2) 对于 GS，构造相应的 LL(1)分析表；(3) 利用 LL(1)分析法判断符号串 aabb是否是文法 GS的合法句子。4-5 设已给文法SSaB|bB AS|a BAc(1) 构造一个与 G等价的 LL(1)文法 GS；(2) 对于 GS，构造相应的 LL(1)分析表；(3) 利用 LL(1)分析法判断符号串 bacabc是否是文法 GS的合法句子。第 4章 习题答案4-1 解： (1) 文法 GS中的 S，A 都是间接左递归的非终结符号。将 A产生式的右部代入产生式SA中，得到与原文法等价的文法 GS：SSA|SB|B|(S)|( ) ASB|B|(S)|( ) BS| 文法

3、GS中的 S是直接左递归的非终结符号，则消除 S产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法 G“S：SBS|(S)S|( )S SAS|BS|ASB|B|(S)|( ) BS| (2) 文法 GS中的 S，A 都是间接左递归的非终结符号。将 A产生式代入产生式SAS中，得到与原文法等价的文法 GS：SSAS|aS|b ASA|a文法 GS中的 S是直接左递归的非终结符号，则消除 S产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法 G“S：SaSS|bS SASS|ASA|a(3) 文法 GS中的 T是直接左递归的非终结符号。则消除 T产生式的直接递

4、归性后，我们便得到了与原文法等价且无任何左递归性的文法 GS：S(T)|a| TSTT,ST|4-2 解： 文法 GS的各候选式的 FIRST集和各非终结符号的 FOLLOW集如答案表 4-2所示。答案表 4-2 文法 GS的各个 FIRST集和 FOLLOW集产 生 式 FIRST FOLLOWSaABSbASab#AaAbA ab,#BbBBb#4-3 解：(1) 因为 D产生式的两个候选式 fD和 f的 FIRST集交集为 f,不为空，所以该文法不是 LL(1)的。(2) 因为文法中含有左递归的非终结符号 A，故此文法具有左递归性，不是 LL(1)的。4-4 解： (1) 文法中含有直接

5、左递归的非终结符号 S和 A，则消除直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法 GS：SAbS|bS SbS| AaA AaA| 文法 GS的各候选式的 FIRST集和各非终结符号的 FOLLOW集如答案表 4-4-(1)所示:答案表 4-4-(1) 文法 GS的各个 FIRST集和 FOLLOW集产 生 式 FIRST FOLLOWSAbSSbSab#SbSSb #AaA a bAaAAa b下面来验证文法 GS是否是 LL(1)文法。对于文法 GS，因为有：对于产生式 SAbS|bS，有 FIRST(AbS)FIRST(bS)=ab=；对于产生式 SbS|，有 FIRST

6、(bS)FOLLOW(S)=b#=；对于产生式 AaA|，有 FIRST(aA)FOLLOW(A)=ab=；所以文法 GS即为所求的与 G等价的 LL(1)文法。(2) 文法 GS的 LL(1)分析表如答案表 4-4-(2)所示:答案表 4-4-(2) 文法 GS的 LL(1)分析表a b #S SAbS SbSS SbS SA AaAA AaA A(3) 对符号串 aabb进行 LL(1)分析的过程如答案表 4-4-(3)所示。答案表 4-4-(3) 对 aabb进行 LL(1)分析的过程 步骤 分析栈 余留输入串 所用产生式1 #S aabb# SAbS2 #SbA aabb# AaA3

7、#SbAa aabb# 4 #SbA abb# AaA5 #SbAa abb# 6 #SbA bb# A7 #Sb bb# 8 #S b# SbS9 #Sb b# 10 #S # S11 # # 分析成功因为分析成功，所以符号串 aabb是文法 GS的合法句子。4-5 解： (1) 文法中含有直接左递归的非终结符号 S，则消除直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法 GS：SbBS SaBS| AS|a BAc 文法 GS的各候选式的 FIRST集和各非终结符号的 FOLLOW集如答案表 4-5-(1)所示:答案表 4-5-(1) 文法 GS的各个 FIRST集和 FOLL

8、OW集产 生 式 FIRST FOLLOWSbBS b #,cSaBSSa #,cAS AabacBAc a,b #,a,c下面来验证文法 GS是否是 LL(1)文法。对于文法 GS，因为有：对于产生式 SaBS|，有 FIRST(aBS)FOLLOW(S)=a#,c=；对于产生式 AS|a，有 FIRST(S)FIRST(a)=ba=；所以文法 GS即为所求的与 G等价的 LL(1)文法。(2) 文法 GS的 LL(1)分析表如答案表 4-5-(2)所示:答案表 4-5-(2) 文法 GS的 LL(1)分析表a b c #S SbBSS SaBS S SA Aa ASB BAc BAc (3

9、) 对符号串 bacabc进行 LL(1)分析的过程如答案表 4-5-(3)所示。答案表 4-5-(3) 对 bacabc进行 LL(1)分析的过程 步骤 分析栈 余留输入串 所用产生式1 #S bacabc# SbBS2 #SBb bacabc# 3 #SB acabc# BAc4 #ScA acabc# Aa5 #Sca acabc# 6 #Sc cabc# 7 #S abc# SaBS8 #SBa abc# 9 #SB bc# BAc10 #ScA bc# AS11 #ScS bc# SbBS12 #ScSBb bc# 13 #ScSB c# 分析失败因为 LL(1)分析表中 B行 c列元素为空，即为“出错” ，故分析失败，所以符号串bacabc不是文法 GS的合法句子。