編譯原理期末試題(8套含答案+大題集)

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

2、要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。(x)10.一個(gè)語(yǔ)義子程序描述了一個(gè)文法所對(duì)應(yīng)的翻譯工作。(x)3 / 81、選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾， 多劃按錯(cuò)4.如果文法G是無(wú)二義的，則它的任何句子aA. ( )最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)必定相同B. ( )最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)可能不同C. ( )最左推導(dǎo)和最右推導(dǎo)必定相同論)(每個(gè)4分，共40分)1詞法分析器的輸出結(jié)果是。A( )單詞的種別編碼C( )單詞的種別編碼和自身值2 正規(guī)式M 1和M 2等價(jià)是指。A.( ) M1和M2的狀態(tài)數(shù)相等的有向邊條數(shù)相等C. ( ) M1和M2所識(shí)別的語(yǔ)言集相等 向邊條數(shù)相等3.

3、文法G Sf所識(shí)別的語(yǔ)言是。A.( )B.( ) ()* C.( ) (nB.()單詞在符號(hào)表中的位置D.( )單詞自身值0)D.( ) x*4 / 81D. ( )可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹(shù)相同5 / 815構(gòu)造編譯程序應(yīng)掌握6四元式之間的聯(lián)系是通過(guò)實(shí)現(xiàn)的。B( )臨時(shí)變量D( )程序變量7.表達(dá)式(門(mén)AVB)A(CVD)的逆波蘭表示為。A. ( )nVAVB. ( ) A門(mén)BVVAC. ( )VnVAD.( ) A門(mén)BVAV8.優(yōu)化可生成的目標(biāo)代碼。A( )運(yùn)行時(shí)間較短B( )占用存儲(chǔ)空間較小C( )運(yùn)行時(shí)間短但占用內(nèi)存空間大D( )運(yùn)行時(shí)間短且占用存儲(chǔ)空間小9下列優(yōu)化

4、方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行的。A. ( )強(qiáng)度削弱B( )刪除歸納變量A( )源程序B( )目標(biāo)語(yǔ)言C( )編譯方法D( )以上三項(xiàng)都是A( )指示器C( )符號(hào)表6 / 81C( )刪除多余運(yùn)算D( )代碼外提10編譯程序使用區(qū)別標(biāo)識(shí)符的作用域。A. ( )說(shuō)明標(biāo)識(shí)符的過(guò)程或函數(shù)名B( )說(shuō)明標(biāo)識(shí)符的過(guò)程或函數(shù)的靜態(tài)層次C( )說(shuō)明標(biāo)識(shí)符的過(guò)程或函數(shù)的動(dòng)態(tài)層次D. ( )標(biāo)識(shí)符的行號(hào)三、填空題(每空1分，共10分)1計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序主要有兩種途徑：解釋和編譯。2掃描器是詞法分析器，它接受輸入的源程序， 對(duì)源程序進(jìn)行詞法分析并 識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語(yǔ)法分析

5、器使用。3自上而下分析法采用移進(jìn)、歸約、錯(cuò)誤處理、接受等四種操作。4一個(gè)分析器包括兩部分：一個(gè)總控程序和一張分析表。5后綴式所代表的表達(dá)式是()。6局部?jī)?yōu)化是在基本塊范圍內(nèi)進(jìn)行的一種優(yōu)化。四、簡(jiǎn)答題(20分)1.簡(jiǎn)要說(shuō)明語(yǔ)義分析的基本功能。答：語(yǔ)義分析的基本功能包括:確定類型、類型檢查、語(yǔ)義處理和某些靜 態(tài)語(yǔ)義檢 查7 / 812.考慮文法GS:S f (T) | | aTf| S消除文法的左遞歸及提取公共左因子。解：消除文法GS的左遞歸：Sf(T) | | aTfTf|提取公共左因子：Sf(T) |Sf|TTfI 3.試為表達(dá)式()*(10)+8)寫(xiě)出相應(yīng)的逆波蘭表示。解：w a b + c

