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

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

2、、自左至右 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、詞法分析應(yīng)遵循( C ) A語義規(guī)則 B語法規(guī)則 C構(gòu)詞規(guī)則 D等價變換規(guī)則10、詞法分析器的輸出

3、結(jié)果是( 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、詞法分析器作為獨立的階段使整個編譯程序結(jié)構(gòu)更加簡潔、明確，因此，( A ) A詞法分析器應(yīng)作為獨立的一遍 B詞法分析器作為子程序較好 C詞法分析器分解為多個過程，由語法分析器選擇使用 D詞法分析器并不作為一個獨立的階段13、如果L(M1)=L(M2)，則M1與M2( A ) A等價 B都是二義的 C都是無二義的 D它們的狀態(tài)數(shù)相等

4、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上下文無關(guān)文法 B上下文有關(guān)文法 C正規(guī)文法 D短語文法17、編譯過程中掃描器的任務(wù)包括 d 。組織源程序的輸入 按詞法規(guī)則分割出單詞，識別出其屬性，并轉(zhuǎn)換成屬性字的形式輸出 刪除注解 刪除空格及無用字符 行計數(shù)、列計數(shù) 發(fā)現(xiàn)并定位詞法錯誤 建立符號表可選項有：a、 b、 c、 d、18、正則式的“”讀作（1） b ，“·”讀作（2） c ，“*”讀作（3） d ?？蛇x項有：

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

6、導(dǎo)和最右推導(dǎo)必定相同 D可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同23、由文法的開始符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號序列是( 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、產(chǎn)生正規(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 的短語。至少包含一個符號 至少包含一個終結(jié)符號 至少包含一個非終結(jié)符號 除自身外不再包含其他終結(jié)符號 除自身外不再包含其他非終結(jié)符號 除自身外不再包含其他短語 除自身外不再包含其他素短語可選項有：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,#

8、 D、# 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最左推導(dǎo)的逆過程 B最右推導(dǎo)的逆過程 C規(guī)范推導(dǎo) 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+

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

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

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

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

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

14、4 ）階段。（1）詞法分析 （2）語法分析 （3）中間代碼生成 （4）語義檢查 （5）目標(biāo)代碼生成24、由文法的開始符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號序列是 C 。A、短語 B、句柄 C、句型D、句子25、產(chǎn)生正規(guī)語言的文法為 D 。A、0型 B、1型 C、 2型D、3型26、對無二義性文法來說，一棵語法樹往往代表了 D 。（1） 多種推導(dǎo)過程（2） 多種最左推導(dǎo)過程（3）一種最左推導(dǎo)過程（4）僅一種推導(dǎo)過程（5）一種最左推導(dǎo)過程A、 B、（1）（3）（5） C、 D27、如果文法G存在一個句子，滿足下列條件 之一時，則稱該文法是二義文法。BCDa. 該句子的最左推導(dǎo)與最右推導(dǎo)相同 b. 該句子

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

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

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

18、向邊條數(shù)相等C( ) M1和M2所識別的語言集相等 D( ) M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等 3 文法G：SxSx|y所識別的語言是_。A( ) xyx  B( ) (xyx)* C( ) xnyxn(n0)     D( ) x*yx* 4如果文法G是無二義的，則它的任何句子_。A( )最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同 B( ) 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同 C( ) 最左推導(dǎo)和最右推導(dǎo)必定相同   D( )可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同 5構(gòu)造編譯程序應(yīng)掌握_。A( )源程序  &#

19、160;B( ) 目標(biāo)語言       C( ) 編譯方法      D( ) 以上三項都是 6四元式之間的聯(lián)系是通過_實現(xiàn)的。 A( ) 指示器         B( ) 臨時變量 C( ) 符號表             D( ) 程序變量 7表達式(AB)(CD)的逆波蘭表示為_。A. ( ) ABCD B( ) ABCD

20、        C( ) ABCD         D( ) ABCD 8. 優(yōu)化可生成_的目標(biāo)代碼。A( ) 運行時間較短               B( ) 占用存儲空間較小C( ) 運行時間短但占用內(nèi)存空間大 D( ) 運行時間短且占用存儲空間小9下列_優(yōu)化方法不是針對循環(huán)優(yōu)化進行的。A. ( ) 強度削弱 &

21、#160;   B( ) 刪除歸納變量     C( ) 刪除多余運算   D( ) 代碼外提10編譯程序使用_區(qū)別標(biāo)識符的作用域。 A. ( ) 說明標(biāo)識符的過程或函數(shù)名B( ) 說明標(biāo)識符的過程或函數(shù)的靜態(tài)層次C( ) 說明標(biāo)識符的過程或函數(shù)的動態(tài)層次 D. ( ) 標(biāo)識符的行號編譯原理期末試題（二）1、描述由正規(guī)式b*(abb*)*(a| e)定義的語言，并畫出接受該語言的最簡DFA。2、證明文法E ® E + id | id是SLR(1)文法。5、下面C語言程序經(jīng)非優(yōu)化編譯后，若運行時輸入2，則結(jié)果是are

22、a=12.566360, addr=-1073743076經(jīng)優(yōu)化編譯后，若運行時輸入2，則結(jié)果是area=12.566360, addr=-1073743068請解釋為什么輸出結(jié)果有區(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*定義的語言，并畫出接受該語言的最簡DFA。7、下面的文法產(chǎn)生代表正二進制數(shù)的0和1的串集：B ® B 0 | B 1

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

24、下：func(i) long i; long j;j = i 1;func(j);下面左右兩邊的匯編代碼是兩個不同版本GCC編譯器為該函數(shù)產(chǎn)生的代碼。左邊的代碼在調(diào)用func之前將參數(shù)壓棧，調(diào)用結(jié)束后將參數(shù)退棧。右邊代碼對參數(shù)傳遞的處理方式?jīng)]有實質(zhì)區(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,

25、-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上不含子串a(chǎn)a的所有串的集合。最簡DFA如下：2、先給出接受該文法活前綴的DFA如下：E¢ ®·EE ®·E + idE ®·idI0E¢

26、 ® E·E ® E·+ idI1E ® id·I2Eid+E ® E +·idI3E ® E + id·I4idI0和I3都只有移進項目，肯定不會引起沖突；I2和I4都無移進項目并僅含一個歸約項目，也肯定不會引起沖突；在I1中，E¢的后繼符號只有$，同第2個項目的展望符號“+”不一樣，因此I1也肯定不會引起沖突。由此可以斷定該文法是SLR(1)的。3、語法制導(dǎo)定義如下。S ® id := E S.type := if (id.type = bool and E.type =

27、 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 = 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

28、.type = int then bool else type_error E ® id E.type := lookup(id.entry) 4、對于函數(shù)f1，局部變量x聲明的作用域是整個函數(shù)體，導(dǎo)致在函數(shù)體中不可能訪問形式參數(shù)x。由于這是一個合法的C語言函數(shù)，因此編譯器給出警告錯誤。對于函數(shù)f2，由于局部變量x的作用域只是函數(shù)體的一部分，不會出現(xiàn)上述問題，因而編譯器不報錯。5、使用非優(yōu)化編譯時，變量s, pi, r在局部數(shù)據(jù)區(qū)都分配4個字節(jié)的空間。使用優(yōu)化編譯時，由于復(fù)寫傳播，pi*r*r 變成3.14159*r*r，pi=3.14159成為無用賦值而刪去，函數(shù)中不再有pi的引用

29、，因此不必為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是第一個字母。該正規(guī)式定義的語言是：至少含一個a，但不含子串a(chǎn)a的所有a和b的串集。最簡DFA如下：start2abb10ab7、消除左遞歸后的文法：B ® 1 B¢B¢ ® 0 B¢ | 1 B¢ | e相應(yīng)的翻譯方案如下：B ®

30、; 1 B¢.i := 1 B¢B.val := B¢.valB¢ ® 0 B¢1.i := B¢.i ´ 2 B¢1 B¢.val := B¢1.val| 1 B¢1.i := B¢.i ´ 2 +1 B¢1 B¢.val := B¢1.val| e B¢.val := B¢.i8、表達式&i的類型表達式是pointer(long)，表達式&i-&j的類型表達式是long。按照C語

31、言的規(guī)定，指向同一個類型的兩個指針可以相加減，它們值的差是它們之間的元素個數(shù)。9、左邊的編譯器版本：一般只為局部變量分配空間。調(diào)用函數(shù)前，用若干次pushl指令將參數(shù)壓棧，返回后用addl $n, %esp一次將所有參數(shù)退棧（常數(shù)n根據(jù)調(diào)用前做了多少次pushl來決定）。右邊的編譯器版本：除了為局部變量分配空間外，同時還為本函數(shù)中出現(xiàn)的函數(shù)調(diào)用的參數(shù)分配空間，并且參數(shù)所用空間靠近棧頂。調(diào)用函數(shù)前，用movl指令將參數(shù)移入棧頂，調(diào)用結(jié)束后無需參數(shù)退棧指令。優(yōu)點是每次函數(shù)調(diào)用結(jié)束后不需要執(zhí)行addl $n, %esp指令，另外增加優(yōu)化的可能性。編譯原理期末試題（三）1、 從優(yōu)化的范圍的角度，優(yōu)化可

32、以分哪兩類？對循環(huán)的優(yōu)化可以有哪三種？ 答：從優(yōu)化的范圍的角度，優(yōu)化可以分為局部優(yōu)化和全局優(yōu)化兩類；對循環(huán)的優(yōu)化有三種：循環(huán)不變表達式外提、歸納變量刪除與計算強度削減。2、寫出表達式a=b*c+b*d對應(yīng)的逆波蘭式、四元式序列和三元式序列。 答：逆波蘭式： 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、對于文法

33、G(S): SbM(TMabL)答：1） 2） 短語: Ma)， (Ma)， b(Ma)b直接短語: Ma) 句柄: Ma)三、 設(shè)有字母表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分別對應(yīng)非終結(jié)符B和AG: AaB|a|； BaB|bA|a|b|；可化簡為：G: AaB|；BaB|bA|四、 設(shè)將文法G改寫成等價的LL(1)文法，并構(gòu)造預(yù)測分析表

34、。 G：SS*aT|aT|*aT； T+aT|+a 解：消除左遞歸后的文法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)= 所以該文法是L

