編譯技術(shù)考試試題及答案-資料下載頁
2024-10-25 08:58本頁面
【導(dǎo)讀】和目標(biāo)代碼生成五個階段。的語法分析方法。弱、復(fù)寫傳播、等。每題2分，共20分）。述?！?amp;#215;8、√9、×10、×符號串baabbb是該文法的句子(3分)。所以該文法為SLR文法。其分析表如下：(8分). 循的是語義規(guī)則，并且語義規(guī)則可以定義一個程序的意義。
【正文】 法樹如圖 283 所示 （ 2）由圖 283 可知： ① 短語： S、 a、 (a)、 S,(a)、 (S,(a))； ② 直接短語： a、 S； ③ 句柄： S； ④ 素短語：素短語可由圖 283 中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得，即； 因此素短語為 a。 考慮文法 G[T]： T→T*F|F F→F↑P|P P→（ T） |i 證明 T*P↑（ T*F）是該文法的一個句型，并指出直接短語和句柄。 【解答】 首先構(gòu)造 T*P↑（ T*F）的語法樹如圖 284 所示。 由圖 284 可知， T*P↑（ T*F）是文法 G[T]的一個句型。 直接短語有兩個，即 P 和 T*F；句柄為 P。 一、單項選擇題 詞法分析所依據(jù)的是 。 a. 語義規(guī)則 b. 構(gòu)詞規(guī)則 c. 語法規(guī)則 d. 等價變換規(guī)則 詞法分析器的輸出結(jié)果是 。 a. 單詞的種別編碼 b. 單詞在符號表中的位置 c. 單詞的種別編碼和自 身值 d. 單詞自身值 正規(guī)式 M1 和 M2 等價是指 。 a. M1 和 M2 的狀態(tài)數(shù)相等 b. M1 和 M2 的有向弧條數(shù)相等 c. M1 和 M2 所識別的語言集相等 d. M1 和 M2 狀態(tài)數(shù)和有向弧條數(shù)相等 狀態(tài)轉(zhuǎn)換圖（見圖 361）接受的字集為 。 a. 以 0 開頭的二進(jìn)制數(shù)組成的集合 b. 以 0 結(jié)尾的二進(jìn)制數(shù)組成的集合 c. 含奇數(shù)個 0 的二進(jìn)制數(shù)組成的集合 d. 含偶數(shù)個 0 的二進(jìn)制數(shù)組成的集合 詞法分析器作為獨立的階段使整個編譯程序結(jié)構(gòu)更加簡潔、明確，因 此， 。 a. 詞法分析器應(yīng)作為獨立的一遍 b. 詞法分析器作為子程序較好 c. 詞法分析器分解為多個過程，由語法分析器選擇使用 d. 詞法分析器并不作為一個獨立的階段 解答 b c c d b 二、多項選擇題 在詞法分析中，能識別出 。 a. 基本字 b. 四元式 c. 運算符 d. 逆波蘭式 e. 常數(shù) 令 ∑={a,b}，則 ∑上所有以 b 開頭，后跟若干個 ab 的字的全體對應(yīng)的正規(guī)式為 。 a. b(ab)* b. b(ab)+ c.(ba)*b d. (ba)+b e. b(a|b) 解答 a、 c、 e a、 b、 d 三、填空題 確定有限自動機 DFA 是 的一個特例。 若二個正規(guī)式所表示的 相同，則認(rèn)為二者是等價的。 一個字集是正規(guī)的，當(dāng)且僅當(dāng)它可由 所 。 解答 NFA 正規(guī)集 DFA（ NFA）所識別 四、判斷題 一個有限狀態(tài)自動機中，有且僅有一個唯一終態(tài)。 （ ） 設(shè) r 和 s 分別是正規(guī)式，則有 L（ r|s） =L(r)|L(s)。 （ ） 自動機 M 和 M′的狀態(tài)數(shù)不同，則二者必不等價。 （ ） 確定的自動機以及不確定的自動機都能正確地識別正規(guī)集。 （ ） 對任意一個右線性文法 G，都存在一個 NFA M，滿足 L(G)=L(M)。 （ ） 對任意一個右線性文法 G，都存在一個 DFA M，滿足 L(G)=L(M)。 （ ） 對任何正規(guī)表達(dá)式 e，都存在一個 NFA M，滿足 L(G)=L(e)。 （ ） 對任何正規(guī)表達(dá)式 e，都存 在一個 DFA M，滿足 L(G)=L(e)。 （ ） 解答 1 、 錯 正確 五、基本題 設(shè) M＝（ {x,y}, {a,b}, f,x,{y}）為一非確定的有限自動機，其中 f 定義如下： f（ x,a）＝ {x,y} f（ x,b）＝ {y} f（ y,a）＝ φ f（ y,b）＝ {x,y} 試構(gòu)造相應(yīng)的確定有限自動機 M′。 解答：對照自動機的定義 M=(S,Σ,f,S0,Z)，由 f 的定義可知 f(x,a)、 f(y,b)均為多值函數(shù)，所以是一非確定有限自動機，先畫 出 NFA M 相應(yīng)的狀態(tài)圖，如圖 362所示。 用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣表 363 所示。 I Ia Ib {x} {x,y} {y} {y} — {x,y} {x,y} {x,y} {x,y} 將轉(zhuǎn)換矩陣中的所有子集重新命名而形成表 364 所示的狀態(tài)轉(zhuǎn)換矩陣。 表 364 狀態(tài)轉(zhuǎn)換矩陣 a b 0 2 1 1 — 2 2 2 2 即得到 M′=（ {0,1,2}, {a,b}, f,0, {1,2}），其狀態(tài)轉(zhuǎn)換圖如圖 365 所示。 將圖 365 的 DFA M′最小化。首 先，將 M′的狀態(tài)分成終態(tài)組 {1， 2}與非終態(tài)組{0}；其次，考察 {1,2}。由于 {1,2}a={1,2}b={2}? {1,2}，所以不再將其劃分了，也即整個劃分只有兩組 {0}， {1,2}：令狀態(tài) 1 代表 {1,2}，即把原來到達(dá) 2 的弧都導(dǎo)向 1，并刪除狀態(tài) 2。最后，得到如圖 366 所示化簡 DFA M′。 對給定正規(guī)式 b*（ d|ad）（ b|ab） +，構(gòu)造其 NFA M； 解答：首先用 A+=AA*改造正規(guī)式得： b*(d|ad)(b|ab)(b|ab)*；其次，構(gòu)造該正規(guī)式的 NFA M，如圖 367 所示。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1