編譯原理期末復(fù)習(xí)題含答案2023

本文格式為Word版，下載可任意編輯——編譯原理期末復(fù)習(xí)題(含答案2023編譯原理復(fù)習(xí)題一、填空題：

1、編譯方式與解釋方式的根本區(qū)別在于（是否生成目標(biāo)代碼）。

2、對編譯程序而言，輸入數(shù)據(jù)是（源程序），輸出結(jié)果是（目標(biāo)程序）。3、假使編譯程序生成的目標(biāo)程序是機器代碼程序，則源程序的執(zhí)行分為兩大階段：（編譯階段）和（運行階段）。

4、假使編譯程序生成的目標(biāo)程序是匯編語言程序，則源程序的執(zhí)行分成三個階段：（編譯階段）、（匯編階段）和（運行階段）。

5、自頂向下語法分析方法會遇到的主要問題有（回溯）和（（左遞歸帶來的）無限循環(huán)）。

6、LL(k)分析法中，第一個L的含義是（從左到右進(jìn)行分析），其次個L的含義是（每次進(jìn)行最左推導(dǎo)），“k〞的含義是（向輸入串中查看K個輸入符號）。7、LL(1)分析法中，第一個L的含義是（從左到右進(jìn)行分析），其次個L的含義是（每次進(jìn)行最左推導(dǎo)），“1〞的含義是（向輸入串中查看1個輸入符號）。8、自頂向下語法分析方法的基本思想是：從（識別符號）出發(fā)，不斷建立（直接推導(dǎo)），試圖構(gòu)造一個推導(dǎo)序列，最終由它推導(dǎo)出與輸入符號一致的（符號串）。

9、自底向上語法分析方法的基本思想是：從待輸入的符號串開始，利用文法的規(guī)則步步向上進(jìn)行（直接歸約），試圖（歸約）到文法的（識別符號|開始符號）。10、LR(0)分析法的名字中，“L〞的含義是（從左到右進(jìn)行分析），“R〞的含義是（采用最右推導(dǎo)的逆過程最左歸約），“0〞的含義是（向貌似句柄的符號串后查看0個輸入符號）。

11、LR(1)分析法的名字中，“L〞的含義是（從左到右進(jìn)行分析），“R〞的含義是（采用最右推導(dǎo)的逆過程最左歸約），“1〞的含義是（向貌似句柄的符號串后查看1個輸入符號）。

12、SLR(1)分析法的名字中，“S〞的含義是（簡單的），“L〞的含義是（從左到右進(jìn)行分析），“R〞的含義是（采用最右推導(dǎo)的逆過程最左歸約），“1〞的含義是（向貌似句柄的符號串后查看1個輸入符號）。

13、在編譯過程中，常見的中間語言形式有（逆波蘭表示）、（三元式）、（四元式）和（樹形表示）。

14、在編譯程序中安排中間代碼生成的目的是（便于代碼優(yōu)化）和（便于目標(biāo)程序的移植）。

15、表達(dá)式-a+b*(-c+d)的逆波蘭表示為（a-bc-d+*+）。16、表達(dá)式a+b*(c+d/e)的逆波蘭表示為（abcde/+*+）。

17、表達(dá)式a:=a+b*c↑(d/e)/f的逆波蘭表示為（aabcde/↑*f/+:=）。18、文法符號的屬性有（繼承屬性）和（綜合屬性）兩種。

19、一個文法符號的繼承屬性是通過語法樹中它的（兄弟結(jié)點與父）結(jié)點的相應(yīng)文法符號的屬性來計算的。

20、一個文法符號的綜合屬性是通過語法樹中它的（子）結(jié)點的屬性來計算的。21、語法制導(dǎo)的編譯程序能同時進(jìn)行（語法）分析和（語義）分析。22、編譯過程中掃描器所完成的任務(wù)是從（源程序）中識別出一個個具有（獨立語法意義的單詞）。

23、確定的有窮自動機是一個（五元組），尋常表示為（DFA=（K，∑，M，S，Z））。

24、已知文法G(E):E->T|E+T|E-TT->F|T*F|T/FF->(E)|i

該文法的開始符號是（E），終結(jié)符號集合VT是（{+,-,*./,(,),i}），非終結(jié)符號集合VN是（{E,T,F}），句型T+T*F+i的短語有（T+T*F+I，T*F第一個T，i）。25、已知文法G(E):E->T|E+T|E-TT->F|T*F|T/FF->(E)|i

改寫該文法以消除直接左遞歸，改寫后的文法為：E->（+TE‘|-TE‘|ε），T->（FT‘），（T‘->*FT‘|ε），F(xiàn)->（（E）|i）。26、已知文法G(Z):Z->U0|V1U->Z1|1V->Z0|0

請寫出全部由此文法描述的只含四個符號的句子：（0101，1010，1001，0110）。該文法是Chomsky（3）型文法。

27、Chomsky定義的四種形式語言文法分別為：（0型）文法--又稱（短語文法）文法，（1型）文法--又稱（上下文有關(guān)）文法，（2型）文法--又稱（上下文無關(guān)）文法，（3型）文法--又稱（正則）文法。28、文法G(S):S->AB

A->aAb|abB->Bc|ε

其描述的語言L(G[S])=（abc,n≥1，m≥0）。29、文法G(S):S->SAS|b|cA->aaA|a

其描述的語言L(G[S])=（b,C,或者是以b開頭、以c結(jié)尾的、中間是任意個由b或c間隔開的奇數(shù)個a組成的符號串）。

30、過程與過程引用中信息交換的方法是（全局變量的使用）和（參數(shù)傳遞）。31、形式參數(shù)和實在參數(shù)之間的對應(yīng)關(guān)系尋常按（它們在源程序中的位置）來確定。

32、按傳結(jié)果的方式進(jìn)行形實參數(shù)結(jié)合，是一種把（傳地址）和（傳值）的特點相結(jié)合的參數(shù)傳遞方式。

33、在PASCAL中，由于允許用戶動態(tài)申請與釋放內(nèi)存空間，所以必需采用（堆）存儲分派方式。

34、編譯程序進(jìn)行數(shù)據(jù)流分析的目的是（為了進(jìn)行全局優(yōu)化）。

35、根據(jù)所涉及程序的范圍，優(yōu)化可分為（局部優(yōu)化）、（循環(huán)優(yōu)化）和（全局優(yōu)化）三種。

36、局部優(yōu)化是局限于一個（基本塊）范圍內(nèi)的一種優(yōu)化。

37、詞法分析階段的錯誤主要是（拼寫錯誤），可通過（最小距離匹配）的方法去改正錯誤。

38、對錯誤的處理方法一般有（校正法）和（局部優(yōu)化法）。

39、源程序中的錯誤一般有（詞法錯誤）、（語法錯誤）、（語義錯誤）和（違反環(huán)境限制的錯誤）四種。

40、翻譯程序是這樣一種程序，它能夠?qū)ⅲㄓ眉渍Z言書寫的程序）轉(zhuǎn)換成與其等價的（用乙語言書寫的程序）。

