【文章內(nèi)容簡(jiǎn)介】 A． ( ) 遞歸的 B． ( ) 前后文無(wú)關(guān)的 C． ( ) 二義性的 D． ( ) 無(wú)二義性的 3． 四種形式語(yǔ)言文法中， 1 型文法又稱(chēng)為 _____文法。 A． ( ) 短語(yǔ)結(jié)構(gòu)文法 B． ( ) 前后文無(wú)關(guān)文法 C． ( ) 前后文有關(guān)文法 D． ( ) 正規(guī)文法 4． 一個(gè)文法所描述的語(yǔ)言是 _____。 A． ( ) 唯一的 B． ( ) 不唯一的 C． ( ) 可能唯一，好可能不唯一 D． ( ) 都不對(duì) 5． _____和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。 A． ( ) 語(yǔ)法分析 B． ( ) 中間代碼生成 C． ( ) 詞法分析 D． ( ) 目標(biāo)代碼生成 6． _____是兩類(lèi)程序 語(yǔ)言處理程序。 A． ( ) 高級(jí)語(yǔ)言程序和低級(jí)語(yǔ)言程序 B． ( ) 解釋程序和編譯程序 C． ( ) 編譯程序和操作系統(tǒng) D． ( ) 系統(tǒng)程序和應(yīng)用程序 7． 數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的 _____的信息。 A. ( ) 維數(shù) B． ( ) 類(lèi)型 C． ( ) 維上下界 D． ( ) 各維的界差 8. 一個(gè)上下文無(wú)關(guān)文法 G 包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組 _____。 A． ( ) 句子 B． ( ) 句型 C． ( ) 單詞 D． ( ) 產(chǎn)生式 9． 文法分為四種類(lèi)型，即 0 型、 1 型、 2 型、 3 型。其中 2 型文法是 _____。 A. ( ) 短語(yǔ)文法 B． ( ) 正則文法 C． ( ) 上下文有關(guān)文法 D． ( ) 上下文無(wú)關(guān)文法 10． 文法 G 所描述的語(yǔ)言是 _____的集合。 A. ( ) 文法 G 的字母表 V 中所有符號(hào)組成的符號(hào)串 B． ( ) 文法 G 的字母表 V 的閉包 V* 中的所有符號(hào)串 C． ( ) 由文法的開(kāi)始符號(hào)推出的所有終極符串 D. ( ) 由文法的開(kāi)始符號(hào)推出的所有符號(hào)串 三、填空題 (每空 1 分，共 10 分 ) 1． 一個(gè)句型中的最左簡(jiǎn)單短語(yǔ)稱(chēng)為該句型的 ___句柄 __。 2． 對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱(chēng)為 __語(yǔ)義規(guī)則 ___ 。 3． 一個(gè)典型的編譯程序中，不僅包括 __詞法分析 ___、 __語(yǔ)法分析 ___、 __中間代碼生成 ___、代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。 4． 從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為 __執(zhí)行性 ___語(yǔ)句和 __說(shuō)明性 ___語(yǔ)句兩大類(lèi)。 5． 掃描器的任務(wù)是從 __源程序 ___中識(shí)別出一個(gè)個(gè) ___單詞符號(hào) __。 6． 產(chǎn)生式是用于定義 __語(yǔ)法范疇 ___的一種書(shū)寫(xiě)規(guī)則。 四、簡(jiǎn)答題（ 20 分） 1. 寫(xiě)一個(gè)文法，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(shù)不以 0 開(kāi)頭。 解：文法 G(N)： N→AB|B A→AC|D B→1|3|5|7|9 D→B|2|4|6|8 C→0|D 2. 設(shè)文法 G(S)： S→(L)|a S|a L→L ， S|S (1) 消除左遞歸和回溯； (2) 計(jì)算每個(gè)非終結(jié)符的 FIRST 和 FOLLOW。 解： (1) S→(L)|aS39。 S39?！鶶|ε L→SL39。 L39。→SL39。|ε (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)的最右推導(dǎo)； (2)給出句型 (T *F＋ i)的短語(yǔ)、素短語(yǔ)。 解： (1) 最右推導(dǎo)： ETF(E)(E ＋ T)(E ＋ F)(E ＋ i) (T＋ i)(T*F＋ i) (2) 短語(yǔ)： (T*F＋ i)， T*F＋ i， T*F， i 素短語(yǔ)： 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) 五 .計(jì)算題（ 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}, 構(gòu)造相應(yīng)的 DFA并最小化。 解：根據(jù)題意有 NFA 圖 : 下 表 由 子 集 法 將 NFA 轉(zhuǎn)換為 DFA ： 下面將該 DFA 最小化： (1) 首先將它的狀態(tài)集分成兩個(gè)子集： 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 等價(jià)。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而 D， E 不等價(jià)（見(jiàn)下步），從而 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 不等價(jià)，所以 A， E 可以區(qū)分。 (5) 綜上所述， DFA 可以區(qū)分為 P={{A}， {B}， {D}， {E}， {C， F}}。所以最小化的 DFA如下： 《編譯原理》模擬試題四 一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃 √，錯(cuò)誤的劃 ）（每個(gè) 2 分，共 20 分） 1． 一個(gè) LL(l)文法一定是無(wú)二義的。 ( ) 2． 正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)關(guān)文法來(lái)描述。 ( ) 3． 一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初 態(tài)，最多只有一個(gè)終態(tài)。 (√) 4． 目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。 ( ) 5． 逆波蘭法表示的表達(dá)式亦稱(chēng)前綴式 。 (√ ) 6． 如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱(chēng)這個(gè)文法是二義的。 (√ ) 7． LR 法是自頂向下語(yǔ)法分析方法。 ( ) 8． 數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。 ( ) 9． 算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。 () 10． 對(duì)于數(shù)據(jù)空間的存貯分配， FORTRAN 采用動(dòng)態(tài)貯存分配策略。 () 二、選擇題 (請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一 項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論 )(每個(gè) 4 分，共40 分 ) 1． 詞法分析器用于識(shí)別 _____。 A． ( ) 字符串 B． ( )語(yǔ)句 C． ( )單詞 D． ( )標(biāo)識(shí)符 2． 文法分為四種類(lèi)型，即 0 型、 1 型、 2 型、 3 型。其中 0 型文法是 _____。 A. ( ) 短語(yǔ)文法 B． ( ) 正則文法 C． ( ) 上下文有關(guān)文法 D． ( ) 上下文無(wú)關(guān)文法 3． 一個(gè)上下文無(wú)關(guān)文法 G 包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組 _____。 A． ( ) 句子 B． ( ) 句型 C． ( ) 單詞 D． ( ) 產(chǎn)生式 4． _____是一種典型的解釋型語(yǔ)言。 A． ( ) BASIC B． ( ) C C． ( ) FORTRAN D． ( ) PASCAL 5． 與編譯系統(tǒng)相比，解釋系統(tǒng) _____。 A． ( ) 比較簡(jiǎn)單 , 可移植性好 , 執(zhí)行速度快 B． ( ) 比較復(fù)雜 , 可移植性好 , 執(zhí)行速度快 C． ( ) 比較簡(jiǎn)單 , 可移植性差 , 執(zhí)行速度慢 D． ( ) 比較簡(jiǎn)單 , 可移植性好 , 執(zhí)行速度慢 6． 用高級(jí)語(yǔ)言編寫(xiě)的程序經(jīng)編譯后產(chǎn)生的程序叫 _____。 A． ( ) 源程序