《編譯原理》考試試題及答案（匯總）一、是非題（請在括號內(nèi)，正確的劃，，錯誤的劃X）（每個2分，共20分）編譯程序是對高級語言程序的解釋執(zhí)行。（x）TOC\o"1-5"\h\z一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。 （X）一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應。 （，）4．語法分析時必須先消除文法中的左遞歸 。（X）．分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準確地指出出錯地點。（V）.逆波蘭表示法表示表達式時無須使用括號。 （，）7．靜態(tài)數(shù)組的存儲空間可以在編譯時確定。 （X）8．進行代碼優(yōu)化時應著重考慮循環(huán)的代碼優(yōu)化， 這對提高目標代碼的效率將起更大作用。（X）9．兩個正規(guī)集相等的必要條件是他們對應的正規(guī)式等價。 （X）(X)10(X)多劃按錯二、選擇題(請在前括號內(nèi)選擇最確切的一項作為答案劃一個勾，多劃按錯論)(每個4分，共40分)1．詞法分析器的輸出結(jié)果是。1．詞法分析器的輸出結(jié)果是。A．()單詞的種別編碼C．()單詞的種別編碼和自身值正規(guī)式M1和M2等價是指。A.()M1和M2的狀態(tài)數(shù)相等的有向邊條數(shù)相等C.()M1和M2所識別的語言集相等向邊條數(shù)相等3.文法GS7所識別的語言是。B．()單詞在符號表中的位置D．()單詞自身值B.()M1和M2D.()M1和M2狀態(tài)數(shù)和有A.() B.()()*C.()(n>0) D.()x**4.如果文法G是無二義的，則它的任何句子 a。A．()最左推導和最右推導對應的語法樹必定相同B．()最左推導和最右推導對應的語法樹可能不同C．()最左推導和最右推導必定相同D．()可能存在兩個不同的最左推導，但它們對應的語法樹相同