35、L(1)文法。預(yù)測分析表： *+a#S*aTSaTSS*aTST+aTT T 6設(shè)文法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構(gòu)造的DFA 如下:項目集規(guī)范族看出，不存在沖突動作。該文法是LR(1)文法。（2） LR(1)分析表如下： (3)輸入串a(chǎn)bab 的分析過程為： 簡答題 3、設(shè)有文法GS: SS(S)S|，該文法是否為二義文法？說明理由。 答：是二義的，因為對于（）（）可以構(gòu)造兩棵不同的語法樹。 S S S ( S

36、) S S ( S ) S S ( S ) S S ( S ) S 五、 給定文法GS： SaA|bQ； AaA|bB|b；BbD|aQ ；QaQ|bD|b；DbB|aA ；EaB|bF FbD|aE|b構(gòu)造相應(yīng)的最小的DFA 。 解：先構(gòu)造其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進行分

37、割： P2（0,5, 6,1,2,3,4）再用a、b 進行分割，仍不變。 再令為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)先文法，因為任何兩個終結(jié)符之間至多只有一種優(yōu)先關(guān)系。（2分）(3) 給出輸入串(a,a)#的算符優(yōu)先分析過程。步驟 棧當(dāng)前輸入字符剩余輸入串動作1#(a,a#<( 移進2

