編譯原理復(fù)習(xí)題

1、編譯原理復(fù)習(xí)題一、是非題1 計(jì)算機(jī)高級語言翻譯成低級語言只有解釋一種方式。(X )3 每個(gè)文法都能改寫為 LL(1) 文法。(X )4 算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。(V)5 LR分析方法是自頂向下語法分析方法。(X )6 “用高級語言書寫的源程序都必須通過編譯，產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行”這種說法。(X)7一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。(V)8僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無用的。(V )9在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達(dá)式外提和削減運(yùn)算強(qiáng)度。(X )10. 對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRA采用動態(tài)貯存分配策略。(X)11甲機(jī)上的某編譯程序在乙機(jī)

2、上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。(X )12遞歸下降分析法是自頂向下分析方法。 (V )13產(chǎn)生式是用于定義詞法成分的一種書寫規(guī)則。 (X)14.在SLR 分析法的名稱中，S的含義是簡單的。(V)15綜合屬性是用于“ 自上而下 ” 傳遞信息。 (X )16符號表中的信息欄中登記了每個(gè)名字的屬性和特征等有關(guān)信息，如類型、種屬、所占單元大小、地址等等。 (X)17程序語言的語言處理程序是一種應(yīng)用軟件。(X)18.解釋程序適用于 COBOL和FORTRAN語言。(X)19一個(gè) LL(l) 文法一定是無二義的。 ( V) 20正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。(

3、 V)21一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。( X )22目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。( V)22逆波蘭法表示的表達(dá)式亦稱后綴式。 (V )23如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義的。(V )24數(shù)組元素的地址計(jì)算與數(shù)組的存儲方式有關(guān)。(V)25算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。(X)28.個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。(V )29語法分析時(shí)必須先消除文法中的左遞歸。(X)30. LR分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。(V)31 .逆波蘭表示法表示

4、表達(dá)式時(shí)無須使用括號。(V )32. 靜態(tài)數(shù)組的存儲空間可以在編譯時(shí)確定。(V)33. 進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對提高目標(biāo)代碼的效率將起更大作用。( V)34. 兩個(gè)正規(guī)集相等的必要條件是他們對應(yīng)的正規(guī)式等價(jià)。( V)35. 一個(gè)語義子程序描述了一個(gè)文法所對應(yīng)的翻譯工作。(X)36. 設(shè)r和s分別是正規(guī)式，則有 L(r|s)=L(r)L(s)。( X)37. 確定的自動機(jī)以及不確定的自動機(jī)都能正確地識別正規(guī)集。(V)38. 詞法分析作為單獨(dú)的一遍來處理較好。(X )39. 構(gòu)造LR分析器的任務(wù)就是產(chǎn)生 LR分析表。(V)40. 規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。 ( V)4

5、1. 同心集的合并有可能產(chǎn)生新的“移進(jìn)” / “歸約”沖突。(X )42. LR分析技術(shù)無法適用二義文法。(X )43. 樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。(X)44. 程序中的表達(dá)式語句在語義翻譯時(shí)不需要回填技術(shù)。(V)45. 對中間代碼的優(yōu)化依賴于具體的計(jì)算機(jī)。(X )46. 若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。(X)47. 在程序中標(biāo)識符的出現(xiàn)僅為使用性的。(X)48. 削減運(yùn)算強(qiáng)度破壞了臨時(shí)變量在一基本塊內(nèi)僅被定義一次的特性。(X)49. 編譯程序與具體的機(jī)器有關(guān)，與具體的語言無關(guān)。(X)二、選擇題 (請?jiān)谇袄ㄌ杻?nèi)選擇最確切的一項(xiàng)作為

