編譯原理試題匯總

1、編譯原理考試題及答案匯總一、選擇1 將編譯程序分成若干個(gè)“遍”是為了 _B_。A . 提高程序的執(zhí)行效率B. 使程序的結(jié)構(gòu)更加清晰C. 利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率D.利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率2 正規(guī)式MI 和 M2 等價(jià)是指_C_。A . MI 和 M2 的狀態(tài)數(shù)相等B.Ml 和 M2 的有向弧條數(shù)相等。C .M1 和 M2 所識(shí)別的語(yǔ)言集相等D. Ml 和 M2 狀態(tài)數(shù)和有向弧條數(shù)相等3中間代碼生成時(shí)所依據(jù)的是_C_ 。A.語(yǔ)法規(guī)則 B .詞法規(guī)則 C .語(yǔ)義規(guī)則 D .等價(jià)變換規(guī)則4 .后綴式ab+cd+/可用表達(dá)式_B_來(lái)表示。A a+b/c+d B (a+b

2、)/(c+d) C a+b/(c+d) D a+b+c/d6 一個(gè)編譯程序中，不僅包含詞法分析， _A，中間代碼生成，代碼優(yōu)化， 目標(biāo)代碼生成等五個(gè)部分。A ( ) 語(yǔ)法分析 B ( ) 文法分析 C ( ) 語(yǔ)言分析 D ( ) 解釋分析7 詞法分析器用于識(shí)別_C_。A ( ) 字符串 B ( ) 語(yǔ)句 C ( ) 單詞 D ( ) 標(biāo)識(shí)符8 語(yǔ)法分析器則可以發(fā)現(xiàn)源程序中的_D_。A ( ) 語(yǔ)義錯(cuò)誤B ( ) 語(yǔ)法和語(yǔ)義錯(cuò)誤C ( ) 錯(cuò)誤并校正D ( ) 語(yǔ)法錯(cuò)誤9 下面關(guān)于解釋程序的描述正確的是_B_。(1) 解釋程序的特點(diǎn)是處理程序時(shí)不產(chǎn)生目標(biāo)代碼(2)解釋程序適用于 COBOL和F

3、ORTRAN語(yǔ)言(3) 解釋程序是為打開(kāi)編譯程序技術(shù)的僵局而開(kāi)發(fā)的A ( ) (1)(2) B ( ) (1) C ( ) (1)(2)(3) D ( ) (2)(3)10 解釋程序處理語(yǔ)言時(shí), 大多數(shù)采用的是_B_方法。A ( )源程序命令被逐個(gè)直接解釋執(zhí)行8 ( )先將源程序轉(zhuǎn)化為中間代碼, 再解釋執(zhí)行C ( )先將源程序解釋轉(zhuǎn)化為目標(biāo)程序, 再執(zhí)行D ( )以上方法都可以11 編譯過(guò)程中 , 語(yǔ)法分析器的任務(wù)就是_B_。(1) 分析單詞是怎樣構(gòu)成的 (2) 分析單詞串是如何構(gòu)成語(yǔ)句和說(shuō)明的(3) 分析語(yǔ)句和說(shuō)明是如何構(gòu)成程序的 (4) 分析程序的結(jié)構(gòu)A ( ) (2)(3) B ( )

4、(2)(3)(4)C ( ) (1)(2)(3) D ( ) (1)(2)(3)(4)12 編譯程序是一種_C_。A. ( ) 匯編程序 B ( ) 翻譯程序 C ( ) 解釋程序 D ( ) 目標(biāo)程序13 文法 G 所描述的語(yǔ)言是_C的集合。A. ( )文法G的字母表V中所有符號(hào)組成的符號(hào)串8 ( )文法G的字母表V的閉包 V* 中的所有符號(hào)串C ( )由文法的開(kāi)始符號(hào)推出的所有終極符串D. ( )由文法的開(kāi)始符號(hào)推出的所有符號(hào)串14 文法分為四種類(lèi)型，即 0 型、 1 型、 2 型、 3 型。其中 3 型文法是_B_。A. ( ) 短語(yǔ)文法 B ( ) 正則文法 C ( ) 上下文有關(guān)文法

