(完整版)編譯原理試題.docx

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

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

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

4、 編譯程序是一種_C_。A. ( )匯編程序 B ( )翻譯程序 C ( )解釋程序D( )目標(biāo)程序13 文法 G 所描述的語言是_C_的集合。A. ( )文法 G 的字母表 V中所有符號組成的符號串B ( )文法 G 的字母表 V的閉包 V*中的所有符號串C ( )由文法的開始符號推出的所有終極符串D. ( )由文法的開始符號推出的所有符號串14 文法分為四種類型，即0型、 1 型、 2 型、 3 型。其中 3型文法是 _B_。A. ( )短語文法 B ( )正則文法 C ( )上下文有關(guān)文法D ( )上下文無關(guān)文法15 一個上下文無關(guān)文法G 包括四個組成部分，它們是：一組非終結(jié)符號，一組終

5、結(jié)符號，一個開始符號，以及一組_D_ 。A( )句子 B( )句型 C( )單詞 D( )產(chǎn)生式16 通常一個編譯程序中，不僅包含詞法分析，語法分析， 中間代碼生成， 代碼優(yōu)化， 目 標(biāo)代碼生成等五個部分，還應(yīng)包括_C_。A( )模擬執(zhí)行器B ( )解釋器C( )表格處理和出錯處理D ( )符號執(zhí)行器17 文法 GN= （ b， N， B， N， N b bB， B bN ），該文法所描述的語言是 CA ( ) L(GN)=bi i 0B ( ) L(GN)=b2i i 0C ( ) L(GN)=b2i+1 i 0D ( ) L(GN)=b2i+1 i 118 一個句型中的最左_B_稱為該句型

6、的句柄。A( )短語 B ()簡單短語C ()素短語D ( )終結(jié)符號19設(shè) G 是一個給定的文法， S 是文法的開始符號，如果 S->x(其中 x V*),則稱 x是文法 G 的一個 _B_。A( )候選式B ( )句型C ( )單詞 D( ) 產(chǎn)生式20 文法 GE ：ETETTFTFF a （ E）該文法句型 E F (E T)的簡單短語是下列符號串中的_。 （E T ） ETFF (E T)A() 和 B ()和 C() 和 D() 21 若一個文法是遞歸的，則它所產(chǎn)生的語言的句子_A_。A( )是無窮多個B ( )是有窮多個C( )是可枚舉的D ( )個數(shù)是常量22 詞法分析器

7、用于識別_C_。A( )句子B ( )句型C ( )單詞 D ()產(chǎn)生式23 在語法分析處理中，F(xiàn)IRST集合、 FOLLOW 集合、 SELECT 集合均是 _B_。A.()非終極符集B ( )終極符集C ( )字母表 D.()狀態(tài)集24 在自底向上的語法分析方法中，分析的關(guān)鍵是_A_。A.()尋找句柄 B .( )尋找句型 C .( )消除遞歸D.()選擇候選式25 在 LR 分析法中，分析棧中存放的狀態(tài)是識別規(guī)范句型_C_的 DFA 狀態(tài)。A.()句柄B.()前綴C.()活前綴 D .( ) LR(0)項(xiàng)目26 文法 G產(chǎn)生的 _D_的全體是該文法描述的語言。A( )句型 B( )終結(jié)符

8、集 C ( )非終結(jié)符集 D( )句子27 若文法 G 定義的語言是無限集，則文法必然是_A_A( )遞歸的B()前后文無關(guān)的C ()二義性的D ( )無二義性的28 四種形式語言文法中，1型文法又稱為 _A_ 文法。A( )短語結(jié)構(gòu)文法B ( )前后文無關(guān)文法C( )前后文有關(guān)文法D ( )正規(guī)文法29 一個文法所描述的語言是_A_。A( )唯一的B()不唯一的C( )可能唯一，好可能不唯一D () 都不對30 _B_ 和代碼優(yōu)化部分不是每個編譯程序都必需的。A( )語法分析 B ( )中間代碼生成C( )詞法分析D ( )目標(biāo)代碼生成31 _B_是兩類程序語言處理程序。A( )高級語言程序