6、答案劃一個(gè)勾，多劃按錯(cuò)論)1. 一個(gè)編譯程序中，不僅包含詞法分析， ( A ) ，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分。A. 語法分析B.文法分析 C.語言分析D.解釋分析2. 語法分析器則可以發(fā)現(xiàn)源程序中的 ( D ) 。A. 語義錯(cuò)誤B .語法和語義錯(cuò)誤C.錯(cuò)誤并校正D.語法錯(cuò)誤3. 解釋程序處理語言時(shí) , 大多數(shù)采用的是 ( B ) 方法。A. 源程序命令被逐個(gè)直接解釋執(zhí)行B. 先將源程序轉(zhuǎn)化為中間代碼，再解釋執(zhí)行C. 先將源程序解釋轉(zhuǎn)化為目標(biāo)程序，再執(zhí)行D. 以上方法都可以4 編譯程序是一種 ( B ) 。A.匯編程序B.翻譯程序C.解釋程序D 目標(biāo)程序5. 文法分為四種類型

7、，即0 型、 1 型、 2 型、3型。其中 3 型文法是 ( B ) 。A. 短語文法B .正則文法C.上下文有關(guān)文法D 上下文無關(guān)文法6. 通常一個(gè)編譯程序中，不僅包含詞法分析，語法分析， 中間代碼生成， 代碼優(yōu)化， 目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括 ( C ) 。A.模擬執(zhí)行器B.解釋器C.表格處理和出錯(cuò)處理D .符號執(zhí)行器7. 一個(gè)句型中的最左 ( B ) 稱為該句型的句柄。D .終結(jié)符號A.短語B .簡單短語C.素短語8. 文法 GE ：i T I E + TF I T * F該文法句型 E F(E T) 的簡單短語是下列符號串中的(E T)A.和B.和C .和D.9. 詞法分析器用于

8、識別 ( C ) 。A.句子B.句型C.單詞D .產(chǎn)生式10. 在自底向上的語法分析方法中，分析的關(guān)鍵是A .尋找句柄B .尋找句型C .消除遞歸D. 選擇候選式11. 文法 G 產(chǎn)生的 ( D ) 的全體是該文法描述的語言。A.句型B .終結(jié)符集C.非終結(jié)符集D.句子12. 若文法 G 定義的語言是無限集，則文法必然是 ( A ) 。A.遞歸的B.前后文無關(guān)的C.二義性的D .無二義性的13. 四種形式語言文法中， 1 型文法又稱為 ( C ) 文法。A.短語結(jié)構(gòu)文法B .前后文無關(guān)文法C.前后文有關(guān)文法D .正規(guī)文法14 一個(gè)文法所描述的語言是 ( A )A.唯一的B.不唯一的C.可能唯一

9、，好可能不唯一D.都不對15 ( B ) 和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。A.語法分析B.中間代碼生成C.詞法分析D .目標(biāo)代碼生成16. ( B ) 是兩類程序語言處理程序。A.高級語言程序和低級語言程序B.解釋程序和編譯程序C.編譯程序和操作系統(tǒng)D.系統(tǒng)程序和應(yīng)用程序17. 數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的 ( D ) 的信息。A.維數(shù)B.類型C.維上下界D 各維的界差18. 一個(gè)上下文無關(guān)文法 G 包括四個(gè)組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個(gè)開始符號，以 及一組 ( D ) 。A.句子B.句型C.單詞D.產(chǎn)生式19 文法分為四種類型，即 0型、1型、2型、3型。其

10、中 2型文法是 ( D ) 。A.短語文法B.正則文法C. 上20文法 G 所描述的語言是 ( C ) 的集合。A.文法G的字母表V中所有符號組成的符號串C.由文法的開始符號推出的所有終極符串 21詞法分析器用于識別 ( C ) 。A .字符串B.語句C.單詞F文有關(guān)文法D.上下文無關(guān)文法B 文法 G 的字母表 V 的閉包 V* 中的所有符號串D 由文法的開始符號推出的所有符號串D 標(biāo)識符22 文法分為四種類型，即0型、1 型、2型、3型。其中 0 型文法是 ( A )A 短語文法B 正則文法24 ( A ) 是一種典型的解釋型語言。C 上下文有關(guān)文法D 上下文無關(guān)文法A BASIC B C

