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

第四章练习题1消除4-1以下语法的左递归性。(1) SSA|A ASB|B|(S)|() BS| (2) SAS|b ASA|a(3) S(T)|a| TS|T，s对于42次的语法，求出各候补式的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|bAAa|a(1)与g等价的LL(1)语法g s ；(2)对于g s ，构建对应的LL(1)分析表(使用LL(1)分析法判断符号串aabb是否为语法GS的合法句子。给了4-5语法SSaB|bB AS|a BAc(1)与g等价的LL(1)语法g s ；(2)对于g s ，构建对应的LL(1)分析表(采用LL(1)分析法，判断符号串bacabc是否是句法GS的合法句子。第四章练习题的答案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|bASA|a如果语法gs的s是直接左递归的非终结符号，则如果消除s生成式的直接递归性，则与原文法等价且没有左递归性的语法gs :sass|bs sass|ASA|a(3)语法GS中的t是直接左递归的非终结符。 如果消除t生成式的直接递归性，则与原文法等价且没有左递归性的语法gs :S(T)|a|tst t，ST|4-2解：句法GS的各候补式的FIRST集和各非终端符号的FOLLOW集如回答表4-2所示。答案表4-2语法GS的各FIRST集和FOLLOW集正式仪式FIRSTFOLLOWSaABSbASab#AaAbAab，#BbBBb#4-3解：(1)d生成式的2个候补式fD和f的FIRST集合交叉为f，因为不是空栏，所以该语法不是LL(1)的。(2)由于语法中含有左递归的非终结符号a，因此语法是左递归的而不是LL(1)。4-4解：(1)如果语法中包含直接左递归的非终结符号s和a，则直接递归性消失时，与原文法等价且没有左递归性的语法gs :sabs|bs sbs|aaa aaa|回答语法g s 的各候补式的FIRST集和各非终结符号的FOLLOW集，在表4-4-(1)中表示：答案表4-4-(1)语法g s 的各FIRST集和FOLLOW集正式仪式FIRSTFOLLOWsabs sbs ab#sbs sb#aaa abaaa aab接着，验证语法gs是否是LL(1)语法。 关于语法gs生成式sABS|bs 中有first (ABS )first (bs )= a b =。生成式sbs|是first(bs)follow(s)=b卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡发生式aaa|有first(aa)follow(a)=ab=。因此，语法gs是与求出的g等价的LL(1)语法。(2)将语法g s 的LL(1)分析表设为解答表4-4-(2)所示的：解答表4-4-(2)语法g s 的LL(1)分析表a.a乙组联赛#ssabs sbs s sbs sa.aaaa a aaa a(3)对符号串aabb进行LL(1)解析的过程如解答表4-4-(3)所示。答案表4-4-(3) ll (1)分析AABB的过程步骤分析堆栈馀数输入列要使用的生成表达式1#Saabb#sabs 2#sbaaabb#aaa 3#sbaaaabb#4#sba abb#aaa 5#sbaaabb#6#sba bb#a7#sbbb#8# s b#sbs 9#sbb#10# s #s11#分析成功由于分析成功，符号串aabb是语法GS的合法句子。4-5解：(1)如果语法中包含直接左递归的非终结符号s，则直接递归性消失时，与原文法等价且没有左递归性的语法gs :sbbs sabs|AS|aBAc回答语法g s 的各候补式的FIRST集和各非终结符号的FOLLOW集，在表4-5-(1)中表示：答案表4-5-(1)语法g s 的各FIRST集和FOLLOW集正式仪式FIRSTFOLLOWsbbs b#、csabs sa#、cASAabacBAca，b #、a、c接着，验证语法gs是否是LL(1)语法。 关于语法gs生成式sABS|表示first(ABS)follow(s)=a铮铮铮铮653关于发生式AS|a，请参照first(s)22卡卡卡卡卡卡卡卡卡卡卡6因此，语法gs是与求出的g等价的LL(1)语法。(2)将语法g s 的LL(1)分析表设为解答表4-5-(2)所示的：解答表4-5-(2)语法g s 的LL(1)分析表a.a乙组联赛c.c#ssbbs s sabs ssa.aAaAS乙组联赛BAcBAc(3)对符号串bacabc进行LL(1)分析的过程如解答表4-5-(3)所示。答案表4-5-(3)对BAC ABC进行LL(1)分析的过程步骤分析堆栈馀数输入列要使用的生成表达式1#Sbacabc#sbbs 2#sbbbacabc#3#sbacabc#BAc4#scaacabc#Aa5#scaacabc#6#sccabc#7# s abc#sa