編譯原理期末考試選擇題匯總

1、精選文檔一、單項選擇題 1、將編譯程序分成若干個“遍”是為了( B ) A提高程序的執(zhí)行效率 B. 使程序的結構更加清楚 C利用有限的機器內存并提高機器的執(zhí)行效率D利用有限的機器內存但降低了機器的執(zhí)行效率2、不行能是目標代碼的是( D ) A匯編指令代碼 B可重定位指令代碼 C確定指令代碼 D中間代碼3、詞法分析器的輸入是( B ) A單詞符號串 B源程序 C語法單位 D目標程序4、編譯程序中的語法分析器接受以 c 為單位的輸入，并產生有關信息供以后各階段使用?？蛇x項有：a、表達式 b、產生式 c、單詞 d、語句 5、高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于 b 分析方法?？蛇x

2、項有：a、自左至右 b、自頂向下 c、自底向上 d、自右向左 6、已知文法GE： ETE E +TE TFT T *FT F（E）id 求：FOLLOW（F）=（1） d ， FIRST（T）=（2） b 可選項有： a、*，+ b、*， c、+,#，） d、*，+，#，） e、#，） f、*，+，#，id 7、中間代碼生成時所遵循的是( C ) A語法規(guī)章 B詞法規(guī)章 C語義規(guī)章 D等價變換規(guī)章8、編譯程序是對( D ) A匯編程序的翻譯 B高級語言程序的解釋執(zhí)行 C機器語言的執(zhí)行 D高級語言的翻譯9、詞法分析應遵循( C ) A語義規(guī)章 B語法規(guī)章 C構詞規(guī)章 D等價變換規(guī)章10、詞法分析

3、器的輸出結果是( C ) A單詞的種別編碼 B單詞在符號表中的位置 C單詞的種別編碼和屬性值 D單詞屬性值11、正規(guī)式M1和M2等價是指( C ) AM1和M2的狀態(tài)數(shù)相等 BM1和M2的有向弧條數(shù)相等 CM1和M2所識別的語言集相等 DM1和M2狀態(tài)數(shù)和有向弧條數(shù)相等12、詞法分析器作為獨立的階段使整個編譯程序結構更加簡潔、明確，因此，( A ) A詞法分析器應作為獨立的一遍 B詞法分析器作為子程序較好 C詞法分析器分解為多個過程，由語法分析器選擇使用 D詞法分析器并不作為一個獨立的階段13、假如L(M1)=L(M2)，則M1與M2( A ) A等價 B都是二義的 C都是無二義的 D它們的狀

4、態(tài)數(shù)相等14、文法G：SxSx|y所識別的語言是( C ) Axyx B(xyx)* cxnyxn(n0) dx*yx*15、文法G描述的語言L(G)是指( A ) A B C D16、有限狀態(tài)自動機能識別( C ) A上下文無關文法 B上下文有關文法 C正規(guī)文法 D短語文法17、編譯過程中掃描器的任務包括 d 。組織源程序的輸入 按詞法規(guī)章分割出單詞，識別出其屬性，并轉換成屬性字的形式輸出 刪除注解 刪除空格及無用字符 行計數(shù)、列計數(shù) 發(fā)覺并定位詞法錯誤 建立符號表可選項有：a、 b、 c、 d、18、正則式的“”讀作（1） b ，“”讀作（2） c ，“*”讀作（3） d ?？蛇x項有：a、

5、并且 b、或者 c、連接 d、閉包19 、 b 這樣一些語言，它們能被確定的有窮自動機識別，但不能用正則表達式表示。可選項有：a、存在 b、不存在 c、無法判定是否存在20、編譯過程中，語法分析的任務是 c 。分析單詞是怎樣構成的 分析單詞是如何構成語句和說明的分析語句和說明是如何構成程序的 分析程序的結構可選項有：a、和 b、 c、 d、 21、語法分析的常用方法有 b 。自頂向下 自底向上 自左向右 自右向左可選項有：a、 b、 c、 d、 22、假如文法G是無二義的，則它的任何句子( A ) A最左推導和最右推導對應的語法樹必定相同 B最左推導和最右推導對應的語法樹可能不同 C最左推導和