11、C FORTRAND PASCAL25 與編譯系統(tǒng)相比，解釋系統(tǒng) ( D ) 。A 比較簡單 , 可移植性好 , 執(zhí)行速度快C 比較簡單 , 可移植性差 , 執(zhí)行速度慢26 用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫A 源程序B 目標(biāo)程序27 詞法分析器用于識別 ( A ) 。B 比較復(fù)雜 , 可移植性好 , 執(zhí)行速度快 D 比較簡單 , 可移植性好 , 執(zhí)行速度慢 ( B ) 。C 連接程序D 解釋程序A 字符串B 語句C 單詞D 標(biāo)識符28編寫一個(gè)計(jì)算機(jī)高級語言的源程序后, 到正式上機(jī)運(yùn)行之前，一般要經(jīng)過 ( B ) 這幾步 :(1) 編輯 (2) 編譯 (3) 連接 (4) 運(yùn)行A(1)(

12、2)(3)(4)B(1)(2)(3)C (1)(3)D (1)(4)29把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由( B ) 完成的。A.編譯器B.匯編器C.解釋器D.預(yù)處理器31. 詞法分析器的輸出結(jié)果是 ( C ) 。A.單詞的種別編碼B.單詞在符號表中的位置C.單詞的種別編碼和自身值D.單詞自身值32. 正規(guī)式 M 1 和 M 2 等價(jià)是指 ( C ) 。A. M1和M2的狀態(tài)數(shù)相等B. M1和M2的有向邊條數(shù)相等C. M1和M2所識別的語言集相等D. M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等33. 文法G: S xSx|y所識別的語言是(C )。A. xyxB . (xyx)* C.

13、xn yxn(n 0)D. x*yx*34. 如果文法 G是無二義的，則它的任何句子a ( A )。A.最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同B.最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同C.最左推導(dǎo)和最右推導(dǎo)必定相同D.可能存在兩個(gè)不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同35構(gòu)造編譯程序應(yīng)掌握 ( D ) 。A.源程序B.目標(biāo)語言C.編譯方法D .以上三項(xiàng)都是36四元式之間的聯(lián)系是通過 ( B ) 實(shí)現(xiàn)的。A.指示器B.臨時(shí)變量C.符號表D .程序變量37. 表達(dá)式(AV B) A (C V D)的逆波蘭表示為(B )。A.n ABVACDVB.An BV CDVAC.ABVnCD/AD.AnBV

14、A CDV38. 優(yōu)化可生成 ( D ) 的目標(biāo)代碼。A.運(yùn)行時(shí)間較短B.占用存儲空間較小C.運(yùn)行時(shí)間短但占用內(nèi)存空間大D.運(yùn)行時(shí)間短且占用存儲空間小39下列 ( C ) 優(yōu)化方法不是針對循環(huán)優(yōu)化進(jìn)行的。A.強(qiáng)度削弱B .刪除歸納變量C.刪除多余運(yùn)算D .代碼外提40編譯程序使用 ( B ) 區(qū)別標(biāo)識符的作用域。C.說明標(biāo)識符的過程或函數(shù)的動態(tài)層次D.標(biāo)識符的行號41編譯程序絕大多數(shù)時(shí)間花在 ( D ) 上。A.出錯(cuò)處理B.詞法分析C.目標(biāo)代碼生成D.表格管理42編譯程序是對 ( D ) 。A.匯編程序的翻譯B 高級語言程序的解釋執(zhí)行C.機(jī)器語言的執(zhí)行D.高級語言的翻譯43采用自上而下分析，必

15、須 ( C ) 。A.消除左遞歸B.消除右遞歸C.消除回溯D.提取公共左因子44在規(guī)范歸約中，用 ( B ) 來刻畫可歸約串。A.直接短語B.句柄C.最左素短語D.素短語45. 若a為終結(jié)符，則 A-a a3為( B )項(xiàng)目。A.歸約B.移進(jìn)C.接受D.待約46間接三元式表示法的優(yōu)點(diǎn)為( A )A.采用間接碼表，便于優(yōu)化處理B. 節(jié)省存儲空間，不便于表的修改C. 便于優(yōu)化處理，節(jié)省存儲空間D. 節(jié)省存儲空間，不便于優(yōu)化處理47基本塊內(nèi)的優(yōu)化為 ( B ) 。A.代碼外提，刪除歸納變量B. 刪除多余運(yùn)算，刪除無用賦值C. 強(qiáng)度削弱，代碼外提D. 循環(huán)展開，循環(huán)合并48. 在目標(biāo)代碼生成階段，符號

