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

編譯原理期末試題8套含答案大題集《編譯原理》期末試題（一）×個2分，共20分）2．一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。(×)3．一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。(√)4．語法分析時必須先消除文法中的左遞歸。(×)5．LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準確地指出出錯地點。(√)8高目標代碼的效率將起更大作用。(×)9．兩個正規(guī)集相等的必要條件是他們對應(yīng)的正規(guī)式等價。(×)10(×)(請在前括號內(nèi)選擇最確切的一項作為答案劃一個勾，多劃按錯論)(每個4分，共40分)．()單詞的種別編碼和自身值．()單詞自身值()M1和M2所識別的語言集相等()M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等()xyx()(xyx)*C()xnyxn(n≥0)D()x*yx*4．如果文法G是無二義的，則它的任何句子α_____。．(可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同5．構(gòu)造編譯程序應(yīng)掌握______。．(源程序．()目標語言C．()編譯方法．()以上三項都是6．四元式之間的聯(lián)系是通過_____實現(xiàn)的。∧8.優(yōu)化可生成_____的目標代碼。10．編譯程序使用_____區(qū)別標識符的作用域。1．計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：___解釋__和__編譯___。2．掃描器是__詞法分析器___，它接受輸入的__源程序_，對源程序進行___詞法分析__并識別出一個個單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用。3．自上而下分析法采用___移進__、歸約、錯誤處理、___接受_等四種操作。4．一個LR分析器包括兩部分：一個總控程序和一張分析表。5．后綴式abc-/所代表的表達式是___a/(b-c)__。6．局部優(yōu)化是在__基本塊___范圍內(nèi)進行的一種優(yōu)化。四、簡答題（20分）1.簡要說明語義分析的基本功能。答：語義分析的基本功能包括:確定類型、類型檢查、2.考慮文法G[S]:S→(T)|a+S|aT→T,S|S消除文法的左遞歸及提取公共左因子。S→(T)|a+S|aT→ST′T→ST′3.試為表達式w+(a+b)*(c+d/(e-10)+8)寫出相應(yīng)的逆波蘭表示。4.按照三種基本控制結(jié)構(gòu)文法將下面的語句翻譯成四元式序列：}。解：該語句的四元式序列如下其中、E2和E3分別對應(yīng)＜∧＜DA≥1和A≤D5.已知文法G[S]為S→aSb|Sb|bG[S]由文法G[S]，對句子aabbbb對應(yīng)的兩棵語法樹為：因此，文法G[S]為二義文法。S'->A下面構(gòu)造它的LR(0)項目集規(guī)范族為：從上表可看出,狀態(tài)I0和I2存在移進不是LR(0)文法。對于I0來說有：FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ，所以在I0狀態(tài)下面臨輸入符號為ab,d,#對于I2來說有也有與I0完全相同的結(jié)論。這就是說，以上的移進-歸約沖突是可以解決的，因此該文法是SLR(1)文法。對輸入串a(chǎn)b#給出分析過程為：《編譯原理》期末試題（二）一、是非題：1.一個上下文無關(guān)文法的開始符，可以是終結(jié)符或結(jié)2.一個句型的直接短語是唯一的。（）3.已經(jīng)證明文法的二義性是可判定的。（）4.每個基本塊可用一個DAG表示。（）6.2型文法一定是3型文法。（）7.一個句型一定句子。()8.算符優(yōu)先分析法每次都是對句柄進行歸約。X9.采用三元式實現(xiàn)三地址代碼時，不利于對中間代碼進行優(yōu)化。（）10.編譯過程中，語法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。()11.一個優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。()12.目標代碼生成時，應(yīng)考慮如何充分利用計算機的13.遞歸下降分析法是一種自下而上分析法。14.并不是每個文法都能改寫成LL(1)文法。()15.每個基本塊只有一個入口和一個出口。()16.一個LL(1)文法一定是無二義的。()17.逆波蘭法表示的表達試亦稱前綴式。()18.目標代碼生成時，應(yīng)考慮如何充分利用計算機的寄存器的問題。()20.一個優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。()21.3型文法一定是2型文法。()22.如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則文法是二義性的。()答案：1.×2.×3.×4.√5.√6.×7.×8.×9.√10.×11.×12.√13.×14.√15.√16.√17.×18.√19.√20.×21.√22.√二、填空題：2.編譯過程可分為（詞法分析）（語義分析與中間代碼生成代碼生成）五個階段。3.如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是（二義性的4.從功能上說，程序語言的語句大體可分為（執(zhí)行性）語句和（說明性類。源程序中個個（單詞符號7.符號表中的信息欄中登記了每個名字的有關(guān)的性8.一個過程相應(yīng)的DISPLAY表的內(nèi)容為(現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址)10.常用的兩種動態(tài)存貯分配辦法是（棧式）動態(tài)分配和（堆式）動態(tài)分配。11.一個名字的屬性包括(類型)和(作用12.常用的參數(shù)傳遞方式有名）13.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為14.語法分析的方法大致可分為兩類，一類是（自和一個（符號棧）進行聯(lián)合控制的。17.一張轉(zhuǎn)換圖只包含有限個狀態(tài),其中有一個被認為是（初）態(tài);而且實際上至少要有一個（終）態(tài)。19.語法分析是依據(jù)語言的（語法）規(guī)則進行。中間代碼產(chǎn)生是依據(jù)語言的（語義）規(guī)則進行的。21.一個文法M不含多重定義，則該文法是（LL(1)文法）文法。22.對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用(靜態(tài)策略，PASCAL采用(動態(tài))策略。24.稱為（規(guī)范）句型。26.對于文法G，僅含終結(jié)符號的句型稱為(句27.所謂自上而下分析法是指(從開始符號出發(fā)，向下推導(dǎo)，推出句子）31.2型文法又稱為（上下文無關(guān)）文法；3型文法又稱為（正則）文法。32.每條指令的執(zhí)行代價定義為(指令訪問主存次數(shù)加1）33.算符優(yōu)先分析法每次都是對(最左素短語）進行歸約。1.局部優(yōu)化-------局限于基本塊范圍的優(yōu)化稱。2.二義性文法------如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義性文法。3.DISPLAY表----過程的嵌套層次顯示表，記錄該過程的各外層過程的最新活動記錄的起始地址。5.最左推導(dǎo)------任何一步α=>β都是對α中的最右非終結(jié)符替換。6.語法------一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。7.文法------描述語言的語法結(jié)構(gòu)的形式規(guī)則。8.基本塊------指程序中一順序執(zhí)行的語句序列，其中只有一個入口和一個出口，入口就是其中的第一個語句，出口就是其中的最后一個語句。9.語法制導(dǎo)翻譯------在語法分析過程中，根據(jù)每個產(chǎn)生式所對應(yīng)的語義子程序進行翻譯的辦法叫做語法制導(dǎo)翻譯。10.短語------令G是一個文法，S劃文法的開始符號，假定αβδ是文法GSαAδ且Aβ，則稱β是句型αβδ相對非終結(jié)符A的短語。i對A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。12.規(guī)范句型------由規(guī)范推導(dǎo)所得到的句型。13.掃描器------執(zhí)行詞法分析的程序。14.超前搜索------在詞法分析過程中，有時為了確定詞性，需超前掃描若干個字符。15.句柄------一個句型的最左直接短語。16.語法制導(dǎo)翻譯------在語法分析過程中，根據(jù)每個產(chǎn)生式所對應(yīng)的語義程序進行翻譯的方法叫做語法制導(dǎo)翻譯。17.規(guī)范句型------由規(guī)范推導(dǎo)所得到的句型。18.素短語------素短語是指這樣一個短語，至少含有一個終結(jié)符，并且，除它自身外不再含任何更小的素短語。19.語法------是組規(guī)則，用它可形成和產(chǎn)生一個合式的程序。i對A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。1.寫一個文法G,使其語言為不以0開頭的偶數(shù)集。2.已知文法G(S)及相應(yīng)翻譯方案寫出句子b(aa)b的規(guī)范歸約過程。procedurep(x,y,z)；beginA:=2;試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出A,B的值是什么?5．文法G(S)S→dAB是二義性的。7.已知文法G(S)S→BAacd#b給出句子adccd的分析過程。8.寫一個文法G,使其語言為L(G)={abcab|l>=0,lmlnn12.一字母表Σ={a,b}，試寫出Σ上所有以a為首的字組成的正規(guī)集相對應(yīng)的正規(guī)式。13.基本的優(yōu)化方法有哪幾種？procedurep(x,y,z);beginbegina:=2;b:=3;試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出a的值是什么?16.寫出表達式a＋b*(c-d)/e的逆波蘭式和三元序列。17.證明文法G(A)18.令Σ={a,b}，則正規(guī)式ab|ba表示的正規(guī)集是什**beginz:=z+x;enda:=5;b:=2;試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出a的值是什么?21.寫一個文法G,使其語言為L(G)={abc|n>0為nnm22.寫出表達式a:=(b+c)*e+(b+c)/f的逆波蘭式和三元消除文法左遞歸和提公共左因子。25.符號表的作用是什么？符號表查找和整理技術(shù)有哪幾種？3.句子b(aa)b的規(guī)范歸約過程：步驟符號棧輸入串0#(aa)b#2#b(3#b(a歸約移進因為文法G[S]存在句子aa有兩個不同的最左推導(dǎo)，所以文法G[S]是是二義性的。S=>SaS=>SaSaS=>aSaS=>aaS=>aa7.句子adccd的分析過程：dccd#ccd#ccd#cd#cd#d#d#9.10.優(yōu)化：對程序進行各種等價變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標代碼。三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化11.目標代碼通常采用三種形式：機器語言，匯編語言，待裝配機器語言模塊。(1)如何使生成的目標代碼較短；(2)如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；13.刪除多余運算，代碼外提，強度削弱，變換循環(huán)控制條件，合并已知量，復(fù)寫傳播和刪除無用賦值。14.文法G[S]:oparg1arg2cdb因為文法G[S]存在句子()有兩個不同的最左推導(dǎo)，所以文法G[S]是是二義性的。A=>AA=>(A)A=>()A=>()A=>AA=>A=>(A)=>()**19.Display表:嵌套層次顯示表由于過程嵌套允許內(nèi)層過程引用外層過程定義的數(shù)過程的最新活動記錄起始地址，display表就是用于登記每個外層過程的最新活動記錄起始地址。20.傳地址a=12S→AC22.逆波蘭式abc+e*bc+f/+:=(1)becf*提公共左因子,文法G’(S)S→aFS’|*aFS’25.作用：登記源程序中出現(xiàn)的各種名字及其信息，以及了解各階段的進展狀況。主要技術(shù)：線性表，對折查找，雜奏技術(shù)。五、計算題：(1）計算FIRSTVT和LASTVT；（2）構(gòu)造優(yōu)先關(guān)系表。4.設(shè)某語言的for語句的形式為fori:＝EtoEdoS其語義解釋為again:ifi＜＝LIMITthenBeginS;ifc>0thena:=a+1elsea:=a*3-1;假設(shè)基本塊出口時只有M還被引用，請寫出優(yōu)化后的四元序列。thenwhileX>0doX:=A*3(2)給出句型(E+T)*i+F的短語，素短語和最左素短語。13.設(shè)文法()SS→aS→^S→(TS→CSa>.>>S→FS(2)F→fori:=EtoEdo{GEN(:=,E.place,_,entry(i));F.place:=entry(i);LIMIT:=Newtemp;GEN(+,F.place,1,F.place);GEN(j,_,_,F.QUAD);S.chain:=F.chain}5.(1)(j<,a,‘10’,(3))(2)(j,_,_,(12))(3)(j>,c,‘0’,(5))(5)(+,a,‘1’,T1))(8)(*,a,‘13’,T2)(9)(-,T2,‘1’,T3)短語T,ST,S句柄T,S8.(1)S→doMSwhileMEM→ε112→112121S.nextlist=E.falelist;}10.(1)S→(L)|aS’S’→S|εL→SL’FIRST(S’)={a,(,ε}FIRST(L)={a,FOLLOW(S’)={,,),#}FOLLOW(L)={),#’L’→εL’1(9)(j,_,_,(5))122LASTVT(S)={∨,∧,i,-}LASTVT(T)={∧,i,-}LASTVT(U)={i,-}-《編譯原理》期末試題（二）3、下面是表達式和賦值語句的文法，其中andintint，的類型是intint:=要求id和E的類型都是int或者都是。為該文檢查。EEandE|E+E|E=E|id4、對于下面C語言文件s.cf1(intx){longx;x=1;}f2(intx){{longx;x=1;}}某編譯器編譯時報錯如下：s.c:Infunctionf1’:s.c:3:warning:declarationof‘’shadowsaparameter{floats,pi,r;pi=3.14159;scanf("%f",&r);addr=%d\n",}BB0|B1|111118、在C語言中，如果變量i和j都是long類為提示，它運行時輸出1。main(){longi,j;printf(“”,&j);}func(j);}pushl%ebp|pushl%ebpmovl%esp,%ebp|movl%esp,%ebpsubl$4,%esp|subl$8,%espmovl8(%ebp),%edx|movl8(%ebp),%eaxdecl%edx|decl%eaxmovl%edx,-4(%ebp)|movl%eax,-4(%ebp)movl-4(%ebp),%eax|movl-4(%ebp),%eaxpushl%eax|movl%eax,(%esp)callfunc|callfuncaddl$4,%esp|leave2如下：EEEEEEEE+iE032413、語法制導(dǎo)定義如下。Sid:=E{S.type:=if(id.type=boolandE.type=bool)or(id.type=intandE.type=int)thentype_okelsetype_error}EEandE{E.type:=ifE.type=bool1212EE+E{E.type:=ifE.type=intand121E.type=intthenintelsetype_error}2EE=E{E.type:=ifE.type=intand1212Eid{E.type:=lookup(id.entry)}ba210|1|相應(yīng)的翻譯方案如下：11.val}1|1.i:=.i2+1}{B.val:=11.val}1|.val:=}《編譯原理》期末試題（三）1、答：從優(yōu)化的范圍的角度，優(yōu)化可以分為局部優(yōu)化和全局優(yōu)化兩類；四元式序列：(3)(+(1)，(2))(4)(:=(3)，a)(4)(:=，t3，/，a)SSbMbb(Lbb(Ma)b2）短語:Ma)，(Ma)，b(Ma)bbMb直接短語:Ma)句柄:Ma)(設(shè)有字母表{a，b}上的正規(guī)式R=(ab|a)*。Ma)（2）將（1）所得的非確定有限自動機確定化εab-01+3（4）令狀態(tài)1和2分別對應(yīng)非終結(jié)符B和A設(shè)將文法G改寫成等價的LL(1)文法，并構(gòu)造預(yù)測分析表。Select(S→aTS’)={a}Select(S→*aTS’)={*}Select(S→aTS’)∩Select(S→*aTS’)=ФSelect(S’→*aTS’)={*}Select(S’→ε)=Follow(s’)={#}Select(S’→*aTS’)∩Select(S’→ε)=ФSelect(T→+aT’)={+}Select(T’→T)=First(T)={+}Select(T’→ε)=Follow(T’)={*,#}Select(T’→T)∩Select(T’→ε)=Ф所以該文法是文法。預(yù)測分析表：T6設(shè)文法G為：S→A；A→BA|ε；B→aB|b項目集規(guī)范族看出，不存在沖突動作?！嘣撐姆ㄊ荓R(1)文法。（2）LR(1)分析表如下：S令P＝（｛0,1,2,5,6｝｛3,4｝）用b進行分割：0FIRSTVT(S)a,^,(}FIRSTVTT){,,a,^,(}LASTVT(S)a,^,)}LASTVTT){,,a,^,)}a^(),#>>>(<<<=<(2)是算符優(yōu)先文法，因為任何兩2分）,<<<>>(3)給出輸入串(a,a)#的算符優(yōu)先分析過程。步驟1棧當(dāng)前輸入字符剩余輸入串動作《編譯原理》期末試題（四）（）letter（letter|）*5111）L={ab|n≥1}L={aba|n≥1，≥0}nnnm+nm12G1：四、對下面的文法：S→a|b|（T）→a|b|（T）T→ST’T’→，ST’|G2是LL（1）文法。（T）TT→T→T→ST’ST’ST’T’(1)計算該文法的每一個非終結(jié)符的FIRST集和FOLLOW集；(2)試判斷該文法是否為LL（15）FIRSTCA,c,dDDA,b,c,g六、對表達式文法：E→E+T|TT→T*F|FF→(E)|IE*，i*，i+*II=11《編譯原理》期末試題（五）一、單項選擇題共10小題，每小題2分，共20分)1．語言是B．短語C．句子CALLLL0123．LLLL3210C．L=LLL32100123．分析句子．生成目標的含義8．常用的中間代碼形式不含D．語法樹9．代碼優(yōu)化的目的是A．節(jié)省時間．節(jié)省空間．把編譯程10．代碼生成階段的主要任務(wù)是．把高級語言翻譯成匯編語言．把高級語言翻譯成機器語言C．把中間代碼變換成依賴具體機器的目標代．把匯編語言翻譯成機器語言1．詞法分析2．LL(1)文法若文法的任何兩個產(chǎn)生式A都滿足下面兩個條件：))=；（2）若*，那么FOLLOW(A)=。NT型都能構(gòu)造與之關(guān)聯(lián)的RRN4．分析器5．語言和文法NTNTNTNNT}T3．簡述自下而上的分析方法。五、綜合應(yīng)用題共3小題，每小題10分，共30分)1．證明下述文法：SaSbS|aS|d是二義性文法。解：文法是二義性文法。SaSa(1)(2)B句型baSb的語法樹如圖五(2)所示。bba解：狀態(tài)轉(zhuǎn)換距陣為：01ABCCC11AB《編譯原理》期末試題（六）【013【型。。。[D]ab@c-*。]]和TT*F。?！拧摹拧摹：?。本過程的SP的地址0M1四：】五L＝{1010|0}nmmn五A→0A1|εFIERSTVT(P)=LASTBVT（P）={c}FIERSTVT(Q)={a}LASTBVT（Q）={a}構(gòu)造優(yōu)先關(guān)系表為：abc<>b<>>>c）A→eSA82→·aAd,#ecI：S→9八十（1）傳值；（2）傳地址25；（3）傳名45十為()語義規(guī)則BS{;;;；《編譯原理》期末試題（七）S-屬性文法是只含有綜合屬性的屬性文法。1113400III01{0,1,2}{1,2}{1,2,3}{1,2,3}{1,2,3,4}{1,2,3}{1,2,3,4}01010040111四、對于文法G(E):(8分)T|E+TF|T*F(E)|i1.寫出句型(T*F+i)的最右推導(dǎo)并畫出語法樹。2.寫出上述句型的短語，直接短語、句柄和素短語。ET(E)(E+T)(E+F)短語：(T*F+i),T*F+i,T*F,i直接短語：T*F,i句柄：T*F素短語：T*F,i五、設(shè)文法G(S)：(12分)1．構(gòu)造各非終結(jié)符的FIRSTVT和LASTVT集合；2．構(gòu)造優(yōu)先關(guān)系表和優(yōu)先函數(shù)。(12分)答：(6分)FIRSTVT(S)={，+，，(}FIRSTVT(A)={，，(}FIRSTVT(B)={，(}LASTVT(S)={i，，，(}LASTVT(A)={，*，(}LASTVT(B)={*，(}i)<<*i+()*>>><<>>i()21六、設(shè)某語言的do-while語句的語法形式為(9分)Sdo(1)WhileE(2)寫出每個產(chǎn)生式對應(yīng)的語義動作。答：(1).適合語法制導(dǎo)翻譯的文法(3分){U.QUAD:=R.QUAD;WhileME(1)12Mε{M.QUAD:=NXQ}SdoM(1)WhileME12(1)21七、(8分將語句100，，，102)101，，，109)102，B，0，104)103，，，109)104，，0，106)105，，，109)106，，，T1)107，T1，，C)108，，，104)109B:=T6A/+nnnTnTR3S4(2)四元式序列：(4分)T1:=S+RT4:=S/RA:=T1-T4B:=T1*4(1)SBB(2)BaB(3)b的LR分析表如下0s3s4121acc2s6s73s3s44r3r356s6s797步驟狀態(tài)符號輸入串a(chǎn)bab#bab#ab#ab#ab#026b#《編譯原理》期末試題（八）415分）就下面文法?給出一個語法制導(dǎo)定義，它輸出配對括號的個數(shù)。?給出一個翻譯方案，它輸出每個a的嵌套深度。如句子(a,(a,a)，第一小題的輸出是2，第二小題的輸出是122。func(i1,i2,i3)longj1,j2,j3;printf("Addressesofi1,i2,i3=%o,%o,%o\n",&i1,&i2,&i3);printf("Addressesofj1,j2,j3=%o,%o,%o\n",&j1,&j2,&j3);.file"static.c".version"01.01"gcc2_compiled.:.data.sizefunc,.Lfe1-funcAABoth2*/45LR（1）文法SABAaaAb|ab|BBb|3．intid,$R,idRRprint(S.num)LL,SLSL.num:=L.num+S.numL.num:=S.num11L{L.depth:=L.depth}L,{S.depth:=L.depth}S11L{S.depth:=L.depth}S5．t:=initial1t:=final2ift>tgotoL112v:=1L2:stmtifv=tgotoL12v:=v+1gotoL2AB?將S提交給CC進行編譯，得到一個可執(zhí)行程序。BA?將S提交給上述可執(zhí)行程序進行編譯，得到所需的編譯器CC。BB《編譯原理》期末大題1.設(shè)有如下文法（S—>Sa|a2.試構(gòu)造與下面G（S）等價的無左遞歸的文法。N—>Sd|Ne|f→fN|cS,S→′′′|,N→eN′|B—>b|ε①求各產(chǎn)生式的FIRSTFOLLOW(B),以及各產(chǎn)生式的SELECT集。②構(gòu)造LL(1)分析表，并分析符號串baabbb是否是。解：（1）FIRST(aBc)={a},FIRST(bAB)=FIRST(aAb)={a},A→b:→b)=,B→b:FIRST(b)=,FIRST(εε}FOLLOW(A)