6、最右推導必定相同 D可能存在兩個不同的最左推導，但它們對應的語法樹相同23、由文法的開頭符經0步或多步推導產生的文法符號序列是( C ) A短語 B句柄 C句型 D句子24、文法G：EE+T|T TT*P|P P(E)|i則句型P+T+i的句柄為( B ) AP+T BP CP+T+i Di25、文法G：Sb|(T) TTS|S則FIRSTVT(T)=( C ) A b，( B b，) C b，(， D b，）， 26、產生正規(guī)語言的文法為( D ) A0型 B1型 C2型 D3型27、任何算符優(yōu)先文法( D )優(yōu)先函數(shù)。 A有一個 B沒有 C有若干個 D可能有若干個28、接受自上而下分析，必

7、需( C ) A消退左遞歸 B消退右遞歸 C消退回溯 D提取公共左因子29、素短語是指 D 的短語。至少包含一個符號 至少包含一個終結符號 至少包含一個非終結符號 除自身外不再包含其他終結符號 除自身外不再包含其他非終結符號 除自身外不再包含其他短語 除自身外不再包含其他素短語可選項有：A、 B、 C、 D、30、給定文法AbAcc，下面的符號串中，為該文法句子的是 A 。cc bcbc bcbcc bccbcc bbbcc可選項有：A、 B、 C、 D、 31、已知文法 GS： SeTRT TDR RdR Dabd則FOLLOW（T）= D ?？蛇x項有：A、d B、a,b C、a,b,# D

8、、# E、d,#32、正則式中的 “*”讀作 D ?？蛇x項有：A、并且 B、或者 C、連接 D、閉包33、在規(guī)范歸約中，用( B )來刻畫可歸約串。 A直接短語 B句柄 C最左素短語 D素短語34、有文法G：EE*T|T TT+i|i句子1+2*8+6按該文法G歸約，其值為( B ) A23 B42 C30 D1735、假如文法是無二義的，那么規(guī)范歸約是指( B ) A最左推導的逆過程 B最右推導的逆過程 C規(guī)范推導 D最左歸約的逆過程36、文法G:SS+T|T TT*P|P P(S)|i句型P+T+i的短語有( B ) Ai,P+T BP,P+T,i,P+T+i CP+T+i DP，P+T，

9、i37、高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于 b 分析方法?？蛇x項有：A、自左至右 B、自頂向下 C、自底向上 D、自右向左 38、一般程序設計語言的定義都涉及 A 三個方面。語法 語義 語用 程序基本符號的確定可選項有：A、 B、 C、 D、39、編譯過程中，語法分析器的任務是 B 。分析單詞是怎樣構成的 分析單詞串是如何構成語句和說明的 分析語句和說明是如何構成程序的 分析程序的結構可選項有：A、 B、 C、 D、40、編譯程序生成的目標程序 B 是機器語言的程序。可選項有：A、肯定 B、不肯定 C、無法推斷 D、肯定不 一、單項選擇題（將正確答案的字母填入括號，每題1

10、.5分，共30分）1、一般程序設計語言的定義都涉及到（ 1.2.3）3個方面。（1）語法 （2）語義 （3）語用 （4）程序基本符號的確定2、程序語言一般分為（ 1 ）和（ 2 ）。（1）高級語言；（2）低級語言；（3）專用程序語言；（4）通用程序語言3、面對機器語言指的是（ B ）。A用于解決機器硬件設計問題的語言B特定計算機系統(tǒng)所固有的語言C各種計算機系統(tǒng)都通用的語言D只能在一臺計算機上使用的語言4面對機器語言的特點是（ D ）。A程序的執(zhí)行效率低，編制效率低，可讀性差B程序的執(zhí)行效率高，編制效率高，可讀性強C程序的執(zhí)行效率低，編制效率高，可讀性強D程序的執(zhí)行效率高，編制效率低，可讀性差5

11、、程序設計語言常見的數(shù)據(jù)類型有：1.2.3.4（1）數(shù)值型數(shù)據(jù) （2）規(guī)律數(shù)據(jù) （3）字符數(shù)據(jù) （4）指針類型6、下列程序設計語言中是應用式語言的是：BA、PASCAL B、LISP C、VB D、PROLOG7、任何語法結構都可以用（ C ）來表示。A、語法樹 B、樹 C、抽象語法樹 D、二義文法樹8、字母表是符號的有窮集合，由（ C ）組成詞和句子。A、字符串 B、字符 C、符號 D、語言9、下列符號是終結符的是（ A）。A、c B、A C、S D、10、語法樹用（ C ）關系說明白句子中以操作符為核心的操作挨次，同時也說明白每一個操作符的操作對象。A、上下 B、先后 C、層次 D、關聯(lián)1

12、1、循環(huán)語句的語法樹為（ D ）A、 B、 C、 D、12、表達式中間代碼的生成可接受（ B ）。A、三地址代碼 B、四元式 C、三元式 D、間接三元式13、下列文法中，賦值語句的文法是（ C ）。A、 B、 C、 D、EE op E 14、詞法分析的任務是（ A ）A、識別單詞 B、分析句子的含義 C、識別句子 D、生成目標代碼15、常用的中間代碼形式中不含（ D ）A、三元式 B、四元式 C、 逆波蘭式 D、語法樹16、代碼優(yōu)化的目的是（ C ）A、節(jié)省時間 B、節(jié)省空間 C、節(jié)省時間和空間 D、把編譯程序進行等價轉換17、代碼生成階段的主要任務是（ C ）A、把高級語言翻譯成匯編語言 B

13、、把高級語言翻譯成機器語言 C、把中間代碼變換成依靠具體機器的目標代碼 D、把匯編語言翻譯成機器語言18、詞法分析器的輸入是（ B ）A、單詞符號串 B、源程序 C、語法單位 D、目標程序19、中間代碼的生成所遵循的是（ C ）A、語法規(guī)章 B、詞法規(guī)章 C、語義規(guī)章 D、等價變換規(guī)章20、編譯程序是對（ D ）A、匯編程序的翻譯 B、高級語言程序的解釋并執(zhí)行 C、機器語言的執(zhí)行 D、高級語言的翻譯21、語法分析應遵循（ C ）A、語義規(guī)章 B、語法規(guī)章 C、構詞規(guī)章 D、等價變換規(guī)章 22、編譯程序各階段的工作都涉及到（ B ）A、語法分析 B、表格管理、出錯處理 C、語義分析 D、詞法分析

14、23、編譯程序工作時，通常有（ 1.2.3.4 ）階段。（1）詞法分析 （2）語法分析 （3）中間代碼生成 （4）語義檢查 （5）目標代碼生成24、由文法的開頭符經0步或多步推導產生的文法符號序列是 C 。A、短語 B、句柄 C、句型D、句子25、產生正規(guī)語言的文法為 D 。A、0型 B、1型 C、 2型D、3型26、對無二義性文法來說，一棵語法樹往往代表了 D 。（1） 多種推導過程（2） 多種最左推導過程（3）一種最左推導過程（4）僅一種推導過程（5）一種最左推導過程A、 B、（1）（3）（5） C、 D27、假如文法G存在一個句子，滿足下列條件 之一時，則稱該文法是二義文法。BCDa.

15、該句子的最左推導與最右推導相同 b. 該句子有兩個不同的最左推導c. 該句子有兩棵不同的最右推導 d. 該句子有兩棵不同的語法樹 e.該句子的語法樹只有一個28、優(yōu)化可生成（ D ）的目標代碼。A、運行時間較短 B、占用存儲空間較小 C、運行時間短且占用內存空間大 D、運行時間短且存儲空間小29、構造編譯程序應把握（ D ）A、源程序 B、目標程序 C、編譯方法 D、以上三項都是30、賦值語句x=a+b*c-d的逆波蘭式為（ B）A、xab+c*d-= B、xabc*+d-= C、xabcd*+-= D、x=abc*+d-31、詞法分析器的輸出結果是（ C ）A、單詞的種別編碼 B、單詞在符號

16、表中的位置 C、單詞的種別編碼和自身值 D、單詞自身值編譯原理期末試題（一）一、是非題（請在括號內，正確的劃，錯誤的劃）（每個2分，共20分）1編譯程序是對高級語言程序的解釋執(zhí)行。( )2一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。()3一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應。 ( )4語法分析時必需先消退文法中的左遞歸 。 ()5LR分析法在自左至右掃描輸入串時就能發(fā)覺錯誤，但不能精確地指出出錯地點。 ()6逆波蘭表示法表示表達式時無須使用括號。 ( )7靜態(tài)數(shù)組的存儲空間可以在編譯時確定。 ()8進行代碼優(yōu)化時應著重考慮循環(huán)的代碼優(yōu)化，這對提高目標代碼的效率將起更大作用。 ()9

17、兩個正規(guī)集相等的必要條件是他們對應的正規(guī)式等價。 ( )10一個語義子程序描述了一個文法所對應的翻譯工作。 ()二、選擇題(請在前括號內選擇最精確的一項作為答案劃一個勾，多劃按錯論)(每個4分，共40分)1詞法分析器的輸出結果是_。A( ) 單詞的種別編碼 B( ) 單詞在符號表中的位置 C( ) 單詞的種別編碼和自身值 D( ) 單詞自身值2 正規(guī)式 M 1 和 M 2 等價是指_。 A( ) M1和M2的狀態(tài)數(shù)相等 B( ) M1和M2的有向邊條數(shù)相等C( ) M1和M2所識別的語言集相等 D( ) M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等 3 文法G：SxSx|y所識別的語言是_。A( ) xy

18、x B( ) (xyx)* C( ) xnyxn(n0) D( ) x*yx* 4假如文法G是無二義的，則它的任何句子_。A( )最左推導和最右推導對應的語法樹必定相同 B( ) 最左推導和最右推導對應的語法樹可能不同 C( ) 最左推導和最右推導必定相同 D( )可能存在兩個不同的最左推導，但它們對應的語法樹相同 5構造編譯程序應把握_。A( )源程序B( ) 目標語言 C( ) 編譯方法 D( ) 以上三項都是 6四元式之間的聯(lián)系是通過_實現(xiàn)的。 A( ) 指示器 B( ) 臨時變量 C( ) 符號表 D( ) 程序變量 7表達式(AB)(CD)的逆波蘭表示為_。A. ( ) ABCD B

19、( ) ABCD C( ) ABCD D( ) ABCD 8. 優(yōu)化可生成_的目標代碼。A( ) 運行時間較短 B( ) 占用存儲空間較小C( ) 運行時間短但占用內存空間大 D( ) 運行時間短且占用存儲空間小9下列_優(yōu)化方法不是針對循環(huán)優(yōu)化進行的。A. ( ) 強度減弱 B( ) 刪除歸納變量 C( ) 刪除多余運算 D( ) 代碼外提10編譯程序使用_區(qū)分標識符的作用域。 A. ( ) 說明標識符的過程或函數(shù)名B( ) 說明標識符的過程或函數(shù)的靜態(tài)層次C( ) 說明標識符的過程或函數(shù)的動態(tài)層次 D. ( ) 標識符的行號編譯原理期末試題（二）1、描述由正規(guī)式b*(abb*)*(a| e)

20、定義的語言，并畫出接受該語言的最簡DFA。2、證明文法E E + id | id是SLR(1)文法。5、下面C語言程序經非優(yōu)化編譯后，若運行時輸入2，則結果是area=12.566360, addr=-1073743076經優(yōu)化編譯后，若運行時輸入2，則結果是area=12.566360, addr=-1073743068請解釋為什么輸出結果有區(qū)分。main() float s, pi, r; pi=3.14159; scanf(%f, &r); printf(area=%f, addr=%dn, s=pi*r*r, &r);6、描述由正規(guī)式b*a(bb*a) *b*定義的語言，并畫出接受該語

21、言的最簡DFA。7、下面的文法產生代表正二進制數(shù)的0和1的串集：B B 0 | B 1 | 1下面的翻譯方案計算這種正二進制數(shù)的十進制值：B B1 0B.val := B1.val 2 | B1 1B.val := B1.val 2 +1| 1 B.val := 1 請消退該基礎文法的左遞歸，再重寫一個翻譯方案，它仍舊計算這種正二進制數(shù)的十進制值。8、在C語言中，假如變量i和j都是long類型，請寫出表達式&i和表達式&i-&j的類型表達式。為掛念你回答問題，下面給出一個程序作為提示，它運行時輸出1。main() long i, j;printf(“%dn”, &i-&j);9、一個C語言的函

22、數(shù)如下：func(i) long i; long j;j = i 1;func(j);下面左右兩邊的匯編代碼是兩個不同版本GCC編譯器為該函數(shù)產生的代碼。左邊的代碼在調用func之前將參數(shù)壓棧，調用結束后將參數(shù)退棧。右邊代碼對參數(shù)傳遞的處理方式沒有實質區(qū)分。請敘述右邊代碼對參數(shù)傳遞的處理方式并推想它帶來的優(yōu)點。func:|func:pushl%ebp|pushl%ebpmovl%esp, %ebp|movl%esp, %ebpsubl$4, %esp|subl$8, %espmovl8(%ebp), %edx|movl8(%ebp), %eaxdecl%edx|decl%eaxmovl%edx

23、, -4(%ebp)|movl%eax, -4(%ebp)movl-4(%ebp), %eax|movl-4(%ebp), %eaxpushl%eax|movl%eax, (%esp)callfunc|callfuncaddl$4, %esp|leaveleave|retret|編譯原理試卷八答案start1abb21、由正規(guī)式b*(abb*)*(a| e)定義的語言是字母表a, b上不含子串aa的全部串的集合。最簡DFA如下：2、先給出接受該文法活前綴的DFA如下：E EE E + idE idI0E EE E+ idI1E idI2Eid+E E +idI3E E + idI4idI0和I

24、3都只有移進項目，確定不會引起沖突；I2和I4都無移進項目并僅含一個歸約項目，也確定不會引起沖突；在I1中，E的后繼符號只有$，同第2個項目的展望符號“+”不一樣，因此I1也確定不會引起沖突。由此可以斷定該文法是SLR(1)的。3、語法制導定義如下。S id := E S.type := if (id.type = bool and E.type = bool) or (id.type = int and E.type = int)then type_ok else type_error E E1 and E2 E.type := if E1.type = bool and E2.type =

25、 bool then bool else type_error E E1 + E2 E.type := if E1.type = int and E2.type = int then int else type_error E E1 = E2 E.type := if E1.type = int and E2.type = int then bool else type_error E id E.type := lookup(id.entry) 4、對于函數(shù)f1，局部變量x聲明的作用域是整個函數(shù)體，導致在函數(shù)體中不行能訪問形式參數(shù)x。由于這是一個合法的C語言函數(shù)，因此編譯器給出警告錯誤。對于函

26、數(shù)f2，由于局部變量x的作用域只是函數(shù)體的一部分，不會消滅上述問題，因而編譯器不報錯。5、使用非優(yōu)化編譯時，變量s, pi, r在局部數(shù)據(jù)區(qū)都安排4個字節(jié)的空間。使用優(yōu)化編譯時，由于復寫傳播，pi*r*r 變成3.14159*r*r，pi=3.14159成為無用賦值而刪去，函數(shù)中不再有pi的引用，因此不必為pi安排空間。類似地，s=3.14159*r*r也是一個無用賦值（表達式要計算，但賦值是無用的），也不必為s安排空間。這樣，和非優(yōu)化狀況相比，局部數(shù)據(jù)區(qū)少了8個字節(jié)， 因此r的地址向高地址方向移動了8個字節(jié)。6、正規(guī)式b*a(bb*a) *b*體現(xiàn)的特點是，每個a的左邊都有若干b，除非a是第

27、一個字母。該正規(guī)式定義的語言是：至少含一個a，但不含子串aa的全部a和b的串集。最簡DFA如下：start2abb10ab7、消退左遞歸后的文法：B 1 BB 0 B | 1 B | e相應的翻譯方案如下：B 1 B.i := 1 BB.val := B.valB 0 B1.i := B.i 2 B1 B.val := B1.val| 1 B1.i := B.i 2 +1 B1 B.val := B1.val| e B.val := B.i8、表達式&i的類型表達式是pointer(long)，表達式&i-&j的類型表達式是long。依據(jù)C語言的規(guī)定，指向同一個類型的兩個指針可以相加減，它們值

28、的差是它們之間的元素個數(shù)。9、左邊的編譯器版本：一般只為局部變量安排空間。調用函數(shù)前，用若干次pushl指令將參數(shù)壓棧，返回后用addl $n, %esp一次將全部參數(shù)退棧（常數(shù)n依據(jù)調用前做了多少次pushl來打算）。右邊的編譯器版本：除了為局部變量安排空間外，同時還為本函數(shù)中消滅的函數(shù)調用的參數(shù)安排空間，并且參數(shù)所用空間靠近棧頂。調用函數(shù)前，用movl指令將參數(shù)移入棧頂，調用結束后無需參數(shù)退棧指令。優(yōu)點是每次函數(shù)調用結束后不需要執(zhí)行addl $n, %esp指令，另外增加優(yōu)化的可能性。編譯原理期末試題（三）1、 從優(yōu)化的范圍的角度，優(yōu)化可以分哪兩類？對循環(huán)的優(yōu)化可以有哪三種？ 答：從優(yōu)化的

29、范圍的角度，優(yōu)化可以分為局部優(yōu)化和全局優(yōu)化兩類；對循環(huán)的優(yōu)化有三種：循環(huán)不變表達式外提、歸納變量刪除與計算強度削減。2、寫出表達式a=b*c+b*d對應的逆波蘭式、四元式序列和三元式序列。 答：逆波蘭式： abc*bd*+:= 四元式序列：三元式序列: OP ARG1 ARG2(1) (*， b， c， t1) (1) (* b， c )(2) (*， b， d， t2) (2) (* b， d )(3) (+， t1， t2，t3) (3) (+ (1)， (2)(4) (:=， t3， /， a)(4) (:= (3)， a)3、對于文法G(S): SbM(TMabL)答：1） 2） 短語

30、: Ma)， (Ma)， b(Ma)b直接短語: Ma) 句柄: Ma)三、 設有字母表a，b上的正規(guī)式R=(ab|a)*。 解：（1）0123baa-+（2）將（1）所得的非確定有限自動機確定化ab-01131221+3ab-+013123+12312313+13123012aaba-+（3）對（2）得到的DFA化簡，合并狀態(tài)0和2 為狀態(tài)2：12aab-+（4）令狀態(tài)1和2分別對應非終結符B和AG: AaB|a|； BaB|bA|a|b|；可化簡為：G: AaB|；BaB|bA|四、 設將文法G改寫成等價的LL(1)文法，并構造猜測分析表。 G：SS*aT|aT|*aT； T+aT|+a