5、D ( ) 上下文無(wú)關(guān)文法15 一個(gè)上下文無(wú)關(guān)文法G 包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組_D_ 。A ( ) 句子 B ( ) 句型 C ( ) 單詞 D ( ) 產(chǎn)生式16 通常一個(gè)編譯程序中， 不僅包含詞法分析， 語(yǔ)法分析， 中間代碼生成， 代碼優(yōu)化， 目 標(biāo) 代碼生成等五個(gè)部分，還應(yīng)包括_C。A ( ) 模擬執(zhí)行器 B ( ) 解釋器C ( ) 表格處理和出錯(cuò)處理 D ( ) 符號(hào)執(zhí)行器17 .文法 GN=( b , N , B , N , N -b bB , B-bN)，該文法所描述的語(yǔ)言是 CA. ( ) L(GN尸bii > 0 B

6、 . ( ) L(GN尸b2ii > 0C. ( ) L(GN尸b2i+1i > 0 D . ( ) L(GN尸b2i+1i > 118 一個(gè)句型中的最左_B稱(chēng)為該句型的句柄。A ( ) 短語(yǔ) B ( ) 簡(jiǎn)單短語(yǔ)C ( ) 素短語(yǔ) D ( ) 終結(jié)符號(hào)19 .設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果S->x(其中x CV*),則稱(chēng)x是文法 G 的一個(gè)_B_。A ( ) 候選式 B ( ) 句型 C ( ) 單詞 D ( ) 產(chǎn)生式20 文法 GE ： E f T I E + TT f F I T * FFfa I ( E )該文法句型E + F * (E + T

7、)的簡(jiǎn)單短語(yǔ)是下列符號(hào)串中的 。(E+T) E + T F F*(E+ T)A ( ) 和 B ( ) 和 C ( ) 和 D ( ) 21 若一個(gè)文法是遞歸的，則它所產(chǎn)生的語(yǔ)言的句子_A_。A( )是無(wú)窮多個(gè)B () 是有窮多個(gè)C( )是可枚舉的D ( ) 個(gè)數(shù)是常量22 詞法分析器用于識(shí)別_C_。A ( ) 句子 B ( ) 句型 C ( ) 單詞 D ( ) 產(chǎn)生式23 . 在語(yǔ)法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是_B。A . ( ) 非終極符集B ( ) 終極符集C ( ) 字母表 D . ( ) 狀態(tài)集24 在自底向上的語(yǔ)法分析方法中，分析的關(guān)鍵是_A

8、_。A .( ) 尋找句柄 B .( ) 尋找句型C .( ) 消除遞歸 D .( ) 選擇候選式25 在 LR 分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型_C_的 DFA 狀態(tài)。A .( ) 句柄 B .( ) 前綴 C .( ) 活前綴 D .( ) LR(0) 項(xiàng)目26 文法 G 產(chǎn)生的_D_的全體是該文法描述的語(yǔ)言。A ( ) 句型 B ( ) 終結(jié)符集 C ( ) 非終結(jié)符集D ( ) 句子27 若文法 G 定義的語(yǔ)言是無(wú)限集，則文法必然是_A_A ( ) 遞歸的 B ( ) 前后文無(wú)關(guān)的C ( ) 二義性的 D ( ) 無(wú)二義性的28 四種形式語(yǔ)言文法中， 1 型文法又稱(chēng)為_(kāi)A_

9、文法。A ( ) 短語(yǔ)結(jié)構(gòu)文法B ( ) 前后文無(wú)關(guān)文法C ( ) 前后文有關(guān)文法D ( ) 正規(guī)文法29 一個(gè)文法所描述的語(yǔ)言是_A_。A ( ) 唯一的 B ( ) 不唯一的C ( ) 可能唯一，好可能不唯一D ( ) 都不對(duì)30 _B_ 和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。A ( ) 語(yǔ)法分析 B ( ) 中間代碼生成C ( ) 詞法分析 D ( ) 目標(biāo)代碼生成31 _B是兩類(lèi)程序語(yǔ)言處理程序。A ( ) 高級(jí)語(yǔ)言程序和低級(jí)語(yǔ)言程序B ( ) 解釋程序和編譯程序C ( ) 編譯程序和操作系統(tǒng)D ( ) 系統(tǒng)程序和應(yīng)用程序32 數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的 _A的信息。A . (

10、 ) 維數(shù) B ( ) 類(lèi)型 C ( ) 維上下界D ( ) 各維的界差33 . 一個(gè)上下文無(wú)關(guān)文法G 包括四個(gè)組成部分，它們是： 一組非終結(jié)符號(hào)， 一組終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組 _D_ 。A ( ) 句子 B ( ) 句型C ( ) 單詞 D ( ) 產(chǎn)生式34 文法分為四種類(lèi)型，即 0 型、 1 型、 2 型、 3 型。其中 2 型文法是_D_。A . ( ) 短語(yǔ)文法B ( ) 正則文法C ( ) 上下文有關(guān)文法D ( ) 上下文無(wú)關(guān)文法35 一個(gè)上下文無(wú)關(guān)文法G 包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組_D_ 。A ( ) 句子 B ( )

11、 句型 C ( ) 單詞 D ( ) 產(chǎn)生式36 _A_是一種典型的解釋型語(yǔ)言。A ( ) BASIC B ( ) C C ( ) FORTRAN D ( ) PASCAL37與編譯系統(tǒng)相比，解釋系統(tǒng)_D_。A()比較簡(jiǎn)單,可移植性好,執(zhí)行速度快8 ()比較復(fù)雜,可移植性好,執(zhí)行速度快C ( ) 比較簡(jiǎn)單 , 可移植性差, 執(zhí)行速度慢D()比較簡(jiǎn)單,可移植性好,執(zhí)行速度慢38用高級(jí)語(yǔ)言編寫(xiě)的程序經(jīng)編譯后產(chǎn)生的程序叫_B_。A ( ) 源程序 B ( ) 目標(biāo)程序 C ( ) 連接程序 D ( ) 解釋程序39編寫(xiě)一個(gè)計(jì)算機(jī)高級(jí)語(yǔ)言的源程序后, 到正式上機(jī)運(yùn)行之前，一般要經(jīng)過(guò)_B_這幾步:9 )

12、 編輯 (2) 編譯 (3) 連接 (4) 運(yùn)行A . ( ) (1)(2)(3)(4) B ( ) (1)(2)(3) C ( ) (1)(3) D ( ) (1)(4)40把匯編語(yǔ)言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由_A_完成的。A ( ) 編譯器 B ( ) 匯編器C ( ) 解釋器 D ( ) 預(yù)處理器41詞法分析器的輸出結(jié)果是_C_。A ( ) 單詞的種別編碼B ( ) 單詞在符號(hào)表中的位置C ( ) 單詞的種別編碼和自身值 D ( ) 單詞自身值42 . 文法G : S- xSx|y 所識(shí)別的語(yǔ)言是 _C。A. ( ) xyx B . ( ) (xyx)* C . ( ) x

13、nyxn(n > 0) D . ( ) x*yx*43 .如果文法 G是無(wú)二義的，則它的任何句子aA 。A( )最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)必定相同8 ( )最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)可能不同C( )最左推導(dǎo)和最右推導(dǎo)必定相同D( )可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹(shù)相同44構(gòu)造編譯程序應(yīng)掌握_D_。A( )源程序B( )目標(biāo)語(yǔ)言C( )編譯方法D ()以上三項(xiàng)都是45四元式之間的聯(lián)系是通過(guò)_B_實(shí)現(xiàn)的。A( )指示器B ()臨時(shí)變量C( )符號(hào)表D( )程序變量46 .表達(dá)式(A V B) A (C V D)的逆波蘭表示為 B_。A . ( ) n ABV A CDV

14、B . ( ) A n B V CDV AC. ( ) AB Vn CDV A D . ( ) A n B V A CDV47 . 優(yōu)化可生成_D_的目標(biāo)代碼。A ( ) 運(yùn)行時(shí)間較短B ( ) 占用存儲(chǔ)空間較小C ( ) 運(yùn)行時(shí)間短但占用內(nèi)存空間大D ( ) 運(yùn)行時(shí)間短且占用存儲(chǔ)空間小48 下列 _C優(yōu)化方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行的。A . ( ) 強(qiáng)度削弱 B ( ) 刪除歸納變量C ( ) 刪除多余運(yùn)算D ( ) 代碼外提49編譯程序使用_B_區(qū)別標(biāo)識(shí)符的作用域。A . ( ) 說(shuō)明標(biāo)識(shí)符的過(guò)程或函數(shù)名B ( ) 說(shuō)明標(biāo)識(shí)符的過(guò)程或函數(shù)的靜態(tài)層次C ( ) 說(shuō)明標(biāo)識(shí)符的過(guò)程或函數(shù)的動(dòng)態(tài)層次

15、D . ( ) 標(biāo)識(shí)符的行號(hào)50編譯程序絕大多數(shù)時(shí)間花在A ( ) 出錯(cuò)處理 B ( )51 編譯程序是對(duì)_D_。A()匯編程序的翻譯C()機(jī)器語(yǔ)言的執(zhí)行52 采用自上而下分析，必須A()消除左遞歸B_D_ 上。表格管理詞法分析 C ( ) 目標(biāo)代碼生成D ( )B ( ) 高級(jí)語(yǔ)言程序的解釋執(zhí)行D ( ) 高級(jí)語(yǔ)言的翻譯_C_。( ) 消除右遞歸C( )消除回溯D ( )提取公共左因子53在規(guī)范歸約中，用_B_來(lái)刻畫(huà)可歸約串。A( )直接短語(yǔ)B ( )句柄C ( ) 最左素短語(yǔ)D ( ) 素短語(yǔ)54. 若a為終結(jié)符，則 A -> a ? a 3A ( ) 歸約 B ( ) 移進(jìn) C55

16、間接三元式表示法的優(yōu)點(diǎn)為_(kāi)A_。A ( )采用間接碼表，便于優(yōu)化處理C ( )便于優(yōu)化處理，節(jié)省存儲(chǔ)空間56基本塊內(nèi)的優(yōu)化為_(kāi)B_。A . ( ) 代碼外提，刪除歸納變量C ( ) 強(qiáng)度削弱，代碼外提 D57 在目標(biāo)代碼生成階段，符號(hào)表用 _A ( ) 目標(biāo)代碼生成B ( ) 語(yǔ)義檢查_(kāi)B_項(xiàng)目。 ( ) 接受 D ( ) 待約B ( ) 節(jié)省存儲(chǔ)空間，不便于表的修改D ( ) 節(jié)省存儲(chǔ)空間，不便于優(yōu)化處理B ( ) 刪除多余運(yùn)算，刪除無(wú)用賦值 ( ) 循環(huán)展開(kāi)，循環(huán)合并D_。C ( ) 語(yǔ)法檢查 D ( ) 地址分配58 .若項(xiàng)目集Ik 含有A -> a ?,則在狀態(tài)k時(shí)，僅當(dāng)面臨的輸

17、入符號(hào)a £ FOLLOW(A)時(shí)，才采取“ A -> a ? ”動(dòng)作的一定是_D。A . ( ) LALR 文法 B ( ) LR(0) 文法C ( ) LR(1) 文法 D ( ) SLR(1) 文法59堆式動(dòng)態(tài)分配申請(qǐng)和釋放存儲(chǔ)空間遵守_D_原則。A . ( ) 先請(qǐng)先放 B ( ) 先請(qǐng)后放C ( ) 后請(qǐng)先放 D . ( ) 任意、判斷1 .計(jì)算機(jī)高級(jí)語(yǔ)言翻譯成低級(jí)語(yǔ)言只有解釋一種方式。(X)2 .在編譯中進(jìn)行語(yǔ)法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。(X)3甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。(，)4 .正則文法其產(chǎn)生式為

18、 A->a , A->Bb, A,B C VN , a、b VT。(X)5 .每個(gè)文法都能改寫(xiě)為L(zhǎng)L(1)文法。(M)6 .遞歸下降法不允許任一非終極符是直接左遞歸的。(，)7算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。( X )8自底而上語(yǔ)法分析方法的主要問(wèn)題是候選式的選擇。( X)9 LR 法是自頂向下語(yǔ)法分析方法。 ( X)10簡(jiǎn)單優(yōu)先文法允許任意兩個(gè)產(chǎn)生式具有相同右部。 ( X )11 “ 用高級(jí)語(yǔ)言書(shū)寫(xiě)的源程序都必須通過(guò)編譯 , 產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行 ”這種 說(shuō)法。 ( X )12 若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。 ( X )13 . 一個(gè)

19、句型的句柄一定是文法某產(chǎn)生式的右部。(V)14 在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。 ( X )15 僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無(wú)用的。 ( V )16 削減運(yùn)算強(qiáng)度破壞了臨時(shí)變量在一基本塊內(nèi)僅被定義一次的特性。 ( V )17 .在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達(dá)式外提和削減運(yùn)算強(qiáng)度。(x )18 .數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。(x )19 .編譯程序與具體的機(jī)器有關(guān)，與具體的語(yǔ)言無(wú)關(guān)。(x )20 .遞歸下降分析法是自頂向上分析方法。(V )21 .產(chǎn)生式是用于定義詞法成分的一種書(shū)寫(xiě)規(guī)則。(X )22 . LR法是自頂向下語(yǔ)法分析方法。(X)23 .在SL

20、R ( 1 )分析法的名稱(chēng)中，S的含義是簡(jiǎn)單的。(V)24綜合屬性是用于“ 自上而下” 傳遞信息。 ( X )25 符號(hào)表中的信息欄中登記了每個(gè)名字的 屬性和特征等有關(guān)信息 ，如類(lèi)型、種屬、所占單元大小、地址等等。 ( X )26程序語(yǔ)言的語(yǔ)言處理程序是一種應(yīng)用軟件。( X )27 一個(gè)LL(l) 文法一定是無(wú)二義的。 ( X )28正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)關(guān)文法來(lái)描述。( X )29 .一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。(V)30目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。( X )31 .逆波蘭法表示的表達(dá)式亦稱(chēng)后綴式。(，)32

