蔣立源編譯原理第三版第四章-習(xí)題與答案1

1、第4章習(xí)題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集和各非終結(jié)符號的 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òu)造一個與G等價的LL(1)文法G' S;(2) 對于G S，構(gòu)造相應(yīng)的LL(1)分析表；(3) 利用LL(1)分析法判斷符號串a(chǎn)abb是否是文法GS的合法句子。4-5 設(shè)已給文法Sf SaB|bBA f S|a Bf Ac(1) 構(gòu)造一個與G等價的LL(1)文法G S;(2) 對于G S，構(gòu)造相應(yīng)的LL(1)分析表；(3) 利用LL(1)分析法判斷符號串bacabc是否是文法GS的合法句子第4章習(xí)題答案4-1 解：(1)文法GS中的S, A都是間接左遞歸的非終結(jié)符號。將A產(chǎn)生式的右部代入產(chǎn)生式4

3、A中，得到與原文法等價的文法G' S:4 SA|SB|B|(S)|()L SB|B|(S)|()EH S|文法G S中的S是直接左遞歸的非終結(jié)符號，那么消除S產(chǎn)生式的直接遞歸性后，我們便得到了與原文法等價且無任何左遞歸性的文法G"S:ShBS' |(S)S ' |( )S 'S'f AS' |BS' | &Ah SB|B|(S)|()S|(2)文法GS中的S, A都是間接左遞歸的非終結(jié)符號。將A產(chǎn)生式代入產(chǎn)生式Sh AS中，得到與原文法等價的文法G' S:Sh SAS|aS|bAh SA|a文法G S中的S是直接

4、左遞歸的非終結(jié)符號，那么消除S產(chǎn)生式的直接遞歸性后，我們便得到了與原文法等價且無任何左遞歸性的文法G"S:ShaSS' |bS 'S'h ASS | &Ah SA|a(3) 文法GS中的T是直接左遞歸的非終結(jié)符號。那么消除T產(chǎn)生式的直接遞歸性后,我們便得到了與原文法等價且無任何左遞歸性的文法G S:4 (T)|a|&T ST'T'fST' | &4-2 解：文法GS的各候選式的FIRST集和各非終結(jié)符號的 FOLLOW如答案表4-2所示。答案表4-2 文法GS的各個FIRST集和FOLLOWI產(chǎn)生式FIRSTFO

5、LLOWS aABaS bAb#S£汀A aAbab,#A£汀4 bBb#B£汀4-3 解：(1)因為D產(chǎn)生式的兩個候選式fD和f的FIRST集交集為f,不為空，所以該文法不是LL(1)的。A,故此文法具有左遞歸性，不是LL(1)S和A,那么消除直接遞歸性后，我們便得G' S:(2)因為文法中含有左遞歸的非終結(jié)符號 的。4-4 解：(1)文法中含有直接左遞歸的非終結(jié)符號 到了與原文法等價且無任何左遞歸性的文法S AbS' |bS 'S'f bS' I &2 aA'A'f aA' | &

6、文法G S的各候選式的FIRST集和各非終結(jié)符號的FOLLOW如答案表44(1)所示:答案表4-4-(1) 文法G S的各個FIRST集和FOLLOWI產(chǎn)生式FIRSTFOLLOWS AbS'a#S bS 'bS ' bS'bS ' £汀#A aA 'abA aA'aA £汀b下面來驗證文法 G S是否是LL(1)文法。對于文法 G S，因為有：對于產(chǎn)生式 S AbS |bS '，有 FIRST(AbS ' ) Q FIRST(bS') =a Q b=; 對于產(chǎn)生式 S' bS'

7、 | &,有 FIRST(bS' ) Q FOLLOW(S ) =b Q #=; 對于產(chǎn)生式 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' £對符號串a(chǎn)abb進行LL(

8、1)分析的過程如答案表4-4-(3)所示。答案表4-4-(3)對aabb進行LL(1)分析的過程步驟分析棧余留輸入串所用產(chǎn)生式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、成功因為分析成功，所以符號串a(chǎn)abb是文法GS的合法句子。4-5 解：(1)文法中含有直接左遞歸的非終結(jié)符號S,貝府肖除直接遞歸性后，我們便得到了與原文法等價且無任何左遞歸性的文法G S:4 bBS'S' aBS | &S|a4 Ac文法G S的各候選式的FIRST集和各非終結(jié)符號的FOLLOW如答案表4-5-(1)所示:答案表4-5-(1) 文法G S的各個FIRST集和FOLLOWI產(chǎn)生式FIRSTFOLLOWS bBS'b#,cS' aBSaS' £汀#,cA SbcA aa4 Aca,b #,a,c下面來驗證文法 G S是否是L

10、L(1)文法。對于文法 G S，因為有: 對于產(chǎn)生式 S'f aBS | & ,有 FIRST(aBS' ) Q FOLLOW(S) =a Q #,c= 對于產(chǎn)生式 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)分析的過程步驟分析棧余留輸入串所用產(chǎn)生式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&#