9、和低級語言程序B ( ) 解釋程序和編譯程序C( )編譯程序和操作系統(tǒng)D ( ) 系統(tǒng)程序和應(yīng)用程序32 數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的_A_的信息。A.()維數(shù)B ( )類型C ( )維上下界 D ( )各維的界差33. 一個上下文無關(guān)文法 G 包括四個組成部分， 它們是： 一組非終結(jié)符號， 一組終結(jié)符號，一個開始符號，以及一組 _D_ 。A() 句子B () 句型C( )單詞D ( )產(chǎn)生式34 文法分為四種類型，即0 型、1型、 2型、 3型。其中 2型文法是 _D_。A.()短語文法B ( )正則文法C ( ) 上下文有關(guān)文法D ()上下文無關(guān)文法35一個上下文無關(guān)文法G 包括四個組

10、成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組_D_ 。A( )句子B ( )句型 C()單詞D ()產(chǎn)生式36 _A_是一種典型的解釋型語言。A ( ) BASIC B()CC ( ) FORTRAN D ( ) PASCAL37與編譯系統(tǒng)相比，解釋系統(tǒng)_D_。A( )比較簡單 ,可移植性好 ,執(zhí)行速度快B( )比較復(fù)雜 ,可移植性好 ,執(zhí)行速度快C ()比較簡單,可移植性差 ,執(zhí)行速度慢D( )比較簡單 ,可移植性好 ,執(zhí)行速度慢38用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫_B_。A( )源程序 B ( )目標(biāo)程序 C ( )連接程序 D ( )解釋程序39編寫一個計

11、算機(jī)高級語言的源程序后, 到正式上機(jī)運(yùn)行之前，一般要經(jīng)過_B_這幾步:(1)編輯 (2)編譯(3)連接(4)運(yùn)行A . ( ) (1)(2)(3)(4) B ( ) (1)(2)(3) C ( ) (1)(3) D( ) (1)(4)40把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由A( )編譯器B( )匯編器C( )解釋器 D( )預(yù)處理器_A_完成的。41詞法分析器的輸出結(jié)果是_C_。A ( )單詞的種別編碼B ( )單詞在符號表中的位置C ( )單詞的種別編碼和自身值D ( )單詞自身值42 文法 G ： S xSx|y所識別的語言是_C_。A ( ) xyx B( ) (xyx)*

12、 C( ) xnyxn(n 0) D ( ) x*yx*43如果文法G 是無二義的，則它的任何句子_A_。A ( )最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同B ( )最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同44構(gòu)造編譯程序應(yīng)掌握_D_。A( )源程序B()目標(biāo)語言C( )編譯方法 D ( )以上三項(xiàng)都是45四元式之間的聯(lián)系是通過_B_實(shí)現(xiàn)的。A( )指示器B ( )臨時變量C( )符號表D ()程序變量46表達(dá)式 ( A B) (C D)的逆波蘭表示為 _B_。A.() AB CDB( ) A B CDC ( ) AB CDD()A B CD47. 優(yōu)化可生成 _D_的目標(biāo)代碼。A ( ) 運(yùn)行時

13、間較短 B ( ) 占用存儲空間較小C ( )運(yùn)行時間短但占用內(nèi)存空間大D ( )48下列 _C_優(yōu)化方法不是針對循環(huán)優(yōu)化進(jìn)行的。A.()強(qiáng)度削弱B()刪除歸納變量C ( )刪除多余運(yùn)算D ( )代碼外提運(yùn)行時間短且占用存儲空間小49編譯程序使用_B_區(qū)別標(biāo)識符的作用域。A . ( )說明標(biāo)識符的過程或函數(shù)名B ( )說明標(biāo)識符的過程或函數(shù)的靜態(tài)層次C ( ) 說明標(biāo)識符的過程或函數(shù)的動態(tài)層次D.()標(biāo)識符的行號50編譯程序絕大多數(shù)時間花在_D_ 上。A( )出錯處理 B( )詞法分析 C ( ) 目標(biāo)代碼生成 D ( )表格管理51 編譯程序是對 _D_。A ( ) 匯編程序的翻譯B ( )

