編譯原理 第二章習(xí)題答案
第2章 習(xí)題解答1.文法GS為: S->Ac|aB A->ab B->bc 寫(xiě)出L(GS)的全部元素。 答案 S=>Ac=>abc 或S=>aB=>abc 所以L(GS)=abc =2. 文法GN為: N->D|ND D->0|1|2|3|4|5|6|7|8|9 GN的語(yǔ)言是什么? 答案 GN的語(yǔ)言是V+。V=0,1,2,3,4,5,6,7,8,9 N=>ND=>NDD. =>NDDDD.D=>D.D =3.已知文法GS: SdAB AaA|a B|bB 問(wèn):相應(yīng)的正規(guī)式是什么?GS能否改寫(xiě)成為等價(jià)的正規(guī)文法? 答案 正規(guī)式是daa*b*; 相應(yīng)的正規(guī)文法為(由自動(dòng)機(jī)化簡(jiǎn)來(lái)): GS:SdA Aa|aB BaB|a|b|bC CbC|b 也可為(觀察得來(lái)):GS:SdA Aa|aA|aB BbB| =4.已知文法GZ: Z->aZb|ab 寫(xiě)出L(GZ)的全部元素。 答案 Z=>aZb=>aaZbb=>aaa.Z.bbb=> aaa.ab.bbb L(GZ)=anbn|n>=1 =5.給出語(yǔ)言anbncm|n>=1,m>=0的上下文無(wú)關(guān)文法。 分析 本題難度不大,主要是考上下文無(wú)關(guān)文法的基本概念。上下文無(wú)關(guān)文法的基本定義是:A->,AVn,(VnVt)*,注意關(guān)鍵問(wèn)題是保證anbn的成立,即“a與b的個(gè)數(shù)要相等”,為此,可以用一條形如A->aAb|ab的產(chǎn)生式即可解決。 答案 構(gòu)造上下文無(wú)關(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)寫(xiě)為S->AB,其中A推出anbn,B推出cm。因?yàn)閙可為0,故上式進(jìn)一步改寫(xiě)為S->AB|A。接下來(lái)考慮A,凡是要求兩個(gè)終結(jié)符個(gè)數(shù)相等的問(wèn)題,都應(yīng)寫(xiě)為A->aAb|ab形式,對(duì)于B就很容易寫(xiě)成B->Bc|c了。 =6 .寫(xiě)一文法,使其語(yǔ)言是偶正整數(shù)集合。 要求: (1)允許0開(kāi)頭; (2)不允許0開(kāi)頭。 答案 (1)允許0開(kāi)頭的偶正整數(shù)集合的文法 E->NT|G|SFM T->NT|G N->D|1|3|5|7|9 D->0|G G->2|4|6|8 S->NS| F->1|3|5|7|9|GM->M0|0 (2)不允許0開(kāi)頭的偶正整數(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)及語(yǔ)法樹(shù) (1)i; (2)i*i+i (3)i+i*i (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)造兩棵語(yǔ)法樹(shù),從而證明下述文法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á)式> =>表達(dá)式運(yùn)算符表達(dá)式運(yùn)算符 i =>表達(dá)式運(yùn)算符表達(dá)式 * i => 表達(dá)式運(yùn)算符i * i =>表達(dá)式+ i * i => i + i * i 所以,該文法是二義的。=9. 文法GS為: S->Ac|aB A->ab B->bc 該文法是否為二義的?為什么? 答案 對(duì)于串a(chǎn)bc (1)S=>Ac=>abc (2)S=>aB=>abc 即存在兩不同的最右推導(dǎo) 所以,該文法是二義的。 =10.考慮下面上下文無(wú)關(guān)文法: S->SS*|SS+|a (1)表明通過(guò)此文法如何生成串a(chǎn)a+a*,并為該串構(gòu)造語(yǔ)法樹(shù)。 (2) GS的語(yǔ)言是什么? 答案 (1)此文法生成串a(chǎn)a+a*的最右推導(dǎo)如下 S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a* (2)該文法生成的語(yǔ)言是即加法和乘法的逆波蘭式, =11. 令文法GE為: E->E+T|E-T T->T*F|T/F|F F->(E)|I 證明E+T*F是它的一個(gè)句型,指出這個(gè)句型的所有短語(yǔ)、直接短語(yǔ)和句柄。 答案 此句型對(duì)應(yīng)語(yǔ)法樹(shù)如右,故為此文法一個(gè)句型。 或者:因?yàn)榇嬖谕茖?dǎo)序列: E=>E+T=>E+T*F,所以 E+T*F句型 此句型相對(duì)于E的短語(yǔ)有:E+T*F;相對(duì)于T的短語(yǔ)有T*F, 直接短語(yǔ)為:T*F;。句柄為:T*F 12.已知文法GE: EET+|T TTF* | F FF | a 試證:FF*是文法的句型,指出該句型的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄. 答案 該句型對(duì)應(yīng)的語(yǔ)法樹(shù)如下:該句型相對(duì)于E的短語(yǔ)有FF*;相對(duì)于T的短語(yǔ)有FF*,F;相對(duì)于F的短語(yǔ)有F;F;簡(jiǎn)單短語(yǔ)有F;F;句柄為F. 13.一個(gè)上下文無(wú)關(guān)文法生成句子abbaa的推導(dǎo)樹(shù)如下: (1)給出串a(chǎn)bbaa最左推導(dǎo)、最右推導(dǎo)。 (2)該文法的產(chǎn)生式集合P可能有哪些元素? (3)找出該句子的所有短語(yǔ)、直接短語(yǔ)、句柄。(1)串a(chǎn)bbaa最左推導(dǎo): S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa 最右推導(dǎo): S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa (2)產(chǎn)生式有:SABS |Aa| Aa BSBB|b (3)該句子的短語(yǔ)有a1b1b2a2a3、a1、b1、b2、b1b2、a2a3、a2; 直接短語(yǔ)有a1、b1、b2、a2; 句柄是a1。 =14.給出生成下列語(yǔ)言的上下文無(wú)關(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 .給出生成下列語(yǔ)言的三型文法。 (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| B->bB|cC| C->cC| =16.構(gòu)造一文法產(chǎn)生任意長(zhǎng)的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è)產(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則反之。 說(shuō)明該文法是二義的。 對(duì)上述文法略作修改,使之非二義,并產(chǎn)生同樣的語(yǔ)言。(略做修改的含義是:不增加非終結(jié)符。) 答案 句子aabbab有兩種不同的推導(dǎo)。 S=>aB=>aaBB=>aabB=>aabbS=>aabbaB=>aabbab S=>aB=>aaBB=>aabSB=>aabbAB=>aabbaB=>aabbab 即它可以產(chǎn)生兩棵不同的語(yǔ)法樹(shù),故它是二義的。 修改后的無(wú)二義文法如下: S->aBS|bAS|aB|bA B->aBB|b A->bAA|a =18.給出0,1,2,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)*,我們說(shuō)G=(Vt,VN,S,)是一個(gè)0型文法。 0型文法也稱短語(yǔ)文法。一個(gè)非常重要的理論結(jié)果是,0型文法的能力相當(dāng)于圖靈(Tunring)機(jī)?;蛘哒f(shuō),任何0型語(yǔ)言都是遞歸可枚舉的;反之,遞歸可枚舉集必定是一個(gè)0型語(yǔ)言。 如果把0型文法分別加上以下的第i條限制,則我們就得i型文法為: 1G的任何產(chǎn)生式-> 均滿足|<=|;僅僅S->例外,但S不得出現(xiàn)在任何產(chǎn)生式的右部。 2G的任何產(chǎn)生式為A->,AVn,(VnUVt)* 3G的任何產(chǎn)生式為A->aB或A->a,其中A,BVn 1型文法也稱上下文有關(guān)文法。這種文法意味著,對(duì)非終結(jié)符進(jìn)行替換時(shí)務(wù)必考慮上下文,而且,般不允許替換成空串。 2型文法對(duì)非終結(jié)符進(jìn)行替換時(shí)無(wú)須考慮上下文, 3型文法也稱線性文法。