38、#(a,a)#(<a 移進3#(a,a)#a>, 歸約4#(N,a)#(<, 移進5#(N,a)#,<a 移進6#(N,a)#a>) 歸約7#(N,N）#,>) 歸約8#(N)#(=) 移進9#(N)# )># 歸約10#N#接受編譯原理期末試題（四）二、構(gòu)造下列正規(guī)式相應(yīng)的DFA（用狀態(tài)轉(zhuǎn)換圖表示）（15）（1） 1（0 | 1）*10,1（2） 0*10*10*10*1（3） letter（letter | digit）*31021（1）0051（2）104130211letter(3)2letter1digit三、給出下面語言的相應(yīng)文法

39、：（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）文法，如果是，給出其預(yù)測分析表。（15）G2： Sa | b | （T） T ST T，S T | G2是LL（1）文法。ab（），#SSa Sb S（T）TT STT STT STTT T，S T 五、設(shè)有文法GA：ABCc | gDBBbCDE |CDaB | caDdD |EgAf | c(1)

40、計算該文法的每一個非終結(jié)符的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）造各非終結(jié)符的FIRSTVT和LASTVT集合；（2）構(gòu)造文法的算符優(yōu)先關(guān)系表。（15）FIRSTVTLASTVTETF*，+，（，i*，（，i（，i*，+，），i*，），i），i 算符優(yōu)先關(guān)系表+*I（）#+*I（）#>>><><<>>

41、;<><<<<<<<<<>>>=>>>>>=七、有定義二進制整數(shù)的文法如下：L LB | BB 0 | 1構(gòu)造一個翻譯模式，計算該二進制數(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句子的集合 B產(chǎn)生式的集合 C符號

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

43、L1ÌL0 CL3=L2ÌL1ÌL0 DL0ÌL1ÌL2=L37詞法分析的任務(wù)是 A識別單詞 B分析句子的含義 C識別句子 D生成目標(biāo)代碼8常用的中間代碼形式不含 A三元式 B四元式 C逆波蘭式 D語法樹9 代碼優(yōu)化的目的是 A節(jié)省時間 B節(jié)省空間 C節(jié)省時間和空間 D把編譯程序進行等價交換10代碼生成階段的主要任務(wù)是 A把高級語言翻譯成匯編語言 B把高級語言翻譯成機器語言 C把中間代碼變換成依賴具體機器的目標(biāo)代碼 D把匯編語言翻譯成機器語言四、簡答題(共4小題，每小題5分，共20分)1編譯程序和高級語言有什么區(qū)別? 用匯編語言或高級語言編寫的程序，必須先送入計算機，經(jīng)過轉(zhuǎn)換成用機器語言表示的目標(biāo)程序（這個過程即編譯），才能由計算機執(zhí)行。執(zhí)行轉(zhuǎn)換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉(zhuǎn)換過的叫目標(biāo)程序，也就是機器語言。 編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