6、 d e 10 - / + 8 + * +4.按照三種基本控制結(jié)構(gòu)文法將下面的語(yǔ)句翻譯成四元式序列：(ACAB1) 1;8 / 81(AwD)2;。解： 該語(yǔ)句的四元式序列如下(其中E1、E2和E3分別對(duì)應(yīng)AvCABvD、A1和AwD,并且關(guān)系運(yùn)算符優(yōu)先級(jí)高)：100 (j,102)101 (,113)102 (j判斷該文法是否是（1）文法，若是構(gòu)造相應(yīng)分析表，并對(duì)輸入串 給出分 析過(guò)程。解：增加一個(gè)非終結(jié)符后，產(chǎn)生原文法的增廣文法有：S-A下面構(gòu)造它的（0）項(xiàng)目集規(guī)范族為：abdSiA10 / 81AT氐A(chǔ)兮“拖A，血Ii：W *InaccIciAW Ad衛(wèi)亠血衛(wèi)亠I；L：A-aA-dA-a

7、AbI5：IiA-*aA.dlI ;A-aAb 從上表可看出,狀態(tài)I0和12存在移進(jìn)-歸約沖突，該文法不是（0）文法。對(duì) 于I0來(lái)說(shuō)有：（A）na=na=，所以在I0狀態(tài)下面臨輸入符號(hào)為a時(shí)移進(jìn)，為時(shí)歸約，為其他時(shí)報(bào)錯(cuò)。對(duì)于I2來(lái)說(shuō)有也有與I0完全相同的結(jié)論。這就是說(shuō)，以上的移進(jìn)-歸約沖突是可以解決的，因此該文法是（1）文法 其(1)分析表為:對(duì)輸入串給出分析過(guò)程為:11 / 81狀暮棧符號(hào)樸ACTIOMGOTO1S：202b#r?59029b#S.40234口1501acc編譯原理期末試題(二)一、是非題.1.一個(gè)上下文無(wú)關(guān)文法 的開(kāi)始符，可以是終結(jié)符或非終結(jié)符。2.一 個(gè)句型的直接短語(yǔ)是唯

8、一的。3.已)經(jīng)證明文法的二義性是可判定的。()4.每 個(gè)基本塊可用一個(gè)表示。()5.每個(gè)過(guò)程的活動(dòng)記錄的體積在編譯時(shí)可靜態(tài)確定。6.2”型 文 法一定 是3型 文 法。 ( )7.一 個(gè) 句 型 一 定 句 子。()8.算符優(yōu)先分析法每次都是對(duì)句柄進(jìn)行歸約。X()9.采用三元式實(shí)現(xiàn)三地址代碼時(shí)，不利于對(duì)中間代碼進(jìn)行優(yōu)化。 ( )10.編譯過(guò)程中，語(yǔ) 法分析器 的任務(wù)是 分析單 詞是怎樣構(gòu) 成的。11.（一）個(gè)優(yōu) 先表一定存在相應(yīng)的 優(yōu)先函數(shù)。X12.（目標(biāo)）代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。13.（遞）歸 下 降 分 析 法 是 一 種 自 下 而 上 分 析 法 。14.

9、并 不 是 每 個(gè) 文 法 都 能 改 寫(xiě) 成（1）文 法 。15.（每）個(gè) 基 本 塊 只 有 一 個(gè) 入 口 和 一 個(gè) 出 口 。16.一 個(gè)（1）文 法 一 定 是 無(wú) 二 義 的 。17.逆 波 蘭 法 表 示 的 表 達(dá) 試 亦 稱 前 綴 式 。18.（目標(biāo)）代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。19.（正）規(guī)文法產(chǎn)生的語(yǔ)言都可以用 上下文無(wú)關(guān)文法 來(lái)描述。20.一 個(gè) 優(yōu) 先 表 一 定 存 在 相 應(yīng) 的 優(yōu) 先 函 數(shù) 。21.3型 文 法 一 定12 / 81是2型 文 法 。22.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則文法是二義性的。( )答案：

10、1.X2.X3.X4.V5.V6.X7.X8.X9.V10.X11.X12.V13.X14.V15.V16.V17.X18.V19.V20.X21.V22.V二、填空題：2.編譯過(guò)程可分為 （ 詞法分析） ，（語(yǔ)法分析），（語(yǔ)義分析與中間 代碼生成 ） ，（優(yōu)化）和（目標(biāo)代碼生成 ）五個(gè)階段。3.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法 是（ 二義性的 ）。4.從功能上說(shuō)， 程序語(yǔ)言的語(yǔ)句大體可分為（ 執(zhí)行性 ）語(yǔ)句和 （說(shuō)明性 ）語(yǔ)句兩大類。5.語(yǔ)法分析器的輸入是（ 單詞符號(hào) ），其輸出是（ 語(yǔ)法單 位 ）。6.掃描器的任務(wù)是從（ 源程序中 ）中識(shí)別出一個(gè)個(gè)（ 單詞符 號(hào)

11、）。7.符號(hào)表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)， 如（類型、種屬、 所占單元大小、地址）等等。8.一個(gè)過(guò)程相應(yīng)的表的內(nèi)容為（現(xiàn)行活動(dòng)記錄地址和所有外層最新活 動(dòng)記錄的地址）10.常用的兩種動(dòng)態(tài)存貯分配辦法是（棧式）動(dòng)態(tài)分配和（堆式）動(dòng)態(tài) 分配。13 / 8111.一個(gè)名字的屬性包括（類型）和（作用域）。12.常用的參數(shù)傳遞方式有（傳地址）,（傳值）,（傳名）13.根據(jù)優(yōu)化所涉及的程序范圍， 可將優(yōu)化分成為（局部?jī)?yōu)化），（循環(huán)優(yōu) 化），（全局優(yōu)化）三個(gè)級(jí)別。14.語(yǔ)法分析的方法大致可分為兩類，一類是（自上而下）分析法，另一類是（自下而上）分析法。15.預(yù)測(cè)分析程序是使用一張（分析表）和一個(gè)

12、（符號(hào)棧）進(jìn)行聯(lián)合控制的。17.一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是（初）態(tài)；而且 實(shí)際上至少要有一個(gè)（終）態(tài)。19.語(yǔ)法分析是依據(jù)語(yǔ)言的（語(yǔ)法）規(guī)則進(jìn)行。中間代碼產(chǎn)生是依據(jù)語(yǔ) 言的（語(yǔ)義）規(guī)則進(jìn)行的。21.一個(gè)文法G若它的預(yù)測(cè)分析表M不含多重定義，則該文法是（1）文法）文法。22.對(duì)于數(shù)據(jù)空間的存貯分配，采用（靜態(tài)策略， 采用（動(dòng)態(tài)）策略。24.最右推導(dǎo)亦稱為（規(guī)范推導(dǎo)），由此得到的句型稱為（規(guī)范）句型。26.對(duì)于文法G僅含終結(jié)符號(hào)的句型稱為（句子）。27.所謂自上而下分析法是指（從開(kāi)始符號(hào)出發(fā)，向下推導(dǎo)，推出句子）29.局限于基本塊范圍的優(yōu)化稱（局部?jī)?yōu)化 ）。31.2型文法又稱為