41、編譯程序的工作過程一般可以劃分成（詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化）等五個基本階段。

42、編譯程序的工作過程還會伴有（表格處理）和（出錯處理）。

二、選擇題：

1、在使用高級語言編程時，首先可通過編譯程序發(fā)現(xiàn)源程序的全部（A）錯誤和部分（B）錯誤。

A、語法B、語義C、語用D、運行

n

nm

2、程序語言的處理程序是一種（A）。

A、系統(tǒng)軟件B、應(yīng)用軟件C、實時系統(tǒng)D、分布式系統(tǒng)

3、（B）是兩類程序語言處理程序，它們的主要區(qū)別在于是否生成目標(biāo)代碼。A、高級語言和低級語言B、解釋程序和編譯程序C、編譯程序和操作系統(tǒng)D、系統(tǒng)程序和應(yīng)用程序

4、匯編語言是將（A）翻譯成（B）；編譯程序是將（C）翻譯成（D）。

A、匯編語言程序B、機器語言程序C、高級語言程序D、匯編或機器語言程序e、匯編或高級語言程序F、機器或高級語言程序

5、編譯程序與具體的機器（A），與具體的語言（B）。A、有關(guān)B、無關(guān)

6、編譯程序生成的目標(biāo)程序（B）是可執(zhí)行的程序。A、一定B、不一定

