編譯原理歷年試題及答案

1、編譯原理歷年試題及答案一（每項選擇2 分，共 20 分）選擇題1 將編譯程序分成若干個“遍”是為了_b_。a.提高程序的執(zhí)行效率b.使程序的結構更加清晰c.利用有限的機器內存并提高機器的執(zhí)行效率d.利用有限的機器內存但降低了機器的執(zhí)行效率2 構造編譯程序應掌握_d_。a.源程序b.目標語言c.編譯方法d.以上三項都是3 .變量應當c oa.持有左值b.持有右值c.既持有左值又持有右值d.既不持有左值也不持有右值4 編譯程序絕大多數(shù)時間花在_d_上。a.出錯處理b.詞法分析c.目標代碼生成d.管理表格5 詞法分析器的輸出結果是_c_。a.單詞的種別編碼b.單詞在符號表中的位置c.單詞的種別編碼和

2、自身值d.單詞自身值6 正規(guī)式MI 和 M2 等價是指_c_。a. MI 和 M2 的狀態(tài)數(shù)相等b.Ml 和 M2 的有向弧條數(shù)相等。12 / 59C.M1 和 M2 所識別的語言集相等d. Ml 和 M2 狀態(tài)數(shù)和有向弧條數(shù)相等7 中間代碼生成時所依據(jù)的是c。a.語法規(guī)則b.詞法規(guī)則c.語義規(guī)則d.等價變換規(guī)則8 .后綴式ab+cd+何用表達式_b_來表示。a a+b/c+d b (a+b)/(c+d) c a+b/(c+d) d a+b+c/d管理技術。9 程序所需的數(shù)據(jù)空間在程序運行前就可確定，稱為_ca.動態(tài)存儲b.棧式存儲c.靜態(tài)存儲d.堆式存儲10 .堆式動態(tài)分配申請和釋放存儲空間

3、遵守 d原則。a.先請先放b.先請后放c.后請先放d.任意二(每小題 10 分，共 80 分)簡答題1 . 畫出編譯程序的總體結構圖，簡述各部分的主要功能。2 . 已知文法 GE:E ET+|T T TF* | F F - 1 | a試證：FF*是文法的句型，指出該句型的短語、簡單短語和句柄3 為正規(guī)式(a|b) *a(a|b) 構造一個確定的有限自動機。4 設文法G(S：)Sf (L)|a S|aLL, S|S(1)消除左遞歸和回溯；(2)計算每個非終結符的FIRSTS口 FOLLOW（3）構造預測分析表。5 已知文法A-aAd| aAb| e判斷該文法是否SLR（1）文法，若是構造相應分析

4、表，并對輸入串ab#合出分析過程。6 .構造算符文法GH的算符優(yōu)先關系（含#）。GH：HH H;M|MMH d|aHb7 已構造出文法G（ S）（ 1） S BB（ 2） B aB（ 3） B b1） ）。給出 DFA 圖2） .給出LR分析表3） .假定輸入串為abaab,請名出LR分析過程（即狀態(tài)，符號，輸入串的 變化過程）。8 將下面的語句翻譯成四元式序列：while ACA BD doif A=1 then C:=C+lelse while A A(1) A-aAd(2)A- aAb(3)A- &(2)構造識別活前綴的 DFAFOLLOW(A)=d,b,#對于狀態(tài) I0: FOLLOW

5、(A) a=對于狀態(tài) I1: FOLLOW(A) a=因為，在DFA 中無沖突的現(xiàn)象，所以該文法是SLR(1)文法。(3)SLR(1)分析表狀態(tài) ACTION GOTOa B d # A0 S2 r3 r3 r3 11 acc2 S2 r3 r3 r3 33 S5 S44 r1 r1 r15 r2 r2 r2(4)串ab#的分析過程步驟狀態(tài)棧符號棧當前字符剩余字符串動作1 0 # a b#進2 02 #a b #)*A A- &3 023 #aA b #移進4 0235 #aAb #歸約 A- aAb5 01 #A #接受6【解答】由MHd和MH a,得：FIRSTVT(M尸d,a;由H-H；