21、.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱(chēng)這個(gè)文法是二義的。(V )33數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。 ( X )34.對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動(dòng)態(tài)貯存分配策略。(X )35編譯程序是對(duì)高級(jí)語(yǔ)言程序的解釋執(zhí)行。( X )36一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。( X )37語(yǔ)法分析時(shí)必須先消除文法中的左遞歸。 ( X )38 . LR分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。(V )39 .逆波蘭表示法表示表達(dá)式時(shí)無(wú)須使用括號(hào)。(V )40靜態(tài)數(shù)組的存儲(chǔ)空間可以在編譯時(shí)確定。( X )41進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代

22、碼優(yōu)化，這對(duì)提高目標(biāo)代碼的效率將起更大作用。( X )42 兩個(gè)正規(guī)集相等的必要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。 ( X )43 一個(gè)語(yǔ)義子程序描述了一個(gè)文法所對(duì)應(yīng)的翻譯工作。 ( X )44 r 和 s 分別是正規(guī)式，則有L(r|s)=L(r)L(s)。 ( X )45 .確定的的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正集(V)46分析作為單獨(dú)的一遍來(lái)處理較好。( X )47 LR 分析器的任務(wù)就是產(chǎn)生LR 分析表。 ( V )48歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過(guò)程。( V )49同心集的合并有可能產(chǎn)生新的“移進(jìn)”/ “歸約” 沖突 ( X)50.lR 分析技術(shù)無(wú)法適用二義文法。 ( X )51樹(shù)形

