編譯原理試題3

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

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

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

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

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

6、）#的分析過程，并說明該串是否為GS的句子。（5分）七、對給定文法GS':(共18分)0)S'fS1)Sf2)SfB3)AfaAc4)Aa5)BfbBd6)Bb1 、構造GS'的LR(O)項目集規(guī)范族DFA并據此判斷GS'是否為LR(O)文法。(6分)2 、進一步判斷GS'是否為SLR(1)文法，并給出對應的SLR(1)分析表。(6分)3、給出輸入串bbd#的SLR(1)分析過程。(4分)4 、判斷GS'是否為LR(1)文法和LALR(1)文法。(2分)編譯原理課程測試試卷評分標準(數計學院03B卷)第一題：判斷題(15分)1 、共有15道小題，

7、每小題1分，15X1=15分。第二題：(9分)1、表達式A:=B*(C-D)/D的逆波蘭式表示：ABCD-*D/:=。(2分)2、表達式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分)：因為存在推導序列E=>E+T=>T+T=>F+T=>F+T*F=>F+T*(E)，即有EF+T*(E)成立，所以，F+T*(E)是文法的一個句型。2 、語法樹(3分)3 、句型分析(6分)句型F+T*

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

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

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

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