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

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

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

4、輸入串 ab#給出分析過程。6 構造算符文法 GH的算符優先關系（含）。GH：HH;M|MMd|aHb7已構造出文法 G（S）（1）S BB（2）B aB（3）B b1）。給出 DFA 圖2）.給出 LR 分析表3）假定輸入串為 abaab，請給出 LR 分析過程（即狀態，符號，輸入串的變化過程）。8 將下面的語句翻譯成四元式序列：while ACBA (1) A-aAd (2)A- aAb (3)A-(2)構造識別活前綴的 DFAFOLLOW(A)=d,b,#對于狀態 I0：FOLLOW(A)a=對于狀態 I1：FOLLOW(A)a=因為，在 DFA 中無沖突的現象，所以該文法是 SLR(1

5、)文法。(3)SLR(1)分析表狀態 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#的分析過程步驟 狀態棧 符號棧 當前字符 剩余字符串 動作1 0 # a b# 移進2 02 #a b # 歸約 A-3 023 #aA b # 移進4 0235 #aAb # 歸約 A- aAb5 01 #A # 接受6 【解答】由 Md 和 Ma得：FIRSTVT(M)=d,a；由 H-H;得：FIRSTVT(H)=；由 HM 得：FIRSTVT(M) cFIRSTVT(H)

