編譯原理試題及答案.doc

歷年試題及答案一 （每項選擇2分，共20分）選擇題1將編譯程序分成若干個“遍”是為了_b_。a.提高程序的執(zhí)行效率b.使程序的結構更加清晰c.利用有限的機器內存并提高機器的執(zhí)行效率d.利用有限的機器內存但降低了機器的執(zhí)行效率2構造編譯程序應掌握_d_。a.源程序 b.目標語言c.編譯方法 d.以上三項都是3變量應當c。a.持有左值 b.持有右值c.既持有左值又持有右值 d.既不持有左值也不持有右值4編譯程序絕大多數時間花在_d_上。a.出錯處理 b.詞法分析c.目標代碼生成 d.管理表格5詞法分析器的輸出結果是_c_。a.單詞的種別編碼 b.單詞在符號表中的位置c.單詞的種別編碼和自身值 d.單詞自身值6正規(guī)式mi和m2等價是指_c_。a. mi和m2的狀態(tài)數相等 b.ml和m2的有向弧條數相等。c.m1和m2所識別的語言集相等 d. ml和m2狀態(tài)數和有向弧條數相等7中間代碼生成時所依據的是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/d9程序所需的數據空間在程序運行前就可確定，稱為_c_管理技術。 a.動態(tài)存儲 b.棧式存儲 c.靜態(tài)存儲 d.堆式存儲10.堆式動態(tài)分配申請和釋放存儲空間遵守_d_原則。 a.先請先放 b.先請后放 c.后請先放 d.任意二（每小題10分，共80分）簡答題1.畫出編譯程序的總體結構圖，簡述各部分的主要功能。2.已知文法ge: eet+|tttf* | fff | a 試證：ff*是文法的句型，指出該句型的短語、簡單短語和句柄. 3為正規(guī)式(a|b) *a(a|b)構造一個確定的有限自動機。4設文法g(s)： s(l)|a s|a ll，s|s (1) 消除左遞歸和回溯； (2) 計算每個非終結符的first和follow； (3) 構造預測分析表。5 已知文法 a-aad| aab| 判斷該文法是否slr（1）文法，若是構造相應分析表，并對輸入串ab#給出分析過程。6構造算符文法gh的算符優(yōu)先關系（含）。 gh：hh;m|m md|ahb7已構造出文法g（s）（1）s bb（2）b ab（3）b b1）。給出dfa圖2）.給出lr分析表3）假定輸入串為abaab，請給出lr分析過程（即狀態(tài)，符號，輸入串的變化過程）。8將下面的語句翻譯成四元式序列： while acba(1) a-aad(2)a- aab(3)a- (2)構造識別活前綴的dfa follow(a)=d,b,# 對于狀態(tài)i0：follow(a)a= 對于狀態(tài)i1：follow(a)a= 因為，在dfa中無沖突的現象，所以該文法是slr(1)文法。 (3)slr(1)分析表 狀態(tài) action goto a b d # a 0 s2 r3 r3 r3 1 1 acc 2 s2 r3 r3 r3 3 3 s5 s4 4 r1 r1 r1 5 r2 r2 r2 (4)串ab#的分析過程 步驟 狀態(tài)棧 符號棧 當前字符 剩余字符串 動作 1 0 # a b# 移進 2 02 #a b # 歸約a- 3 023 #aa b # 移進 4 0235 #aab # 歸約a- aab 5 01 #a # 接受 6 【解答】 由md和ma得：firstvt(m)=d,a； 由h-h;得：firstvt(h)=； 由hm得：firstvt(m) cfirstvt(h)，即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 由此得到算符優(yōu)先關系表，見表3.5。7 【解答】（1）lr分析表如下：（2）分析表狀態(tài) action goto a b # s b0 s3 s4 1 21 acc 2 s3 s4 53 s3 s4 64 r3 r3 5 r1 r1 r1 6 r2 r2 r2 (3) 句子abaab的分析過程表:句子abaab的分析過程步驟 狀態(tài) 符號棧 輸入串 所得產生式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 #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并且關系運算符優(yōu)先級高）： 100 (j,a,c,102) 101(j,_,_,113） /*e1為f*/ 102 (j2，4-3 (3)求出流圖中的循環(huán): 回邊5-2對應的循環(huán)：2、5、3、4； 回邊4-3對應的循環(huán)：3、4編譯原理模擬試題一一、是非題（請在括號內，正確的劃，錯誤的劃）（每個2分，共20分）1計算機高級語言翻譯成低級語言只有解釋一種方式。()2在編譯中進行語法檢查的目的是為了發(fā)現程序中所有錯誤。()3甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相同。 ( )4正則文法其產生式為 a-a ， a-bb, a,bvn ， a 、 bvt 。 ()5每個文法都能改寫為 ll(1) 文法。 ()6遞歸下降法允許任一非終極符是直接左遞歸的。 ()7算符優(yōu)先關系表不一定存在對應的優(yōu)先函數。 ()8自底而上語法分析方法的主要問題是候選式的選擇。 ()9lr 法是自頂向下語法分析方法。 ()10簡單優(yōu)先文法允許任意兩個產生式具有相同右部。 ()二、選擇題(請在前括號內選擇最確切的一項作為答案劃一個勾，多劃按錯論)(每個4分，共40分)1 一個編譯程序中，不僅包含詞法分析，_，中間代碼生成，代碼優(yōu)化，目標代碼生成等五個部分。a( ) 語法分析 b( )文法分析c( )語言分析d( )解釋分析2 詞法分析器用于識別_。 a( ) 字符串b( )語句c( )單詞d( )標識符3 語法分析器則可以發(fā)現源程序中的_。a( ) 語義錯誤 b( ) 語法和語義錯誤c( ) 錯誤并校正 d( ) 語法錯誤4 下面關于解釋程序的描述正確的是_。 (1) 解釋程序的特點是處理程序時不產生目標代碼 (2) 解釋程序適用于 cobol 和 fortran 語言 (3) 解釋程序是為打開編譯程序技術的僵局而開發(fā)的 a( ) (1)(2) b( ) (1) c( ) (1)(2)(3) d( ) (2)(3)5 解釋程序處理語言時 , 大多數采用的是_方法。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 所描述的語言是_的集合。 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編譯程序的工作過程一般可以劃分為詞法分析,語法分析,語義分析,中間代碼生成,代碼優(yōu)化等幾個基本階段,同時還會伴有_表格處理_和 _出錯處理_。 2若源程序是用高級語言編寫的,_目標程序_是機器語言程序或匯編程序,則其翻譯程序稱為 _編譯程序_ 。3編譯方式與解釋方式的根本區(qū)別在于_是否生成目標代碼_。4對編譯程序而言,輸入數據是_源程序_, 輸出結果是_目標程序_。5產生式是用于定義_語法成分_的一種書寫規(guī)則。 6語法分析最常用的兩類方法是_自上而下_和_自下而上_分析法。 四、簡答題（20分）1. 什么是句子？ 什么是語言 ? 答：(1)設g是一個給定的文法，s是文法的開始符號，如果s x(其中xvt*),則稱x是文法的一個句子。 (2)設gs是給定文法，則由文法g所定義的語言l(g)可描述為： l(g)xs x,xvt* 。參考答案：(每個2分，共4分)答：(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|d p-np|n d-0|2|4|6|8 n-0|1|2|3|4|5|6|7|8|9 (2)gs=(s,p,r,d,n,q ,0,1,2,9,p,s) p: s-pd|p0|d p-nr|n r-qr|q d-2|4|6|8 n-1|2|3|4|5|6|7|8|9 q-0|1|2|3|4|5|6|7|8|9 3. 已知文法 ge 為： et|e+t|e-t tf|t*f|t/f f （ 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;句柄為第一個t。4. 構造正規(guī)式相應的 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的輸入，所以不是確定的自動機。 要將其他確定化，必須先用代入法得到它對應的正規(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次輸入0的重復輸入，所以上圖只是nfa，下面將它確定化： 下表由子集法將nfa轉換為dfa:由上表可知dfa為：編譯原理模擬試題二一、是非題（請在括號內，正確的劃，錯誤的劃）（每個2分，共20分）1“ 用高級語言書寫的源程序都必須通過編譯,產生目標代碼后才能投入運行 ”這種說法。( )2若一個句型中出現了某產生式的右部，則此右部一定是該句型的句柄。( )3一個句型的句柄一定是文法某產生式的右部。 ()4在程序中標識符的出現僅為使用性的。 ( )5僅考慮一個基本塊，不能確定一個賦值是否真是無用的。 ( )6削減運算強度破壞了臨時變量在一基本塊內僅被定義一次的特性。 ( )7在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達式外提和削減運算強度。 ( )8算符優(yōu)先關系表不一定存在對應的優(yōu)先函數。 ()9數組元素的地址計算與數組的存儲方式有關。 ()10編譯程序與具體的機器有關,與具體的語言無關。 ( )二、選擇題(請在前括號內選擇最確切的一項作為答案劃一個勾，多劃按錯論)(每個4分，共40分)1 通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標代碼生成等五個部分，還應包括_。a( ) 模擬執(zhí)行器b( ) 解釋器 c( ) 表格處理和出錯處理 d( ) 符號執(zhí)行器2 文法 gn= （ b ， n ， b ， n ， nbbb ， bbn ），該文法所描述的語言是 a( ) l(gn)=bii0 b( ) l(gn)=b2ii0 c( ) l(gn)=b2i+1i0 d( ) l(gn)=b2i+1i13 一個句型中的最左_稱為該句型的句柄。a( ) 短語 b( ) 簡單短語 c( ) 素短語 d( ) 終結符號 4 設 g 是一個給定的文法， s 是文法的開始符號，如果 s-x( 其中 xv*), 則稱 x 是文法 g 的一個_。a( ) 候選式 b( ) 句型 c( ) 單詞 d( ) 產生式 5 文法 ge ： ete t tft f fa （ 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 集合、 select 集合均是_。a. ( ) 非終極符集 b( ) 終極符集 c( ) 字母表 d. ( ) 狀態(tài)集 9 在自底向上的語法分析方法中，分析的關鍵是_。 a.( ) 尋找句柄 b.( ) 尋找句型 c.( ) 消除遞歸 d.( ) 選擇候選式 10 在 lr 分析法中，分析棧中存放的狀態(tài)是識別規(guī)范句型_的 dfa 狀態(tài)。 a.( )句柄 b.( ) 前綴 c.( )活前綴 d.( ) lr(0) 項目 三、填空題(每空1分，共10分)1設g是一個給定的文法，s是文法的開始符號，如果s-x( 其中 xvt*), 則稱 x是文法的一個_句子_。 2遞歸下降法不允許任一非終極符是直接_左_遞歸的。3自頂向下的語法分析方法的基本思想是：從文法的_開始符號_開始，根據給定的輸入串并按照文法的產生式一步一步的向下進行_直接推導_，試圖推導出文法的_句子_，使之與給定的輸入串_匹配_。 4自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產生式一步一步地向上進行_直接歸約_ ，力求歸約到文法的_開始符號_。 5常用的參數傳遞方式有_傳地址_，傳值和傳名。 6在使用高級語言編程時,首先可通過編譯程序發(fā)現源程序的全部_語法_錯誤和語義部分錯誤。四、簡答題（20分）1. 已知文法 gs 為： sdab aaa|a bbb| gs 產生的語言是什么？ 答：gs產生的語言是l(gs)=danbmn1,m0。2. 簡述 dfa 與 nfa 有何區(qū)別 ? 答：dfa與nfa的區(qū)別表現為兩個方面:一是nfa可以若干個開始狀態(tài)，而dfa僅只一個開始狀態(tài)。 另一方面，dfa的映象m是從k到k，而nfa的映象m是從k到k的子集， 即映象m將產生一個狀態(tài)集合（可能為空集），而不是單個狀態(tài)。3. 構造正規(guī)式相應的 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)的規(guī)范歸約過程及每一步的句柄。解：句型歸約規(guī)則句柄 (a，a)，a)saa (s，a)，a)tss (t，a)，a)saa (t，s)，a)tt，s t，s (s)，a) tss (t)，a) ss(t) (t) (s，a) tss (t，a) saa (t，s) tt，s t，s (t) s(t)(t) s5. 何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？1)優(yōu)化：對程序進行各種等價變換，使得從變換后的程序出發(fā)，能產生更有效的目標代碼。 (2) 三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。五.計算題（10分） 對下面的文法 g ： e-te e-+e| t-ft t -t| f- pf f- *f| p-(e)|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)=*,; first(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)證明這個方法是ll(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)=a select(p-b)=b select(p-)= 可見，相同左部產生式的select集的交集均為空，所以文法ge是ll(1)文法。 (3)構造它的預測分析表。 文法ge的預測分析表如下： 編譯原理模擬試題三一、是非題（請在括號內，正確的劃，錯誤的劃）（每個2分，共20分）1對于數據空間的存貯分配，fortran采用動態(tài)貯存分配策略。()2甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相同。( )3遞歸下降分析法是自頂向上分析方法。( )4產生式是用于定義詞法成分 的一種書寫規(guī)則。 ()5lr 法是自頂向下語法分析方法。 ( )6在 slr （ 1 ）分析法的名稱中，s的含義是簡單的。()7綜合屬性是用于 “ 自上而下 ” 傳遞信息。( )8符號表中的信息欄中登記了每個名字的 屬性和特征等有關信息 ，如類型、種屬、所占單元大小、地址等等。 ()9程序語言的語言處理程序是一種應用軟件。 ()10解釋程序適用于 cobol 和 fortran 語言。 ()二、選擇題(請在前括號內選擇最確切的一項作為答案劃一個勾，多劃按錯論)(每個4分，共40分)1 文法 g 產生的_的全體是該文法描述的語言。a( ) 句型 b( ) 終結符集 c( ) 非終結符集 d( ) 句子2 若文法 g 定義的語言是無限集，則文法必然是 _。 a( ) 遞歸的 b( ) 前后文無關的 c( ) 二義性的 d( ) 無二義性的3 四種形式語言文法中，1型文法又稱為 _文法。a( ) 短語結構文法 b( ) 前后文無關文法 c( ) 前后文有關文法 d( ) 正規(guī)文法 4 一個文法所描述的語言是_。a( ) 唯一的 b( ) 不唯一的 c( ) 可能唯一，好可能不唯一 d( ) 都不對5 _和代碼優(yōu)化部分不是每個編譯程序都必需的。a( ) 語法分析b( ) 中間代碼生成 c( ) 詞法分析 d( ) 目標代碼生成 6_是兩類程序語言處理程序。 a( ) 高級語言程序和低級語言程序 b( ) 解釋程序和編譯程序 c( ) 編譯程序和操作系統(tǒng) d( ) 系統(tǒng)程序和應用程序 7 數組的內情向量中肯定不含有數組的_的信息。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( ) 由文法的開始符號推出的所有終極符串d. ( ) 由文法的開始符號推出的所有符號串三、填空題(每空1分，共10分)1一個句型中的最左簡單短語稱為該句型的_句柄_。 2對于文法的每個產生式都配備了一組屬性的計算規(guī)則，稱為 _語義規(guī)則_ 。3一個典型的編譯程序中，不僅包括_詞法分析_、_語法分析_、_中間代碼生成_、代碼優(yōu)化、目標代碼生成等五個部分，還應包括表格處理和出錯處理。4 從功能上說，程序語言的語句大體可分為_執(zhí)行性_語句和_說明性_語句兩大類。5 掃描器的任務是從_源程序_中識別出一個個_單詞符號_。 6 產生式是用于定義_語法范疇_的一種書寫規(guī)則。 四、簡答題（20分）1. 寫一個文法，使其語言是奇數集，且每個奇數不以0開頭。解：文法g(n)： nab|b aac|d b1|3|5|7|9 db|2|4|6|8 c0|d2. 設文法g(s)： s(l)|a s|a ll，s|s (1) 消除左遞歸和回溯；(2) 計算每個非終結符的first和follow。解：(1) s(l)|as ss| lsl lsl| (2) first)s)(，afollow(s)#，) first(s)，a,follow(s)#，) first(l)(，afollow(l) ) first(l)，follow(l )3. 已知文法g(e) et|et tf|t *f f(e)|i (1)給出句型(t *fi)的最右推導； (2)給出句型(t *fi)的短語、素短語。解：(1) 最右推導： e-t-f-(e)-(et)-(ef)-(ei) -(ti)-(t*fi) (2) 短語：(t*fi)，t*fi，t*f，i 素短語：t*f,i 4. whilea0 b0do begin x：x1； if a0 then a：a1 else b：b1 end； 翻譯成四元式序列。解： (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) (11) (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) 首先將它的狀態(tài)集分成兩個子集：p1=a,d,e,p2=b,c,f (2) 區(qū)分p2:由于f(f,1)=f(c,1)=e,f(f,0)=f并且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可以區(qū)分。有p21=c,f,p22=b。 (3) 區(qū)分p1:由于a，e輸入0到終態(tài)，而d輸入0不到終態(tài)，所以d與a，e可以區(qū)分，有p11=a,e,p12=d。 (4) 由于f(a,0)=b,f(e,0)=f,而b，f不等價，所以a，e可以區(qū)分。 (5) 綜上所述，dfa可以區(qū)分為p=a，b，d，e，c，f。所以最小化的dfa如下： 編譯原理模擬試題四一、是非題（請在括號內，正確的劃，錯誤的劃）（每個2分，共20分）1一個 ll(l)文法一定是無二義的。 ( )2正規(guī)文法產生的語言都可以用上下文無關文法來描述。 ( )3一張轉換圖只包含有限個狀態(tài)，其中有一個被認為是初態(tài)，最多只有一個終態(tài)。 ()4目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。 ( )5逆波蘭法表示的表達式亦稱前綴式 。 ( )6如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。 ( )7lr 法是自頂向下語法分析方法。 ( )8