7、編譯程序生成的目標(biāo)程序（B）是機器語言程序。A、一定B、不一定

8、把匯編語言程序翻譯成機器可執(zhí)行的目標(biāo)程序的工作是由（B）完成的。A、編譯器B、匯編器C、解釋器D、預(yù)處理器9、編譯過程中，語法分析器的任務(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)10、文法G所描述的語言是（D）的集合

A、文法G的字母表V中所有符號組成的符號串；B、文法G的字母表V的閉包V*中的所有符號串；

C、由文法的識別符號推出的所有符號串；D、由文法的識別符號推出的所有終結(jié)符符號串；

11、描述語言L={ab|n>m>1}的文法為（D）。

A、Z->Abb,A->aA|a,B->bB|bB、Z->ABb,A->Aa|a,B->aBb|bC、Z->Ab,A->aAb|aD、Z->aAb,A->Ab|aAb|@12、一個句型中的最左（B）稱為該句型的句柄。

A、短語B、簡單短語C、素短語D、終結(jié)符號13、文法的二義性和語言的二義性是兩個（A）的概念。A、不同B、一致C、無法判斷

14、上下文無關(guān)文法（A）產(chǎn)生語言L={abc|i>1,n>1}

mn

i

m

n

A、可以B、不可以

15、（B）正規(guī)文法能產(chǎn)生下面的語言：L={ambn|n>1}A、存在一個B、不存在任何c、無法判斷

16、編譯程序中的語法分析器接受以（C）為單位的輸入，并產(chǎn)生有關(guān)信息供以后各階段使用。

A、表達(dá)式B、產(chǎn)生式C、單詞D、語句

17、高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于（B）分析方法。

A、自左至右B、自頂向下C、自底向上D、自右至左

18、算符優(yōu)先分析法每次都是對（E）進(jìn)行歸約，簡單優(yōu)先分析法每次都是對（C）進(jìn)行歸約。

A、最左短語B、簡單短語C、句柄D、素短語E、最左素短語19、文法G(S)：S—>aTb|,，T->R，R—>R/S|S的句型aR/aSb/aTb,b的最左素短語為（B）。

A、aTbB、aSbC、SD、R/E、,

20、LR語法分析棧中存放的狀態(tài)是識別（B）的DFA狀態(tài)。A、前綴B、可歸前綴C、項目D、句柄

21、已知文法G[S]：s->LaR|R，L->bR|c，R->L該文法是（B）。(1)LR(0)文法；(2)SLR(1)文法；(3)LR(1)文法；(4)LALR(1)文法；(5)都不是A、(1)(2)B、(3)(4)C、(1)(2)(3)(4)D、(5)E、(6)

22、若一個句型中出現(xiàn)了某一產(chǎn)生式的右部，則此右部（B）是該句型的句柄。

A、一定B、不一定23、LR(K)方法是（D）。

A、從左到右分析，每次走K步的一種編譯方法B、從左到右分析，共經(jīng)過K步的一種編譯方法C、從左到右分析，每次向前預(yù)計K步的一種編譯方法D、從左到右分析，每次向貌似句柄的符號串后看K個輸入符號的一種編譯方法24、文法G[S]：S->AA，A->Aa|a不是LR(1)文法的理由是（D）A、FIRST(S)NFIRST(A)≠фB、FIRST(A)NFOLLLOW(A)≠фC、FIRST(Aa)NFIRST(a)≠фD、都不是

25、以下關(guān)于標(biāo)識符和名字的表達(dá)中，正確的是（C）。

A、標(biāo)識符有一定的含義B、名字是一個沒有意義的字符序列C、名字有確鑿的屬性D、都不對

26、編譯程序在其工作過程中使用最多的數(shù)據(jù)結(jié)構(gòu)是（C）。它記錄著源程

序中的各種信息，以便查詢或修改。

A、線性表B、鏈表C、表D、符號表

27、在編譯程序在其工作過程中使用的各種表中，以（D）最重要，其生存期最長，使用也最頻繁。

A、線性表B、鏈表C、表D、符號表28、編譯程序使用（B）區(qū)別標(biāo)識符的作用域。

