《編譯原理 第二章習(xí)題答案》由會員分享，可在線閱讀，更多相關(guān)《編譯原理 第二章習(xí)題答案（13頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、第2章 習(xí)題解答 1.文法G[S]為： S->Ac|aB A->ab B->bc 寫出L(G[S])的全部元素。 [答案] S=>Ac=>abc 或S=>aB=>abc 所以L(G[S])={abc} ============================================== 2. 文法G[N]為： N->D|ND D->0|1|2|3|4|5|6|7|8|9 G[N]的語言是什么？ [答案] G[N]的語言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD.... =>NDDDD...

2、D=>D......D =============================================== 3.已知文法G[S]： S→dAB? A→aA|a? B→ε|bB 問：相應(yīng)的正規(guī)式是什么？G[S]能否改寫成為等價(jià)的正規(guī)文法？ [答案] 正規(guī)式是daa*b*； 相應(yīng)的正規(guī)文法為(由自動機(jī)化簡來)： G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b 也可為(觀察得來):G[S]:S→dA A→a|aA|aB B→bB|ε ======================================

3、========================================= 4.已知文法G[Z]： Z->aZb|ab 寫出L(G[Z])的全部元素。 [答案] Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb L(G[Z])={anbn|n>=1} ============================================================================== 5.給出語言{anbncm|n>=1,m>=0}的上下文無關(guān)文法。 [分析] 本題難度不大，主要是考上下文無

4、關(guān)文法的基本概念。上下文無關(guān)文法的基本定義是：A->β,A∈Vn，β∈（Vn∪Vt）*，注意關(guān)鍵問題是保證anbn的成立，即“a與b的個(gè)數(shù)要相等”，為此，可以用一條形如A->aAb|ab的產(chǎn)生式即可解決。 [答案] 構(gòu)造上下文無關(guān)文法如下： S->AB|A A->aAb|ab B->Bc|c [擴(kuò)展] 凡是諸如此類的題都應(yīng)按此思路進(jìn)行，本題可做為一個(gè)基本代表?；舅悸肥沁@樣的： 要求符合anbncm，因?yàn)閍與b要求個(gè)數(shù)相等，所以把它們應(yīng)看作一個(gè)整體單元進(jìn)行，而cm做為另一個(gè)單位，初步產(chǎn)生式就應(yīng)寫為S->AB，其中A推出anbn，B推出cm。因?yàn)閙可為0，故上式進(jìn)

5、一步改寫為S->AB|A。接下來考慮A,凡是要求兩個(gè)終結(jié)符個(gè)數(shù)相等的問題，都應(yīng)寫為A->aAb|ab形式，對于B就很容易寫成B->Bc|c了。 ============================================================================== 6 .寫一文法，使其語言是偶正整數(shù)集合。 要求： (1)允許0開頭； (2)不允許0開頭。 [答案] (1)允許0開頭的偶正整數(shù)集合的文法 E->NT|G|SFM T->NT|G N->D|1|3|5|7|9 D->0|G G->2|4|6|8 S

6、->NS|ε F->1|3|5|7|9|G M->M0|0 (2)不允許0開頭的偶正整數(shù)集合的文法 E->NT|D T->FT|G N->D|1|3|5|7|9 D->2|4|6|8 F->N|0 G->D|0 ============================================================================= 7.已知文法G： E->E+T|E-T|T T->T*F|T/F|F F->(E)|i 試給出下述表達(dá)式的推導(dǎo)及語法樹 (1)i;? (2)i*i+i ??(3)i+i*i