5．構(gòu)造編譯程序應掌握。A．()源程序B．()目標語言C．()編譯方法D．()以上三項都是6．四元式之間的聯(lián)系是通過實現(xiàn)的。A．() 指示器CA．() 指示器C．() 符號表D．()程序變量.表達式([AVB)A(CVD)的逆波蘭表示為。A()[VAV B.()A[BVVAC.()VnVA D.()AiBVAV.優(yōu)化可生成的目標代碼。A． ()運行時間較短B．()占用存儲空間較小C． ()運行時間短但占用內(nèi)存空間大 D．()運行時間短且占用存儲空間小9．下列優(yōu)化方法不是針對循環(huán)優(yōu)化進行的。A.()強度削弱B．()刪除歸納變量C． ()刪除多余運算 D．()代碼外提10．編譯程序使用區(qū)別標識符的作用域。A. () 說明標識符的過程或函數(shù)名() 說明標識符的過程或函數(shù)的靜態(tài)層次C． () 說明標識符的過程或函數(shù)的動態(tài)層次D. () 標識符的行號三、填空題(每空1分，共10分)1．計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：解釋和編譯。2．掃描器是詞法分析器，它接受輸入的源程序，對源程序進行詞法分析并識別出一個個單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用。3．自上而下分析法采用移進、歸約、錯誤處理、接受等四種操作。4．一個分析器包括兩部分：一個總控程序和一張分析表。5．后綴式所代表的表達式是()。6．局部優(yōu)化是在基本塊范圍內(nèi)進行的一種優(yōu)化。四、簡答題(20分)簡要說明語義分析的基本功能。答：語義分析的基本功能包括 :確定類型、類型檢查、語義處理和某些靜態(tài)語義檢查?？紤]文法G[S]:S-(T)IIaT7|S消除文法的左遞歸及提取公共左因子。解：消除文法 G[S]的左遞歸：S-(T)IIa1T，f|￡提取公共左因子：S-(T)| 'S'f| ￡1T，fI￡試為表達式 ()*((10)+8)寫出相應的逆波蘭表示。解：wab+cde10-/+8+*+按照三種基本控制結(jié)構(gòu)文法將下面的語句翻譯成四元式序列：(A<CAB<D)(A>1)1;(A<D)2;}。解：該語句的四元式序列如下(其中E1、E2和E3分別對應AvCABvD、A>\和A<D,并且關(guān)系運算符優(yōu)先級高)：100(j<,102)101(,113)102(j<,104)103(,113)104(,1,106)105(,108)106(+,C,1,C)107(,112)108(j<,110)109(,112)110(+,A,2,A)111(,108)

112(,100)113為二義文法5.已知文法G[S]為S-,試證明文法G[S]為二義文法證明：由文法G[S]:S-,對句子對應的兩棵語法樹為:因此，文法G[S]為二義文法五.計算題(10分)已知文法判斷該文法是否是（1）文法，若是構(gòu)造相應分析表，弁對輸入串給出分析過程。解：增加一個非終結(jié)符后，產(chǎn)生原文法的增廣文法有：S'->A>&下面構(gòu)造它的（0）項目集規(guī)范族為abdSiA母AWaAdAT-aAb2十Li包e曲白廿Ii：SfInr吟qacc卜A今?曲A—I；L=A->aA'dA->aA*bI5:ATakidii乩TaAN%A-^aA.dlI;AT加從上表可看出，狀態(tài)I0和I2存在移進-歸約沖突，該文法不是（0）文法。對于I0來說有：（A）n{a}={}n{a}=①，所以在I0狀態(tài)下面臨輸入符號為a時移進，為時歸約，為其他時報錯。對于I2來說有也有與I0完全相同的結(jié)論。這就是說，以上的移進-歸約沖突是可以解決的，因此該文法是 （1）文法其(1)分析表為:GOTOabd0*itTj12良rir工Tj_33S為44玲玲玲L_5X111X111對輸入串給出分析過程為:步驟狀急棧符號桃輸入隼ACTIOMCOTO1◎#ab#&202b#Li59029b#s4-0234ftaAb*1501*acc一、是非題：.一個上下文無關(guān)文法的開始符，可以是終結(jié)符或非終結(jié)符。.()個句型的直接短語是唯一的。.(已)經(jīng)證明文法的二義性是可判定的。.(每)個基本塊可用一個表示。( ).每個過程的活動記錄的體積在編譯時可靜態(tài)確定。( ).2 型 文法一定是3型文法。一個句型一定句子。(算)符優(yōu)先分析法每次都是對句柄進行歸約。X()采用三元式實現(xiàn)三地址代碼時，不利于對中間代碼進行優(yōu)化。4譯"程中，語法分析器的任務是分析單詞是怎樣構(gòu)成的。()一個優(yōu)先表一定存在相應的優(yōu)先函數(shù)。 X

（目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。）（遞）歸下降分析法是一種自下而上分析法。TOC\o"1-5"\h\z（ 并） 不 是 每 個 文法都能改寫成（1） 文 法 。（ 每） 個 基 本 塊 只有一個入口和一個 出 口 。（一） 個（1）文法一定是無二義的。（ 逆） 波蘭 法 表 示的表達試亦稱前 綴 式 。（目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。）（正）規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。（一）個優(yōu)先表一定存在相應的優(yōu)先函數(shù)。3（）型文法一定是2型文法。22.如果一個文法存在某個句子對應兩棵不同的語法樹，則文法是二義（）性的。（）答案：1.x2.x3.x4. ，5. ，6.x7.x8.x9.V10.X11.X20.V13.X14.V15.V16.V17.X18.V19.VX21.V22.V20.填空題：編譯過程可分為（詞法分析），（語法分析），（語義分析與中間代碼生成），（優(yōu)化）和（目標代碼生成）五個階段。如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是（二義性的）。從功能上說，程序語言的語句大體可分為（執(zhí)行性 ）語句和（說明性）語句兩大類。語法分析器的輸入是（單詞符號 ），其輸出是（語法單位）。掃描器的任務是從（源程序中）中識別出一個個（單詞符號）。符號表中的信息欄中登記了每個名字的有關(guān)的性質(zhì)，如（類型、種屬、所占單元大小、地址）等等。一個過程相應的表的內(nèi)容為（現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址 ）常用的兩種動態(tài)存貯分配辦法是（棧式）動態(tài)分配和（堆式）動態(tài)分配。一個名字的屬性包括 （類型）和（作用域 ）常用的參數(shù)傳遞方式有 （傳地址），（傳值），（傳名）根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（局部優(yōu)化） ，（循環(huán)優(yōu)化），（全局優(yōu)化）三個級別。語法分析的方法大致可分為兩類，一類是（ 自上而下 ）分析法，另一類是（自下而上）分析法。預測分析程序是使用一張（分析表 ）和一個（符號棧）進行聯(lián)合控制的。17.一張轉(zhuǎn)換圖只包含有限個狀態(tài),其中有一個被認為是（初）態(tài)；而且實際上至少要有一個（終）態(tài)。19.語法分析是依據(jù)語言的（語法）規(guī)則進行。中間代碼產(chǎn)生是依據(jù)語言的（語義）規(guī)則進行的。.一個文法G若它的預測分析表M不含多重定義，則該文法是（（1）文法）文法。.對于數(shù)據(jù)空間的存貯分配一采用（靜態(tài)策%采用（動態(tài)）策略。.最右推導亦稱為（規(guī)范推導），由此得到的句知稱為（規(guī)范）句型。.對于文法G僅含終結(jié)符號的句型稱為（句子）。.所謂自上而下分析法是指（從開始符號出發(fā)，向下推導，推出句子）.局限于基本塊范圍的優(yōu)化稱（ 局部優(yōu)化）。.2型文法又稱為（上下文無關(guān)）文法；3型文法又稱為（正則）文.每條指令的執(zhí)行代價定義為（指令訪問主存次數(shù)加1）.算符優(yōu)先分析法每次都是對（最左素短語）進行歸約。三、名詞解釋題：.局部優(yōu)化局限于基本塊范圍的優(yōu)化稱。.二義性文法如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義性文法。3表過程的嵌套層次顯示表，記錄該過程的各外層過程的最新活動記錄的起始地址。.最左推導任何一步a=＞。都是對a中的最右非終結(jié)符替換。.語法一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。.文法描述語言的語法結(jié)構(gòu)的形式規(guī)則。.基本塊指程序中一順序執(zhí)行的語句序列， 其中只有一個入口和一個出口，入口就是其中的第一個語句，出口就是其中的最后一個語句。.語法制導翻譯在語法分析過程中，根據(jù)每個產(chǎn)生式所對應的語義子程序進行翻譯的辦法叫做語法制導翻譯。.短語令G是一個文法^S劃文法的開始符號，假定aB8是文法G的一個句型，如果有S=^aAS且A0B,則稱B是句型aB8相對非終結(jié)符A的短語。.待用信息如果在一個基本塊中，四元式 i對A定值，四元式j要引用A值，而從i至打之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。.規(guī)范句型由規(guī)范推導所得到的句型。.掃描器執(zhí)行詞法分析的程序。.超前搜索在詞法分析過程中，有時為了確定詞性，需超前掃描若干個字.句柄一個句型的最左直接短語。.語法制導翻譯在語法分析過程中，根據(jù)每個產(chǎn)生式所對應的語義程序進行翻譯的方法 叫做語法制導翻譯。.規(guī)范句型由規(guī)范推導所得到的句型。.素短語素短語是指這樣一個短語， 至少含有一個終結(jié)符，弁且，除它自身外不再含任何更小的素短語。

j要引用j要引用A

i的變量A.待用信息如果在一個基本塊中，四元式 i對A定值，四元式值，而從i至打之間沒有A的其它定值，則稱j是四元式的待用信息。.語義定義程序的意義的一組規(guī)則。四、簡答題：.寫一個文法G,使其語言為不以0開頭的偶數(shù)集。.已知文法G(S)及相應翻譯方案TOC\o"1-5"\h\z{ “1”}—a{ “2”}A—{ “3”}A—c { “4”}輸入，輸出是什么？.已知文法G(S)SA7(B|aB—)寫出句子b()b的規(guī)范歸約過程。.考慮卞面的程序：p(x,y,z);*z;2;*2;P(A,A,B);A,B.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出 A,B的值是什么？.文法G(S)-2aBf￡描述的語言是什么？.證明文法G(S)S-￡是二義性的。.已知文法G(S)S-A—dBfIc的預加分析表如下abcd#SS— 1S-1S-AAfA-AfAfdBBfB-B—c給出句子的分析過程。.寫一個文法G,使其語言為L(G)={l>=0,m>=1,n>=2}.已知文法G(S):S-(T)T的優(yōu)先關(guān)系表如下：關(guān)系a(),a--.>.>(<.<.=.<.)--.>.>,<.<..>.>請計算出該優(yōu)先關(guān)系表所對應的優(yōu)先函數(shù)表。.何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？.目標代碼有哪幾種形式？生成目標代碼時通常應考慮哪幾個問題？.一字母表2={a,b},試寫出2上所有以a為首的字組成的正規(guī)集相對應的正規(guī)式。.基本的優(yōu)化方法有哪幾種？.寫一個文法G,使其語言為L(G)={n>0}.考慮下面的程序：p(x,y,z);*;2;3;p(,b,a);a.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出 a的值是什么？.寫出表達式a+b*()的逆波蘭式和三元序列。.證明文法G(A)A—|(A)| ￡是二義性的。 **.令2={},則正規(guī)式aa表示的正規(guī)集是什么？.何謂表？其作用是什么？.考慮下面的程序：p(x,y,z)2;5；2；P(—a)；a.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出a的值是什么？.寫一人文法G,使其語言為L(G)={n>0為奇數(shù)，m>0為偶數(shù)}.寫出表達式()*()的逆波蘭式和三元序列。.一個文法G別是(1)文法的充要條件是什么？.已知文法G[S]S*||*F—I消除文法左遞歸和提公共左因子。.符號表的作用是什么？符號表查找和整理技術(shù)有哪幾種？答案：1.所求文法是G[S]:S—A0A-B-246881357|9A0.輸出是4231.句子b()b的規(guī)范歸約過程：步驟符號棧輸入串動作0#b()預備1()移進2()移進3(a)1移進4(A)1歸約5()移進6()移進7(B歸約8歸約9移進10接受.傳地址6,16傳值2,45(G)={>0,m>0}.因為文法G[S]存在句子有兩個不同的最左推導，所以文法G[S]是是二>>>>>>>>>>.句子的分析過程：

步驟符號棧步驟符號棧輸入串產(chǎn)生式01S一2B一34A一d56A一7B-c89B-c101112A一d13##8.所求文法是G[S]:S-A—DD—bB-9.函數(shù)a(),f4244g5523.優(yōu)化：對程序進行各種等價變換，使得從變換后的程序出發(fā), 能產(chǎn)生更有效的目標代碼。三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化.目標代碼通常采用三種形式： 機器語言，匯編語言，待裝配機器語言模應著重考慮的問題：(1)如何使生成的目標代碼較短；(2)如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；(3)如何充分利用指令系統(tǒng)的特點。.正規(guī)式a(a|b)* 。.刪除多余運算，代碼外提，強度削弱，變換循環(huán)控制條件，合弁已知量，復寫傳播和刪除無用賦值。.文法G[S]:S7|aB-.傳值2傳地址15.逆波蘭式：*

TOC\o"1-5"\h\z三元序列: 1 2- c d* b (1)/ (2) e+ a (3)G[S]是17.G[S]是因為文法G[S]存在句子()有兩個不同的最左推導，所以文法是二義性的。>>(A)>()>()>>>(A)=>().(a a)<……}一>>(A)>()>()>>>(A)=>().(a a)<……}一表:嵌套層次顯示表由于過程嵌套允許內(nèi)層過程引用外層過程定義的數(shù)據(jù)，因此，程運行時必須跟蹤它的所有外層過程的最新活動記錄起始地址，是用于登記每個外層過程的最新活動記錄起始地址。當一個過表就.傳地址12傳值5.所求文法是G[S]:S-Cf逆波蘭式Cf逆波蘭式*三元序列1 2+ b c* (1) e+ b c(4)(5)(3)(2)af(4)23(4)(5)(3)(2)af(4)23.一個爆G別是(1)文法的充要條件(如果消除左遞歸S-，|*Sn(*b)=①B=>￡,(a)n(A)=①FfI提公共左因子,文法G’(S)S-， |*，S'r*'| ￡F—'F'fF|￡25.作用：登記源程序中出現(xiàn)的各種名字及其信息，以及了解各階段的進展狀況。主要技術(shù)：線性表，對折查找，雜奏技術(shù)。五、計算題：1.設文法G(S):S -八IaI(T)T —IS⑴消除左遞歸；

⑵構(gòu)造相應的和集合；⑶構(gòu)造預測分析表語句⑵構(gòu)造相應的和集合；⑶構(gòu)造預測分析表語句ES改寫文法，使之適合語法制導翻譯；寫出改寫后產(chǎn)生式的語義動作。設文法G(S)：T7|S(1)計算和；(2)構(gòu)造優(yōu)先關(guān)系表。4.設某語言的語句的形式為i:=E(1)E/S其語義解釋為i:=E1:=E2)S;i:=i+1(1)寫出適合語法制導翻譯的產(chǎn)生式；(2)寫出每個產(chǎn)生式對應的語義動作。把語句a<10c>01*3-1;翻譯成四元式序列。設有基本塊*C*E22*S假設基本塊出口時只有M還被引用，請寫出優(yōu)化后的四元序列已知文法G(S)a1八I(T)T7|S給出句子 (a,())的最左推導；給出句型 (())的短語 ,直接短語，句柄。對于C語言SE語句改寫文法，使之適合語法制導翻譯；寫出改寫后產(chǎn)生式的語義動作。已知文法G(S)S-A—bBfd給出句子的最左推導及畫出語法樹；給出句型的短語、素短語。設文法G(S):S-(T)IIaT7|S⑴消除左遞歸和提公共左因子；⑵構(gòu)造相應的和集合；⑶構(gòu)造預測分析表。把語句X>0VY<0X>0*33;翻譯成四元式序列。已知文法G(S)E-ITT—T*F…(E)Ii給出句型 ()*的最左推導及畫出語法樹；給出句型 ()*的短語，素短語和最左素短語。設文法G(S)：S—T|SVTT—UAUUl^i1)計算和；2)構(gòu)造優(yōu)先關(guān)系表。答案：（1）消除左遞，文法變?yōu)镚'[S]:S-:IaI(T)′1|ST，f， |￡此文法無左公共左因子答案：（1）消除左遞，文法變?yōu)镚'[S]:S-:IaI(T)′1|ST，f， |￡此文法無左公共左因子(2)構(gòu)造相應的和集合：(S尸{a,八,(} ,(S)={#,,,)}(T)={a,八,(} ,(T)={}}(T)={,, ￡}，(F)={)}(3)構(gòu)造預測分析表：aA(),#SS一aS一人PS-(T)'TIIIT'一e「一，2.(1)(T產(chǎn){+,,(}(S)={a,)}(T產(chǎn){+,a,)}a+()a.>.>+<..><.r.> 「(<.<.<.=.).>.>>.E⑴4.(1)FS一(2)F-{(,E(i)；⑴e(2)⑴，_,(i))；(2)C-E{(,)；}S-⑴{(,S⑴.)}3.(1)(S)={a,(}(,E(2),_,)；；；(j<,(i),,2)；ShL0)}{(S(1),);(+,,1,);(j,_,_,);}5.⑴}5.⑴(j<,a,10',(3))(j,_,_,(12))(j>,c,‘0’,(5))(j,_,_,(8))(+,a,‘1’,T1))(,T1,_,a)(j,_,_,(1))(*,a,‘13’,T2)(-,T2, ‘1’,T3)(,T3,_,a)(j,_,_,(1))優(yōu)化后的四元序列*C*E20最左推導,())

短語,())

短語(())()()a直接短語a句柄(1)SfMlSiM2EM~^￡(2)MHs {;}S~MiSiM2E{(s 1,M2);(,M 1);;}.(i)>>>>短語 :,,d素短語:,dTOC\o"1-5"\h\z.(1)S「(L)| 'SfS|￡L 、L ' |￡(2)(S)={a,(}(S ；尸{a,(, ￡}(L)={a,(}(L )={,, ￡}(S)={,,),#}(S’)={,,),#}(L)={)}(L ’)={)}

()a,#SS-(L)S-，SS—SS'7￡S'7SS'7￡S'T￡LLf’LTL，、L'L'f￡.(1)(j>,X,0,(5))(j,_,_,(3))(j<,Y,0,(5))(j,_,_,(11))(j>0,X,0,(7))(j,_,_,(7))(*,A,3,T.(1)(j>,X,0,(5))(j,_,_,(3))(j<,Y,0,(5))(j,_,_,(11))(j>0,X,0,(7))(j,_,_,(7))(*,A,3,T1)(,T1,_,N)(j,_,_,(5))(j,_,_,(13))(+,B,3,T 2)(,T2,_,Y).(1)>>>T*>F*>(E)*>()*>()*=>()*>()*>()*>()*>()*=>()*>()*(2)短語i,F,,素短語i,

最左素短語(),()*i,()*(S)={V,A,i,-}(T)={A,i,-}(U)={i,-}(2)iVA-S.>.>V<..><.<.A<..>.><.-<..>.><.1、描述由正規(guī)式 b*(*)*(e)定義的語言，并畫出接受該語言的最簡。2、證明文法 E?E+|是(1)文法。3、下面是表達式和賦值語句的文法，其中的類型是‘？，+的類型是‘？，=的類型是'？，要求和E的類型都是或者都是。為該文法寫一個語法制導定義或翻譯方案，它完成類型檢查。S?EE?EE|E+E|E=E4、對于下面C語言文件f1(x){x;x=1;}f2(x){{x;x=1;}}某編譯器編譯時報錯如下：: ‘f1’::3:: ‘x’a請回答，對函數(shù) f2為什么沒有類似的警告錯誤。5、下面 C語言程序經(jīng)非優(yōu)化編譯后，若運行時輸入 2，則結(jié)果是12.566360,1073743076經(jīng)優(yōu)化編譯后，若運行時輸入 2，則結(jié)果是12.566360,1073743068請解釋為什么輸出結(jié)果有區(qū)別。(){s,,r;3.14159;("",);(",\n",*r*r,);}6、描述由正規(guī)式b*a(*a)*b*定義的語言，并畫出接受該語言的最簡。7、下面的文法產(chǎn)生代表正二進制數(shù)的 0和1的串集：B?B0|B1|1下面的翻譯方案計算這種正二進制數(shù)的十進制值：B?B0 {B i ' 2}| Bi1 {B i ' 2+1}|i{i}請消除該基礎(chǔ)文法的左遞歸，再重寫一個翻譯方案，它仍然計算這種正二進制數(shù)的十進制值。8、 在C語言中，如果變量i和j都是類型，請寫出表達式和表達式的類型表達式。為幫助你回答問題，下面給出一個程序作為提示，它運行時輸出i。(){i,j;(“n”,);}9、一個C語言的函數(shù)如下：(i)i;{j;j=i-1；(j);}下面左右兩邊的匯編代碼是兩個不同版本編譯器為該函數(shù)產(chǎn)生的代碼。左邊的代碼在調(diào)用之前將參數(shù)壓棧，調(diào)用結(jié)束后將參數(shù)退棧。右邊代碼對參數(shù)傳遞的處理方式?jīng)]有實質(zhì)區(qū)別。請敘述右

邊代碼對參數(shù)傳遞的處理方式弁推測它帶來的優(yōu)點TOC\o"1-5"\h\z|:|, | ,$4, | $8,8(), | 8(),I,-4() | ,-4()-4(), | -4(),I ,()I$4, |II編譯原理試卷八答案1、由正規(guī)式編譯原理試卷八答案1、由正規(guī)式b*(*)*(e)定義的語言是字母表｛a,b｝上不含子串的所有串的集合。最簡如下：2、先給出接受該文法活前綴的如下:I0和I3都只有移進項目，肯定不會引起沖突； I2和I4都無移進項目弁僅含一個歸約項目，也肯定不會引起沖突；在11中，E。的后繼符號只有$,同第2個項目的展望符號“+”不一樣，因此Ii也肯定不會引起沖突。由此可以斷定該文法是 (1)的。3、語法制導定義如下。TOC\o"1-5"\h\zS?E{(==)(==)}E?EiE2 { E i = E 2= }E?Ei+E2{ E i = E 2= }E?Ei=E2{ E i= E 2= }E? {()}4、對于函數(shù)fl,局部變量x聲明的作用域是整個函數(shù)體，導致在函數(shù)體中不可能訪問形式參數(shù)x。由于這是一個合法的C語言函數(shù)，因此編譯器給出警告錯誤。對于函數(shù)f2,由于局部變量x的作用域只是函數(shù)體的一部分，不會出現(xiàn)上述問題，因而編譯器不報錯。5、使用非優(yōu)化編譯時，變量s,,r在局部數(shù)據(jù)區(qū)都分配4個字節(jié)的空間。使用優(yōu)化編譯時，由于復寫傳播，*r*r變成3.14159*r*r,3.14159成為無用賦值而刪去，函數(shù)中不再有的引用，因此不必為分配空間。類似地，3.14159*r*r也是一個無用賦值(表達式要計算，但賦值是無用的)，也不必為s分配空間。這樣，和非優(yōu)化情況相比，局部數(shù)據(jù)區(qū)少了 8個字節(jié)，因此r的地址向高地址方向移動了8個字節(jié)。6、正規(guī)式b*a(*a)*b*體現(xiàn)的特點是，每個a的左邊都有若干b,除非a是第一個字母。該正規(guī)式定義的語言是：至少含一個a,但不含子串的所有a 和b的串集。最簡如下：7、 消除左遞歸后的文法：B?1B。B。？0B。|1B。|e相應的翻譯方案如下：B? 1{B。1}B。{B。}B。？ 0{B0B。’2}Bi宣B。B0| 1{B0B。'2+1}Bi{B。B耳|e{B。B。}8、表達式的類型表達式是 ()，表達式的類型表達式是。按照C語言的規(guī)定，指向同一個類型的兩個指針可以相加減，它們值的差是它們之間的元素個數(shù)。9、左邊的編譯器版本：一般只為局部變量分配空間。調(diào)用函數(shù)前，用若干次指令將參數(shù)壓棧，返回后用$n,一次將所有參數(shù)退棧(常數(shù) n根據(jù)調(diào)用前做了多少次來決定)。右邊的編譯器版本：除了為局部變量分配空間外，同時還為本函數(shù)中出現(xiàn)的函數(shù)調(diào)用的參數(shù)分配空間，并且參數(shù)所用空間靠近棧頂。調(diào)用函數(shù)前，用指令將參數(shù)移入棧頂，調(diào)用結(jié)束后無需參數(shù)退棧指令。優(yōu)點是每次函數(shù)調(diào)用結(jié)束后不需要執(zhí)行 $n,指令，另外增加優(yōu)化的可能性。三元式序列：三元式序列：12(*b,c)(*b,d)(+ (1),((3) ,a)《編譯原理》期末試題（三）1、從優(yōu)化的范圍的角度，優(yōu)化可以分哪兩類？對循環(huán)的優(yōu)化可以有哪三種？答：從優(yōu)化的范圍的角度，優(yōu)化可以分為局部優(yōu)化和全局優(yōu)化兩類；對循環(huán)的優(yōu)化有三種：循環(huán)不變表達式外提、歸納變量刪除與計算強度削減。2、寫出表達式**d對應的逆波蘭式、四元式序列和三元式序列。答：逆波蘭式：**四元式序列：TOC\o"1-5"\h\z⑴(* , b , c , t1)(2)(* , b , d , t2)⑶(+ , t1 , t 2, t3)(2))⑷(，t3,/,a)3、對于文法G(S):SbMbM(L|aLMa)

答：1)SbMbb(Lbb(Ma)b2)短語：)，()，b()b直接短語：)句柄：)三、 設有字母表｛a,b｝上的正規(guī)式()*解：(1)(2)將(1)所得的非確定有限自動機確定化(3)對(2)得到的化簡，合弁狀態(tài)0和2為狀態(tài)2:(4)令狀態(tài)1和2分別對應非終結(jié)符B和AG:A7￡;B-￡;可化簡為：G:A7￡;Bf&四、設將文法G改寫成等價的(1)文法，弁構(gòu)造預測分析表G:S-S**;T-解：消除左遞歸后的文法G:S-'|*'S'r*'|￡T7提取左公因子得文法G'：S7，「，

S'r*'|￡1T'f￡(S-，尸{a}(S7*')={*}(S7，)n(S"戶中(S，f*')={*}(S'-￡)(s')={#}(S'")n(S'7￡)=①「，)={十}(T'-T)(T)={+}(T'-￡)(「)={*}(T'-T)n(T’-￡)=①所以該文法是（1）文法預測分析表：*+a#S7*'一，S，7*'—￡T［一，—￡-T—￡6設文法G為:S—A;2￡;B~解：(1)拓廣文法G:(0)S'-S⑴S-A⑵A-⑶A-￡(4)B-⑸B-b;(A)={ ￡,a,b};(B)={a,b}構(gòu)造的如下:項目集規(guī)范族看出，不存在沖突動作。..?該文法是 （1）文法。(1)分析表如下:狀態(tài)ActionGotoaBSAB0S4S5r31*31ace2rl3SISi工3634SIS575r5rir56r2F：e4r4t4(3)輸入串的分析過程為:步驟狀態(tài)棧符號桂當甫字符軻余字符出動作⑴0言ababis移進⑵04如bab^移進⑶045%bab#舊約ETH?047標bBabfl歸的B4aE⑸(J3圮abu移進⑹034鋁ELb壯移進⑺0315*典的B->b0317鋁nB#必打B->nE(9)33哪歸納A->E'10：0336ifBBA#典均ATBA(11)036SBA也匏A今映(12)02"A白豹S^A0]襠&CC簡答題3、設有文法G[S]:S-S(S)?該文法是否為二義文法？說明理由。答：是二義的，因為對于()()可以構(gòu)造兩棵不同的語法樹?！?￡S(S)SS(S)S￡￡/&￡￡￡￡&五、給定文法G[S]:A;A7;B7;QH;A;

F-構(gòu)造相應的最小的用子集法將解：先構(gòu)造其:確定化：用子集法將將S、將S、AQ、、DXB重新命名，分別abSAQAAQQQDABDABBQD用0、1、2、3、4、5、6表示。因為3、4中含有z,所以它們?yōu)榻K態(tài)。令P0=({0,1,2,5,6},{3,4})用b進行分割:P仁({0,5,6},{1,2},{3,4})再用b進行分割：P2=({0},{5,6},{1,2},{3,4})再用a、b進行分割，仍不變。再令{0}為 A, {1,2}為B, {3, 4}為 C, {5,6}為D。最小化為右上圖。六、對文法G(S):S-a|八|(T) ;T-T,S|S答：⑴aA(),#a>>>A>>>

任何兩個終結(jié)符之間至多只有一種優(yōu)先關(guān)系。 (2分)(3)給出輸入串()#的算符優(yōu)先分析過程。步驟棧當前輸入字符剩余輸入用動作1#(#<(移進 ]2#(a)#(<a移進3#(a,a)#a>,歸約4#(N,a)#(<,移進5#(N,a)#,<a移進6 #()#a>)歸約7#(#,>)歸約8#(N) :#(=)移進91#(N)#)>#歸約10#接受FIRSTVT(S){a「,(}FIRSTVT(S){a「,(}FIRSTVT(T){-a「,(}LASTVT(S){a,\)}LASTVT(T){,,a,A,)}(2)是算符優(yōu)先文法，因為(<<<=<)>>>,<<<>>#<<<=一、簡述編譯程序的工作過程。(10)編譯程序的工作過程，是指從輸入源程序開始到輸出目標程序為止的整個過程，是非常復雜的，就其過程而言，一般可以劃分為五個工作階段：①詞法分析，對構(gòu)成源程序的字符串進行掃描和分解，識別出一個個的單詞；②語法分析，根據(jù)語言的語法規(guī)則,把單詞符號串分解成各類語法單位；③語義分析與中間代碼產(chǎn)生，即對各類語法單位，分析其漢一弁進行初步翻譯；④代碼優(yōu)化，以期產(chǎn)生更高效的代碼；⑤目標代碼生成，把中間代碼變換成特定機器上的低級語言指令形式。二、構(gòu)造下列正規(guī)式相應的(用狀態(tài)轉(zhuǎn)換圖表示)(15)1(0|1)*1⑵0*10*10*10*1 0,(|)* O01(1)12011111234⑶1三、給出下面語言的相應文法:L1={|n>1}(15)2={|n>1G1:A-G1:S一A一|B一| ￡四、對下面的文法G:S-a|b| (T)T—T,S|S(1)消去文法的左遞歸,得到等價的文法(2)判斷文法G2是否(1)文法，如果是,表。(15)G2;給出其預測分析G2:TOC\o"1-5"\h\zS-a|b| (T)T —'T '7,ST'| ￡G2是(1)文法ab()#SS-^aS^bS^(T)TI，T-，T一’T，一￡,S丁五、設有文法G[A]:Z|B~^|￡Cf||￡J|c計算該文法的每一個非終結(jié)符的集和集；試判斷該文法是否為(1)文法。(15)ABCDEbD是(1)文法六、對表達式文法G:E-|TT—T*F|FF-(E)|I(1)造各非終結(jié)符的和集合；(2)構(gòu)造文法的算符優(yōu)先關(guān)系表。(15)E*,+,(,i*,+,),iT*,(,i*,),iF(,i),i

算符優(yōu)先關(guān)系表+*I()#+><<<>>*>><<>>I>>>>(<<<<=)>>>>#<<<<=七、有定義二進制整數(shù)的文法如下:L7|BB-0|1構(gòu)造一個翻譯模式，計算該二進制數(shù)的值(十進制的值)(15)引入L、B的綜合屬性，翻譯模式為：S-L{()}TOC\o"1-5"\h\zL—LiB{L 1*2}L-B {}Bf0 {0}B—1 {1}《編譯原理》期末試題（五）一、單項選擇題（共10小題，每小題2分，共20分）.語言是A.句子的集合 B .產(chǎn)生式的集合C.符號串的集合 D .句型的集合.編譯程序前三個階段完成的工作是A.詞法分析、語法分析和代碼優(yōu)化B.代碼生成、代碼優(yōu)化和詞法分析C詞法分析、語法分析、語義分析和中間代碼生成D.詞法分析、語法分析和代碼優(yōu)化.一個句型中稱為句柄的是該句型的最左A.非終結(jié)符號B.短語C.句子D.直接短語.下推自動機識別的語言是A.0型語言 B .1型語言C2型語言 D .3型語言.掃描器所完成的任務是從字符串形式的源程序中識別出一個個具有獨立含義的最小語法單位即A.字符B.單詞C.句子D.句型.對應四種文法的四種語言之間的關(guān)系是A. L0A. L01L11L21L3 BC. L321L11L0 D.詞法分析的任務是A.識別單詞 BC.識別句子 D.常用的中間代碼形式不含A.三元式B.四元式.代碼優(yōu)化的目的是A.節(jié)省時間 BC.節(jié)省時間和空間D.L3LLiL。L01L11L23.分析句子的含義.生成目標代碼C.逆波蘭式 D.語法樹.節(jié)省空間.把編譯程序進行等價交換10.代碼生成階段的主要任務是A.把高級語言翻譯成匯編語言B.把高級語言翻譯成機器語言C.把中間代碼變換成依賴具體機器的目標代碼D.把匯編語言翻譯成機器語言二、填空題（本大題共5小題，每小題2分，共10分）.編譯程序首先要識別出源程序中每個（里回），然后再分析每個（句子）并翻譯其意義。.編譯器常用的語法分析方法有（自底向上）和（自頂向下）兩種。.通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的（允近），中間代碼生成、代碼優(yōu)化與目標代碼的生成則是對源程序的（綜合）。.程序設計語言的發(fā)展帶來了日漸多變的運行時存儲管理方案，主要分為兩大類，即（靜態(tài)存儲分配）方案和（動態(tài)存儲分配）方案。.對編譯程序而言，輸入數(shù)據(jù)是（源程序）,輸出結(jié)果是（目標程立）。三、名詞解釋題（共5小題，每小題4分，共20分）.詞法分析詞法分析的主要任務是從左向右掃描每行源程序的符號， 按照詞法規(guī)則從構(gòu)成源程序的字符串中識別出一個個具有獨立意義的最小語法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示（）、送給語法分析程序。.（1）文法若文法的任何兩個產(chǎn)生式A?a|b都滿足下面兩個條件：（a）?（b）=f；（2）若bT*e，那么（a）?（A）=f。我們把滿足這兩個條件的文法叫做（1）文法，其中的第一個L代表從左向右掃描輸入，第二個L表示產(chǎn)生最左推導，1代表在決定分析器的每步動作時向前看一個輸入符號。除了沒有公共左因子外， (1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。.語法樹句子的樹結(jié)構(gòu)表示法稱為語法樹 (語法分析樹或語法推導樹)。給定文法(-P,S),對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹。這棵樹具有下列特征：(1)根節(jié)點的標記是開始符號S。(2)每個節(jié)點的標記都是V中的一個符號。(3)若一棵子樹的根節(jié)點為A,且其所有直接子孫的標記從左向右的排列次序為AA…、那么A?AA…一定是P中的一條產(chǎn)生式。(4)若一標記為A的節(jié)點至少有一個除它以外的子孫，則__o(5)若樹的所有葉節(jié)點上的標記從左到右排列為字符串 w,則w是文法G的句型；若w中僅含終結(jié)符號，則w為文法G所產(chǎn)生的句子。.(0)分析器所謂(0)分析，是指從左至右掃描和自底向上的語法分析， 且在分析的每一步，只須根據(jù)分析棧當前已移進和歸約出的全部文法符號，并至多再向前查看0個輸入符號，就能確定相對于某一產(chǎn)生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當前所應采取的分析動作(是移進還是按某一產(chǎn)生式進行歸約等)。.語言和文法文法就是語言結(jié)構(gòu)的定義和描述，是有窮非空的產(chǎn)生式集合。文法G定義為四元組的形式：(…P,S)其中：是非空有窮集合，稱為非終結(jié)符號集合； 是非空有窮集合，稱為終結(jié)符號集合；P是產(chǎn)生式的集合（非空）；S是開始符號（或識別符號）。這里，n?,u,稱為文法G的字母表，它是出現(xiàn)文法產(chǎn)生式中的一切符號的集合。文法G所描述的語言用L（G）表示，它由文法G所產(chǎn)生的全部句子組成，即L（G）={ST*x,其中S為文法開始符號，且xVt}簡單的說，文法描述的語言是該文法一切句子的集合。四、簡答題（共4小題，每小題5分，共20分）.編譯程序和高級語言有什么區(qū)別？用匯編語言或高級語言編寫的程序，必須先送入計算機，經(jīng)過轉(zhuǎn)換成用機器語言表示的目標程序（這個過程即編譯），才能由計算機執(zhí)行。執(zhí)行轉(zhuǎn)換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉(zhuǎn)換過的叫目標程序、也就是機器語言。編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫的程序，按照一一對應的關(guān)系，轉(zhuǎn)換成用機器語言表刁二的程序。解釋型編譯程序?qū)⒏呒壵Z言程序的一個語句， 先解釋成為一組機器語言的指令，然后立即執(zhí)行，執(zhí)行完了，取下一組語句解釋和執(zhí)行，如此繼續(xù)到完成一個程序止。用解釋型編譯程序、執(zhí)行速度很慢、但可以進行人和計算機的"對話"，隨時可以修改高級語言的程序。語言就是解釋型高級語言。編譯型編譯程序?qū)⒓壵Z言編寫的程序，一次就會部翻譯成機器語言表示的程序， 而且過程進行很快，在過程中，不能進行人機對話修改。語言就是編譯型高級語言。.編譯程序的工作分為那幾個階段？詞法分析、語法分析和語義分析是對源程序進行的分析 （稱為編譯程序的前端），而中間代碼生成、代碼優(yōu)化和代碼生成三個階段合稱為對源程序進行綜合（稱為編譯程序的后端），它們從源程序的中間表示建立起和源程序等價的目標程序。.簡述自下而上的分析方法。所謂自下而上分析法就是從輸入串開始，逐步進行“歸約”，直至歸約到文法的開始符號；或者說從語法樹的末端開始，步步向上“歸約”，直到根節(jié)點。.簡述代碼優(yōu)化的目的和意義。代碼優(yōu)化是盡量生成“好”的代碼的編譯階段。也就是要對程序代碼進行一種等價變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下， 盡量使目標程序運行時所需要的時間短，同時所占用的存儲空間少。五、綜合應用題（共3小題，每小題10分，共30分）.證明下述文法G:S?是二義性文法。解：一個文法，如果存在某個句子有不只一棵語法分析樹與之對應，那么稱這個文法是二義性文法。句子有兩棵語法樹。如下圖：ddd

ddd由此可知，S茂義的文法是二義性文法。.對于文法G[S]:S?,A?,B德句型的全部短語、直接短語和句柄？ S句型的語法樹如圖五(2)明看A Ba解：為句型的相對于S的短語，為句型的相對于A的短語，為句型的相對于B的短語，且為直接短語，a為句型的相對于B的短語，且為直接短語和句柄。.設有非確定的有自限動機 ({A,B,C},{0,1},d,{A},{C}),其中：d(A,0)={C}d(A,1)={A,B}d(B,1)={C}d(C,1)={C}。請畫出狀態(tài)轉(zhuǎn)換距陣和狀態(tài)轉(zhuǎn)換圖。解：狀態(tài)轉(zhuǎn)換距陣為：01ACA,BBCCC狀態(tài)轉(zhuǎn)換圖為《編譯原理》期末試題（六）編譯原理樣題【 】1.型文法也稱為正規(guī)文法。[A]0 [B]1 [C]2 [D]3【 】2.文法不是（1）的。[A]遞歸[B]右遞歸[C]2型[D]含有公共左因子的】3.文法Ef*的句子i**i的不同語法分析樹的總數(shù)為。[A]1 [B]3 [C]5 [D]7】4.四元式之間的聯(lián)系是通過實現(xiàn)。[A] 臨時變量[B]指示器[C]符號表[D]程序變量【 】5.同心集合弁可能會產(chǎn)生的新沖突為。[A]二義[B]移進/移進[C]移進/歸約[D]歸約/歸約】6.代碼優(yōu)化時所依據(jù)的是。[A]語法規(guī)則[B]詞法規(guī)則[C]等價變換規(guī)則[D]語義規(guī)則】7.表達式（）*c的逆波蘭表示為o[A]*[B]*-[CJ [D]* （注：@/單目減運算符）】8.過程的表記錄了。[A]過程的連接數(shù)據(jù) [B] 過程的嵌套層次[C]過程的返回地址 [D] 過程的入口地址填空題.對于文法G1和G2,若有L(G1)(G2)(或G1和G2的語言相回，則稱文法G1和G2是等價的。.對于文法G[E]:JTf*FF-P八Pf(E),句型*的句柄是T,最左素短語是 T*F。.最右推導的逆過程稱為規(guī)范歸約 ,也稱為 最左歸約。.規(guī)范規(guī)約中的可規(guī)約串是句柄_,算符優(yōu)先分析中的可規(guī)約串是 最左素短語.(AVB)A(CV?DAE)的逆波蘭式是ABVCD?EEVAo.在屬性文法中文法符號的兩種屬性分別稱為繼承屬性 和綜合屬性(次序可換)。.符號表的每一項是由名字欄和 地址分配兩個欄目組成。在目標代碼生成階段，符號表是 地址分配的依據(jù)。.一個過程的表的內(nèi)容是它的 直接外層 的表的內(nèi)容加上本過程的的地址三有窮自動機M接受字母表S={0,1}上所有滿足下述條件的串：每個1都有0直接跟在右邊。構(gòu)造一個最小的 M及和M等價的正規(guī)式。三最小的DFAM如下圖所示:與E等價的正規(guī)式為：(0*|(10)*)*四證明正規(guī)式()*a與正規(guī)式a()*等價(用構(gòu)造他們的最小的

六對文法G[S]S7|PP-IQ7六對文法G[S]S7|PP-IQ7|a⑴它是否是算符優(yōu)先文法？請構(gòu)造算符優(yōu)先關(guān)系表⑵文法G[S]消除左遞歸、提取左公因子后是否是（1）文法？請證實。[][]1.求出G[S]的集和集:五寫一個文法，使其語言是:L={1nOmlmOn| >0}[]