編譯原理 第二章習題答案.doc

第2章 習題解答1.文法GS為： S-Ac|aB A-ab B-bc 寫出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的語言是什么？ 答案 GN的語言是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 問：相應的正規(guī)式是什么？GS能否改寫成為等價的正規(guī)文法？ 答案 正規(guī)式是daa*b*； 相應的正規(guī)文法為(由自動機化簡來)： GS:SdA Aa|aB BaB|a|b|bC CbC|b 也可為(觀察得來):GS:SdA Aa|aA|aB BbB| =4.已知文法GZ： Z-aZb|ab 寫出L(GZ)的全部元素。 答案 Z=aZb=aaZbb=aaa.Z.bbb= aaa.ab.bbb L(GZ)=anbn|n=1 =5.給出語言anbncm|n=1,m=0的上下文無關(guān)文法。 分析 本題難度不大，主要是考上下文無關(guān)文法的基本概念。上下文無關(guān)文法的基本定義是：A-,AVn，（VnVt）*，注意關(guān)鍵問題是保證anbn的成立，即“a與b的個數(shù)要相等”，為此，可以用一條形如A-aAb|ab的產(chǎn)生式即可解決。 答案 構(gòu)造上下文無關(guān)文法如下： S-AB|A A-aAb|ab B-Bc|c 擴展 凡是諸如此類的題都應按此思路進行，本題可做為一個基本代表?；舅悸肥沁@樣的： 要求符合anbncm，因為a與b要求個數(shù)相等，所以把它們應看作一個整體單元進行，而cm做為另一個單位，初步產(chǎn)生式就應寫為S-AB，其中A推出anbn，B推出cm。因為m可為0，故上式進一步改寫為S-AB|A。接下來考慮A,凡是要求兩個終結(jié)符個數(shù)相等的問題，都應寫為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-NS| F-1|3|5|7|9|GM-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 試給出下述表達式的推導及語法樹 (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)造兩棵語法樹，從而證明下述文法G是二義的。 表達式-表達式運算符表達式|(表達式)|i 運算符-+|-|*|/ 答案 可為句子i+i*i構(gòu)造兩個不同的最右推導: 最右推導1 表達式=表達式運算符表達式 =表達式運算符i =表達式* i =表達式運算符表達式* i =表達式運算符i * i =表達式+ i * i = i + i * i 最右推導2 表達式=表達式運算符表達式 =表達式運算符表達式運算符表達式 =表達式運算符表達式運算符 i =表達式運算符表達式 * i = 表達式運算符i * i =表達式+ i * i = i + i * i 所以，該文法是二義的。=9. 文法GS為： S-Ac|aB A-ab B-bc 該文法是否為二義的？為什么？ 答案 對于串a(chǎn)bc (1)S=Ac=abc (2)S=aB=abc 即存在兩不同的最右推導 所以，該文法是二義的。 =10.考慮下面上下文無關(guān)文法： S-SS*|SS+|a (1)表明通過此文法如何生成串a(chǎn)a+a*，并為該串構(gòu)造語法樹。 (2) GS的語言是什么？ 答案 (1)此文法生成串a(chǎn)a+a*的最右推導如下 S=SS*=SS*=Sa*=SS+a*=Sa+a*=aa+a* (2)該文法生成的語言是即加法和乘法的逆波蘭式, =11. 令文法GE為: E-E+T|E-T T-T*F|T/F|F F-(E)|I 證明E+T*F是它的一個句型，指出這個句型的所有短語、直接短語和句柄。 答案 此句型對應語法樹如右，故為此文法一個句型。 或者：因為存在推導序列: E=E+T=E+T*F，所以 E+T*F句型 此句型相對于E的短語有:E+T*F；相對于T的短語有T*F, 直接短語為：T*F；。句柄為：T*F 12.已知文法GE: EET+|T TTF* | F FF | a 試證：FF*是文法的句型，指出該句型的短語、簡單短語和句柄. 答案 該句型對應的語法樹如下：該句型相對于E的短語有FF*；相對于T的短語有FF*,F;相對于F的短語有F;F;簡單短語有F;F;句柄為F. 13.一個上下文無關(guān)文法生成句子abbaa的推導樹如下： (1)給出串a(chǎn)bbaa最左推導、最右推導。 (2)該文法的產(chǎn)生式集合P可能有哪些元素？ (3)找出該句子的所有短語、直接短語、句柄。(1)串a(chǎn)bbaa最左推導: S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa 最右推導： S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=abbaa (2)產(chǎn)生式有：SABS |Aa| Aa BSBB|b (3)該句子的短語有a1b1b2a2a3、a1、b1、b2、b1b2、a2a3、a2； 直接短語有a1、b1、b2、a2； 句柄是a1。 =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 .給出生成下列語言的三型文法。 (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)生任意長的a,b串，使得 |a|=|b|bb|b 第1個產(chǎn)生式為遞歸定義，由于在第2個產(chǎn)生式中B被定義為1或2個b，所以第1個產(chǎn)生式可以保證b的個數(shù)在|a|與2|a|之間，而a與b的位置可以任意排布，所以此文法即為所求，注意第1個產(chǎn)生式中要包括s。 =17.下面的文法產(chǎn)生a的個數(shù)和b的個數(shù)相等的非空a,b串 S-aB|bA B-bS|aBB|b A-aS|bAA|a 其中非終結(jié)符B推出b比a的個數(shù)多1個的串，A則反之。 說明該文法是二義的。 對上述文法略作修改，使之非二義，并產(chǎn)生同樣的語言。（略做修改的含義是：不增加非終結(jié)符。） 答案 句子aabbab有兩種不同的推導。 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，3型文法的定義。 答案 喬姆斯基(chomsky)把文法分成類型，即0型，1型，2型和3型，0型強于1型，1型強于2型，2型強于3型。 如果它的每個產(chǎn)生式-的結(jié)構(gòu)是（VnUVt）*且至少含有一個非終結(jié)符,而（VnUVt）*，我們說G=（Vt，VN，S，）是一個0型文法。 0型文法也稱短語文法。一個非常重要的理論結(jié)果是，0型文法的能力相當于圖靈(Tunring)機。或者說，任何0型語言都是遞歸可枚舉的；反之，遞歸可枚舉集必定是一個0型語言。 如果把0型文法分別加上以下的第i條限