14、高級語言程序的解釋執(zhí)行C ( ) 機(jī)器語言的執(zhí)行D( )高級語言的翻譯52 采用自上而下分析，必須_C_。A( )消除左遞歸B ( )消除右遞歸C( )消除回溯 D ( )提取公共左因子53在規(guī)范歸約中，用 _B_來刻畫可歸約串。A( )直接短語 B( )句柄C( )最左素短語D ( )素短語54 若 a為終結(jié)符，則A -> ? a 為 _B_項(xiàng)目。A() 歸約 B ( )移進(jìn) C() 接受 D ()待約55間接三元式表示法的優(yōu)點(diǎn)為_A_。A ( )采用間接碼表，便于優(yōu)化處理B ( )節(jié)省存儲空間，不便于表的修改C ( )便于優(yōu)化處理，節(jié)省存儲空間D ( )節(jié)省存儲空間，不便于優(yōu)化處理5

15、6基本塊內(nèi)的優(yōu)化為_B_。A . ( )代碼外提，刪除歸納變量B ( )刪除多余運(yùn)算，刪除無用賦值C ( )強(qiáng)度削弱，代碼外提D ( )循環(huán)展開，循環(huán)合并57 在目標(biāo)代碼生成階段，符號表用_D_。A ( )目標(biāo)代碼生成B ( )語義檢查C( )58若項(xiàng)目集Ik含有 A -> ? ，則在狀態(tài)k時，才采取“ A -> ? ”動作的一定是_D_。A.()LALR文法B()LR(0)文法C ( ) LR(1)文法D ( ) SLR(1)文法語法檢查 D ( )地址分配時，僅當(dāng)面臨的輸入符號a FOLLOW(A)59堆式動態(tài)分配申請和釋放存儲空間遵守A.()先請先放B()C()后請先放D.(

16、)_D_原則。先請后放任意二、判斷1計算機(jī)高級語言翻譯成低級語言只有解釋一種方式。( ×)2在編譯中進(jìn)行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯誤。( ×)3甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。 ( )4正則文法其產(chǎn)生式為 A->a， A->Bb, A,BVN ， a、 b VT 。 ( ×)5每個文法都能改寫為 LL(1)文法。 ( )6遞歸下降法不允許任一非終極符是直接左遞歸的。( )7算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。( ×)8自底而上語法分析方法的主要問題是候選式的選擇。( ×

17、)9LR 法是自頂向下語法分析方法。( ×)10簡單優(yōu)先文法允許任意兩個產(chǎn)生式具有相同右部。( ×)11“ 用高級語言書寫的源程序都必須通過編譯,產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行”這種說法。( × )12若一個句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。( × )13一個句型的句柄一定是文法某產(chǎn)生式的右部。( )14在程序中標(biāo)識符的出現(xiàn)僅為使用性的。( × )15僅考慮一個基本塊，不能確定一個賦值是否真是無用的。( )16削減運(yùn)算強(qiáng)度破壞了臨時變量在一基本塊內(nèi)僅被定義一次的特性。( )17在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達(dá)式外提和

18、削減運(yùn)算強(qiáng)度。( × )18數(shù)組元素的地址計算與數(shù)組的存儲方式有關(guān)。(× )19編譯程序與具體的機(jī)器有關(guān), 與具體的語言無關(guān)。( × )20遞歸下降分析法是自頂向上分析方法。 ( )21產(chǎn)生式是用于定義詞法成分的一種書寫規(guī)則。( × )22 LR 法是自頂向下語法分析方法。( ×)23在 SLR （ 1 ）分析法的名稱中， S 的含義是簡單的。 ( )24綜合屬性是用于 “ 自上而下 ” 傳遞信息。 ( × )25符號表中的信息欄中登記了每個名字的屬性和特征等有關(guān)信息，如類型、種屬、所占單元大小、地址等等。( × )26程序

19、語言的語言處理程序是一種應(yīng)用軟件。( × )27一個 LL(l) 文法一定是無二義的。( × )28正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。( × )29一張轉(zhuǎn)換圖只包含有限個狀態(tài)，其中有一個被認(rèn)為是初態(tài)，最多只有一個終態(tài)。( )30目標(biāo)代碼生成時，應(yīng)考慮如何充分利用計算機(jī)的寄存器的問題。( × )31逆波蘭法表示的表達(dá)式亦稱后綴式。 ( )32如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義的。( )33數(shù)組元素的地址計算與數(shù)組的存儲方式有關(guān)。( × )34對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動態(tài)貯存分配策略。(

20、 × )35編譯程序是對高級語言程序的解釋執(zhí)行。( × )36一個有限狀態(tài)自動機(jī)中，有且僅有一個唯一的終態(tài)。( × )37語法分析時必須先消除文法中的左遞歸。 ( × )38LR 分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準(zhǔn)確地指出出錯地點(diǎn)。( )39逆波蘭表示法表示表達(dá)式時無須使用括號。( )40靜態(tài)數(shù)組的存儲空間可以在編譯時確定。( × )41進(jìn)行代碼優(yōu)化時應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對提高目標(biāo)代碼的效率將起更大作用。( × )42兩個正規(guī)集相等的必要條件是他們對應(yīng)的正規(guī)式等價。(× )43一個語義子程序描述了一個