23、表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。( X )52序中的表達(dá)式語(yǔ)句在語(yǔ)義翻譯時(shí)不需要回填技術(shù)。( V)三、填空1 編譯程序的工作過(guò)程一般可以劃分為詞法分析 , 語(yǔ)法分析 ,語(yǔ)義分析, 中間代碼生成 ,代碼優(yōu)化等幾個(gè)基本階段,同時(shí)還會(huì)伴有_表格處理 _和 _出錯(cuò)處理_。2 若源程序是用高級(jí)語(yǔ)言編寫(xiě)的,_ 目標(biāo)程序_是機(jī)器語(yǔ)言程序或匯編程序 ,則其翻譯程序稱(chēng)為_(kāi) 編譯程序 _ 。3 編譯方式與解釋方式的根本區(qū)別在于_是否生成目標(biāo)代碼_ 。4 對(duì)編譯程序而言,輸入數(shù)據(jù)是_源程序_, 輸出結(jié)果是_ 目標(biāo)程序 _ 。5 .產(chǎn)生式是用于定義語(yǔ)法成分的一種書(shū)寫(xiě)規(guī)則。6 .語(yǔ)法分析最常用的

24、兩類(lèi)方法是自上而下 和 自下而上 分析法7 .設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果S->x(其中xCVT*),則稱(chēng)x是文法的一個(gè)句子 。8 .遞歸下降法不允許任一非終極符是直接9 .自頂向下的語(yǔ)法分析方法的基本思想是 入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行，使之與給定的輸入串 匹配。10 .自底向上的語(yǔ)法分析方法的基本思想是左 遞歸的。:從文法的 開(kāi)始符號(hào)開(kāi)始，根據(jù)給定的輸直接推導(dǎo)，試圖推導(dǎo)出文法的句子:從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進(jìn)行 直接歸約，力求歸約到文法的開(kāi)始符號(hào)。11常用的參數(shù)傳遞方式有傳地址，傳值和傳名。12 .在使用高級(jí)語(yǔ)言編程時(shí),首先可通過(guò)編譯