6、，即 FIRSTVT(H)=;,d,a由 Md 和 Mb 得：LASTVT(M)=d,b；由 H-，；m 得：LASTVT(H)=；由 HM 得：LASTVT（M）cLASTVT(H），即 LASTVT(H)=;,d,b對文法開始符 H,有#H#存在，即有=，#,也即；，#d. #, b#。對形如 Pab，或 PaQb，有 a=b，由 Ma|b 得：a=b；對形如 PaR，而 bFIRSTVT(R)，有 ab。由 H；M 得：；FIRSTVT(M)，即：d，：a由 MaH得：aFIRSTVT(H)，即：a；，a;，即：；，d；，b；由 MHb 得：LASTVT(H)b，即：；b，db，bb由此

7、得到算符優先關系表，見表 3.5。7 【解答】（1）LR 分析表如下：（2）分析表狀態 ACTION GOTOa b # S B0 s3 s4 1 21 acc2 S3 S4 53 s3 s4 64 r3 r35 R1 R1 r16 R2 R2 R2(3) 句子 abaab 的分析過程表:句子 abaab 的分析過程步驟 狀態 符號棧 輸入串 所得產生式0 #0 # abaad#1 #03 #a baad#2 #034 #ab aab# Bb3 #036 #aB aab# BaB4 #02 #B aab#5 #023 #Ba ab#6 #0233 #Baa b#7 #02334 #Baab #

8、8 #02336 #BaaB #9 #0236 #BaB ad#10 #025 #BB ad#11 #01 #S d#12 # # d#13 識別成功8 【解答】該語句的四元式序列如下（其中 E1、E2 和 E3 分別對應：ACBD, A=1 和 AD 并且關系運算符優先級高）：100 (j,A,C,102)101(j,_,_,113） /*E1 為 F*/102 (j2，4-3(3)求出流圖中的循環:回邊 5-2 對應的循環：2、5、3、4；回邊 4-3 對應的循環：3、4編譯原理模擬試題一一、是非題（請在括號內，正確的劃，錯誤的劃）（每個 2 分，共 20 分）1計算機高級語言翻譯成低級語

9、言只有解釋一種方式。()2在編譯中進行語法檢查的目的是為了發現程序中所有錯誤。()3甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統功能完全相同。 ( )4正則文法其產生式為 A-a ， A-Bb, A,BVN ， a 、 bVT 。 ()5每個文法都能改寫為 LL(1) 文法。 ()6遞歸下降法允許任一非終極符是直接左遞歸的。 ()7算符優先關系表不一定存在對應的優先函數。 ()8自底而上語法分析方法的主要問題是候選式的選擇。 ()9LR 法是自頂向下語法分析方法。 ()10簡單優先文法允許任意兩個產生式具有相同右部。 ()二、選擇題(請在前括號內選擇最確切的一項作為答案

10、劃一個勾，多劃按錯論)(每個 4 分，共 40 分)1 一個編譯程序中，不僅包含詞法分析，_，中間代碼生成，代碼優化，目標代碼生成等五個部分。A( ) 語法分析 B( )文法分析 C( )語言分析 D( )解釋分析2 詞法分析器用于識別_。A( ) 字符串 B( )語句 C( )單詞 D( )標識符3 語法分析器則可以發現源程序中的_。A( ) 語義錯誤 B( ) 語法和語義錯誤C( ) 錯誤并校正 D( ) 語法錯誤4 下面關于解釋程序的描述正確的是_。(1) 解釋程序的特點是處理程序時不產生目標代碼(2) 解釋程序適用于 COBOL 和 FORTRAN 語言(3) 解釋程序是為打開編譯程序

11、技術的僵局而開發的A( ) (1)(2) B( ) (1) C( ) (1)(2)(3) D( ) (2)(3)5 解釋程序處理語言時 , 大多數采用的是_方法。A( ) 源程序命令被逐個直接解釋執行B( ) 先將源程序轉化為中間代碼 , 再解釋執行C( ) 先將源程序解釋轉化為目標程序 , 再執行D( ) 以上方法都可以6 編譯過程中 , 語法分析器的任務就是_。(1) 分析單詞是怎樣構成的 (2) 分析單詞串是如何構成語句和說明的(3) 分析語句和說明是如何構成程序的 (4) 分析程序的結構A( ) (2)(3) B( ) (2)(3)(4)C( ) (1)(2)(3) D( ) (1)(

12、2)(3)(4)7 編譯程序是一種_。A. ( ) 匯編程序 B( ) 翻譯程序 C( ) 解釋程序 D( ) 目標程序8 文法 G 所描述的語言是_的集合。A. ( ) 文法 G 的字母表 V 中所有符號組成的符號串B( ) 文法 G 的字母表 V 的閉包 V* 中的所有符號串C( ) 由文法的開始符號推出的所有終極符串D. ( ) 由文法的開始符號推出的所有符號串9 文法分為四種類型，即 0 型、1 型、2 型、3 型。其中 3 型文法是_。A. ( ) 短語文法 B( ) 正則文法 C( ) 上下文有關文法 D( ) 上下文無關文法10 一個上下文無關文法 G 包括四個組成部分，它們是：

13、一組非終結符號，一組終結符號，一個開始符號，以及一組 _。A( ) 句子 B( ) 句型 C( ) 單詞 D( ) 產生式三、填空題(每空 1 分，共 10 分)1編譯程序的工作過程一般可以劃分為詞法分析,語法分析,語義分析,中間代碼生成,代碼優化等幾個基本階段,同時還會伴有_表格處理_和 _出錯處理_。2若源程序是用高級語言編寫的,_目標程序_是機器語言程序或匯編程序,則其翻譯程序稱為 _編譯程序_ 。3編譯方式與解釋方式的根本區別在于_是否生成目標代碼_。4對編譯程序而言,輸入數據是_源程序_, 輸出結果是_目標程序_。5產生式是用于定義_語法成分_的一種書寫規則。6語法分析最常用的兩類方

14、法是_自上而下_和_自下而上_分析法。四、簡答題（20 分）1. 什么是句子？ 什么是語言 ?答：(1)設 G 是一個給定的文法，S 是文法的開始符號，如果 S x(其中 xVT*),則稱 x 是文法的一個句子。(2)設 GS是給定文法，則由文法 G 所定義的語言 L(G)可描述為： L(G)xS x,xVT* 。2. 寫一文法，使其語言是偶正整數的集合,要求：(1)允許 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)GS=(S,P,R,D,N,Q

15、,0,1,2,9,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 為：ET|E+T|E-TTF|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

16、、T+T*F+i; 簡單短語為 i、T*F、第一個 T;句柄為第一個 T。4. 構造正規式相應的 NFA : 1(0|1)*101解 1(0|1)*101 對 應 的 NFA 為5. 寫出表達式(ab*c)/(ab)d 的逆波蘭表示和三元式序列。逆波蘭表示： abc*ab/d三元式序列： (*，b，c) (，a，) (，a，b) (/，) (，d)五.計算題（10 分）構造下述文法 GS 的自動機： S-A0 A-A0|S1|0該自動機是確定的嗎？若不確定，則對它確定化。解：由于該文法的產生式 S-A0，A-A0|S1 中沒有字符集 VT 的輸入，所以不是確定的自動機。 要將其他確定化，必須先

17、用代入法得到它對應的正規式。把 S?A0 代入產生式 A?S1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入 S-A0 有該文法的正規式：0(0|01)*0，所以，改寫該文法為確定的自動機為：由于狀態 A 有 3 次輸入 0 的重復輸入，所以上圖只是 NFA，下面將它確定化：下 表 由 子 集 法 將 NFA 轉 換 為DFA:由上表可知 DFA 為：編譯原理模擬試題二一、是非題（請在括號內，正確的劃，錯誤的劃）（每個 2 分，共 20 分）1“ 用高級語言書寫的源程序都必須通過編譯,產生目標代碼后才能投入運行 ”這種說法。( )2若一個句型中出現了某產生式的右部，則此

18、右部一定是該句型的句柄。( )3一個句型的句柄一定是文法某產生式的右部。 ()4在程序中標識符的出現僅為使用性的。 ( )5僅考慮一個基本塊，不能確定一個賦值是否真是無用的。 ( )6削減運算強度破壞了臨時變量在一基本塊內僅被定義一次的特性。 ( )7在中間代碼優化中循環上的優化主要有不變表達式外提和削減運算強度。 ( )8算符優先關系表不一定存在對應的優先函數。 ()9數組元素的地址計算與數組的存儲方式有關。 ()10編譯程序與具體的機器有關,與具體的語言無關。 ( )二、選擇題(請在前括號內選擇最確切的一項作為答案劃一個勾，多劃按錯論)(每個 4 分，共40 分)1 通常一個編譯程序中，不

19、僅包含詞法分析，語法分析，中間代碼生成，代碼優化，目標代碼生成等五個部分，還應包括_。A( ) 模擬執行器 B( ) 解釋器C( ) 表格處理和出錯處理 D( ) 符號執行器2 文法 GN= （ b ， N ， B ， N ， NbbB ， BbN ），該文法所描述的語言是A( ) L(GN)=bii0 B( ) L(GN)=b2ii0C( ) L(GN)=b2i+1i0 D( ) L(GN)=b2i+1i13 一個句型中的最左_稱為該句型的句柄。A( ) 短語 B( ) 簡單短語 C( ) 素短語 D( ) 終結符號4設 G 是一個給定的文法， S 是文法的開始符號，如果 S-x( 其中 x

20、V*), 則稱 x 是文法 G 的一個_。A( ) 候選式 B( ) 句型 C( ) 單詞 D( ) 產生式5 文法 GE ：ETE TTFT FFa （ E ）該文法句型 E F (E T) 的簡單短語是下列符號串中的_。 （ E T ） E T F F (E T)A( ) 和 B( ) 和 C( ) 和 D( ) 6 若一個文法是遞歸的，則它所產生的語言的句子_。A( ) 是無窮多個 B( ) 是有窮多個C( ) 是可枚舉的 D( ) 個數是常量7 詞法分析器用于識別_。A( ) 句子 B( ) 句型 C( ) 單詞 D( ) 產生式8 在語法分析處理中， FIRST 集合、 FOLLOW

21、 集合、 SELECT 集合均是_。A. ( ) 非終極符集 B( ) 終極符集 C( ) 字母表 D. ( ) 狀態集9 在自底向上的語法分析方法中，分析的關鍵是_。A.( ) 尋找句柄 B.( ) 尋找句型 C.( ) 消除遞歸 D.( ) 選擇候選式10 在 LR 分析法中，分析棧中存放的狀態是識別規范句型_的 DFA 狀態。A.( )句柄 B.( ) 前綴 C.( )活前綴 D.( ) LR(0) 項目三、填空題(每空 1 分，共 10 分)1設 G 是一個給定的文法，S 是文法的開始符號，如果 S-x( 其中 xVT*), 則稱 x 是文法的一個_句子_。2遞歸下降法不允許任一非終極

22、符是直接_左_遞歸的。3自頂向下的語法分析方法的基本思想是：從文法的_開始符號_開始，根據給定的輸入串并按照文法的產生式一步一步的向下進行_直接推導_，試圖推導出文法的_句子_，使之與給定的輸入串_匹配_。4自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產生式一步一步地向上進行_直接歸約_ ，力求歸約到文法的_開始符號_。5常用的參數傳遞方式有_傳地址_，傳值和傳名。6在使用高級語言編程時,首先可通過編譯程序發現源程序的全部_語法_錯誤和語義部分錯誤。四、簡答題（20 分）1. 已知文法 GS 為：SdABAaA|aBBb|GS 產生的語言是什么？答：GS產生的語言是 L(GS)

23、=danbmn1,m0。2. 簡述 DFA 與 NFA 有何區別 ?答：DFA 與 NFA 的區別表現為兩個方面:一是 NFA 可以若干個開始狀態，而 DFA 僅只一個開始狀態。 另一方面，DFA 的映象 M 是從 K到 K，而 NFA 的映象 M 是從 K到 K 的子集， 即映象 M 將產生一個狀態集合（可能為空集），而不是單個狀態。3. 構造正規式相應的 DFA : 1(1010 * | 1(010) * 1) * 0。解 ： 1(1010 * | 1(010) * 1) * 0 對 應 的 NFA 為 ：4. 已知文法 G(S)Sa|(T)TT，S|S寫出句子(a，a)，a)的規范歸約過