21、文法所對應(yīng)的翻譯工作。(× )44 r 和 s 分別是正規(guī)式，則有 L(r|s)=L(r)L(s)。(× )45確定的的自動機(jī)以及不確定的自動機(jī)都能正確地識別正集( )46分析作為單獨(dú)的一遍來處理較好。( × )47 LR 分析器的任務(wù)就是產(chǎn)生 LR分析表。 ( )48歸約和規(guī)范推導(dǎo)是互逆的兩個過程。( )49同心集的合并有可能產(chǎn)生新的“移進(jìn)”/ “歸約” 沖突( ×)50.lR 分析技術(shù)無法適用二義文法。(× )51樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。( × )52序中的表達(dá)式語句在語義翻譯時不需要回填技術(shù)。

22、( )三、填空1編譯程序的工作過程一般可以劃分為詞法分析 ,語法分析 ,語義分析 ,中間代碼生成 ,代碼優(yōu)化等幾個基本階段 ,同時還會伴有 _表格處理 _ 和 _出錯處理 _。2若源程序是用高級語言編寫的 ,_ 目標(biāo)程序 _是機(jī)器語言程序或匯編程序 , 則其翻譯程序稱為 _ 編譯程序 _ 。3編譯方式與解釋方式的根本區(qū)別在于_是否生成目標(biāo)代碼 _ 。4對編譯程序而言 ,輸入數(shù)據(jù)是 _ 源程序 _, 輸出結(jié)果是 _ 目標(biāo)程序 _ 。5產(chǎn)生式是用于定義 _語法成分 _的一種書寫規(guī)則。6語法分析最常用的兩類方法是_ 自上而下 _ 和_ 自下而上 _分析法7，如果 S->x(其中 xVT*),

23、則稱 x設(shè) G 是一個給定的文法 ，S 是文法的開始符號是文 法的一個 _句子 _ 。8_左 _ _遞歸的。遞歸下降法不允許任一非終極符是直接9：從文法的 _開始符號 _ 開始 ，根據(jù)給定的輸自頂向下的語法分析方法的基本思想是入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行_ 直接推導(dǎo) _ ，試圖推導(dǎo)出文法的 _句子_ ，使之與給定的輸入串_ _匹配 _ 。10：從輸入串入手 ，利用文法的產(chǎn)生式一步一步地自底向上的語法分析方法的基本思想是向上進(jìn)行 _ _直接歸約 _，力求歸約到文法的 _開始符號 _ 。11常用的參數(shù)傳遞方式有_ 傳地址 _ ，傳值和傳名。12,首先可通過編譯程序發(fā)現(xiàn)源程序的全部_語法

24、 _ 錯誤和 語義在使用高級語言編程時的部分錯誤。13一個句型中的最左簡單短語稱為該句型的_ 句柄 _。14對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為 _ 語義規(guī)則 _ 。15一個典型的編譯程序中，不僅包括 _詞法分析 _ 、 _語法分析 _ 、_ 中間代碼生成_ 、 代碼優(yōu)化、目標(biāo)代碼生成等五個部分，還應(yīng)包括表格處理和出錯處理。16 從功能上說 ，程序語言的語句大體可分為_執(zhí)行性 _語句和 _ 說明性 _ 語句兩大類。17 產(chǎn)生式是用于定義 _語法范疇 _ 的一種書寫規(guī)則。18語法分析是依據(jù)語言的_ 語法 _ 規(guī)則進(jìn)行的 ，中間代碼產(chǎn)生是依據(jù)語言的_語義 _規(guī)進(jìn)行的。19語法分析器