25、程序發(fā)現(xiàn)源程序的全部語(yǔ)法錯(cuò)誤和語(yǔ)義的部分錯(cuò)誤。13 . 一個(gè)句型中的最左簡(jiǎn)單短語(yǔ)稱(chēng)為該句型的句柄。14 .對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱(chēng)為語(yǔ)義規(guī)則。15 一個(gè)典型的編譯程序中，不僅包括 詞法分析、語(yǔ)法分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。16 .從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為執(zhí)行性 語(yǔ)句和說(shuō)明性語(yǔ)句兩大類(lèi)。17 .產(chǎn)生式是用于定義語(yǔ)法范疇的一種書(shū)寫(xiě)規(guī)則。18 .語(yǔ)法分析是依據(jù)語(yǔ)言的語(yǔ)法規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語(yǔ)言的語(yǔ)義規(guī)進(jìn)行的。19 .語(yǔ)法分析器的輸入是單詞符號(hào)串，其輸出是語(yǔ)法單位 O2o7產(chǎn)生式是用于定義語(yǔ)法成分的一

26、種書(shū)寫(xiě)規(guī)則。21 .逆波蘭式 ab+c+ d*e- 所表達(dá)的表達(dá)式為 (a+b+c)*d-e 。22 .語(yǔ)法分析最常用的兩類(lèi)方法是 _自上而下 和_自下而上分析法。23 .計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序主要有兩種途徑：解釋和編譯 。24 .掃描器是詞法分析器，它接受輸入的源程序，對(duì)源程序進(jìn)行詞法分析并識(shí)別出一個(gè)個(gè)單詞符號(hào).其輸出結(jié)果是單詞符號(hào)，供語(yǔ)法分析器使用。25 .自上而下分析法采用移進(jìn)、歸約、錯(cuò)誤處理、接受 等四種操作。26 .一個(gè)LR分析器包括兩部分：一個(gè)總控程序和 一張分析表_。27 .后綴式abc-/所代表的表達(dá)式是 a/(b-c)_ _。28 .局部?jī)?yōu)化是在基本塊范圍內(nèi)進(jìn)行的一種