6、,得：FIRSTVT(H) =; 由H-M得：FIRSTVT(M) cFIRSTVT(H即 FIRSTVT(H)=;,d,a由Mfd和MR,b得：LASTVT(M)=d,b；由 H-，；m 得：LASTVT(H)=; ;由H-M得：LASTVT(M) cLASTVT(H ,即 LASTVT(H)=;,d,b對文法開始符 H,#H#ft,即有 # =#, #他即 #; , #d. # d , d#, b#。對形如 6,ab,或 P,aQb,有 a=b,由 MHa|b 得：a=b；對形如 PQ,aR,而 b6FIRSTVT(R)有2 對形如 6,Rb,而 a 6 LASTVT(R)有 ab。由HA

7、, ; M得：;FIRSTVT(M)即： d，：aH,得：aFIRSTVT(H)即：a; , ad, a;即：;,d; , b;由MR,Hb得：LASTVT(H)b 即：; b, db, bb由此得到算符優(yōu)先關系表，見表3.5。7【解答】( 1) LR 分析表如下：( 2)分析表狀態(tài) ACTION GOTOa b # S B0 s3 s4 1 21 acc2 S3 S4 53 s3 s4 64 r3 r35 R1 R1 r16 R2 R2 R27 3)句子 abaab 的分析過程表:句子 abaab 的分析過程步驟狀態(tài)符號棧輸入串所得產生式8 #0 # abaad#1 #03 #a baad#

8、2 #034 #ab aab# B fb3 #036 #aB aab# B aB4 #02 #B aab#5 #023 #Ba ab#6 #0233 #Baa b#7 #02334 #Baab #8 #02336 #BaaB #9 #0236 #BaB ad#10 #025 #BB ad#11 #01 #S d#12 # # d#13識別成功8【解答】該語句的四元式序列如下(其中E1、 E2和E3分另U對應：ACA BD, A=1和AW D并且關系運算符優(yōu)先級高)：100 (j,A,C,102)101(j,_,_,113) /*E1 為 F*/102 O,B,D,104)/*El 為 T*/1

9、03 (j,_,_,113) /*El 為 F*/104 O=,A,1,106)/*Ez 為 T*/105 (j,_,_,108) /*EZ 為 F*/106 (,C,1,C) /*C:=C+1*/ 107 (j,_,_,112)/*跳過 else后的語句 */108 (j 2， 4-3(3)求出流圖中的循環(huán):回邊 5-2對應的循環(huán)：2、 5、3、 4；回邊 4-3對應的循環(huán)：編譯原理模擬試題一一、是非題（請在括號內，正確的劃 M錯誤的劃為（每個2分，共20 分）1 .計算機高級語言翻譯成低級語言只有解釋一種方式。（X）2 .在編譯中進行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯誤。（X ）3 甲機

10、上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操 作系統(tǒng)功能完全相同。（V）4 .正則文法其產生式為 A-a, A-Bb, A,氏VN, a、b6VT。（X）5 每個文法都能改寫為LL（1）文法。 （ V）6 遞歸下降法允許任一非終極符是直接左遞歸的。（ V）7 .算符優(yōu)先關系表不一定存在對應的優(yōu)先函數(shù)。（X ）8 .自底而上語法分析方法的主要問題是候選式的選擇。（X）9 . LR法是自頂向下語法分析方法。（X）10 .簡單優(yōu)先文法允許任意兩個產生式具有相同右部。（x ）二、選擇題（請在前括號內選擇最確切的一項作為答案劃一個勾，多劃按錯論）（每個4分，共40分）1 一個編譯程序中，不

11、僅包含詞法分析，_，中間代碼生成，代碼優(yōu)化，目標代碼生成等五個部分。A （ ）語法分析B ( )文法分析C ( )語言分析D ( )解釋分析2 詞法分析器用于識別_。A ( )字符串B ( )語句C ( )單詞D ( )標識符3 語法分析器則可以發(fā)現(xiàn)源程序中的_。A ( )語義錯誤B ( )語法和語義錯誤C ( )錯誤并校正D ( )語法錯誤4 下面關于解釋程序的描述正確的是_。(1)解釋程序的特點是處理程序時不產生目標代碼(2)解釋程序適用于COBO困FORTRAN言(3)解釋程序是為打開編譯程序技術的僵局而開發(fā)的A ( )(1)(2)B ( )(1)C ( )(1)(2)(3)D ( )(

12、2)(3)5 解釋程序處理語言時,大多數(shù)采用的是_方法。A ( )源程序命令被逐個直接解釋執(zhí)行B ( )先將源程序轉化為中間代碼,再解釋執(zhí)行C ( )先將源程序解釋轉化為目標程序,再執(zhí)行D ( )以上方法都可以6 編譯過程中 ,語法分析器的任務就是_。(1)分析單詞是怎樣構成的(2)分析單詞串是如何構成語句和說明的(3)分析語句和說明是如何構成程序的(4)分析程序的結構A ( )(2)(3)B ( )(2)(3)(4)C ( )(1)(2)(3)D ( )(1)(2)(3)(4)7 編譯程序是一種_。A. ( )匯編程序B ( )翻譯程序C ( )解釋程序D ( )目標程序8 文法G 所描述的

13、語言是_的集合。A. ( )文法G 的字母表 V 中所有符號組成的符號串B.()文法G的字母表V的閉包V*中的所有符號串C ( )由文法的開始符號推出的所有終極符串D. ( )由文法的開始符號推出的所有符號串9 文法分為四種類型，即0 型、 1 型、 2 型、 3 型。其中 3 型文法是A. ( )短語文法B ( )正則文法C ( )上下文有關文法D ( )上下文無關文法10 一個上下文無關文法G 包括四個組成部分，它們是：一組非終結符號，一組終結符號，一個開始符號，以及一組_。A ( )句子B ( )句型C ( )單詞D ( )產生式三、填空題(每空1 分，共 10 分 )1 編譯程序的工作

14、過程一般可以劃分為詞法分析,語法分析,語義分析,中間代碼生成 ,代碼優(yōu)化等幾個基本階段,同時還會伴有_表格處理_和_出錯處理。2 若源程序是用高級語言編寫的,_目標程序_是機器語言程序或匯編程序,則其翻譯程序稱為_編譯程序_。3 編譯方式與解釋方式的根本區(qū)別在于_是否生成目標代碼_。4 對編譯程序而言 ,輸入數(shù)據(jù)是_源程序_,輸出結果是_目標程序_。5 產生式是用于定義_語法成分_的一種書寫規(guī)則。6 語法分析最常用的兩類方法是_自上而下_和_自下而上_分析法。四、簡答題( 20 分)1. 什么是句子？什么是語言 ?答：(1)設G是一個給定的文法，S是文法的開始符號，如果S x箕中x6VT*),

15、則 稱x是文法的一個句子。(2)設GS層給定文法，則由文法G所定義的語言L(G刈描述為：L(G)= x | S 慶xVT*。2 .寫一文法，使其語言是偶正整數(shù)的集合，要求：允許0打頭；(2)不允許0打頭。解：(1)GS=(S,P,D,N,0,1,2,9,P,S)P:S-PD|DP-NP|ND-0|2|4|6|8N-0|1|2|3|4|5|6|7|8|9(2)G*S+=(,S,P,R,D,N,Q,0,1,2,-,P,S)P:S-PD|P0|DP-NR|NR-QR|QD-2|4|6|8N-1|2|3|4|5|6|7|8|9Q-0|1|2|3|4|5|6|7|8|93 .已知文法GE的：E T|E+

16、T|E-TT F|T*F|T/FF- (E) |i 該文法的開始符號(識別符號)是什么？ 請給出該文法的終結符號集合VT 和非終結符號集合VN。 找出句型T+T*F+i的所有短語、簡單短語和句柄。解： 該文法的開始符號(識別符號)是E。該文法的終結符號集合VT=+、-、*、/、(、)、i。非終結符號集合 VN=E、 T、 F。 句型T+T*F+I的短語為i、T*F、第一個T T+T*F+i簡單短語為i、T*F、第一個T;句柄為第一個To4 .構造正規(guī)式相應的NFA :1(0|1)*101解1(0|1)*101對應的NFA為5 .寫出表達式(a b*c)/(a b) d 的逆波蘭表示和三元式序列

17、。逆 xx 表示：abc* ab /d 三元式序列：（* , b, c）（十, a,）（+,a, b）（/,，）（D（一,，d）五 .計算題（10 分）構造下述文法GS的自動機：S-A0 A-A0|S1|0該自動機是確定的嗎？若不確定，則對它確定化。解：由于該文法的產生式S-A0， A-A0|S1 中沒有字符集VT 的輸入，所以不是確定的自動機。要將其他確定化，必須先用代入法得到它對應的正規(guī)式。把 S?A0代入產生式 A?S1有：A=A0|A01|0=A（0|01）|0=0（0|01）* 。代入 S-A0有該文法的正規(guī)式： 0（0|01）*0 ，所以，改寫該文法為確定的自動機為：由于狀態(tài)A有3

18、次輸入0的重復輸入，所以上圖只是 NFA,下面將它確定 化：下表由子集法將NFA轉換為DFA:由上表可知DFA為：編譯原理模擬試題二一、是非題（請在括號內，正確的劃 M錯誤的劃為（每個2分，共20 分）1 “用高級語言書寫的源程序都必須通過編譯,產生目標代碼后才能投入運行”這種說法。（X ）2若一個句型中出現(xiàn)了某產生式的右部，則此右部一定是該句型的句柄。 （X）3 . 一個句型的句柄一定是文法某產生式的右部。（V）4 .在程序中標識符的出現(xiàn)僅為使用性的。（X ）5 僅考慮一個基本塊，不能確定一個賦值是否真是無用的。（ V）6 削減運算強度破壞了臨時變量在一基本塊內僅被定義一次的特性。（ V）7

19、 在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達式外提和削減運算強 度。（X）8 .算符優(yōu)先關系表不一定存在對應的優(yōu)先函數(shù)。（X ）9 .數(shù)組元素的地址計算與數(shù)組的存儲方式有關。（X ）10 .編譯程序與具體的機器有關，與具體的語言無關。（X）二、選擇題（請在前括號內選擇最確切的一項作為答案劃一個勾，多劃按錯論）（每個4分，共 40分）1 通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標代碼生成等五個部分，還應包括_。A （ ）模擬執(zhí)行器B （ ）解釋器C （ ）表格處理和出錯處理D ( )符號執(zhí)行器2.文法GN= (b, N, B, N, N-b | hBB-bN，該

20、文法所描述的語 言是A. ( ) L(GN尸bi| i 0B. ( ) L(GN)=b2i| i 0C. ( ) L(GN)=b2i+1| i 0D. ( ) L(GN)=b2i+1| i 13 一個句型中的最左_稱為該句型的句柄。A ( )短語B ( )簡單短語C ( )素短語D ( )終結符號4 .設G是一個給定的文法，S是文法的開始符號，如果S-x其中x6 V*), 則稱x是文法G的一個。A ( )候選式B ( )句型C ( )單詞D ( )產生式5 文法GE：ET I E+TTF I T* FF (E)該文法句型E+ F* (E+ T)的簡單短語是下列符號串中的 。(E+ T)E +T

21、FF * (E+ T)A ( ) 和 B ( ) 和 C ( ) 和 D ( ) 6 若一個文法是遞歸的，則它所產生的語言的句子_。A ( )是無窮多個B ( )是有窮多個C ( )是可枚舉的D ( )個數(shù)是常量7 詞法分析器用于識別_。A ( )句子8 ( )句型C ( )單詞D ( )產生式8.在語法分析處理中，F(xiàn)IRST合、FOLLOW合、SELEC集合均是A. ( )非終極符集B ( )終極符集C ( )字母表D. ( )狀態(tài)集9 在自底向上的語法分析方法中，分析的關鍵是_。A.( )尋找句柄B.( )尋找句型C.( )消除遞歸D.( )選擇候選式10.在LR分析法中，分析棧中存放的狀

22、態(tài)是識別規(guī)范句型的DFA狀態(tài)。A.( )句柄B.( )前綴C.( )活前綴D.( ) LR(0)項目三、填空題(每空1 分，共 10 分 )1 .設G是一個給定的文法，S是文法的開始符號，如果S-x其中x6 VT*), 則稱 x 是文法的一個_句子 _。2 遞歸下降法不允許任一非終極符是直接_左_遞歸的。3 自頂向下的語法分析方法的基本思想是：從文法的_開始符號_開始，根據(jù)給定的輸入串并按照文法的產生式一步的向下進行_直接推導_，試圖推導出文法的_句子 _，使之與給定的輸入串_匹配 _。4 自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產生式一步地向上進行_直接歸約_，力求歸約到

23、文法的_開始符號_。5 常用的參數(shù)傳遞方式有_傳地址_，傳值和傳名。6 在使用高級語言編程時,首先可通過編譯程序發(fā)現(xiàn)源程序的全部_語法_錯誤和語義部分錯誤。四、簡答題( 20 分)1 .已知文法GS的：5 dABA aA|a8 Bb| &GS產生的語言是什么？答：GS產生的語言是 L(GS尸danbm I n1,m09 .簡述DFA與NFA有何區(qū)別？答：DFA與NFA的區(qū)別表現(xiàn)為兩個方面：一是NFA可以若干個開始狀態(tài)，而 DFA僅只一個開始狀態(tài)。另一方面， DFA的映象M是從KX定U K,而NFA的映象M是從KX 3U K的子集，即映象 M 將產生一個狀態(tài)集合(可能為空集)，而不是單個狀態(tài)。1

24、0 構造正規(guī)式相應的DFA :1(10 * | 1(010) * 1) * 0 。解： 1(10 * | 1(010) * 1) * 0 對應的 NFA為：11 已知文法 G(S)5- a|A|(T)TT, S|S寫出句子(a, a), a)的規(guī)范歸約過程及每一步的句柄解：句型歸約規(guī)則句柄(a， a)， a) S a a(S， a)， a) T S S(T， a)， a) S a a(T， S)， a) T T ， S T， S(S)， a) T S S(T)， a) S S(T) (T)(S， a) T S S(T， a) S a a(T， S) T T ， S T， S(T) S (T)