16、表用A. 目標(biāo)代碼生成B.語義檢查C.語法檢查D.地址分配49.若項(xiàng)目集Ik含有A-a ，則在狀態(tài)k 時(shí)，僅當(dāng)面臨的輸入符號a FOLLOW(A時(shí)，才采取 “A -a ”動作的一定是 ( D ) 。A. LALR文法B. LR(O)文法CLR(1) 文法DSLR(1)文法50堆式動態(tài)分配申請和釋放存儲空間遵守原則。A.先請先放B .先請后放C.后請先放D.任意三、填空題1編譯程序的工作過程一般可以劃分為詞法分析,語法分析 , 語義分析 ,中間代碼生成 , 代碼優(yōu)化等幾個(gè)基本階段同時(shí)還會伴有 _表格處理 _和 _ _出錯(cuò)處理 _。2. 編譯方式與解釋方式的根本區(qū)別在于_是否生成目標(biāo)代碼 _。3.

17、 產(chǎn)生式是用于定義 _語法成分 _的一種書寫規(guī)則。4 .設(shè)G是一個(gè)給定的文法，S是文法的開始符號，如果S-x(其中x VT*),則稱x是文法的一個(gè)句子5自頂向下的語法分析方法的基本思想是：從文法的_開始符號 開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行 _直接推導(dǎo) ，試圖推導(dǎo)出文法的 _句子 ，使之與給定的輸入串 _匹配_。6常用的參數(shù)傳遞方式有 _傳地址 _，傳值和傳名。7一個(gè)句型中的最左簡單短語稱為該句型的_句柄 _。8對于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為_ 語義規(guī)則 _ 。9一個(gè)典型的編譯程序中，不僅包括_詞法分析 _、_語法分析 _、_中間代碼生成 _、代

18、碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。10 從功能上說，程序語言的語句大體可分為_執(zhí)行性 _語句和 _說明性 _語句兩大類。11 掃描器的任務(wù)是從 _源程序 _中識別出一個(gè)個(gè) _單詞符號 _。12 產(chǎn)生式是用于定義 _語法范疇 _的一種書寫規(guī)則。13語法分析是依據(jù)語言的 _語法 _規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語言的_語義_規(guī)進(jìn)行的。14語法分析器的輸入是 _單詞符號串 _，其輸出是 _語法單位 _。15一個(gè)名字的屬性包括 _類型_和_作用域 _。16逆波蘭式 ab+c+ d*e- 所表達(dá)的表達(dá)式為 _(a+b+c)*d-e _ 。 17語法分析最常用的兩類方法是_自上而

19、下 _和 _自下而上 _分析法。18計(jì)算機(jī)執(zhí)行用高級語言編寫的程序主要有兩種途徑：_解釋 _和_編譯 _。19掃描器是 _詞法分析器 _，它接受輸入的 _源程序 _，對源程序進(jìn)行 _詞法分析 _并識別出一個(gè)個(gè)單詞 符號，其輸出結(jié)果是單詞符號，供語法分析器使用。20自上而下分析法采用 _移進(jìn) _、歸約、錯(cuò)誤處理、 _接受 _等四種操作。21一個(gè) LR 分析器包括兩部分：一個(gè)總控程序和_ 一張分析表 _。22后綴式 abc-/ 所代表的表達(dá)式是 _a/(b-c) _。23局部優(yōu)化是在 _基本塊 _范圍內(nèi)進(jìn)行的一種優(yōu)化。24詞法分析基于 _正則 _文法進(jìn)行，即識別的單詞是該類文法的句子。25語法分析

20、基于 _上下文無關(guān) _文法進(jìn)行， 即識別的是該類文法的句子。 語法分析的有效工具是 _語法樹 _ 26分析句型時(shí)，應(yīng)用算符優(yōu)先分析技術(shù)時(shí)，每步被直接歸約的是_最左素短語 _，而應(yīng)用 LR 分析技術(shù)時(shí)，每步被直接歸約的是 _句柄 _。27語義分析階段所生成的與源程序等價(jià)的中間表示形式可以有_逆波蘭 _、 _四無式表示 _與_三元式表示_等。28 按Chomsky分類法，文法按照規(guī)則定義的形式進(jìn)行分類。 29一個(gè)文法能用有窮多個(gè)規(guī)則描述無窮的符號串集合(語言)是因?yàn)槲姆ㄖ写嬖谟衉遞歸 _定義的規(guī)則。四、簡答題1. 寫一文法，使其語言是偶正整數(shù)的集合，要求：允許0打頭；(2) 不允許0打頭。解：(1

21、)GS=(S,P,D,N,0,1,2,9,P,S)P:S-PD|DP-NP|ND-0|2|4|6|8N-0|1|2|3|4|5|6|7|8|9(2)GS=(S,P,R,D,N,Q ,0,1,2,9,P,S)P:S-PD|P0|DP-NR|NR-QR|QD-2|4|6|8N-1|2|3|4|5|6|7|8|9Q-0|1|2|3|4|5|6|7|8|92. 構(gòu)造正規(guī)式相應(yīng)的 NFA : 101)*101解1(0|1)*101 對應(yīng)的NFA為3. 寫出表達(dá)式(a + b*c)/(a + b) d的逆波蘭表示和三元式序列。逆波蘭表示：abc* + ab + /d 三元式序列： (* , b, c) (

22、+, a,) (+, a, b) (/，) (，d)4. 已知文法GS為：St dABBb| GS 產(chǎn)生的語言是什么？答：GS產(chǎn)生的語言是 L(GS)= danbm| n 1,m0。5. 構(gòu)造正規(guī)式相應(yīng)的 DFA : 1(1010 * | 1(010) * 1) * 0解：1(1010 * | 1(010) * 1) * 0對應(yīng)的 NFA為：6. 已知文法 G(S)Sta| A |(T)T, S|S寫出句子(a , a), a)的規(guī)范歸約過程及每一步的句柄。解：句型歸約規(guī)則句柄(a ， a) ， a)Staa(S ， a) ， a)TtSS(T ， a) ， a)Staa(T ， S)， a)