31、解：消退左遞歸后的文法G: SaTS|*aTSS*aTS|T+aT|+a 提取左公因子得文法G:SaTS|*aTSS*aTS|T+aTTT| Select(SaTS)=aSelect(S*aTS)=*Select(SaTS)Select(S*aTS)=Select(S*aTS)=*Select(S)=Follow(s)=#Select(S*aTS)Select(S)= Select(T+aT)=+Select(TT)=First(T) =+Select(T )=Follow(T)=*,#Select(TT)Select(T)= 所以該文法是LL(1)文法。猜測分析表： *+a#S*aTSaTS

32、S*aTST+aTT T 6設文法G 為： SA；ABA|；BaB|b解：（1）拓廣文法G：(0) SS (1) SA (2) ABA(3) A(4) BaB (5) Bb ； FIRST(A) = , a, b；FIRST(B) = a, b構造的DFA 如下:項目集規(guī)范族看出，不存在沖突動作。該文法是LR(1)文法。（2） LR(1)分析表如下： (3)輸入串abab 的分析過程為： 簡答題 3、設有文法GS: SS(S)S|，該文法是否為二義文法？說明理由。 答：是二義的，由于對于（）（）可以構造兩棵不同的語法樹。 S S S ( S ) S S ( S ) S S ( S ) S S

