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

1、蒋立源编译原理第三版第四章 - 习题与答案1第4章习题1f S|4-1消除下列文法的左递归性。 4 SA|A A f SB|B|(S)|( ) B S f AS|b A f SA|a S f (T)|a|&Tf S|T,S4-2 对于如下文法，求各候选式的FIRST集和各非终结符号的 FOLLOW。Sf aAB|bA| &Af aAb|eBf bB| e4-3验证下列文法是否为LL(1)文法。(1)Sf AB|CDaAf ab|cBf dE| eCf eC| &Df fD|fEf dE| eSf aABbCD|&Af ASd| eBf SAc|eC| eCf S

2、f|Cg| &Df aBD| &4-4 对于如下的文法GS:Sf Sb|Ab|bAf Aa|a(1) 构造一个与G等价的LL(1)文法G S;(2) 对于G S，构造相应的LL(1)分析表；(3) 利用LL(1)分析法判断符号串aabb是否是文法GS的合法句子。4-5 设已给文法Sf SaB|bBA f S|a Bf Ac(1) 构造一个与G等价的LL(1)文法G S;(2) 对于G S，构造相应的LL(1)分析表；(3) 利用LL(1)分析法判断符号串bacabc是否是文法GS的合法句子第4章习题答案4-1 解：(1)文法GS中的S, A都是间接左递归的非终结符号 生式4 A

3、中，得到与原文法等价的文法G S:4 SA|SB|B|(S)|()L SB|B|(S)|()EH S|文法G S中的S是直接左递归的非终结符号，则消除 们便得到了与原文法等价且无任何左递归性的文法G"SSh BS' |(S)S '1( )S 'S'f AS' IBS' | &Ah SB|B|(S)|()S|将A产生式的右部代入产S产生式的直接递归性后，我(2)文法GS中的S, A都是间接左递归的非终结符号Sh as中，得到与原文法等价的文法G S:Sh SAS|aS|bAh SA|a文法G S中的S是直接左递归的非终结符号，则消

4、除们便得到了与原文法等价且无任何左递归性的文法G"SShaSS |bS 'S' h ASS | &Ah SA|a将A产生式代入产生式S产生式的直接递归性后，我(3)文法GS中的T是直接左递归的非终结符号。则消除T产生式的直接递归性G S:后，我们便得到了与原文法等价且无任何左递归性的文法4 (T)|a|&T ST'T'fST' | &4-2 解：文法GS的各候选式的FIRST集和各非终结符号的 FOLLOW如答案表4-2所示。答案表4-2 文法GS的各个FIRST集和FOLLOWI产生式FIRSTFOLLOWS aABa

5、S bAb#S £ £ A aAbab,#A £ £ 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' |bSS'f bS' I &A aA”A'f aA | &文法G S

6、的各候选式的FIRST集和各非终结符号的FOLLO喋如答案表44(1)所示:答案表4-4-(1) 文法G S的各个FIRST集和FOLLOWI产生式FIRSTFOLLOWS AbS'a#S bS 'bS ' bS'bS ' & & #A aA 'abA ' aA 'aA ' & & b下面来验证文法 G S是否是LL(1)文法。对于文法 G S，因为有：对于产生式 S AbS' |bS '，有 FIRST(AbS' ) Q FIRST(bS') =a Q b=

7、;对于产生式 S' bS' | & ,有 FIRST(bS' ) Q FOLLOW(S ) =b Q #=_; 对于产生式 A' aA' | & ,有 FIRST(aA ' ) Q FOLLOW(A ) =a Q 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'AA aA &#

8、39;A' &对符号串aabb进行LL(1)分析的过程如答案表 4-4-(3)所示。答案表4-4-(3)对aabb进行LL(1)分析的过程步骤分析栈余留输入串所用产生式1#Saabb#S AbS2#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

9、'#S ' £11#分析成功因为分析成功，所以符号串aabb是文法GS的合法句子4-5 解：(1)文法中含有直接左递归的非终结符号S,贝V消除直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法G' S:4 bBS'S' aBS | &S|a4 Ac文法G S的各候选式的FIRST集和各非终结符号的FOLLO喋如答案表4-5-(1)所示:答案表4-5-(1) 文法G S的各个FIRST集和FOLLOWI产生式FIRSTFOLLOWS bBS'b#,cS' aBSaS' £ & #,cA

10、SbcA aaB Aca,b #,a,c下面来验证文法 G S是否是LL(1)文法。对于文法 G S，因为有：对于产生式 S'f aBS | & ,有 FIRST(aBS' ) Q FOLLOW(S) =a Q #,c=.;对于产生式 A S|a，有 FIRST(S) Q FIRST(a)=b Q a=;所以文法G S即为所求的与G等价的LL(1)文法。 文法G S的LL(1)分析表如答案表4-5-(2)所示:答案表4-5-(2) 文法G S的LL(1)分析表abc#SS bBSS 'S ' aBS'S ' £S ' £AA aA SB4 AcB Ac 对符号串bacabc进行LL(1)分析的过程如答案表 4-5-(3)所示。答案表4-5-(3) 对bacabc进行LL(1)分析的过程步骤分析栈余留输入串所用产生式1#Sbacabc#S bBS2#S ' Bbbacabc#3#S ' Bacabc#B Ac4#S' cAacabc#A f a5#S ' caacabc#6#S' ccabc#7#S'abc#S' aBS'8#S