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

1、第4章习题14-1消除以下文法的左递归性。 4 SA|AA SB|B|(S)|( )Bf S| S f AS|bA f SA|a S f(T)|a|&Tf S|T,S4-2对于如下文法，求各候选式的FIRST集和各非终结符号的 FOLLOW。Sf aAB|bA| & A f aAb| &4-3 验证以下文法是否为 LL(1)文法c(1) Sf AB|CDaA f ab|c BCf eC| & Df fD|fE f dE| &Bf SAc|eC| e(2) Sf aABbCD|&A f ASd| &Cf Sf|Cg| & Df aB

2、D| £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都是间接左递归的非终结符号。将A产生式的右部代入产生式4

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

4、左递归的非终结符号，那么消除S产生式的直接递归性后，我们便得到了与原文法等价且无任何左递归性的文法G"S:ShaSS' |bS 'S'h ASS | &Ah SA|a(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产生式FIRSTFO

5、LLOWS aABaS bAb#S£汀A aAbab,#A£汀4 bBb#B£汀4-3 解：(1)因为D产生式的两个候选式fD和f的FIRST集交集为f,不为空，所以该文法不是LL(1)的。A,故此文法具有左递归性，不是LL(1)S和A,那么消除直接递归性后，我们便得G' S:(2)因为文法中含有左递归的非终结符号 的。4-4 解：(1)文法中含有直接左递归的非终结符号 到了与原文法等价且无任何左递归性的文法S AbS' |bS 'S'f bS' I &2 aA'A'f aA' | &

6、文法G S的各候选式的FIRST集和各非终结符号的FOLLOW如答案表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=; 对于产生式 S' bS'

7、 | &,有 FIRST(bS' ) Q FOLLOW(S ) =b Q #=; 对于产生式 A' aA' | &,有 FIRST(aA' ) Q FOLLOW(A) =a Q b=;所以文法G S即为所求的与G等价的LL(1)文法。 文法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 'A' £对符号串aabb进行LL(

8、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 '#S ' £11#分析

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

10、L(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 SBB 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#Af a5#S 'caacabc#6#S'ccabc#7#S'abc#S' aBS'8#S&#