33、( S ) S 五、 給定文法GS： SaA|bQ； AaA|bB|b；BbD|aQ ；QaQ|bD|b；DbB|aA ；EaB|bF FbD|aE|b構造相應的最小的DFA 。 解：先構造其NFA： 用子集法將NFA確定化： abSAQAABZQQDZBZQDDZABDABBQD 將S、A、Q、BZ、DZ、D、B重新命名，分別用0、1、2、3、4、5、6表示。由于3、4中含有z，所以它們?yōu)榻K態(tài)。ab012113224325416516625 令P0（0,1,2,5,6,3,4）用b進行分割： P1（0,5, 6,1,2,3,4）再用b進行分割： P2（0,5, 6,1,2,3,4）再用a、b

34、 進行分割，仍不變。 再令為A，1，2為B，3，4為C，5，6為D。 最小化為右上圖。六、 對文法G(S)：S a | | (T)；T T，S | S 答：(1) a(),#a(=,#=(2) 是算符優(yōu)先文法，由于任何兩個終結符之間至多只有一種優(yōu)先關系。（2分）(3) 給出輸入串(a,a)#的算符優(yōu)先分析過程。步驟 棧當前輸入字符剩余輸入串動作1#(a,a#( 移進2#(a,a)#(, 歸約4#(N,a)#(, 移進5#(N,a)#,) 歸約7#(N,N）#,) 歸約8#(N)#(=) 移進9#(N)#)# 歸約10#N#接受編譯原理期末試題（四）二、構造下列正規(guī)式相應的DFA（用狀態(tài)轉換圖表