27、優(yōu)化。29 .詞法分析基于正則 文法進(jìn)行，即識(shí)別的單詞是該類(lèi)文法的句子。30 .語(yǔ)法分析基于上下文無(wú)關(guān)文法進(jìn)行，即識(shí)別的是該類(lèi)文法的句子。語(yǔ)法分析的有效工具是語(yǔ)法樹(shù) 。31 .分析句型時(shí)，應(yīng)用算符優(yōu)先分析技術(shù)時(shí)，每步被直接歸約的是最左素短語(yǔ) ，而應(yīng)用LR分析技術(shù)時(shí)，每步被直接歸約的是句柄 。32 .語(yǔ)義分析階段所生成的與源程序等價(jià)的中間表示形式可以有逆波蘭 、 三元式表示與四元式表示等。33 .按Chomsky 分類(lèi)法，文法按照規(guī)則定義的形式進(jìn)行分類(lèi)。34 . 一個(gè)文法能用有窮多個(gè)規(guī)則描述無(wú)窮的符號(hào)串集合偌言)是因?yàn)槲姆ㄖ写嬖谟?遞歸定義的規(guī)則。35 . 一個(gè)名字的屬性包括四、綜合題1.已知文

28、法G(E)E 一 T|E+ T T- F|T *F F 一 (E)|i(1)給出句型(T *F (2)給出句型(T *F 解：類(lèi)型 和作用域+ i)的最右推導(dǎo)；+ i)的短語(yǔ)、簡(jiǎn)單短語(yǔ)、+ i)(1)最右推導(dǎo)：E->T->F->(E)->(E+ T)->(E+ F)->(E+ i) ->(T + i)->(T*F(2)短語(yǔ)：(T*F +i) , T*F+i , T*F, i簡(jiǎn)單短語(yǔ)：T*F,i句柄：T*F素短語(yǔ)：T*F,i最左素短語(yǔ)：T*F2.構(gòu)造正規(guī)式1(0|1)*101 相應(yīng)的DFA 。解：先構(gòu)造NFA :確定化:01XAAAABAPIACA

29、BACAABYABVACAB重新命名，令 AB為B、AC為C、ABY為D得:01YAAABBcBCADDcBS->MH|aH ->LSo| jK ->dML| gL ->eHfM->K|bLM判斷G是否為L(zhǎng)L(1)文法，如果是，構(gòu)造 LL(1)分析表。解：各符號(hào)的 FIRST集和FOLLOW1為：FIRSTFOLLOWS漁M他仆建枷)H 后#喇L值可比科郴K但4各產(chǎn)生式SELECT為:SELECTS->MHd,b,e,#,oS->aaH ->LSoeH - > £#,f,oK ->dMLdK ->工e,#,oL -&g