13、（上下文無(wú)關(guān)）文法；3型文法又稱為（正則 ）文法。_32.每條指令的執(zhí)行代價(jià)定義為（指令訪問(wèn)主存次數(shù)加1）33.算符優(yōu)先分析法每次都是對(duì)（最左素短語(yǔ)）進(jìn)行歸約。三、名詞解釋題：1.局部?jī)?yōu)化局限于基本塊范圍的優(yōu)化稱。2.二義性文法如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是二義性文法。3表過(guò)程的嵌套層次顯示表，記錄該過(guò)程的各外層過(guò)程的最新活動(dòng)記錄的起始地址。5.最左推導(dǎo)任何一步a=S都是對(duì)a中的最右非終結(jié)符替換。6.語(yǔ)法一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。7.文法描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則。8.基本塊指程序中一順序執(zhí)行的語(yǔ)句序列占 其中只有一個(gè)入口和一個(gè)出口，入口就是其中

14、的第一個(gè)語(yǔ)句，出口就是其中的最后一個(gè)語(yǔ)句。9.語(yǔ)法制導(dǎo)翻譯在語(yǔ)法分析過(guò)程中，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序進(jìn)行翻譯的辦法叫做語(yǔ)法制導(dǎo)翻譯。10.短語(yǔ)令G是一個(gè)文法，S劃文法的開(kāi)始符號(hào)，假定aPS是文法G的一個(gè)句型，如果有SaAS且A P,則稱P是句型aPS相對(duì) 非終結(jié)符A的短語(yǔ)。一一11.待用信息如果在一個(gè)基本塊中，四元式i對(duì)A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒(méi)有A的其它定值，則稱j是四元式i的變量A的待用信息。12.規(guī)范句型由規(guī)范推導(dǎo)所得到的句型。13.掃描器執(zhí)行詞法分析的程序。14.超前搜索在詞法分析過(guò)程中，符。、_15.句柄一個(gè)句型的最左直接短語(yǔ)。有時(shí)為了確定詞性，需超前掃描若

15、干個(gè)字14 / 8116.語(yǔ)法制需翻譯在語(yǔ)法分析過(guò)法制導(dǎo)翻譯據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義程序進(jìn)17.規(guī)范句型由規(guī)范推導(dǎo)所得到的句型。18.素短語(yǔ)素短語(yǔ)是指這樣一個(gè)短語(yǔ)，至少含有一個(gè)終結(jié)符，并且，除它自身外不再含任何更小的素短語(yǔ)。19.語(yǔ)法是組規(guī)則，用它可形成和產(chǎn)生一個(gè)合式的程序。20.待用信息如果在一個(gè)基本塊中，四元式i對(duì)A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒(méi)有A的其它定值，則稱j是四元式i的變量A的待用信息。21.語(yǔ)義定義程序的意義的一組規(guī)則。四、簡(jiǎn)答題：1.寫(xiě)一個(gè)文法G,使其語(yǔ)言為 不以0開(kāi)頭的偶數(shù)集。2.已知文法G(S)及相應(yīng)翻譯方案S“1”Sa“2”2“3”Ac“4”輸入,輸出是什么

16、？3.已知文法G(S)SA(B | aB)寫(xiě)出句子b()b的規(guī)范歸約過(guò)程。4.考慮卞面的程序：p(x, y, z);*z;2;*2P(A,A,B);A, B試問(wèn)，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出A, B的值是什么？5.文法G(S)SAaB 描述的語(yǔ)言是什么？6.證明文法G(S)S 是二義性的。7.已知文法G(S)S15 / 81AdB | c的預(yù)測(cè)分析表如下16 / 81abcd#SSfSfSfAA-A-A-AfdB 升升Bc給出句子的分析過(guò)程。8.寫(xiě)一個(gè)文法G,使其語(yǔ)言為L(zhǎng)(G)= l=0, m=1, n=29.已知文法G(S):S-(T)Tf的優(yōu)先關(guān)系表如下：關(guān)系a(

17、)a-.(V.V.V.)-.V.V.12.一字母表 藝=a, b，試寫(xiě)出藝上所有以a為首的字組成的正規(guī)集相對(duì)應(yīng)的正規(guī)式。13.基本的優(yōu)化方法有哪幾種？14.寫(xiě)一個(gè)文法G,使其語(yǔ)言為L(zhǎng)(G)= n015.考慮下面的程序：P(x, y, z);2；3；p(, b, a);a試問(wèn)，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出 值是什么？16.寫(xiě)出表達(dá)式a+b*()的逆波蘭式和三元序列。17.證明文法G(A)Af| (A)|是二義性的。*18.令藝=，則正規(guī)式a a表示的正規(guī)集是什么？19.何謂表？其作用是什么？20.考慮下面的程序：目謂優(yōu)碼?按所涉及的程生成圍可代為哪通常應(yīng)考?哪幾個(gè)問(wèn)題?

