編譯原理題庫(kù)

1、Tiange's reference第一章?什么是編譯器？?編譯程序的結(jié)構(gòu)分為幾個(gè)階段，各階段的任務(wù)是什么？?遍、編譯前端及編譯后端的含義？?編譯程序的生成方式有哪些？第二章?1. 寫(xiě)一文法，使其語(yǔ)言是偶正整數(shù)的集合。?要求：（1）允許 0打頭 （2） 不允許 0 打頭解：（ 1）允許 0 開(kāi)頭的偶正整數(shù)集合的文法Et NT|DTt NT|DNtD|1|3|5|7|9Dt0|2|4|6|8（2）不允許 0 開(kāi)頭的偶正整數(shù)集合的文法E t NT|DT t FT|GN t D|1|3|5|7|9D t 2|4|6|8F tN|0G tD|02.證明下述文法 G表達(dá)式是二義的。表達(dá)式 =a|

2、（表達(dá)式）| 表達(dá)式運(yùn)算符表達(dá)式運(yùn)算符：=+卜|*|/解：可為句子 a+a*a 構(gòu)造兩個(gè)不同的最右推導(dǎo) :最右推導(dǎo) 1表達(dá)式表達(dá)式 運(yùn)算符 表達(dá)式表達(dá)式 運(yùn)算符 a表達(dá)式 * a表達(dá)式 運(yùn)算符 表達(dá)式 * a表達(dá)式運(yùn)算符 a * a表達(dá)式 + a * aa + a * a最右推導(dǎo) 2表達(dá)式表達(dá)式 運(yùn)算符 表達(dá)式表達(dá)式 運(yùn)算符表達(dá)式運(yùn)算符表達(dá)式表達(dá)式 運(yùn)算符表達(dá)式運(yùn)算符 a表達(dá)式 運(yùn)算符表達(dá)式 * a表達(dá)式運(yùn)算符 a * a表達(dá)式 + a * aa + a * a3. 給出生成下述語(yǔ)言的上下文無(wú)關(guān)文法：（1） anbnambm| n ， m>=0（2） 1n0m1m0n| n ， m>

3、;=0 解： （ 1） anbnambm| n ，m>=0StAAAt aAb| eTiange's reference(2) 1nOmlmOn| n , m>=04 1S0|A 2 0A1| £第三章1、構(gòu)造一個(gè)DFA它接收刀=a, b上所有滿足下述條件的字符串：字符串中的每個(gè)a都有至少一個(gè)b直接跟在其右邊。解:(b*abb*)*已知刀=a, b，根據(jù)題意得出相應(yīng)的的正規(guī)式為: 根據(jù)正規(guī)式畫(huà)出相應(yīng)的DFA M如下圖所示用子集法將其確定化Xa2341b65IIaIbX,1,2,3,Y42,345,6,1,2,3,Y|2,342,35,6,1,2,3,Y46,1,2

4、,3,Y6,1,2,3,Y46,1,2,3,YIIaIb0121一3212314414由DFA得狀態(tài)圖 順序重新命名DFA M第四章練習(xí)1 :文法GV:V t N|NE E t V|V+E是否為L(zhǎng)L(1)文法，如不是，如何將其改造成LL(1)文法。解:LL(1)文法的基本條件是不含左遞歸和回溯(公共左因子)，而GV中含有回溯，所以先消Tiange's referenceV ' t£ |E 't£ |+E除回溯得到文法 G V:G ' V :V t NVE t VE' ENt i由LL(1)文法的充要條件可證G V是LL(1)文法練習(xí)2

5、:有文法 Gs:S t ba A t BS|d B t aA|bS|c (1)證明文法G是LL(1)文法。 構(gòu)造LL(1)分析表。A的任何兩個(gè)不同產(chǎn)生式ATa |(3) 寫(xiě)出句子adccd的分析過(guò)程解：(1) 一個(gè)LL(1)文法的充要條件是：對(duì)每一個(gè)非終結(jié)符有下面的條件成立: FIRST( a ) A FIRST( 3 )=;若 B * s ,則有 FIRST( a ) A FOLLOW(A) 對(duì)于文法Gs:S t ba a t BS|d Bt aA|bS|c其FIRST集如下：FIRST(B)=a, b, c; FIRST(A)=a, b, c, d; FIRST(S)=a, b, c。其F

6、OLLOW如下：首先，F(xiàn)OLLOW(S)=#;對(duì) St BA有：FIRST(A) s 加入 FOLLOW(B),即 FOLLOW(B)=a, b, c, d ;對(duì) At BS有：FIRST(S) s 加入 FOLLOW(B),即 FOLLOW(B)=a, b, c, d ;對(duì) Bt aA 有：FOLLOW(B加入 FOLLOW(A),即 FOLLOW(A)=a, b, c, d ;對(duì) Bt bS 有：FOLLOW(B加入 FOLLOW(S),即 FOLLOW(S)=#, a, b, c, d ;由 At BS|d 得：FIRST(BS)A FIRST(d) = a, b, c A d=;由 Bt aA|bS|c 得：FIRST(aA)A FIRST(bS) A FIRST(c) =a A b A c=。由于文法Gs不存在形如3Ts的產(chǎn)生式，故無(wú)需求解形如FIRST( a ) A FOLLOW(A的值。也即，文法 GS是一個(gè)LL(1)文法。(2)由 Gs:S t BAA t BS|d B t aA|bS|c的FIRST(B)=a, b, c;FOLLOW(B)=a, b, c, d ;FIRST(A)=a, b, c, d;FOLLOW(A)=a, b, c, d ;FIRST(S)=a, b, c。 FOLLOW(S)=#, a, b, c, d 可構(gòu)造LL(1)預(yù)測(cè)分析表