25、(T)S5.何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？1) 優(yōu)化：對程序進行各種等價變換，使得從變換后的程序出發(fā)，能產生更有效的目標代碼。(2)三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。五 .計算題( 10 分)對下面的文法G：E-TEE-+E| &T-FTT -T| F- PFF-*F|P-(E)|a|b|A(1)計算這個文法的每個非終結符的FIRST和FOLLOW集。(4分)(2)證明這個方法是LL(1)的。 (4 分)(3)構造它的預測分析表。(2 分)解：(1)計算這個文法的每個非終結符的FIRST#和FOLLOW集。FIRST合有：FIRST(E)=FIRST(T)=FIRST(F

26、)=FIRST(P)=(,a,b,A;FIRST(E尸,+-&FIRST(T尸F(xiàn)IRST(F尸F(xiàn)IRST(P尸(,a,b,A;FIRST(T)=FIRST(T) =(,a,b,A, ;FIRST(F尸F(xiàn)IRST(P尸(abj;FIRST(F尸F(xiàn)IRST(P)=,*;FIRST(P)=(,a,b,A;FOLLOW 合有：FOLLOW(E)=),#;FOLLOW(E)=FOLLOW(E)=),#;FOLLOW(T尸F(xiàn)IRST(EJ)FOLLOW(E尸+,),#;不包含 &FOLLOW(T尸F(xiàn)OLLOW(T尸F(xiàn)IRST (EFOLLOW(E尸+,),#;FOLLOW(F尸F(xiàn)IRST(U)FOLLOW

27、(T尸(,a,b,A,+,),#;環(huán)包含 FOLLOW(F)=FOLLOW(F)=FIRST(TFOLLOW(T)=(,a,b,A,+,),#;FOLLOW(P尸F(xiàn)IRST(E)FOLLOW(F尸*,(,a,b,A,+,),#;冰包含 (2)證明這個方法是LL(1)的。各產生式的SELEC集合有：SELECT(E-TE)=FIRST(T)=(,a,b,A;SELECT(E-+E)=+;SELECT(E-e 尸F(xiàn)OLLOW(E/)=,),#SELECT(T-FT)=FIRST(F)=(,a,b,A;SELECT(T-T)=FIRST(T)=(,a,b,A;SELECT(T-e 尸F(xiàn)OLLOW(T

28、/尸,+立#SELECT(F-PF)=FIRST(P)=(,a,b,A;SELECT(F-*F)=*;SELECT(F-e 尸F(xiàn)OLLOW(F)=,(,a,b,A,+-),#SELECT(P-(E)=(SELECT(P-a)=aSELECT(P-b)=bSELECT(P-A)=A可見，相同左部產生式的 SELEC集的交集均為空，所以文法 GE星LL(1)文法。(3)構造它的預測分析表。文法GE附預測分析表如下：編譯原理模擬試題三一、是非題(請在括號內，正確的劃 M錯誤的劃為(每個2分，共20 分)1 .對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN用動態(tài)貯存分配策略。(X )2 甲機上的某編譯程序在乙

29、機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相同。(X)3 .遞歸下降分析法是自頂向上分析方法。(V)4 .產生式是用于定義詞法成分的一種書寫規(guī)則。 (X )5 . LR法是自頂向下語法分析方法。(V)6 在 SLR(1)分析法的名稱中，S的含義是簡單的。(V)7 .綜合屬性是用于 自上而下”傳遞信息。(X)8 符號表中的信息欄中登記了每個名字的屬性和特征等有關信息，如類型、種屬、所占單元大小、地址等等。(X)9 .程序語言的語言處理程序是一種應用軟件。(x )10 .解釋程序適用于 COBOm口 FORTRAN言。(X)二、選擇題(請在前括號內選擇最確切的一項作為答案劃一個勾，多劃

30、按錯論)(每個 4分，共 40分)11 文法G 產生的_的全體是該文法描述的語言。A ( )句型8. ( )xx集C ( )非 xx 集D ( )句子2 .若文法G定義的語言是無限集，則文法必然是 一。A ( )遞歸的B ( )前后文無關的C ( )二義性的D ( )無二義性的3 四種形式語言文法中，1 型文法又稱為_文法。A ( )短語結構文法B ( )前后文無關文法C ( )前后文有關文法D ( )正規(guī)文法4 一個文法所描述的語言是_。A ( )唯一的B ( )不唯一的C ( )可能唯一，好可能不唯一D ( )都不對5 _和代碼優(yōu)化部分不是每個編譯程序都必需的。A ( )語法分析B ( )

31、中間代碼生成C ( )詞法分析D ( )目標代碼生成6 _是兩類程序語言處理程序。A ( )高級語言程序和低級語言程序B ( )解釋程序和編譯程序C ( )編譯程序和操作系統(tǒng)D ( )系統(tǒng)程序和應用程序7數(shù)組的內情向量中肯定不含有數(shù)組的 _的信息。A. ( )維數(shù)B ( )類型C ( )維上下界D ( )各維的界差8 .一個上下文無關文法G包括四個組成部分，它們是：一組非終結符號，一組終結符號，一個開始符號，以及一組A ( )句子B ( )句型C ( )單詞D ( )產生式2 型文法是9 文法分為四種類型，即 0 型、 1 型、 2 型、 3 型。其中A. ( )短語文法B ( )正則文法C

32、( )上下文有關文法D ( )上下文無關文法10 文法 G 所描述的語言是_的集合。A. ( )文法G 的字母表 V 中所有符號組成的符號串B.()文法G的字母表V的閉包V*中的所有符號串C ( )由文法的開始符號推出的所有終極符串D. ( )由文法的開始符號推出的所有符號串三、填空題 (每空 1 分，共 10 分)1 一個句型中的最左簡單短語稱為該句型的 句柄 。2 對于文法的每個產生式都配備了一組屬性的計算規(guī)則，稱為_語義規(guī)則。3 一個典型的編譯程序中，不僅包括_詞法分析_、 _語法分析_、 _、代碼優(yōu)化、目標代碼生成等五個部分，還應包括表格處理和出錯處理。4 從功能上說，程序語言的語句大

33、體可分為_執(zhí)行性_語句和_說明性_語句兩大類。5 掃描器的任務是從_源程序_中識別出一個個_單詞符號_。6 產生式是用于定義_語法范疇_的一種書寫規(guī)則。四、簡答題( 20 分)1. 寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以 0 開頭。解：文法G(N)：NH AB|BA AC|DB- 1|3|5|7|9D- B|2|4|6|8C- 0|D2.設文法G(S：)Sf (L)|a S|aL-L, S|S(1)消除左遞歸和回溯；(2)計算每個非終結符的FIRS書口 FOLLOW解：1) )Sf (L)|aSS f S| LSLL SL| 2) )FIRST)學(, a FOLLOW(S)#, , ,

34、 )FIRSTS a, FOLLOW(S#, , , )FIRST(L)(, a FOLLOW(L)= )FIRST(L, , FOLLOW(L= )3) 已知文法G(E)E- T|E+ TT F|T *FF-(E)|i(1)給出句型 (T *F i) 的最右推導；(2)給出句型 (T *F i) 的短語、素短語。解：(1)最右推導：E-T-F-(E)-(E T)-(E F)-(E i)-(T i)-(T*F i)(2)短語：(T*F i)， T*F i， T*F， i素短語：T*F,i4) While a0Vb0 then a：=a 1else b：= b+1End；翻譯成四元式序列。解：(

35、1) (j, a, 0, 5)(2) (j， 3)(j10 goto NEXT104: i:=j+j105: ai:=02.設基本塊 p 由如下語句構成：T 0 :3.14;T 1 :=2*T 0 ;T 2 :=R+r;A:=T l *T 2；B:=A;=2*T 0 ;T 4 :=R+r;T 5 :=T 3 *T 4 ;T 6 :=R-r；B:=T 5 *T 6；試給出基本塊p 的 DAG。解：基本塊 p 的 DAG 圖:3 .寫出表達式（a+b）/（a-b-（a+b*c）的三元序列及四元序列。解：（ 1）三元式： （，a， b ） （，a， b ） （/， ， ） （ * ， b， c） （

36、， a， ）(一，)(2)四元式：(十, a, b, T1)(一，a, b, T2)(/, T1, T2, T3)(*, b, c, T4)(十 , a, T4, T5)(，T3, T5, T6)。開頭4 .寫一個文法使其語言為偶數(shù)集，且每個偶數(shù)不以解：文法G (S):SAB|B|AOAAD|CB-2|4|6|8C-1|3|5|7|9|BDOC5 .設文法G (S):SS+ aF|aF| + aFF*aF|*a(1)消除左遞歸和回溯；(2)構造相應的Fl RS林口 Follow集合。1)S-aFS| aFSS-+ aFSl &F-*aFF-F| ( 2)FIRST(S) = a, + FOLL

37、OW(S) = #FIRST (S) = +, FOLLOW (S) = #FIRST(F) = * FOLLoW(F) = (+, # FIRST(F) = *, FOLLOW( + , #五 .計算題(10 分)已知文法為：S-a|T)T-T,S|S構造它的 LR(0)分析表。解：加入非xxS；方法的增廣文法為：S-SS-aS-AS-(T)T-T,ST-S下面構造它的LR（0）項目集規(guī)范族為：從上表可看出,不存在移進-歸約沖突以及歸約沖突，該文法是LR（0）文法。從而有下面的LR（0）分析表：編譯原理模擬試題五一、是非題（請在括號內，正確的劃 M錯誤的劃為（每個2分，共20 分）1 .編譯

38、程序是對高級語言程序的解釋執(zhí)行。（X ）2 . 一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。（X）3 . 一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應。（V）4 .語法分析時必須先消除文法中的左遞歸。（X ）5 . LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準確地指出出 錯地點。 （ V）6 逆波蘭表示法表示表達式時無須使用括號。 （ V）7 .靜態(tài)數(shù)組的存儲空間可以在編譯時確定。（X ）8 進行代碼優(yōu)化時應著重考慮循環(huán)的代碼優(yōu)化，這對提高目標代碼的效率 將起更大作用。（X）9.兩個正規(guī)集相等的必要條件是他們對應的正規(guī)式等價。 （x ）(X)10 一個語義子程序描述了一個文法所對應的翻譯工作。二、選擇題 (請在前括號內選擇最確切的一項作為答案劃一個勾，