18、10.11.17 / 81p(x, y, z)18 / 812；5；2；P(, , a);a試問(wèn)，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出 值是什么？21.寫(xiě)一個(gè)文法G,使其語(yǔ)言為L(zhǎng)(G)= n0為奇數(shù)，m0為偶數(shù)22.寫(xiě)出表達(dá)式()*()的逆波蘭式和三兀序列。23.個(gè)文法G別是(1)文法的充要條件是什么？24.已知文法GSSS* | | *L 丨、消除文法左遞歸和提公共左因子。25.符號(hào)表的作用是什么？符號(hào)表查找和整理技術(shù)有哪幾種？ 答案：1.所求文法是GS:SA0AC1 D02.輸出是42317 |919 / 81步驟符號(hào)棧輸入串動(dòng)作0#b()備1()進(jìn)2()移進(jìn)3(a)a移

19、進(jìn)4(A)a歸約5(移進(jìn)6()移進(jìn)7(B:歸約8歸約9移進(jìn)10接受4.傳地址6, 16傳值2, 45(G)= 0, m0 6.證明：3.句子b()b的規(guī)范歸約過(guò)程:20 / 81因?yàn)槲姆℅S存在句子有兩個(gè)不同的最左推導(dǎo)，所以文法GS是是二義性的。7.句子的分析過(guò)程:步驟符號(hào)棧輸入串產(chǎn)生式01S2升34Ad56A7Bc89Bc101112Ad13#8.所求SAD49.10.優(yōu)化：對(duì)程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。三種級(jí)別：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化、11.目標(biāo)代碼通常米用三種形式： 機(jī)器語(yǔ)言，匯編語(yǔ)言，待裝配機(jī)器語(yǔ)言模 塊。應(yīng)著重考慮的問(wèn)題： 如何使生成的

20、目標(biāo)代碼較短；(2)如何充分利用寄存器，以減少訪問(wèn)內(nèi)存次數(shù)；(3)如何充分利用指令系統(tǒng)的特點(diǎn)。12.正規(guī)式a ( a | b )*。函數(shù)a()5f4244g552321 / 8113.刪除多余運(yùn)算，代碼外提，強(qiáng)度削弱，變換循環(huán)控制條件，合并已知量，22 / 81復(fù)寫(xiě)傳播和刪除無(wú)用賦值。14.文法GS:Sf| aBf15.傳值2傳地址1516.逆波蘭式: *三元序列: 1 2(1)- c d(2)*b(1)(3)/(2)e(4)+a(3)17.證明： 因?yàn)槲姆℅S存在句子()有兩個(gè)不同的最左推導(dǎo)，所以文法GS是是二義性的。(A)()()*(A)=()18. (a a)= 一19表:嵌套層次顯示表

21、 由于過(guò)程嵌套允許內(nèi)層過(guò)程引用外層過(guò)程定義的數(shù)據(jù)， 因此， 當(dāng)一個(gè)過(guò) 程運(yùn)行時(shí)必須跟蹤它的所有外層過(guò)程的最新活動(dòng)記錄起始地址，表就是用于登記每個(gè)外層過(guò)程的最新活動(dòng)記錄起始地址。20.傳地址12傳值521.所求文法是GS:SfAfCf22.逆波蘭式*三元 序列12(1) +bc(2) *(1)e(3) +bc(4) /(3)f(5) +(2)(4)23.一個(gè)文法G別麗(1)文法的充要條件是Ff|提公共左因子,文法G(S)Sf| *Sf*|Ff25.作鬲了登記源程序中出現(xiàn)的各種名字及其信息，以及了解各階段的進(jìn)展(2()1)(女諜24.消除左遞歸n(B)=a)n(A)=Sf| *Sf*23 / 81

22、狀況。 主要技術(shù)：線性表，對(duì)折查找，雜奏技術(shù)。 五、計(jì)算題：1.設(shè)文法G(S):S-八| a | (T)TI S 消除左遞歸； 構(gòu)造相應(yīng)的和集合； 構(gòu)造預(yù)測(cè)分析表2.語(yǔ)句E S(1)改寫(xiě)文法，使之適合語(yǔ)法制導(dǎo)翻譯；(2)寫(xiě)出改寫(xiě)后產(chǎn)生式的語(yǔ)義動(dòng)作。3.設(shè)文法G(S)：S-(T) | aT| S(1)計(jì)算 和；(2)構(gòu)造優(yōu)先關(guān)系表。4.設(shè)某語(yǔ)言的語(yǔ)(1)句的(形2)式為i:=古E(2fS其語(yǔ)義解釋(為1)i:= S:=孑):iv =S;十1(1)寫(xiě)出適合語(yǔ)法制導(dǎo)翻譯的產(chǎn)生式；(2)寫(xiě)出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作。5.把語(yǔ)句a0 1*3-1;翻譯成四元式序列。6.設(shè)有基本塊*C*E2*C2*S*Q