23、TtT， ST， S(S) ， a)TtSS(T) ， a)StS(T)(T)(S， a)TtSS(T， a)Staa(T， S)TtT， ST， S(T)St(T)(T)S7. 寫一個(gè)文法，使其語言是奇數(shù)集，且每個(gè)奇數(shù)不以 0 開頭。解：文法 G(N)：NtAB|BAtAC|DBt1|3|5|7|9DtB|2|4|6|8Ct 0|DSt (L)|a S|aLtL, S|S(1) 消除左遞歸和回溯；(2)計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW解： (1)St(L)|aSS tS| LtSLLtSL| (2)FOLLOW(S=# , )FOLLOW(S)= # , )FOLLOW(L)= )

24、FOLLOW(L= )FIRST)S) = ( , aFIRST(S) = , a, FIRST(L) = ( , aFIRST(L) = , 9. 已知文法 G(E)EtT|ETTtF|T *FFt(E)|i(1) 給出句型 (T *F i) 的最右推導(dǎo)；給出句型(T *F + i)的短語、素短語。解：(1) 最右推導(dǎo)： E=T-F=(E)-(E T)=(E F)-(E i)=(T i)=(T*F i)(2) 短語： (T*F i) ， T*Fi ， T*F， i素短語： T*F,i10. While a 0 V b v 0 doBeginX : = X+ 1 ；if a 0 then a

25、：= a 1else b : = b+ 1翻譯成四元式序列。解：(1) (j, a, 0,5)(2) (j，3)(3) (jv, b, 0,5)(4) (j，15)(5) (, X, 1, T1)(6) (: =, T1, X)(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)11. 寫出下列表達(dá)式的三地址形式的中間表示。(1) 5+6 *(a + b);(2) for j:=1 to 10 do aj +

26、j:=0答： (1)100: t1:=a+b101: t2:=6*t1102: t3:=5+t2(2)100: j:=1101: if j10 goto NEXT102: i:=j+j103: ai:=012. 設(shè)基本塊 p 由如下語句構(gòu)成：T 0 : =;T 1 :=2*T 0 ;T 2 :=R+r;A:=T l *T 2;B:=A;T 3 :=2*T 0 ;T 4 :=R+r;T 5 :=T 3 *T 4 ;T 6 :=R-r;B:=T 5 *T 6;試給出基本塊p的DAG 。! 1T。解：基本塊p的DAG圖:Rr13. 寫出表達(dá)式（a+b）/（a-b-（a+b*c）的三元序列及四元序列。

27、解：（1 ）三元式: （+, a, b） （，a， b）3（ /，）*, b, c） （+, a,） （，）（2 ）四元式： (+, a, b, T1) (一，a, b, T2)3( / , T1, T2, T3)* , b, c, T4) (+, a, T4, T5) (，T3, T5, T6)14. 寫一個(gè)文法使其語言為偶數(shù)集,且每個(gè)偶數(shù)不以0 開頭。解：文法 G(S)：St AB|B|AOA AD|CBt2|4|6|8Ct1|3|5|7|9|BDt0|C15. 設(shè)文法 G ( S )：StS aF|aF| aFFt*aF|*a(1)消除左遞歸和回溯；(2)構(gòu)造相應(yīng)的 FIRST 和 Fo

28、llow 集合。解：(1)S-aFS| aFSS- + aFS| &F-*aFF- F|&(2)FIRST (S) = a, +FOLLOW( S) = #FIRST ( S ) = +, FOLLOW( S ) = #FIRST ( F) = * FOLLoW ( F) = ( +,#FIRST ( F ) = * , FOLLOW( +,#查。16. 簡要說明語義分析的基本功能。答：語義分析的基本功能包括 : 確定類型、類型檢查、語義處理和某些靜態(tài)語義檢17. 考慮文法 GS:S t (T) | a+S | aT t T,S | S 消除文法的左遞歸及提取公共左因子。解：消除文法 GS 的

29、左遞歸：St (T) I a+S | aSTTt ,ST |提取公共左因子：St(T) I aS St +S |&TtSTTt ,st | 18. 試為表達(dá)式 w+(a+b)*(c+d/(e-10)+8) 寫出相應(yīng)的逆波蘭表示。解： w a b + c d e 10 - / + 8 + * +19. 按照三種基本控制結(jié)構(gòu)文法將下面的語句翻譯成四元式序列：while (AC A B 1) C=C+1;else whi le (A 1和A D,并且關(guān)系運(yùn)算符優(yōu)先級高) ：100 (j,A,C,102)101 (j,_,_,113)102 (j,B,D,104)103 (j,_,_,113)104

30、(j=,A,1,106)105 (j,_,_,108)106 (+, C, 1, C)107 (j,_,_,112)108 (j Ac|aBA-abB-bc寫出 L(GS) 的全部元素。解： S=Ac=abc或 S=aB=abc所以 L(GS)=abc22. 構(gòu)造正規(guī)式 1(0|1)*101 相應(yīng)的 DFA。解：先構(gòu)造 NFA：確定化：重新命名，令 AB為B、AC為C ABY為D得：所以，可得DFA為：23. 文法S-aF|(T)T-T,S|S對(a,(a,a) 和(a,a)f,(a),a)的最左推導(dǎo)。解：對(a,(a,a)的最左推導(dǎo)為：=(a,(T) =(a,(T,S) =(a,(S,S)=

31、(a,(a,S) =(a,(a,a)對(a,a),(a),a)的最左推導(dǎo)為：S=(T) =(T,S) =(S,S) =(T),S)=(T,S),S) =(T,S,S),S) =(S,S,S),S)=(T),S,S),S) =(T,S),S,S),S) =(S,S),S,S),S)=(a,S),S,S),S) =(a,a),S,S),S) =(a,a),A,S),S)=(a,a)f,(T),S) =(a,a)f,(S),S) =(a,a),A,(a),S) =(a,a)f ,(a) ),a)24. 文法：S-MH|aH-LSo| &K-dML| L-eHfM-K|bLM分析表。LL(1) 的。判