35、示）（15）（1） 1（0 | 1）*10,1（2） 0*10*10*10*1（3） letter（letter | digit）*31021（1）0051（2）104130211letter(3)2letter1digit三、給出下面語言的相應文法：（15）L1=an bn | n1 L2=anbm+nam | n1，m0 G1： SAB AaAb | ab BbBa | G1： AaAb |ab 四、對下面的文法G： Sa | b | （T）TT，S | S(1) 消去文法的左遞歸，得到等價的文法G2；(2) 推斷文法G2是否LL（1）文法，假如是，給出其猜測分析表。（15）G2： Sa

36、| b | （T） T ST T，S T | G2是LL（1）文法。ab（），#SSa Sb S（T）TT STT STT STTT T，S T 五、設有文法GA：ABCc | gDBBbCDE |CDaB | caDdD |EgAf | c(1) 計算該文法的每一個非終結符的FIRST集和FOLLOW集；(2) 試推斷該文法是否為LL（1）文法。（15）FIRSTFOLLOWABCDEA,b,c,d,gbA,c,dDC,gA,c,dC,d,gA,b,c,g是LL（1）文法。六、對表達式文法G：E E+T | TT T*F | FF (E) | I（1）造各非終結符的FIRSTVT和LASTV

37、T集合；（2）構造文法的算符優(yōu)先關系表。（15）FIRSTVTLASTVTETF*，+，（，i*，（，i（，i*，+，），i*，），i），i 算符優(yōu)先關系表+*I（）#+*I（）#=七、有定義二進制整數(shù)的文法如下：L LB | BB 0 | 1構造一個翻譯模式，計算該二進制數(shù)的值（十進制的值）。（15）引入L、B的綜合屬性val，翻譯模式為： S L print(L.val)L L1B L.val= L1.val*2+B.valL B L.val= B.valB 0 B.val=0B 1 B.val=1編譯原理期末試題（五）一、單項選擇題(共10小題，每小題2分，共20分)1語言是A句子的集合