23、*5假設(shè)基本塊出口時(shí)只有M還被引用，請(qǐng)寫(xiě)出優(yōu)化后的四元序列。7.已知文法G(S)24 / 81Sfa |八I (T)T| S(1)給出句子(a,()的最左推導(dǎo)；(2)給出句型()的短語(yǔ),直接短語(yǔ)，句柄。8.對(duì)于C語(yǔ)言S E語(yǔ)句(1)改寫(xiě)文法，使之適合語(yǔ)法制導(dǎo)翻譯；(2)寫(xiě)出改寫(xiě)后產(chǎn)生式的語(yǔ)義動(dòng)作。9.已知文法G(S)SfAfbBfd(1)給出句子的最左推導(dǎo)及畫(huà)出語(yǔ)法樹(shù)；(2)給出句型的短語(yǔ)、素短語(yǔ)。10.設(shè)文法G(S):Sf(T) | | aTf| S消除左遞歸和提公共左因子；構(gòu)造相應(yīng)的和集合；構(gòu)造預(yù)測(cè)分析表。11.把語(yǔ)句X0VYvoX0 *33;翻譯成四元式序列。12.已知文法G(S)Ef|

24、 TTfT* FFf(E)| i(1)給出句型()*的最左推導(dǎo)及畫(huà)出語(yǔ)法樹(shù)；(2)給出句型()*的短語(yǔ)，素短語(yǔ)和最左素短語(yǔ)。13.設(shè)文法G(S)：SfT | SVTTUAUUfi(1)計(jì)算 和；(2)構(gòu)造優(yōu)先關(guān)系表。25 / 815.(1)10, (3)答案：(1)消除左遞，文法變?yōu)镚 S:S: | a | (T)TS T|此文法無(wú)左公共左因子。構(gòu)造相應(yīng)的和集合：(S) =a,八,(，(S)=#, , )(T) =a,八,(，(T)=(T)=,(F)=)(3)構(gòu)造預(yù)測(cè)分析表：aA()#SPSAS(T)TTTTTTT2. (1)C-E(2)CE (,)；(, S(1). )3. (1) (S)=

25、a, ( (T)=+, , (S)=a, ) (T)=+, a, )(,E(2), _,)；(jw, (i), , 2) (S(1),)；(+, , 1,)；(j, _, _,)；S(1)(1)a+()a.+V.V.(V.V.V.=).4. (1) FS-(1)、(1)Fv丿E (, E(i); (i);Sh_,0)E26 / 81(2) (j, _, _, (12)(3) (j , c,0, (5)(4) (j, _, _, (8)(5) (+, a,1, T1)(6) (, T1, _, a)(7) (j, _, _, (1)(8) (*, a,13, T2)(9) (-, T2,1, T

26、3)(10)(, T3, _, a)(11)(j, _, _, (1)6.優(yōu)化后的四元序列*C*E207.最左推導(dǎo)(T)=()=()=()=(a,(T)=(a,()=(a,()=(a,()=(a ,()短語(yǔ)()()()a直接短語(yǔ)a句柄8.(1)SfMiSiM2EMe(2)Mfe;SfM1S1M2E (s1, M2);(, M1);J10.(1) Sf(L) |SfS |eLfLf|e(2) (S)=a, (S)=a, (,(L)=a, (L)=,e(S)=, ), #(S)=, ), #9.(1) 27 / 81(L)= )(L)= )28 / 81()a#SS-(L)S0SfSS；SSS；-

27、SLL-LL-LLEiVA-S.VV.V.V.AV.V.-V.V.編譯原理期末試題(二)D7)7D11,(c (o ,-o廠_x一：，_o5)5),v , , ooooo_AT_ ,* ,X7xl7X7xl7 X7xl7X7xl7 x7./x7./0202 3 3 4 4 5 5 6 6 7 7 8 8 9 9 /I/I /I/I/I/IT TTTT2)YT _B,T1 2t*29 / 811、 描述由正規(guī)式b*(*)*()定義的語(yǔ)言，并畫(huà)出接受該語(yǔ)言的最簡(jiǎn)。2、證明文法E E + |是(1)文法。3、下面是表達(dá)式和賦值語(yǔ)句的文法，其中的類型是，+的類型是，=的類型是，要求和E的類型都是或者都

28、是。為該文法寫(xiě)一個(gè)語(yǔ)法制導(dǎo)定義或翻譯方案， 它完成 類型檢查。S EE E E | E + E | E = E4、對(duì)于下面C語(yǔ)言文件f1( x)X；X = 1;30 / 81f2( x)x;x = 1;某編譯器編譯時(shí)報(bào)錯(cuò)如下：:f1:3: :xa請(qǐng)回答，對(duì)函數(shù)f2為什么沒(méi)有類似的警告錯(cuò)誤。5、下面C語(yǔ)言程序經(jīng)非優(yōu)化編譯后，若運(yùn)行時(shí)輸入 是12.566360, 1073743076經(jīng)優(yōu)化編譯后，若運(yùn)行時(shí)輸入2，則結(jié)果是12.566360, 1073743068請(qǐng)解釋為什么輸出結(jié)果有區(qū)別。()s, , r;3.14159;(,)；(,n, *r*r,);6、描述由正規(guī)式b a( a) b定義的語(yǔ)言

29、，并畫(huà)出接受該語(yǔ)言的2，則結(jié)果31 / 81最簡(jiǎn)。7、下面的文法產(chǎn)生代表正二進(jìn)制數(shù)的0和1的串集:BB 0 | B 1 | 1F面的翻譯方案計(jì)算這種正二進(jìn)制數(shù)的十進(jìn)制值:BB 0 B12 | B11 B12 +1I 1 1 請(qǐng)消除該基礎(chǔ)文法的左遞歸，再重寫(xiě)一個(gè)翻譯方案，它仍然 計(jì)算這種正二進(jìn)制數(shù)的十進(jìn)制值。8在C語(yǔ)言中，如果變量i和j都是類型，請(qǐng)寫(xiě)出表達(dá)式和 表達(dá)式 的類型表達(dá)式。為幫助你回答問(wèn)題，下面給出一個(gè)程序 作為提示，它運(yùn)行時(shí)輸出1。()i, j;(“n”,);9、一個(gè)C語(yǔ)言的函數(shù)如下:(i) i; j;j = i-1；(j);下面左右兩邊的匯編代碼是兩個(gè)不同版本編譯器為該函數(shù)產(chǎn)生 的

30、代32 / 81碼。 左邊的代碼在調(diào)用之前將參數(shù)壓棧， 調(diào)用結(jié)束后將參數(shù) 退棧。右邊代碼對(duì)參數(shù)傳遞的處理方式?jīng)]有實(shí)質(zhì)區(qū)別。 請(qǐng)敘述右 邊代碼對(duì)參數(shù)傳遞的處理方式并推測(cè)它帶來(lái)的優(yōu)點(diǎn)。| :, |$4,J|8(), |8(),|, -4() |, -4()-4(), |-4(),|, ()|$4,|33 / 81編譯原理試卷八答案1、由正規(guī)式b*(*)*()定義的語(yǔ)言是字母表a, b上不含子串的所有串的集合。最簡(jiǎn)如下：2、先給出接受該文法活前綴的如下:I0和I3都只有移進(jìn)項(xiàng)目，肯定不會(huì)引起沖突；I2和I4都無(wú)移 進(jìn)項(xiàng)目并僅含一個(gè)歸約項(xiàng)目，也肯定不會(huì)引起沖突；在11中，E的后繼符號(hào)只有$，同第2個(gè)項(xiàng)

31、目的展望符號(hào)“+”不一樣，因此11也肯定不會(huì)引起沖突。由此可以斷定該文法是(1)的。3、語(yǔ)法制導(dǎo)定義如下。SE(=)(=)EE1E2E1=E2=EE1+ E2E1=E2=E E+34 / 81E Ei= E2 Ei= E2=E () 4、對(duì)于函數(shù)fl，局部變量x聲明的作用域是整個(gè)函數(shù)體，導(dǎo)致 在函數(shù)體中不可能訪問(wèn)形式參數(shù)X。由于這是一個(gè)合法的C語(yǔ)言 函數(shù)，因此編譯器給出警告錯(cuò)誤。對(duì)于函數(shù)f2，由于局部變量x的作用域只是函數(shù)體的一部分， 不會(huì)出現(xiàn)上述問(wèn)題，因而編譯器不報(bào)錯(cuò)。5、使用非優(yōu)化編譯時(shí)，變量s, , r在局部數(shù)據(jù)區(qū)都分配4個(gè)字節(jié)的空間。 使用優(yōu)化編譯時(shí)， 由于復(fù)寫(xiě)傳播，*r*r變成3.1

32、4159*r*r，3.14159成為無(wú)用賦值而刪去，函數(shù)中不再有的 引用，因此不必為分配空間。類似地，3.14159*r*r也是一個(gè)無(wú)用賦值(表達(dá)式要計(jì)算，但賦值是無(wú)用的)，也不必為s分配空 間。這樣，和非優(yōu)化情況相比，局部數(shù)據(jù)區(qū)少了8個(gè)字節(jié)，因此r的地址向高地址方向移動(dòng)了8個(gè)字節(jié)。6、 正規(guī)式b a( a) b體現(xiàn)的特點(diǎn)是，每個(gè)a的左邊都有若干b， 除非a是第一個(gè)字母。該正規(guī)式定義的語(yǔ)言是：至少含一個(gè)a，但不含子串的所有a和b的串集。最簡(jiǎn)如下：35 / 817、消除左遞歸后的文法:B1 BB0 B| 1 BI相應(yīng)的翻譯方案如下：B1 B1B B B0 B1B2B1BB1| 1 B1B2 +1

33、 B1B B1IB B8表達(dá)式的類型表達(dá)式是（），表達(dá)式 的類型表達(dá)式是。按照C語(yǔ)言的規(guī)定，指向同一個(gè)類型的兩個(gè)指針可以相加減，它們值 的差是它們之間的元素個(gè)數(shù)。9、左邊的編譯器版本：一般只為局部變量分配空間。調(diào)用函數(shù) 前，用若干次指令將參數(shù)壓棧，返回后用$n,次將所有參數(shù)退棧（常數(shù)n根據(jù)調(diào)用前做了多少次來(lái)決定）。右邊的編譯器版本：除了為局部變量分配空間外，同時(shí)還為 本函數(shù)中出現(xiàn)的函數(shù)調(diào)用的參數(shù)分配空間，并且參數(shù)所用空間靠近棧頂。調(diào)用函數(shù)前，用指令將參數(shù)移入棧頂，調(diào)用結(jié)束后無(wú)需 參數(shù)退棧指令。優(yōu)點(diǎn)是每次函數(shù)調(diào)用結(jié)束后不需要執(zhí)行$n,指令，另外增加 優(yōu)化的可能性。36 / 81編譯原理期末試題（

34、三）1、從優(yōu)化的范圍的角度，優(yōu)化可以分哪兩類？對(duì)循環(huán)的優(yōu)化 可以有哪三種？答：從優(yōu)化的范圍的角度，優(yōu)化可以分為局部?jī)?yōu)化和全局優(yōu)化 兩類；對(duì)循環(huán)的優(yōu)化有三種： 循環(huán)不變表達(dá)式外提、 歸納變量刪除與計(jì) 算強(qiáng)度削減。2、寫(xiě)出表達(dá)式*d對(duì)應(yīng)的逆波蘭式、四元式序列和三元式序列。答：逆波蘭式：*四元式序列：三元式序列: 12(1) (*，b，c，t1)(1) (*b，c )(2) (*，b，d，t2)(2) (*b，d )37 / 81(+,t1,t2,t3)(3)(+(1)(，t3,/,a)(3),a)3、 對(duì)于文法G(S)SbMbM(L|aLMa)答：1)SbMb b(Lb b(Ma)b2)短語(yǔ):)，

35、()，b()b直接短語(yǔ):)句柄:)三、設(shè)有字母表a,b上的正規(guī)式()*a(3)對(duì)(2)得到的化簡(jiǎn)，合并狀態(tài)0和2為狀態(tài)2:38 / 81a(4)令狀態(tài)1和2分別對(duì)應(yīng)非終結(jié)符B和AG: Afg;Bfg;可化簡(jiǎn)為：G: Afg;四、設(shè)將文法G改寫(xiě)成等價(jià)的(1)文法，并構(gòu)造預(yù)測(cè)分析表G:SfS*;Tf解：消除左遞歸后的文法提取左公因子得文法Sf|*Sf*|gTfTfgf)=af*)=*f )n(Sf*)=f* )=*fg)(s)=#f*)n(S fg)=f)=+fT)(T) =+f g)(T)=*、fT)n(Tfg)=所以該文法是(1)文法。預(yù)測(cè)分析表：SSSSSSTTTTG : SfSf*|gTf