A、說明標(biāo)識符的過程或函數(shù)名B、說明標(biāo)識符的過程或函數(shù)的靜態(tài)層次C、說明標(biāo)識符的過程或函數(shù)的動態(tài)層次D、標(biāo)識符的行號29、動態(tài)存儲分派時，可以采用的分派方法有（C）。

(1)以過程為單位的棧式動態(tài)存儲分派；(2)堆存儲分派；(3)最正確分派方法A、(1)B、(2)C、(1)(2)D、(1)(2)(3)30、過程調(diào)用時，參數(shù)的傳遞方法尋常有（D）。(1)傳值；(2)傳地址；(3)傳結(jié)果；(4)傳名

A、(1)(2)B、(1)(2)(3)C、(1)(2)(4)D、(1)(2)(3)(4)31、在編譯方法中，動態(tài)存儲分派的含義是（A）。

A、在運行階段對源程序中的量進(jìn)行分派B、在編譯階段對源程序中的量進(jìn)行分派

C、在編譯階段對源程序中的量進(jìn)行分派，在運行時這些量的地址可以根據(jù)需要改變

D、以上都不對

32、PASCAL中過程說明的局部量地址分派在（B）。

A、調(diào)用者的數(shù)據(jù)區(qū)中B、被調(diào)用者的數(shù)據(jù)區(qū)C、主程序的數(shù)據(jù)區(qū)D、公共數(shù)據(jù)區(qū)

33、表達(dá)式-a+b*c+d+(e*f)/d*e，假使優(yōu)先級由高到低依次為-、+、*、/，且均為左結(jié)合，則其后綴式為（D）。

A、abc*+d+ef*d/e*+-B、a-bc*def*d/e*+++C、a-bc*+def*d/e*++D、a-b+cd+ef*+*de*/

34、表達(dá)式a*b-c-d$e$f-g-h*i中，運算符的優(yōu)先級由高到低依次為-、*、$，且均為右結(jié)合，則其后綴式為（D）。

A、ab*c-d-e$fg-h-i*$B、$*a-b-cd$e*-f-ghiC、bcd--a*efgh--i*$$D、abcd--*efgh--i*$$E、ab*c-d-e$fg-h-i*$35、a:=a+b*c↑(d/e)/f的逆波蘭記號表示是（C）。