7、 ?(4)i+(i+i) [答案] (1)E=>T=>F=>i (2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i (3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i (4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T) =>i+(i+T)=>i+(i+F)=>i+(i+i) 8 .為句子i+i*i構(gòu)造兩棵語法樹，從而證明

8、下述文法G[<表達(dá)式>]是二義的。 〈表達(dá)式〉->〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉|(〈表達(dá)式〉)|i 〈運(yùn)算符〉->+|-|*|/ [答案] 可為句子i+i*i構(gòu)造兩個(gè)不同的最右推導(dǎo): 最右推導(dǎo)1 ?〈表達(dá)式〉=>〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉 =>〈表達(dá)式〉〈運(yùn)算符〉i =>〈表達(dá)式〉* i =>〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉* i =>〈表達(dá)式〉〈運(yùn)算符〉i? * i =>〈表達(dá)式〉+ i * i => i + i * i 最右推導(dǎo)2 〈表達(dá)式〉=>〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉 =>〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)

9、式> =>〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉〈運(yùn)算符〉 i =>〈表達(dá)式〉〈運(yùn)算符〉〈表達(dá)式〉 * i => 〈表達(dá)式〉〈運(yùn)算符〉i? * i =>〈表達(dá)式〉+ i * i =>?? i + i * i 所以，該文法是二義的。 ====================================================================== 9. 文法G[S]為： S->Ac|aB A->ab B->bc 該文法是否為二義的？為什么？ [答案] 對于串a(chǎn)bc (1)S=>Ac=>abc (2)S=>aB=>abc

10、 即存在兩不同的最右推導(dǎo) 所以，該文法是二義的。 =========================================================================== 10.考慮下面上下文無關(guān)文法： S->SS*|SS+|a (1)表明通過此文法如何生成串a(chǎn)a+a*，并為該串構(gòu)造語法樹。 (2) G[S]的語言是什么？ [答案] (1)此文法生成串a(chǎn)a+a*的最右推導(dǎo)如下 S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a* (2)該文法生成的語言是即加法和乘法的逆波蘭式, =========

11、===================================================================== 11. 令文法G[E]為: E->E+T|E-T T->T*F|T/F|F F->(E)|I 證明E+T*F是它的一個(gè)句型，指出這個(gè)句型的所有短語、直接短語和句柄。 [答案] 此句型對應(yīng)語法樹如右，故為此文法一個(gè)句型。 或者：因?yàn)榇嬖谕茖?dǎo)序列:? E=>E+T=>E+T*F，所以 E+T*F句型 此句型相對于E的短語有:E+T*F；相對于T的短語有T*F, 直接短語為：T*F；。 句柄為：T*F

12、 12.已知文法G[E]: E→ET+|T? T→TF* | F? F→F^ | a 試證：FF^^*是文法的句型，指出該句型的短語、簡單短語和句柄. [答案] 該句型對應(yīng)的語法樹如下： 該句型相對于E的短語有FF^^*；相對于T的短語有FF^^*,F;相對于F的短語有F^;F^^;簡單短語有F;F^;句柄為F. 13.一個(gè)上下文無關(guān)文法生成句子abbaa的推導(dǎo)樹如下： (1)給出串a(chǎn)bbaa最左推導(dǎo)、最右推導(dǎo)。 (2)該文法的產(chǎn)生式集合P可能有哪些元素？ (3)找出該句子的所有短語、直接短語、句柄。

13、 (1)串a(chǎn)bbaa最左推導(dǎo): S=>ABS=>aBS=>aSBBS=>aεBBS=>aεbBS=>aεbbS=>aεbbAa=>aεbbaa 最右推導(dǎo)： S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Aεbbaa=>aεbbaa (2)產(chǎn)生式有：S→ABS |Aa|ε A→a B→SBB|b (3)該句子的短語有a1b1b2a2a3、a1、b1、b2、b1b2、a2a3、a2； 直接短語有a1、b1、b2、a2； 句柄是a1。 ====================================

14、================================= 14.給出生成下列語言的上下文無關(guān)文法。 （1）{ anbnambm |n，m>=0} (2) { 1n0m 1m0n| n，m>=0} （3）{WaWr|W屬于{0|a}*，Wr表示W(wǎng)的逆} [答案] （1）{anbnambm| n，m>=0} S->AA A->aAb|ε (2) { 1n0m 1m0n| n，m>=0} S->1S0|A A->0A1|ε （3）{WaWr|W屬于{0|a}*，Wr表示W(wǎng)的逆} S->0S0|1S1|ε ===