36、G:*+a#Sf*fSf*f gTf39 / 8140 / 81TT6設(shè)文法G為:SA;心 ；B解：(1)拓廣文法G:(0) S SSAAAB(5) Bb;(A) = , a, b;(B) = a, b構(gòu)造的如下:項(xiàng)目集規(guī)范族看出，不存在沖突動(dòng)作。二該文法是(1)文法。(2)(1)分析表如下:ActionG&toaBsAB0S4S5r31巧M31acc2rl3SiSir3634S4務(wù)75r5r5r541 / 81dr27rlrlrl(3)輸入串的分析過(guò)程為:步羿當(dāng)前宇符和余字符串動(dòng)作Cababis(2)04rfahabl?轎進(jìn)045tabab#，約B-b047毎aB3bP歸旳B4aBC

37、3itBaba移進(jìn)034鋁Elb#收進(jìn)(7)0315#Bab歸約B-b(8)0947+BaB舊的B-oB033s?BB歸的Gf10：0336BBAA-BA(11)036SBA歸約ABA(12102 A嚴(yán)S-A(13)Cftacc簡(jiǎn)答題3、設(shè)有文法GS: S - S(S)，該文法是否為二義文法？說(shuō)明理由。答：是二義的，因?yàn)閷?duì)于()()可以構(gòu)造兩棵不同的語(yǔ)法樹(shù)。E五、給定文法GS:S42 / 814; L; 4 ;QH;i構(gòu)造相應(yīng)的最小的。解：先構(gòu)造其：用子集法將確定化：將S、A Q、D B重新命名，分別用0、1、2、3、4、5、6表示。因?yàn)?、4中含有z,所以它們?yōu)榻K態(tài)。令P0=(0,125,6

