【文章內容簡介】 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)： N→AB|B A→AC|D B→1|3|5|7|9 D→B|2|4|6|8 C→0|D 2. 設文法 G(S)： S→(L)|a S|a L→L ， S|S (1) 消除左遞歸和回溯； (2) 計算每個非終結符的 FIRST 和 FOLLOW。 解： (1) S→(L)|aS39。 S39?！鶶|ε L→SL39。 L39?！鶶L39。|ε (2) FIRST)S)＝ {(， a} FOLLOW(S)＝ {，， )} FIRST(S39。)＝ {， a,ε} FOLLOW(S39。)＝ {，， )} FIRST(L)＝ {(， a} FOLLOW(L)＝ { )} FIRST(L39。)＝ {， ε} FOLLOW(L39?！常?{ )} 3. 已知文法 G(E) E→T|E ＋ T T→F|T *F F→(E)|i (1)給出句型 (T *F＋ i)的最右推導； (2)給出句型 (T *F＋ i)的短語、素短語。 解： (1) 最右推導： ETF(E)(E ＋ T)(E ＋ F)(E ＋ i) (T＋ i)(T*F＋ i) (2) 短語： (T*F＋ i)， T*F＋ i， T*F， i 素短語： T*F,i 4. While a＞ 0 ∨ b＜ 0 do Begin X：＝ X＋ 1； if a＞ 0 then a：＝ a－ 1 else b：＝ b＋ 1 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． 如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。 (√ ) 7． LR 法是自頂向下語法分析方法。 ( ) 8． 數組元素的地址計算與數組的存儲方式有關。 ( ) 9． 算符優(yōu)先關系表不一定存在對應的優(yōu)先函數。 () 10． 對于數據空間的存貯分配， FORTRAN 采用動態(tài)貯存分配策略。 () 二、選擇題 (請在前括號內選擇最確切的一 項作為答案劃一個勾，多劃按錯論 )(每個 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． ( ) PASCAL 5． 與編譯系統(tǒng)相比，解釋系統(tǒng) _____。 A． ( ) 比較簡單 , 可移植性好 , 執(zhí)行速度快 B． ( ) 比較復雜 , 可移植性好 , 執(zhí)行速度快 C． ( ) 比較簡單 , 可移植性差 , 執(zhí)行速度慢 D． ( ) 比較簡單 , 可移植性好 , 執(zhí)行速度慢 6． 用高級語言編寫的程序經編譯后產生的程序叫 _____。 A． ( ) 源程序