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

第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)文法GS；(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| 文法GS中的S是直接左递归的非终结符号，则消除S产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法GS：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产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法GS：SaSS|bS SASS|ASA|a(3) 文法GS中的T是直接左递归的非终结符号。则消除T产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法GS：S(T)|a| TSTT,ST|4-2 解： 文法GS的各候选式的FIRST集和各非终结符号的FOLLOW集如答案表4-2所示。答案表4-2 文法GS的各个FIRST集和FOLLOW集产 生 式FIRSTFOLLOWSaABSbASab#AaAbA a b,# BbB Bb#4-3 解：(1) 因为D产生式的两个候选式fD和f的FIRST集交集为f,不为空，所以该文法不是LL(1)的。(2) 因为文法中含有左递归的非终结符号A，故此文法具有左递归性，不是LL(1)的。4-4 解： (1) 文法中含有直接左递归的非终结符号S和A，则消除直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法GS：SAbS|bS SbS| AaA AaA| 文法GS的各候选式的FIRST集和各非终结符号的FOLLOW集如答案表4-4-(1)所示:答案表4-4-(1) 文法GS的各个FIRST集和FOLLOW集产 生 式FIRSTFOLLOWSAbSSbSab#SbSSb#AaAab AaA Aab下面来验证文法GS是否是LL(1)文法。对于文法GS，因为有：对于产生式SAbS|bS，有FIRST(AbS)FIRST(bS)=ab=；对于产生式SbS|，有FIRST(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)分析表ab#SSAbSSbSSSbSSAAaAAAaAA(3) 对符号串aabb进行LL(1)分析的过程如答案表4-4-(3)所示。答案表4-4-(3) 对aabb进行LL(1)分析的过程 步骤分析栈余留输入串所用产生式1#Saabb# SAbS2 #SbAaabb# AaA3 #SbAaaabb# 4#SbAabb# AaA5 #SbAaabb# 6#SbAbb# A7#Sbbb# 8#Sb# SbS9#Sbb# 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集和FOLLOW集产 生 式FIRSTFOLLOWSbBSb#,cSaBSSa#,cAS Aabac BAca,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)分析表abc#SSbBSSSaBSSSAAaASBBAcBAc (3) 对符号串bacabc进行LL(1)分析的过程如答案表4-5-(3)所示。答案表4-5-(3) 对bacabc进行LL(1)分析的过程 步骤分析栈余留输入串所用产生式1#Sbacabc# SbBS2 #SBbbacabc# 3 #SBacabc# BAc4#ScAacabc# Aa5 #Scaacabc# 6#Sccabc# 7#Sabc# SaBS8#SB