24、程及每一步的句柄。解：句型 歸約規則 句柄(a，a)，a) Sa a(S，a)，a) TS S(T，a)，a) Sa a(T，S)，a) TT，S T，S(S)，a) TS S(T)，a) SS(T) (T)(S，a) TS S(T，a) Sa a(T，S) TT，S T，S(T) S(T) (T)S5. 何謂優化？按所涉及的程序范圍可分為哪幾級優化？1)優化：對程序進行各種等價變換，使得從變換后的程序出發，能產生更有效的目標代碼。(2) 三種級別：局部優化、循環優化、全局優化。五.計算題（10 分）對下面的文法 G ：E-TEE-+E| T-FTT -T| F- PFF- *F| P-(E)

25、|a|b|(1)計算這個文法的每個非終結符的 FIRST 集和 FOLLOW 集。 (4 分)(2) 證明這個方法是 LL(1) 的。(4 分)(3) 構造它的預測分析表。(2 分)解：（1）計算這個文法的每個非終結符的 FIRST 集和 FOLLOW 集。FIRST 集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(E)=+,FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(T)=FIRST(T)=(,a,b,;FIRST(F)=FIRST(P)=(,a,b,;FIRST(F)=FIRST(P)=*,;FI

26、RST(P)=(,a,b,;FOLLOW 集合有：FOLLOW(E)=),#;FOLLOW(E)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#;/不包含 FOLLOW(T)=FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#;/不包含 FOLLOW(F)=FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#;FOLLOW(P)=FIRST(F)FOLLOW(F)=*,(,a,b,+,),#;/不包含 (2)證明這個方法是 L

27、L(1)的。各產生式的 SELECT 集合有：SELECT(E-TE)=FIRST(T)=(,a,b,;SELECT(E-+E)=+;SELECT(E-)=FOLLOW(E/)=),#SELECT(T-FT)=FIRST(F)=(,a,b,;SELECT(T-T)=FIRST(T)=(,a,b,;SELECT(T-)=FOLLOW(T/)=+,),#;SELECT(F-PF)=FIRST(P)=(,a,b,;SELECT(F-*F)=*;SELECT(F-)=FOLLOW(F)=(,a,b,+,),#;SELECT(P-(E)=(SELECT(P-a)=aSELECT(P-b)=bSELECT

28、(P-)=可見，相同左部產生式的 SELECT 集的交集均為空，所以文法 GE是 LL(1)文法。(3)構造它的預測分析表。文法 GE的預測分析表如下：編譯原理模擬試題三一、是非題（請在括號內，正確的劃，錯誤的劃）（每個 2 分，共 20 分）1對于數據空間的存貯分配，FORTRAN 采用動態貯存分配策略。()2甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統功能完全相同。( )3遞歸下降分析法是自頂向上分析方法。( )4產生式是用于定義詞法成分 的一種書寫規則。 ()5LR 法是自頂向下語法分析方法。 ( )6在 SLR （ 1 ）分析法的名稱中，S 的含義是簡單的。()

29、7綜合屬性是用于 “ 自上而下 ” 傳遞信息。( )8符號表中的信息欄中登記了每個名字的 屬性和特征等有關信息 ，如類型、種屬、所占單元大小、地址等等。 ()9程序語言的語言處理程序是一種應用軟件。 ()10解釋程序適用于 COBOL 和 FORTRAN 語言。 ()二、選擇題(請在前括號內選擇最確切的一項作為答案劃一個勾，多劃按錯論)(每個 4 分，共40 分)1 文法 G 產生的_的全體是該文法描述的語言。A( ) 句型 B( ) 終結符集 C( ) 非終結符集 D( ) 句子2 若文法 G 定義的語言是無限集，則文法必然是 _。A( ) 遞歸的 B( ) 前后文無關的C( ) 二義性的

30、D( ) 無二義性的3 四種形式語言文法中，1 型文法又稱為 _文法。A( ) 短語結構文法 B( ) 前后文無關文法C( ) 前后文有關文法 D( ) 正規文法4 一個文法所描述的語言是_。A( ) 唯一的 B( ) 不唯一的C( ) 可能唯一，好可能不唯一 D( ) 都不對5 _和代碼優化部分不是每個編譯程序都必需的。A( ) 語法分析 B( ) 中間代碼生成C( ) 詞法分析 D( ) 目標代碼生成6_是兩類程序語言處理程序。A( ) 高級語言程序和低級語言程序 B( ) 解釋程序和編譯程序C( ) 編譯程序和操作系統 D( ) 系統程序和應用程序7 數組的內情向量中肯定不含有數組的_的

31、信息。A. ( ) 維數 B( ) 類型 C( ) 維上下界 D( ) 各維的界差8. 一個上下文無關文法 G 包括四個組成部分，它們是：一組非終結符號，一組終結符號，一個開始符號，以及一組 _。A( ) 句子 B( ) 句型C( ) 單詞 D( ) 產生式9 文法分為四種類型，即 0 型、1 型、2 型、3 型。其中 2 型文法是_。A. ( ) 短語文法 B( ) 正則文法C( ) 上下文有關文法 D( ) 上下文無關文法10文法 G 所描述的語言是_的集合。A. ( ) 文法 G 的字母表 V 中所有符號組成的符號串B( ) 文法 G 的字母表 V 的閉包 V* 中的所有符號串C( )

32、由文法的開始符號推出的所有終極符串D. ( ) 由文法的開始符號推出的所有符號串三、填空題(每空 1 分，共 10 分)1一個句型中的最左簡單短語稱為該句型的_句柄_。2對于文法的每個產生式都配備了一組屬性的計算規則，稱為 _語義規則_ 。3一個典型的編譯程序中，不僅包括_詞法分析_、_語法分析_、_中間代碼生成_、代碼優化、目標代碼生成等五個部分，還應包括表格處理和出錯處理。4 從功能上說，程序語言的語句大體可分為_執行性_語句和_說明性_語句兩大類。5 掃描器的任務是從_源程序_中識別出一個個_單詞符號_。6 產生式是用于定義_語法范疇_的一種書寫規則。四、簡答題（20 分）1. 寫一個文

33、法，使其語言是奇數集，且每個奇數不以 0 開頭。解：文法 G(N)：NAB|BAAC|DB1|3|5|7|9DB|2|4|6|8C0|D2. 設文法 G(S)：S(L)|a S|aLL，S|S(1) 消除左遞歸和回溯；(2) 計算每個非終結符的 FIRST 和 FOLLOW。解：(1)S(L)|aSSS|LSLLSL|(2)FIRST)S)(，a FOLLOW(S)#，)FIRST(S)，a, FOLLOW(S)#，)FIRST(L)(，a FOLLOW(L) )FIRST(L)， FOLLOW(L )3. 已知文法 G(E)ET|ETTF|T *FF(E)|i(1)給出句型(T *Fi)的最

34、右推導；(2)給出句型(T *Fi)的短語、素短語。解 ： (1) 最 右 推 導 ： E-T-F-(E)-(E T)-(E F)-(E i)-(Ti)-(T*Fi)(2) 短語：(T*Fi)，T*Fi，T*F，i素短語：T*F,i4. While a0 b0 doBeginX：X1；if a0 then a：a1else b：b1End；翻譯成四元式序列。解：(1) (j，a，0，5)(2) (j，3)(3) (j，b，0，5)(4) (j，15)(5) (，1，T1)(6) (：，T1，)(7) (j，a，0，9)(8) (j，12)(9) (，a，1，T2)(10) (：，T2，a)(1

35、1) (j，1)(12) (，b，1， T3)(13) (：，T3，b)(14) (j，1)(15)五.計算題（10 分）已知 NFA= （ x,y,z,0,1,M,x,z ），其中：M(x,0)=z,M(y,0)=x,y,M(z,0)=x,z,M(x,1)=x, M(y,1)= ,M(z,1)=y, 構造相應的 DFA并最小化。解：根據題意有 NFA 圖:下 表 由 子 集 法 將 NFA 轉 換 為 DFA ：下面將該 DFA 最小化：(1) 首先將它的狀態集分成兩個子集：P1=A,D,E,P2=B,C,F(2) 區 分 P2: 由 于 F(F,1)=F(C,1)=E,F(F,0)=F 并

36、 且 F(C,0)=C, 所 以 F ， C 等 價 。 由 于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而 D，E 不等價（見下步），從而 B 與 C，F 可以區分。有 P21=C,F,P22=B。(3) 區分 P1:由于 A，E 輸入 0 到終態，而 D 輸入 0 不到終態，所以 D 與 A，E 可以區分，有 P11=A,E,P12=D。(4) 由于 F(A,0)=B,F(E,0)=F,而 B，F 不等價，所以 A，E 可以區分。(5) 綜上所述，DFA 可以區分為 P=A，B，D，E，C，F。所以最小化的 DFA如下：編譯原理模擬試題四一、是非題（請在括號內，

37、正確的劃，錯誤的劃）（每個 2 分，共 20 分）1一個 LL(l)文法一定是無二義的。 ( )2正規文法產生的語言都可以用上下文無關文法來描述。 ( )3一張轉換圖只包含有限個狀態，其中有一個被認為是初態，最多只有一個終態。 ()4目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。 ( )5逆波蘭法表示的表達式亦稱前綴式 。 ( )6如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。 ( )7LR 法是自頂向下語法分析方法。 ( )8數組元素的地址計算與數組的存儲方式有關。( )9算符優先關系表不一定存在對應的優先函數。 ()10對于數據空間的存貯分配， FORTRA

38、N 采用動態貯存分配策略。 ()二、選擇題(請在前括號內選擇最確切的一項作為答案劃一個勾，多劃按錯論)(每個 4 分，共40 分)1詞法分析器用于識別_。A( ) 字符串 B( )語句C( )單詞 D( )標識符2文法分為四種類型，即 0 型、1 型、2 型、3 型。其中 0 型文法是_。A. ( ) 短語文法 B( ) 正則文法C( ) 上下文有關文法 D( ) 上下文無關文法3一個上下文無關文法 G 包括四個組成部分，它們是：一組非終結符號，一組終結符號，一個開始符號，以及一組 _。A( ) 句子 B( ) 句型 C( ) 單詞 D( ) 產生式4_是一種典型的解釋型語言。A( ) BASIC B( ) C C( ) FORTRAN D( ) PASCAL5與編譯系統相比，解釋系統_。A( ) 比較簡單 , 可移植性好 , 執行速度快B( ) 比較復雜 , 可移植性好 , 執行速度快C( ) 比較簡單 , 可移植性差 , 執行速度慢D( ) 比較簡單 , 可移植性好 , 執行速度慢6用高級