編譯原理試題3

1、編譯原理試題3編譯原理試題3課程測(cè)試試題（B卷）一、判斷（15分）1 、編譯程序是一種語(yǔ)言翻譯程序，它將源語(yǔ)言程序翻譯成功能等價(jià)的目標(biāo)語(yǔ)言程序。2 、所謂規(guī)則或產(chǎn)生式是指形如af®或a:=卩的（a,卩）有序?qū)?，其中a是字母表V的正閉包元素，而卩是字母表V的閉包元素。3 、設(shè)文法G=（VN,VT,P,S）,若P中的每一個(gè)規(guī)則都是AfaB或Afa,其中A和B是非終結(jié)符，而a是終結(jié)符，則稱(chēng)此文法G為正規(guī)文法或3型文法。4 、實(shí)用文法中不得含有形如UfU的有害規(guī)則，也不得含有由不可達(dá)或不可終止的非終結(jié)符所構(gòu)成的多余規(guī)則。5 、對(duì)任意給定的一個(gè)正規(guī)式R,都可以將它轉(zhuǎn)換為與之功能等價(jià)的正規(guī)文法，

2、或與之功能等價(jià)的有窮自動(dòng)機(jī)。6 、LEX是一個(gè)用于構(gòu)造各種各樣語(yǔ)言的詞法分析程序；YACC是一個(gè)用于構(gòu)造各種各樣語(yǔ)言的語(yǔ)法分析程序。7 、假設(shè)現(xiàn)有五元組表示的有窮自動(dòng)機(jī)M=（K，V,F，S，Z），若M是NFA則S表示初態(tài)，且S具有唯一性，它是狀態(tài)集K的一個(gè)元素。8 、算符優(yōu)先分析方法和LR分析方法都是自下而上的分析方法，它們的分析過(guò)程實(shí)際上就是規(guī)范歸約過(guò)程。9 、LR（0）項(xiàng)目集規(guī)范族中的項(xiàng)目由兩部分構(gòu)成，一部分是心，即原來(lái)的LR（1）項(xiàng)目，另一部分是向前搜索符號(hào)集。10 、所謂優(yōu)化實(shí)質(zhì)上是對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼運(yùn)行結(jié)果與變換前的代碼運(yùn)行結(jié)果相同，但運(yùn)行速度或占用的存儲(chǔ)空間加大。

3、常用的優(yōu)化技術(shù)有刪除多余運(yùn)算、代碼外提、強(qiáng)度削弱、變換循環(huán)控制條件、合并已知變量與復(fù)寫(xiě)傳播等。11 、對(duì)一個(gè)不包含空規(guī)則的算符文法，如果文法中的任意兩個(gè)終結(jié)符構(gòu)成的符號(hào)對(duì)之間最多只有大于、小于和等于三種優(yōu)先關(guān)系中的一種成立，則稱(chēng)該算符文法為算符優(yōu)先文法。12 、目標(biāo)程序運(yùn)行時(shí)的動(dòng)態(tài)數(shù)據(jù)存儲(chǔ)區(qū)分為堆區(qū)和棧區(qū)，它用于存放可變數(shù)據(jù)以及管理過(guò)程活動(dòng)的控制信息。13 、在語(yǔ)法分析過(guò)程中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)規(guī)則所對(duì)應(yīng)的語(yǔ)義子程序或語(yǔ)義動(dòng)作進(jìn)行翻譯的辦法，稱(chēng)為語(yǔ)法制導(dǎo)翻譯，它被現(xiàn)代很多編譯程序所采用。14 、可歸前綴本身就是活前綴，它是包含句柄在內(nèi)的活前綴。15 、符號(hào)表用來(lái)存放語(yǔ)言程序中出現(xiàn)的有