25、的輸入是 _ 單詞符號串 _ ，其輸出是 _語法單位_ 。20產(chǎn)生式是用于定義 _ 語法成分 _ 的一種書寫規(guī)則。21逆波蘭式 ab+c+ d*e-所表達(dá)的表達(dá)式為 _(a+b+c)*d-e_。22語法分析最常用的兩類方法是_ 自上而下 _ 和 _自下而上 _ 分析法。23計算機(jī)執(zhí)行用高級語言編寫的程序主要有兩種途徑：_ 解釋 _和_ 編譯 _ 。24掃描器是 _詞法分析器 _ ，它接受輸入的 _源程序 _ ，對源程序進(jìn)行 _ 詞法分析_并識別出一個個 單詞符號 ，其輸出結(jié)果是單詞符號，供語法分析器使用。25自上而下分析法采用 _ 移進(jìn) _ 、歸約、錯誤處理、 _接受 _等四種操作。26一個

26、LR 分析器包括兩部分：一個總控程序和 _ 一張分析表 _。27后綴式 abc-/ 所代表的表達(dá)式是 _ a/(b-c)_ _ 。28局部優(yōu)化是在 _ 基本塊 _ 范圍內(nèi)進(jìn)行的一種優(yōu)化。29詞法分析基于 _ 正則 _ 文法進(jìn)行 ，即識別的單詞是該類文法的句子。30語法分析基于 _ 上下文無關(guān) _ 文法進(jìn)行 ，即識別的是該類文法的句子。語法分析的有效工具是 _ 語法樹 _ 。31分析句型時 ，應(yīng)用算符優(yōu)先分析技術(shù)時 ，每步被直接歸約的是_ 最左素短語 _ ，而應(yīng)用LR 分析技術(shù)時 ，每步被直接歸約的是 _ 句柄 _ 。32語義分析階段所生成的與源程序等價的中間表示形式可以有_ 逆波蘭 _ 、 _

27、 三元式表示 _ 與 _ 四元式表示 _等。33按 Chomsky 分類法 ，文法按照 _ 規(guī)則定義的形式 _進(jìn)行分類。34一個文法能用有窮多個規(guī)則描述無窮的符號串集合（語言 ）是因?yàn)槲姆ㄖ写嬖谟?_ 遞歸_ 定義的規(guī)則。35 一個名字的屬性包括_ 類型 _ 和 _ 作用域 _ 。四、綜合題1. 已知文法 G(E) E T|E T TF|T *F(1) 給出句型 (T *F i) 的最右推導(dǎo)；(2) 給出句型 (T *F i) 的短語、簡單短語、句柄、素短語、最左素短語。解：2.(1)最右推導(dǎo)： E ->T->F->(E)->(E(2)短語： (T*F i)， T*F

28、i簡單短語： T*F,i句柄： T*F素短語： T*F,i最左素短語： T*F構(gòu)造正規(guī)式1(0|1)*101相應(yīng)的 T)->(E，T*F ， iDFA 。F)->(Ei)->(T i)->(T*F i)解：先構(gòu)造NFA：確定化：重新命名，令A(yù)B 為 B、AC 為 C、ABY為 D 得：所以，可得DFA 為：3. 文法：S->MH|aH ->LSo|K ->dML|L ->eHfM->K|bLM判斷 G 是否為解：各符號的LL(1) FIRST文法，如果是，構(gòu)造集和 FOLLOW集為：LL(1)分析表。各產(chǎn)生式 SELECT集為：SELECT

29、S->MHd,b,e,#,oS->aaH ->LSoeH - >#,f,oK ->dMLdK -> e,#,oL ->eHfeM->Kd,e,#,oM-> bLMb預(yù)測分析表由于預(yù)測分析表中無多重入口，所以可判定文法是LL(1) 的。4. 對下面的文法 G ：E ->TE'E'->+E|T ->FT'T' ->T|F-> PF'F'-> *F'|P->(E)|a|b|(1) 計算這個文法的每個非終結(jié)符的FIRST 集和 FOLLOW集。 (4