38、,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進(jìn)abSAQAAQQQDABDABBQD43 / 81行分割，仍不變。44 / 81再令0為A,1,2為B,3,4為C,5,6為Do最小化為右上圖。六、對(duì)文法G(S):S-a |八| (T)答:(1)FIRSTVT(S) a,八，(FIRSTVT(T) , ,a,A,(LASTVT(S) a/,)LASTVT(T) , ,a,A,)（2）是算符優(yōu)先文法，因?yàn)?任何兩個(gè)終結(jié)符之間至多只有一種 優(yōu)先關(guān)系。 （2分）（3）給出輸入串（）#的算符優(yōu)先分析過(guò)程。步驟棧當(dāng)前輸入字符

39、剩余輸入串 動(dòng)作1-(#（移進(jìn)2#(a)#（a 移進(jìn)3#(a!a)#a,歸約4#(NJa)#（,移進(jìn)5#(N,a)#,a 移進(jìn)6#()#a）歸約7#()#,）歸約3#(N)#（=）移進(jìn)9#(N)#）#歸約10#接受編譯原理期末試題（四）簡(jiǎn)述編譯程序的工作過(guò)程。（10）aA()J#aA(=J#1 L2= | n1,m047 / 81TT,S | S（1）消去文法的左遞歸， 得到等價(jià)的文法G2;（2）判斷文法G2是否（1）文法，如果是，給出其預(yù)測(cè)分析表。（15）G2:Sa | b |(T)T,S T|G2是（1）文法ab()5#SSaSbS(T)TTTTTTT,S T五、設(shè)有文法GA:AI4 |

40、CIX IEIc(1)計(jì)算該文法的每一個(gè)非終結(jié)符的集和集；48 / 81試判斷該文法是否為（1）文法。（15）49 / 81ABCDEbD是（1）文法六、對(duì)表達(dá)式文法G:E - | TTT*F | FF - （E） | I（1） 造各非終結(jié)符的和集合；（2） 構(gòu)造文法的算符優(yōu)先關(guān)系表。（15）ETF*，+， （，i*，（，i（，i*， +,），i*,），i），i50 / 81算符優(yōu)先關(guān)系表+*I()#+*I()#七、有定義二進(jìn)制整數(shù)的文法如下：Lf| BBf0 | 1構(gòu)造一個(gè)翻譯模式，計(jì)算該二進(jìn)制數(shù)的值(十進(jìn)制的值)(15)引入L、B的綜合屬性，翻譯模式為：SfL()LfLiB L1*2LfB

41、 Bf00Bf1151 / 81編譯原理期末試題（五）一、單項(xiàng)選擇題（共10小題，每小題2分，共20分）1.語(yǔ)言是A.句子的集合B.產(chǎn)生式的集合C.符號(hào)串的集合D.句型的集合2.編譯程序前三個(gè)階段完成的工作是52 / 81A.詞法分析、語(yǔ)法分析和代碼優(yōu)化B.代碼生成、代碼優(yōu)化和詞法分析C.詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼生成D.詞法分析、語(yǔ)法分析和代碼優(yōu)化3.個(gè)句型中稱為句柄的是該句型的最左A.非終結(jié)符號(hào)B.短語(yǔ)C.句子D.直接短語(yǔ)4.下推自動(dòng)機(jī)識(shí)別的語(yǔ)言是A. 0型語(yǔ)言B.1型語(yǔ)言C. 2型語(yǔ)言D.3型語(yǔ)言5.掃描器所完成的任務(wù)是從字符串形式的源程序中識(shí)別出一個(gè) 個(gè)具有獨(dú)立含義的最小語(yǔ)

42、法單位即A.字符B.單詞C.句子D.句 型6.對(duì)應(yīng)四種文法的四種語(yǔ)言之間的關(guān)系是7.詞法分析的任務(wù)是.分析句子的含義 .生成目標(biāo)代碼8.常用的中間代碼形式不含9.代碼優(yōu)化的目的是A.LoLiL2L3L3L2LiLoC.L32LiLo.LoLiL23A.識(shí)別單詞C.識(shí)A.三元式B.四元式.逆波蘭式D.語(yǔ)法樹(shù)53 / 81A.節(jié)省時(shí)間B.節(jié)省空間C.節(jié)省時(shí)間和空間D.把編譯程序進(jìn)行等價(jià)交換10.代碼生成階段的主要任務(wù)是A.把高級(jí)語(yǔ)言翻譯成匯編語(yǔ)言B.把高級(jí)語(yǔ)言翻譯成機(jī)器語(yǔ)言C.把中間代碼變換成依賴具體機(jī)器的目標(biāo)代碼D.把匯編語(yǔ)言翻譯成機(jī)器語(yǔ)言二、填空題（本大題共5小題，每小題2分，共10分）1.編

43、譯程序首先要識(shí)別出源程序中每個(gè)（單詞），然后再分析每 個(gè)（句子）并翻譯其意義。2.編譯器常用的語(yǔ)法分析方法有（自底向上）和（自頂向下）兩種。3.通常把編譯過(guò)程分為分析前端與綜合后端兩大階段。詞法、語(yǔ)法和語(yǔ)義分析是對(duì)源程序的（分析）,中間代碼生成、代碼優(yōu)化 與目標(biāo)代碼的生成則是對(duì)源程序的（綜合）。4.程序設(shè)計(jì)語(yǔ)言的發(fā)展帶來(lái)了日漸多變的運(yùn)行時(shí)存儲(chǔ)管理方案，主要分為兩大類，即（靜態(tài)存儲(chǔ)分配）方案和（動(dòng)態(tài)存儲(chǔ)分配）方 案。5.對(duì)編譯程序而言，輸入數(shù)據(jù)是（源程序），輸出結(jié)果是（目標(biāo)程 序）。三、名詞解釋題（共5小題，每小題4分，共20分）1.詞法分析54 / 81詞法分析的主要任務(wù)是從左向右掃描每行源程

44、序的符號(hào)，按照詞法規(guī)則從構(gòu)成源程序的字符串中識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的最小語(yǔ) 法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示（），送給語(yǔ)法分析程序。2.（1）文法若文法的任何兩個(gè)產(chǎn)生式A|都滿足下面兩個(gè)條件：(1)()()=;(2)若*，那么（）(A)=。我們把滿足這兩個(gè)條件的文法叫做（1）文法，其中的第一個(gè)L代表從左向右掃描輸入， 第一個(gè)L表示產(chǎn)生最左推導(dǎo)，1代表仕決定分析器的每步動(dòng)作時(shí)向前看個(gè)輸入符號(hào)。除了沒(méi)有公共左因子外，（1）文法還有一些明顯的性質(zhì),它不是二義的，也不含左遞歸。3.語(yǔ)法樹(shù)句子的樹(shù)結(jié)構(gòu)表示法稱為語(yǔ)法樹(shù)（語(yǔ)法分析樹(shù)或語(yǔ)法推導(dǎo)樹(shù)）。給定文法（P, S），對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)。這棵樹(shù)具有下列