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

1、蔣立源編譯原理第三版第四章 - 習(xí)題與答案1第4章習(xí)題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 對(duì)于如下文法，求各候選式的FIRST集和各非終結(jié)符號(hào)的 FOLLOW。Sf aAB|bA| &Af aAb|eBf bB| e4-3驗(yàn)證下列文法是否為L(zhǎng)L(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 對(duì)于如下的文法GS:Sf Sb|Ab|bAf Aa|a(1) 構(gòu)造一個(gè)與G等價(jià)的LL(1)文法G S;(2) 對(duì)于G S，構(gòu)造相應(yīng)的LL(1)分析表；(3) 利用LL(1)分析法判斷符號(hào)串a(chǎn)abb是否是文法GS的合法句子。4-5 設(shè)已給文法Sf SaB|bBA f S|a Bf Ac(1) 構(gòu)造一個(gè)與G等價(jià)的LL(1)文法G S;(2) 對(duì)于G S，構(gòu)造相應(yīng)的LL(1)分析表；(3) 利用LL(1)分析法判斷符號(hào)串bacabc是否是文法GS的合法句子第4章習(xí)題答案4-1 解：(1)文法GS中的S, A都是間接左遞歸的非終結(jié)符號(hào) 生式4 A

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

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

5、S bAb#S £ £ A aAbab,#A £ £ B bBb#B £ £ 4-3 解：(1)因?yàn)镈產(chǎn)生式的兩個(gè)候選式fD和f的FIRST集交集為f,不為空，所以該文法不是LL(1)的。(2)的。因?yàn)槲姆ㄖ泻凶筮f歸的非終結(jié)符號(hào)A,故此文法具有左遞歸性，不是LL(1)4-4解：(1)文法中含有直接左遞歸的非終結(jié)符號(hào)S和A,則消除直接遞歸性后，我們便得到了與原文法等價(jià)且無(wú)任何左遞歸性的文法G' S:S AbS' |bSS'f bS' I &A aA”A'f aA | &文法G S

6、的各候選式的FIRST集和各非終結(jié)符號(hào)的FOLLO喋如答案表44(1)所示:答案表4-4-(1) 文法G S的各個(gè)FIRST集和FOLLOWI產(chǎn)生式FIRSTFOLLOWS AbS'a#S bS 'bS ' bS'bS ' & & #A aA 'abA ' aA 'aA ' & & b下面來(lái)驗(yàn)證文法 G S是否是LL(1)文法。對(duì)于文法 G S，因?yàn)橛校簩?duì)于產(chǎn)生式 S AbS' |bS '，有 FIRST(AbS' ) Q FIRST(bS') =a Q b=

7、;對(duì)于產(chǎn)生式 S' bS' | & ,有 FIRST(bS' ) Q FOLLOW(S ) =b Q #=_; 對(duì)于產(chǎn)生式 A' aA' | & ,有 FIRST(aA ' ) Q FOLLOW(A ) =a Q b= ;所以文法G S即為所求的與G等價(jià)的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' &對(duì)符號(hào)串a(chǎn)abb進(jìn)行LL(1)分析的過(guò)程如答案表 4-4-(3)所示。答案表4-4-(3)對(duì)aabb進(jìn)行LL(1)分析的過(guò)程步驟分析棧余留輸入串所用產(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

9、'#S ' £11#分析成功因?yàn)榉治龀晒Γ苑?hào)串a(chǎn)abb是文法GS的合法句子4-5 解：(1)文法中含有直接左遞歸的非終結(jié)符號(hào)S,貝V消除直接遞歸性后，我們便得到了與原文法等價(jià)且無(wú)任何左遞歸性的文法G' S:4 bBS'S' aBS | &S|a4 Ac文法G S的各候選式的FIRST集和各非終結(jié)符號(hào)的FOLLO喋如答案表4-5-(1)所示:答案表4-5-(1) 文法G S的各個(gè)FIRST集和FOLLOWI產(chǎn)生式FIRSTFOLLOWS bBS'b#,cS' aBSaS' £ & #,cA

10、SbcA aaB Aca,b #,a,c下面來(lái)驗(yàn)證文法 G S是否是LL(1)文法。對(duì)于文法 G S，因?yàn)橛校簩?duì)于產(chǎn)生式 S'f aBS | & ,有 FIRST(aBS' ) Q FOLLOW(S) =a Q #,c=.;對(duì)于產(chǎn)生式 A S|a，有 FIRST(S) Q FIRST(a)=b Q a=;所以文法G S即為所求的與G等價(jià)的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 對(duì)符號(hào)串bacabc進(jìn)行LL(1)分析的過(guò)程如答案表 4-5-(3)所示。答案表4-5-(3) 對(duì)bacabc進(jìn)行LL(1)分析的過(guò)程步驟分析棧余留輸入串所用產(chǎn)生式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