30、分 )(2) 證明這個方法是 LL(1) 的。 (4 分)(3) 構(gòu)造它的預(yù)測分析表。 (2 分 )解：（ 1）計算這個文法的每個非終結(jié)符的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)U =(,a,b, ;FIRST(F)=FIRST(P)=(,a,b,;FIRST(F')=FIRST(P)=*,;FIRST(P)=(,a,b,;FOLLOW集合有：

31、FOLLOW(E)=),#;FOLLOW(E')=FOLLOW(E)=),#; FOLLOW(T)=FIRST(E')UFOLLOW(E)=+,),#;/不包含 FOLLOW(T')=FOLLOW(T)=FIRST(E')UFOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T')UFOLLOW(T)=(,a,b,+,),#;/不包含 FOLLOW(F')=FOLLOW(F)=FIRST(T')UFOLLOW(T)=(,a,b,+,),#;FOLLOW(P)=FIRST(F')UFOLLOW(F)=*,(,a,b,+,

32、),#;/不包含 (2) 證明這個方法是LL(1)的。各產(chǎn)生式的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&

33、#39;->*F')=*;SELECT(F'-> )=FOLLOW(F')=(,a,b,+,),#;SELECT(P->(E)=(SELECT(P->a)=aSELECT(P->b)=bSELECT(P->)=第9頁共 6 頁可見，相同左部產(chǎn)生式的 SELECT 集的交集均為空，所以文法 GE 是 LL(1) 文法。 (3) 構(gòu)造它的預(yù)測分析表。 文法 GE 的預(yù)測分析表如下：5. 已知文法 GS 為：S->a|(T)T-> T,S|S(1) 計算 GS 的 FIRSTVT 和 LASTVT 。(2) 構(gòu)造 GS 的算符優(yōu)

34、先關(guān)系表并說明 GS 是否未算符優(yōu)先文法。(3) 給出輸入串 (a,a)# 的算符優(yōu)先分析過程。解：（ 1）各符號的FIRSTVT 和 LASTVT：（ 2）算符優(yōu)先關(guān)系表：（ 3）句子 (a,a)# 分析過程如下：第10頁共 6 頁6. 已知文法為：S->a|(T)T->T,S|S構(gòu)造它的LR(0) 分析表。解：加入非終結(jié)符S'，方法的增廣文法為：S'->SS->aS->S->(T)T ->T,ST ->S下面構(gòu)造它的LR(0) 項(xiàng)目集規(guī)范族為：從上表可看出, 不存在移進(jìn) - 歸約沖突以及歸約歸約沖突，該文法是LR(0) 文法。

35、從而有下面的LR(0) 分析表：7. 已知文法為：A - >aAd|aAb| 第11頁共 6 頁判斷該文法是否是 SLR(1) 文法 ，若是構(gòu)造相應(yīng)分析表 ，并對輸入串 ab# 給出分析過程。 解：增加一個非終結(jié)符 S/ 后，產(chǎn)生原文法的增廣文法有 ： S'->A A - >aAd|aAb| 下面構(gòu)造它的 LR(0) 項(xiàng)目集規(guī)范族為 ：從上表可看出, 狀態(tài)I0 和 I2 存在移進(jìn) - 歸約沖突 ，該文法不是LR(0) 文法。對于I0 來說有 ：FOLLOW(A) a=b,d,# a= ，所以在I0 狀態(tài)下面臨輸入符號為a 時移進(jìn) ，為 b,d,# 時歸約 ，為其他時報

36、錯。對于I2 來說有也有與I0 完全相同的結(jié)論。這就是說，以上的移進(jìn)- 歸約沖突是可以解決的 ，因此該文法是SLR(1) 文法。其 SLR(1) 分析表為：對輸入串a(chǎn)b# 給出分析過程為：一（每項(xiàng)選擇2 分，共 20 分）選擇題第12頁共 6 頁1將編譯程序分成若干個“遍”是為了_b_。a.提高程序的執(zhí)行效率b.使程序的結(jié)構(gòu)更加清晰c.利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率d.利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率2構(gòu)造編譯程序應(yīng)掌握_d_。a.源程序b.目標(biāo)語言c.編譯方法d.以上三項(xiàng)都是3變量應(yīng)當(dāng)c。a.持有左值b.持有右值c.既持有左值又持有右值d.既不持有左值也不持有右值4編譯程序絕

37、大多數(shù)時間花在_d_上。a.出錯處理b.詞法分析c.目標(biāo)代碼生成d.管理表格5詞法分析器的輸出結(jié)果是_c_。a.單詞的種別編碼b.單詞在符號表中的位置c.單詞的種別編碼和自身值d.單詞自身值6正規(guī)式MI 和 M2 等價是指 _c_。a. MI 和 M2 的狀態(tài)數(shù)相等b.Ml 和 M2 的有向弧條數(shù)相等。C.M1 和 M2 所識別的語言集相等d. Ml 和 M2 狀態(tài)數(shù)和有向弧條數(shù)相等7中間代碼生成時所依據(jù)的是c。a語法規(guī)則b詞法規(guī)則c語義規(guī)則d等價變換規(guī)則8后綴式ab+cd+/ 可用表達(dá)式 _b_來表示。a a+b/c+d b (a+b)/(c+d) c a+b/(c+d) d a+b+c/d

38、9程序所需的數(shù)據(jù)空間在程序運(yùn)行前就可確定，稱為_c_管理技術(shù)。a.動態(tài)存儲b.棧式存儲c.靜態(tài)存儲d.堆式存儲10.堆式動態(tài)分配申請和釋放存儲空間遵守_d_原則。a.先請先放b.先請后放c.后請先放d.任意二（每小題10 分，共 80 分）簡答題1.畫出編譯程序的總體結(jié)構(gòu)圖，簡述各部分的主要功能。2. 已知文法GE:E ET+|T T TF* | F F F | a試證： FF* 是文法的句型，指出該句型的短語、簡單短語和句柄.3為正規(guī)式 (a|b) *a(a|b) 構(gòu)造一個確定的有限自動機(jī)。4 設(shè)文法 G(S)：S (L)|a S|aL L，S|S(1) 消除左遞歸和回溯；(2) 計算每個非

39、終結(jié)符的 FIRST和 FOLLOW；(3) 構(gòu)造預(yù)測分析表。5 已知文法A->aAd| aAb|判斷該文法是否SLR（ 1）文法，若是構(gòu)造相應(yīng)分析表，并對輸入串a(chǎn)b#給出分析過程。第13頁共 6 頁6 構(gòu)造算符文法 GH的算符優(yōu)先關(guān)系（含） 。GH： HH;M|MM d|aHb7已構(gòu)造出文法 G（S）（1） S BB（ 2） B aB（ 3） B b1）。給出 DFA圖2）.給出 LR分析表3）假定輸入串為 abaab，請給出 LR分析過程（即狀態(tài)，符號，輸入串的變化過程）。8 將下面的語句翻譯成四元式序列：while A<C B<D doif A=1 then C:=C+

40、lelse while A D doA:=A+2；9 對下面的流圖，(1)求出流圖中各結(jié)點(diǎn) N 的必經(jīng)結(jié)點(diǎn)集 D(n)，(2)求出流圖中的回邊，(3)求出流圖中的循環(huán)。參考答案一單項(xiàng)選擇題1.將編譯程序分成若干個“遍”是為了使編譯程序的結(jié)構(gòu)更加清晰，故選b。2. .構(gòu)造編譯程序應(yīng)掌握源程序、目標(biāo)語言及編譯方法等三方面的知識，故選d。3.對編譯而言，變量既持有左值又持有右值，故選c。4.編譯程序打交道最多的就是各種表格，因此選d 。5.詞法分析器輸出的結(jié)果是單詞的種別編碼和自身值，選C。6.正規(guī)式 M1 和 M2 所識別的語言集相等，故選C。7.選 c。8.選 b。9.選 C10.堆式動態(tài)分配申請和釋放存儲空間不一定遵守先請后放和后請先放的原則，故選d二簡答題1 【解答】編譯程序的總體結(jié)構(gòu)圖如圖1.2 所示。詞法分析器：輸入源程序，進(jìn)行詞法分析，輸出單詞符號。語法分析器：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則（文法規(guī)則）把單詞符號串分解成各類語法單位，并判斷輸入串是否構(gòu)成語法上正確的“程序”。中間代碼生成器：按照語義規(guī)則把語法分析器歸約（或推導(dǎo)）出的語法單位翻譯成一定形式的中間代碼，比如說四元式。優(yōu)化：對中間代碼進(jìn)行優(yōu)化處理。目標(biāo)代碼生成器：把中間代碼翻譯成目標(biāo)語言程序。表格管理模塊保存一系列