32、斷 G 是否為 LL(1) 文法，如果是，構(gòu)造 LL(1)解：各符號的 FIRST集和FOLLOW為：預(yù)測分析表為：由于預(yù)測分析表中無多重入口，所以可判定文法是 25敘述由下列正規(guī)式描述的語言(a) 0(0|1)*0(b) ( & |0)1*)*(c) (0|1)*0(0|1)(0|1)(d) 0*10*10*10*(e) (00|11)*(01|10)(00|11)*(01|10)(00|11)*)*解： (a) 以 0開頭、以 0 結(jié)尾的所有 0和 1的串。(b) 由 0 和 1 組成的串，包括空串。(c) 倒數(shù)第 3個(gè)字符為 0，由 0 和 1組成的串。(d) 含有 3個(gè) 1的所有 0和

33、 1的串。(e) 由偶數(shù)個(gè) 0 和偶數(shù)個(gè) 1 構(gòu)成的所有 0 和 1 的串。26已知文法 GS：S- (L)|aL L,S|S為句子 (a,(a,a) 構(gòu)造最左推導(dǎo)和最右推導(dǎo)。解：句子 (a,(a,a) 的最左推導(dǎo)為：S=(L)=(L,S) =(S,S)=(a,S) =(a,(L)=(a,(L,S) =(a,(S,S)=(a,(a,S)=(a,(a,a)句子(a,(a,a)的最右推導(dǎo)為：S=(L)=(L ,S)=(l,(L)=(L,(L,S)=(L,(L,a)=(L,(S,a)=(L,(a,a)=(S,(a,a)=(a,(a,a)五. 計(jì)算題1構(gòu)造下述文法 GS 的自動機(jī)：S-A0A-A0|S

34、1|0該自動機(jī)是確定的嗎？若不確定，則對它確定化。解：由于該文法的產(chǎn)生式 S-AO, A-A0|S1中沒有字符集 VT的輸入，所以不是確定的自動機(jī)。要將其他確定化，必須先用代入法得到它對應(yīng)的正規(guī)式。把S?A0代入產(chǎn)生式 A?S1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入S-A0有該文法的正規(guī)式：0(0|01)*0 ，所以，改寫該文法為確定的自動機(jī)為：由于狀態(tài)A有3次輸入0的重復(fù)輸入，所以上圖只是 NFA下面將它確定化：下表由子集法將 NFA轉(zhuǎn)換為DFA:由上表可知DFA為：2對下面的文法 G ：E-TEE- +E| T-FTT -T| F- PFF- *F|P-(E

35、)|a|bF(1) 計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST集和FOLLOW集。(2) 證明這個(gè)方法是 LL(1) 的。(3) 構(gòu)造它的預(yù)測分析表。解：(1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST集和FOLLOW!。FIRST集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b;FIRST(E)=+, FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,A;FIRST(T)=FIRST(T) U =(,a,b,A, ;FIRST(F)=FIRST(P)=(,a,b,A;FIRST(F)=FIRST(P)=*, ;FIRST(P)=(,a,b,A

36、;FOLLOW集 合有：FOLLOW(E)=),#;FOLLOW(E)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(E) U FOLLOW(E)=+,),#; 不包含 FOLLOW(T)=FOLLOW(T)=FIRST(E) U FOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T) U FOLLOW(T)=(,a,b,A,+,),#;不包含 FOLLOW(F)=FOLLOW(F)=FIRST(T)UFOLLOW(T)=(,a,b,A,+,),#;FOLLOW(P)=FIRST(F) U FOLLOW(F)=*,(,a,b,A,+,),#;不包含 (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-*F)=*;SELECT(P-(E)=(SELECT(P-a)=aSELECT(P-b)=bSELECT(P-A)=A可見，相同左部產(chǎn)生式的SEL