4、關(guān)標(biāo)識(shí)符的屬性信息，這些信息集中反映了標(biāo)識(shí)符的語(yǔ)義特征屬性。二、將表達(dá)式A:=B*（C-D）/D：（共9分）1、翻譯成逆波蘭式的中間代碼形式。（2分）2、翻譯成四元式的中間代碼形式。（4分）3、將譯成的四元式用DAG表示。（3分）三、現(xiàn)有文法GE：（共12分）EE+T|E-T|TTfT*F|T/F|FFfi|（E）4、證明：F+T*（E）是文法的一個(gè)句型。（3分）5、構(gòu)造句型F+T*（E）的語(yǔ)法推導(dǎo)樹(shù)。（3分）6、指出該句型所有短語(yǔ)、直接短語(yǔ)和句柄。（6分）四、給定正規(guī)式R=d（a|bc）*d，要求：（12分）1 、構(gòu)造對(duì)應(yīng)的NFAM狀態(tài)圖，使得L（M）=L（R）。（4分）2、將所得NFAM確

5、定化和最小化。（8分）五、現(xiàn)有文法GS:（共16分）SfS;D|DDfD（T）|HHfm|（S）TfT*S|S1 、計(jì)算GS的FIRSTVT和LASTVT（4分）2 、構(gòu)造GS的算符優(yōu)先關(guān)系表,并說(shuō)明GS是否為算符優(yōu)先文法；分）3 、給出輸入串（m*m）#的算符優(yōu)先分析過(guò)程。（4分）4、根據(jù)分析過(guò)程總結(jié)算符優(yōu)先分析方法的優(yōu)缺點(diǎn)。（2分）六、已知GS:（18分）Sf（A）|a|bAfA,S|S1 、給出（a,（b,b）的最左推導(dǎo)。（3分）2 、判斷該文法是否為L(zhǎng)L（1）文法。若是，直接給出它的預(yù)測(cè)分析表；若不是，先將其改寫(xiě)為L(zhǎng)L（1）文法，再給出它的預(yù)測(cè)分析表；（10分）3 、給出輸入串（b,b

6、）#的分析過(guò)程，并說(shuō)明該串是否為GS的句子。（5分）七、對(duì)給定文法GS':(共18分)0)S'fS1)Sf2)SfB3)AfaAc4)Aa5)BfbBd6)Bb1 、構(gòu)造GS'的LR(O)項(xiàng)目集規(guī)范族DFA并據(jù)此判斷GS'是否為L(zhǎng)R(O)文法。(6分)2 、進(jìn)一步判斷GS'是否為SLR(1)文法，并給出對(duì)應(yīng)的SLR(1)分析表。(6分)3、給出輸入串bbd#的SLR(1)分析過(guò)程。(4分)4 、判斷GS'是否為L(zhǎng)R(1)文法和LALR(1)文法。(2分)編譯原理課程測(cè)試試卷評(píng)分標(biāo)準(zhǔn)(數(shù)計(jì)學(xué)院03B卷)第一題：判斷題(15分)1 、共有15道小題，

7、每小題1分，15X1=15分。第二題：(9分)1、表達(dá)式A:=B*(C-D)/D的逆波蘭式表示：ABCD-*D/:=。(2分)2、表達(dá)式A:=B*(C-D)/D的四元式表示：(4分)(1)(-,C,D,t1)(2)(*,B,t1,t2)(3)(/,t2,D,t3)(4)(:=,t3,_,A)3、將譯成的四元式用DAG表示：(3分)第三題：(12分)1 、證明(3分)：因?yàn)榇嬖谕茖?dǎo)序列E=>E+T=>T+T=>F+T=>F+T*F=>F+T*(E)，即有EF+T*(E)成立，所以，F(xiàn)+T*(E)是文法的一個(gè)句型。2 、語(yǔ)法樹(shù)(3分)3 、句型分析(6分)句型F+T*