30、t;eHfeM->Kd,e,#,oM-> bLMb預(yù)測(cè)分析表4&他一期SM總理.拿您班.激H -費(fèi)強(qiáng)->LSoV111義j-出匚由于預(yù)測(cè)分析表中無(wú)多重入口，所以可判定文法是LL(1)的。4 .對(duì)下面的文法G :E ->TE'E'->+E| eT ->FT'T' ->T| 三F-> PF'F'-> *F'|£P->(E)|a|bF計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST集和FOLLOW集。(4分)(2)證明這個(gè)方法是 LL(1)的。(4分)(3)構(gòu)造它的預(yù)測(cè)分析表。

31、(2分)解：(1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST集和FOLLOW集。FIRST集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,A;FIRST(E'尸+, £ FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,A；FIRST(T')=FIRST(T)U_ £ =(,a,b,£ ;FIRST(F)=FIRST(P)=(,a,b,A；FIRST(F')=FIRST(P)=*, £ ;FIRST(P)=(,a,b,A;FOLLOW1合有：FOLLOW(E)=),#;FOL

32、LOW(E')=FOLLOW(E)=),#; FOLLOW(T)=FIRST(E')UFOLLOW(E)=+,),#;/ 不包含 sFOLLOW(T'尸F(xiàn)OLLOW(T尸F(xiàn)IRST(E')UFOLLOW(E尸+,),#;FOLLOW(F)=FIRST(T')UFOLLOW(T)=(,a,b,A,+,),#;/ 不包含 £FOLLOW(F')=FOLLOW(F)=FIRST(T')UFOLLOW(T)=(,a,b,A,+,),#;FOLLOW(P)=FIRST(F')UFOLLOW(F)=*,(,a,b,A,+,),#;/

33、 不包含 £(2)證明這個(gè)方法是 LL(1)的。各產(chǎn)生式的SELECT集合有：SELECT(E->TE')=FIRST(T)=(,a,b,A；SELECT(E'->+E尸+;SELECT(E'-> 力FOLLOW(E/)=),#SELECT(T->FT')=FIRST(F)=(,a,b,A；SELECT(T'->T)=FIRST(T)=(,a,b,A；SELECT(T'-> 力FOLLOW(T/尸+,),#;SELECT(F->PF')=FIRST(P)=(,a,b,A；SELECT(F

34、'->*F')=*;SELECT(F'-> 工)=FOLLOW(F')=(,a,b,A,+,),#;SELECT(P->(E)=(SELECT(P->a尸aSELECT(P->b)=bSELECT(P->a)=a可見(jiàn)，相同左部產(chǎn)生式的SELECT集的交集均為空，所以文法GE是LL(1)文法。(3)構(gòu)造它的預(yù)測(cè)分析表。文法GE的預(yù)測(cè)分析表如下：+*()abA#ETTETTE今TE,似T3FT->F 丁+F 丁今£TT吟£->TTTT名F4PFfTFF'TPF'-> £

35、;9W4 e->sT £T sP40ThW5 .已知文法GS為：S->a1Al(T)T-> T,S|S(1)計(jì)算 GS的 FIRSTVT 和 LASTVT。(2)構(gòu)造GS的算符優(yōu)先關(guān)系表并說(shuō)明GS是否未算符優(yōu)先文法(3)給出輸入用(a,a)# 的算符優(yōu)先分析過(guò)程。解：(1)各符號(hào)的 FIRSTVT和LASTVT:FIRSTVTLASTV1sTa、A (v x 3 A(包、)* % a. A )(2)算符優(yōu)先關(guān)系表:a(F八件a>>(<<<)<< j>>><>»*律4(3)句子(a,a)#分析過(guò)程如下:步驟棧優(yōu)先關(guān)系當(dāng)前符號(hào)剩余輸入串移進(jìn)或歸約1蘋(píng)林(a用考移進(jìn)2極(<aa.啟建移進(jìn)3