15、================================================================ 15 .給出生成下列語言的三型文法。 (1){ an|n >=0 } (2){ anbm|n,m>=1 } (3){anbmck|n,m,k>=0 } [答案] (1) { an|n >=0 }的三型文法為： S->aS|ε (2){ anbm|n,m>=1 }的三型文法為： S->aA???? A->aA|bB B->bB|ε (3){anbmck|n,m,k>=0 }的三型文法為: A->aA|bB|cC|ε

16、 B->bB|cC|ε C->cC|ε ========================================================================== 16.構(gòu)造一文法產(chǎn)生任意長的a,b串，使得 |a|<=|b|<=2|a| 其中，“|a|”表示a字符的個(gè)數(shù);“|b|”表示b字符的個(gè)數(shù)。 [分析] b的個(gè)數(shù)在a與2a之間，所以應(yīng)想到形如aSBS和BSaS的形式，B為1到2個(gè)b，即可滿足條件。 [答案] 如分析中所述，可得文法如下： S-aSBS|BSaS|ε B->bb|b 第1個(gè)產(chǎn)生式為遞歸定義，由于在第2個(gè)

17、產(chǎn)生式中B被定義為1或2個(gè)b，所以第1個(gè)產(chǎn)生式可以保證b的個(gè)數(shù)在|a|與2|a|之間，而a與b的位置可以任意排布，所以此文法即為所求，注意第1個(gè)產(chǎn)生式中要包括s。 ============================================================================== 17.下面的文法產(chǎn)生a的個(gè)數(shù)和b的個(gè)數(shù)相等的非空a,b串 S->aB|bA B->bS|aBB|b A->aS|bAA|a? 其中非終結(jié)符B推出b比a的個(gè)數(shù)多1個(gè)的串，A則反之。 說明該文法是二義的。 對上述文法略作修改，使之非二義，并產(chǎn)生同樣的語

18、言。（略做修改的含義是：不增加非終結(jié)符。） [答案] 句子aabbab有兩種不同的推導(dǎo)。 S=>aB=>aaBB=>aabB=>aabbS=>aabbaB=>aabbab S=>aB=>aaBB=>aabSB=>aabbAB=>aabbaB=>aabbab 即它可以產(chǎn)生兩棵不同的語法樹，故它是二義的。 修改后的無二義文法如下： S->aBS|bAS|aB|bA B->aBB|b A->bAA|a ==================================================================== 18.給出0，1，2

19、，3型文法的定義。 [答案] 喬姆斯基(chomsky)把文法分成類型，即0型，1型，2型和3型，0型強(qiáng)于1型，1型強(qiáng)于2型，2型強(qiáng)于3型。 如果它的每個(gè)產(chǎn)生式α->β的結(jié)構(gòu)是α∈（VnUVt）*且至少含有一個(gè)非終結(jié)符,而β∈（VnUVt）*，我們說G=（Vt，VN，S，δ）是一個(gè)0型文法。 0型文法也稱短語文法。一個(gè)非常重要的理論結(jié)果是，0型文法的能力相當(dāng)于圖靈(Tunring)機(jī)?；蛘哒f，任何0型語言都是遞歸可枚舉的；反之，遞歸可枚舉集必定是一個(gè)0型語言。 如果把0型文法分別加上以下的第i條限制，則我們就得i型文法為： 1．G的任何產(chǎn)生式α->β 均滿足|α|<=|β|；僅僅S->ε例外，但S不得出現(xiàn)在任何產(chǎn)生式的右部。 2．G的任何產(chǎn)生式為A->β，A∈Vn，β∈（VnUVt）* 3．G的任何產(chǎn)生式為A->aB或A->a，其中A，B∈Vn 1型文法也稱上下文有關(guān)文法。這種文法意味著，對非終結(jié)符進(jìn)行替換時(shí)務(wù)必考慮上下文，而且，—般不允許替換成空串。 2型文法對非終結(jié)符進(jìn)行替換時(shí)無須考慮上下文， 3型文法也稱線性文法。