A、aabc*+↑de/f/:=B、aabcde↑/*f/:=C、aabcde/↑*f/+:=D、以上都不對。

三、簡答題：

1、什么是語法制導(dǎo)翻譯？

答：所謂語法制導(dǎo)翻譯，是指在語法規(guī)則的制導(dǎo)下，通過計算語義規(guī)則，完成對輸入符號的翻譯。

由于使用屬性文法時把語法規(guī)則和語義規(guī)則分開，但在使用語法規(guī)則進(jìn)行推導(dǎo)或歸約的同時又使用這些語義規(guī)則來指導(dǎo)翻譯與最終產(chǎn)生目標(biāo)代碼，所以稱為語法制導(dǎo)翻譯。

2、寫出算術(shù)表達(dá)式A+B*(C-D)+E/(C-D)**N的三元式、四元式序列。

答：四元式：三元式：

（-，C，D，T1）（1）（-，C，D）（*，B，T1，T2）（2）（*，B，（1））（+，A，T2，T3）（3）（+，A，（2））（-，C，D，T4）（4）（-，C，D）（**，T4，N，T5）（5）（**，（4），N）（/，E，T5，T6）（6）（/，E，（5））（+，T3，T6，T7）（7）（+，（3），（6））

3、寫出條件語句IFa，a，0，T1）

（2）（BMZ，T1，，（6））（3）（+，x，1，T2）（4）（：=，T2，，x）（5）（BR，，，（9））（6）（-，x，1，T3）（7）（*，4，T3，T4）（8）（：=，T4，，x）（9）

4、把語句IFA∨B3dobegina:=a+3*b;

b:=a+e-f*e;

end;的四元式序列。

答：（1）（+，x，y，T1）（2）（>，T1，3，T2）（3）（BMZ，T2，,(12)）（4）（*，3，b，T3）（5）（+，a，T3，T4）（6）（：=，T4，，a）（7）（+，a，e，T5）

（8）（*，f，e，T6）（9）（-，T5，T6，T7）（10）（：=，T7，，b）（11）（BR，，，（1））（12）8、將語句

ifAVB>0thenwhileC>0doC:=C+D翻譯成四元式。答：

100(jnz，A，-，104)101(j，-，-，102)102(j>，B，0，104)103(j，-，-，109)104(j>，C，0，106)105(j，-，-，109)106(+，C，D，T1)107(:=，T1，-，C)108(j，-，-，104)

109

9、對以下文法G:S'->#S#S->D(R)R->R;P|PP->S|iD->i

（1）計算文法G中每個非終結(jié)符的FIRSTVT集；（2）計算文法G中每個非終結(jié)符的LASTVT集；答：（1）各非終結(jié)符的FIRSTVT集合為：

FIRSTVT（S’）={#}FIRSTVT（P）={（，F(xiàn)IRSTVT（S）={（，i）FIRSTVT（D）={i}FIRSTVT（R）={；，（，i）（2）各非終結(jié)符的LASTVT集合為：

LASTVT（S’）={#}LASTVT（P）={}，i}LASTVT（S）={}}LASTVT（D）={i}

LASTVT（R）={；，），i}10、對以下文法G:

）iS'->#S#S->fStSS->i=EE->E+T|TT->P↑T|PP->(E)|i

（1）計算文法G中每個非終結(jié)符的FIRSTVT集；（2）計算文法G中每個非終結(jié)符的LASTVT集；

答：（1）各非終結(jié)符的FIRSTVT集合為：

FIRSTVT（S’）={#}FIRSTVT（T）={↑，（，i）FIRSTVT（S）={f，i}FIRSTVT（E）={+，↑，（，i）FIRSTVT（P）={（，i）

（2）各非終結(jié)符的LASTVT集合為：

LASTVT（S’）={#}LASTVT（T）={↑，}，i}LASTVT（S）={t，=，+，↑，)，i}LASTVT（E）={+，↑，}，i}LASTVT（P）={}，i}

11、文法G1：P->PaP|PbP|cP|Pe|f

證明文法G1是二義文法。

答：由于文法存在句型：fbfbf，此句型有兩棵不同的語法樹，所以文法是二義的。

或存在2種最右推導(dǎo)：

A、P=>PbP=>PbPbP=>PbPbf=>Pbfbf=>fbfbfB、P=>PbP=>Pbf=>PbPbf=>Pbfbf=>fbfbf12、有文法G[N]：

N->SE|ES->SD|D

E->0|2|4|6|8|10D->0|1|2|3|4|5|6|7|8|9

證明該文法是二義的；此文法描述的語言是什么？并試寫出另一文法，使L（G‘）=L（G），且G‘是無二義的。

答：對于該文法，存在句型110，有兩棵不同的語法樹或兩種不同的最右推導(dǎo)，因此文法具有二義性。

A、N=>SE=>S10=>D10=>110

B、N=>SE=>S0=>SD0=>S10=>D10=>110

該文法描述的語言是偶數(shù)集合。等價的無二義文法是：G‘[N]：N->SE|ES->SD|DE->0|2|4|6|8

D->0|1|2|3|4|5|6|7|8|9

13、寫出不能被5整除的偶整數(shù)的文法。答：G[Z]:

Z->(+|-)AB

A->0|1|2|3|4|5|6|7|8|9|AAB->1|2|3|4|5|6|7|8|914、對于文法G=（VN，VT，S，P）：

VN={S，A，B，}；VT={a，b}，開始符號為S

P：S->aB|bAA->aS|bAA|aB->bS|aBB|b給出串a(chǎn)aabbabbba的

（1）最左推導(dǎo)；（2）最右推導(dǎo)；（3）推導(dǎo)樹。答：最左推導(dǎo)：

S=>aB=>aaBB=>aaaBBB=>aaabSBB=>aaabbABB=>aaabbaBB=>aaabbabB=>aaabbabbS=>aaabbabbbA=>aaabbabbba最右推導(dǎo)：

S=>aB=>aaBB=>aaBbS=>aaBbbA=>aaBbba=>aaaBBbba=>aaaBbbba=>aaabSbbba=>aaabbAbbba=>aaabbabbba

15、什么是句柄？

答：一個句型德最左直接短語稱為句柄。16、什么是最左素短語？

17、上下文無關(guān)文法

答：若一個形式文法G=(N,Σ,P,S)的產(chǎn)生式規(guī)則都取如下的形式：V->w，則稱之為上下文無關(guān)的，其中V∈N，w∈(N∪Σ)*。上下文無關(guān)文法取名為“上下文無關(guān)〞的原因就是由于字符V總可以被字串w自由替換，而無需考慮字符V出現(xiàn)的上下文。上下文無關(guān)文法重要的原因在于它們擁有足夠強的表達(dá)力來表示大多數(shù)程序設(shè)計語言的語法；

四、問答題：

1、給出將賦值語句翻譯成四元式的語法制導(dǎo)定義，允許右部表達(dá)式含有加法、乘法、取負(fù)、括號運算。生成賦值語句x:=b*(c+d)+a的四元式。

2、出條件賦值語句i:=ifbthene1elsee2的語義子程序。其中b是布爾表達(dá)式，e1和e2是算術(shù)表達(dá)式，I代表與e1和e2類型一致的左部變量。按寫出的語義子程序生成條件賦值語句z:=ifa>cthenx+yelsex-y+0.5的四元式序列。

3、試寫出PASCAL循環(huán)語句forI:=1tondos的語義子程序，假定該語句的文法為：

F1:=fori:=1tonS:=F1doS1

4、給出做為條件控制的布爾表達(dá)式翻譯為四元式的語法制導(dǎo)定義，允許布爾表達(dá)式中有與、或、非及括弧運算。（如在翻譯過程中使用了自定義的函數(shù)，可以不寫函數(shù)過程，但請注明函數(shù)的功能和出入口的參數(shù)）。

5、按語法制導(dǎo)的定義將下面的后綴表達(dá)式翻譯成中綴表達(dá)式。注意：不允許出現(xiàn)冗余括號。

E->E1E2+E->E1E2*E->id

6、某程序設(shè)計語言說明部分的語法制導(dǎo)定義如下所示：

D->TLT->int|realL->L1,id|id

給出其語法制導(dǎo)定義及自底向上的翻譯方案，并比較兩者的不同。7、設(shè)有文法G[S]：

S->E

(1)

E->Aa(2)|Bb(3)A->cA(4)|d(5)B->cB|d

構(gòu)造其LR（0）分析表并利用此分析表判斷符號串a(chǎn)cccd是否是該文法的句子。8、對以下文法：

S’->SS->bRSTS->bRR->dSa

R->eT->fRaT->f

(1)出非終結(jié)符的FIRST和FOLLOW的集合。（2）構(gòu)造該文法的SLR（1）分析表。

9、給定文法G[S]：

S→SaA|aA→AbS|b

⑴請構(gòu)造該文法的以LR(0)項目集為狀態(tài)的識別規(guī)范句型活前綴的DFA。⑵請構(gòu)造該文法的LR(0)分析表。

⑶什么是LR(0)文法？該文法是LR(0)文法嗎？為什么？⑷什么是SLR(1)文法？該文法是SLR(1)文法嗎？為什么？

10、構(gòu)造以下文法的LR（1）分析表，其中S’是文法的開始符號。

S’->S

S->Aa|dAb|Bb|dBaA->cB->c

11、對下面的文法G：

S’->bAAB|bAA->dSa|bB->cAa|c

（1）判斷此文法是以下文法中的哪一種？并說明理由。LR（0）、SLR（1）、LALR（1）、LR（1）（2）構(gòu)造相應(yīng)文法的項目集族和分析表。12、對下面的文法G[S]：

(6)

(7)

S->aBc|bABA->aAb|bB->b|ε

構(gòu)造其LL（1）分析表，并利用符號棧分析符號串baabbb是否是該文法的句子。

13、對下面的文法G：

E->E+T|TT->T*F|FF->(E)|I

(1)構(gòu)造其消除直接左遞歸后的文法G’；

（2）構(gòu)造文法G’的LL（1）分析表，并利用符號棧分析符號串i1*i2+i3是否是該文法的句子。14、對下面的文法G：

P-