38、 B產生式的集合 C符號串的集合 D句型的集合2編譯程序前三個階段完成的工作是A詞法分析、語法分析和代碼優(yōu)化 B代碼生成、代碼優(yōu)化和詞法分析C詞法分析、語法分析、語義分析和中間代碼生成 D詞法分析、語法分析和代碼優(yōu)化3一個句型中稱為句柄的是該句型的最左 A非終結符號 B短語 C句子 D直接短語4下推自動機識別的語言是A0型語言 B1型語言 C2型語言 D3型語言5掃描器所完成的任務是從字符串形式的源程序中識別出一個個具有獨立含義的最小語法單位即 A 字符 B單詞 C句子 D句型6對應Chomsky四種文法的四種語言之間的關系是 AL0L1L2L3 BL3L2L1L0 CL3=L2L1L0 DL

39、0L1L2=L37詞法分析的任務是 A識別單詞 B分析句子的含義 C識別句子 D生成目標代碼8常用的中間代碼形式不含 A三元式 B四元式 C逆波蘭式 D語法樹9 代碼優(yōu)化的目的是 A節(jié)省時間 B節(jié)省空間 C節(jié)省時間和空間 D把編譯程序進行等價交換10代碼生成階段的主要任務是 A把高級語言翻譯成匯編語言 B把高級語言翻譯成機器語言 C把中間代碼變換成依靠具體機器的目標代碼 D把匯編語言翻譯成機器語言四、簡答題(共4小題，每小題5分，共20分)1編譯程序和高級語言有什么區(qū)分? 用匯編語言或高級語言編寫的程序，必需先送入計算機，經過轉換成用機器語言表示的目標程序（這個過程即編譯），才能由計算機執(zhí)行。執(zhí)行轉換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉換過的叫目標程序，也就是機器語言。 編譯程序的工作狀況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫的程序，依據(jù)一一對應的關系，轉換成用機器語言表示的程序。解釋型編譯程序將高級語言程序的一個語句，先解釋成為一組機器語言的指令，然后馬上執(zhí)行，執(zhí)行完了，取下一