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

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

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

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

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

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

6、最右推導(dǎo)必定相同 D可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語法樹相同23、由文法的開頭符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號(hào)序列是( 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有一個(gè) B沒有 C有若干個(gè) D可能有若干個(gè)28、接受自上而下分析，必

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

8、、# E、d,#32、正則式中的 “*”讀作 D 。可選項(xiàng)有：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+T，

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

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

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

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

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

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

15、該句子的最左推導(dǎo)與最右推導(dǎo)相同 b. 該句子有兩個(gè)不同的最左推導(dǎo)c. 該句子有兩棵不同的最右推導(dǎo) d. 該句子有兩棵不同的語法樹 e.該句子的語法樹只有一個(gè)28、優(yōu)化可生成（ D ）的目標(biāo)代碼。A、運(yùn)行時(shí)間較短 B、占用存儲(chǔ)空間較小 C、運(yùn)行時(shí)間短且占用內(nèi)存空間大 D、運(yùn)行時(shí)間短且存儲(chǔ)空間小29、構(gòu)造編譯程序應(yīng)把握（ D ）A、源程序 B、目標(biāo)程序 C、編譯方法 D、以上三項(xiàng)都是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、單詞在符號(hào)

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

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

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

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

20、定義的語言，并畫出接受該語言的最簡DFA。2、證明文法E E + id | id是SLR(1)文法。5、下面C語言程序經(jīng)非優(yōu)化編譯后，若運(yùn)行時(shí)輸入2，則結(jié)果是area=12.566360, addr=-1073743076經(jīng)優(yōu)化編譯后，若運(yùn)行時(shí)輸入2，則結(jié)果是area=12.566360, addr=-1073743068請(qǐng)解釋為什么輸出結(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*定義的語言，并畫出接受該語

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

22、數(shù)如下：func(i) long i; long j;j = i 1;func(j);下面左右兩邊的匯編代碼是兩個(gè)不同版本GCC編譯器為該函數(shù)產(chǎn)生的代碼。左邊的代碼在調(diào)用func之前將參數(shù)壓棧，調(diào)用結(jié)束后將參數(shù)退棧。右邊代碼對(duì)參數(shù)傳遞的處理方式?jīng)]有實(shí)質(zhì)區(qū)分。請(qǐng)敘述右邊代碼對(duì)參數(shù)傳遞的處理方式并推想它帶來的優(yōu)點(diǎn)。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上不含子串a(chǎn)a的全部串的集合。最簡DFA如下：2、先給出接受該文法活前綴的DFA如下：E EE E + idE idI0E EE E+ idI1E idI2Eid+E E +idI3E E + idI4idI0和I

24、3都只有移進(jìn)項(xiàng)目，確定不會(huì)引起沖突；I2和I4都無移進(jìn)項(xiàng)目并僅含一個(gè)歸約項(xiàng)目，也確定不會(huì)引起沖突；在I1中，E的后繼符號(hào)只有$，同第2個(gè)項(xiàng)目的展望符號(hào)“+”不一樣，因此I1也確定不會(huì)引起沖突。由此可以斷定該文法是SLR(1)的。3、語法制導(dǎo)定義如下。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、對(duì)于函數(shù)f1，局部變量x聲明的作用域是整個(gè)函數(shù)體，導(dǎo)致在函數(shù)體中不行能訪問形式參數(shù)x。由于這是一個(gè)合法的C語言函數(shù)，因此編譯器給出警告錯(cuò)誤。對(duì)于函

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

27、一個(gè)字母。該正規(guī)式定義的語言是：至少含一個(gè)a，但不含子串a(chǎn)a的全部a和b的串集。最簡DFA如下：start2abb10ab7、消退左遞歸后的文法：B 1 BB 0 B | 1 B | e相應(yīng)的翻譯方案如下：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、表達(dá)式&i的類型表達(dá)式是pointer(long)，表達(dá)式&i-&j的類型表達(dá)式是long。依據(jù)C語言的規(guī)定，指向同一個(gè)類型的兩個(gè)指針可以相加減，它們值

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

29、范圍的角度，優(yōu)化可以分為局部優(yōu)化和全局優(yōu)化兩類；對(duì)循環(huán)的優(yōu)化有三種：循環(huán)不變表達(dá)式外提、歸納變量刪除與計(jì)算強(qiáng)度削減。2、寫出表達(dá)式a=b*c+b*d對(duì)應(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、對(duì)于文法G(S): SbM(TMabL)答：1） 2） 短語

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

32、S*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 如下:項(xiàng)目集規(guī)范族看出，不存在沖突動(dòng)作。該文法是LR(1)文法。（2） LR(1)分析表如下： (3)輸入串a(chǎn)bab 的分析過程為： 簡答題 3、設(shè)有文法GS: SS(S)S|，該文法是否為二義文法？說明理由。 答：是二義的，由于對(duì)于（）（）可以構(gòu)造兩棵不同的語法樹。 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構(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進(jìn)行分割： P1（0,5, 6,1,2,3,4）再用b進(jìn)行分割： P2（0,5, 6,1,2,3,4）再用a、b

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

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三、給出下面語言的相應(yīng)文法：（15）L1=an bn | n1 L2=anbm+nam | n1，m0 G1： SAB AaAb | ab BbBa | G1： AaAb |ab 四、對(duì)下面的文法G： Sa | b | （T）TT，S | S(1) 消去文法的左遞歸，得到等價(jià)的文法G2；(2) 推斷文法G2是否LL（1）文法，假如是，給出其猜測(cè)分析表。（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 五、設(shè)有文法GA：ABCc | gDBBbCDE |CDaB | caDdD |EgAf | c(1) 計(jì)算該文法的每一個(gè)非終結(jié)符的FIRST集和FOLLOW集；(2) 試推斷該文法是否為LL（1）文法。（15）FIRSTFOLLOWABCDEA,b,c,d,gbA,c,dDC,gA,c,dC,d,gA,b,c,g是LL（1）文法。六、對(duì)表達(dá)式文法G：E E+T | TT T*F | FF (E) | I（1）造各非終結(jié)符的FIRSTVT和LASTV

37、T集合；（2）構(gòu)造文法的算符優(yōu)先關(guān)系表。（15）FIRSTVTLASTVTETF*，+，（，i*，（，i（，i*，+，），i*，），i），i 算符優(yōu)先關(guān)系表+*I（）#+*I（）#=七、有定義二進(jìn)制整數(shù)的文法如下：L LB | BB 0 | 1構(gòu)造一個(gè)翻譯模式，計(jì)算該二進(jìn)制數(shù)的值（十進(jìn)制的值）。（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編譯原理期末試題（五）一、單項(xiàng)選擇題(共10小題，每小題2分，共20分)1語言是A句子的集合

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

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