8、(E)相對(duì)于E的短語(yǔ)有：F+T*(E),F。句型F+T*(E)相對(duì)于T的短語(yǔ)有：F,T*(E)o句型F+T*(E)相對(duì)于F的短語(yǔ)有：(E)。(3分)句型F+T*(E)相對(duì)于TfF的直接短語(yǔ)有：Fo句型F+T*(E)相對(duì)于Ff(E)的直接短語(yǔ)有：(E)o(2分)句型F+T*(E)的句柄為：Fo(1分)(2)短語(yǔ)每錯(cuò)兩個(gè)扣1分。第四題：(12分)1、NFAM(4分)2 、（1）確定化（4分）步驟如下表所示（可省）：將集合TO至T3各用一個(gè)狀態(tài)表示，確定化后所得DFAM如下：（2）最小化（4分）步驟如下表所示（可?。鹤詈筮€有4個(gè)不可再分割的子集，每個(gè)子集中只包含一個(gè)狀態(tài)，即原DFAM已經(jīng)是最小化D

9、FA。第五題：（16分）1 、對(duì)文法進(jìn)行拓廣，加入規(guī)則S'-S后得GS，其非終結(jié)符的FIRSTVTLASTVT集計(jì)算如下：（4分）由FIRSTVTLASTVT集構(gòu)造玄和如下：2 、（1）優(yōu)先關(guān)系表為：（4分）（2）該文法是算符優(yōu)先文法（2分）。3 、（1）輸入串（m*m）#的算符優(yōu)先分析過(guò)程：（4分）（2由上述分析過(guò)程可知，用算符優(yōu)先分析法分析在確定句柄時(shí)只考慮終結(jié)符之間的優(yōu)先關(guān)系，而與非終結(jié)符無(wú)關(guān)，這使得算符優(yōu)先分析法具有效率高的優(yōu)點(diǎn)；但是，由于去掉了單非終結(jié)符之間的歸約，有可能將錯(cuò)誤的句子識(shí)別為正確的。上例中對(duì)輸入串（m*m）#能分析成功，但（m*m）#并不是文法GS的句子。這就是

10、算符優(yōu)先分析法的缺點(diǎn)。第六題：（18分）1 、給出（a,（b,b）的最左推導(dǎo)：（3分）S=（A）=（A,S）=（S,S）=（a,S）=（a,（A）=（a,（A,S）=（a,（S,S）=（a,（b,S）=（a,（b,b）2 、（1）判斷：（3分）計(jì)算各條規(guī)則的SELECT集及左部相同規(guī)則的SELECT集的交集如下：（2）將GS改寫(xiě)如下：（4分）GS:S-a|b|（A）A',SA'|&ASA（2）預(yù)測(cè)分析表：（3分）第七題：（18分）1、（1）GS'的LR（O）項(xiàng)目集規(guī)范族DFA（4分）：(2)檢查發(fā)現(xiàn)14=Afa.,Af.aAc,Af.a和15=Bfb.,Bf.b

11、Bd,Bf.b中存在移進(jìn)一歸約沖突，所以，GS'不是LR(O)文法。(2分)2、(1)在I4=Afa.,Af.aAc,Af.a中，由于根據(jù)歸約項(xiàng)目Afa.所得的FOLLOW(A)=c,#中不含移進(jìn)項(xiàng)目Af.aAc,或Af.a中的“a”。在構(gòu)造LR分析表時(shí)，遇到移進(jìn)項(xiàng)目Af.aAc,或Af.a時(shí)，在“a”列置移進(jìn)標(biāo)記S4；遇到歸約項(xiàng)目Afa.時(shí)，只在“c”,“#”兩列置歸約標(biāo)記r4。所以，I4中的移進(jìn)歸約沖突通過(guò)引入FOLLOW集得到了解決。、同樣，在I5=Bfb.,Bf.bBd,Bf.b中，由于FOLLOW(B)=d,#中不含“b”。在構(gòu)造LR分析表時(shí)，遇到移進(jìn)項(xiàng)目Bf.bBd,Bf.b時(shí)，在“b”列置移進(jìn)標(biāo)記S5;遇到歸約項(xiàng)目Bfb.時(shí)，只在“d”，“#”兩列置歸約標(biāo)記r5。所以，15中的移進(jìn)一歸約沖突通過(guò)引入FOLLOW也得到了解決。故GS'