編譯原理試題庫

一填空題1．編譯程序首先要識別出源程序中每個，然后再分析每個并翻譯其意義。單詞，句子2．編譯器常用的語法分析方法有和兩種。自底向上，自頂向下2．通常把編譯過程分為分析 與綜合兩大階段。詞法、語法和語義分析是對源程序的分析，中間代碼生成、代碼優(yōu)化與目標代碼的生成則是對源程序的綜合。前端，后端4．程序設(shè)計語言的發(fā)展帶來了日漸多變的精品文庫運行時存儲管理方案，主要分為兩大類，即 方案和 分配方案。靜態(tài)存儲分配，動態(tài)存儲5．對編譯程序而言，輸入數(shù)據(jù)是 ，輸出結(jié)果是 。源程序，目標程序6．文法G包括四個組成部分：一組終結(jié)符號，一組非終結(jié)符號，一組 ，以及一個開始符號。產(chǎn)生式7．文法按產(chǎn)生式的形式分為四種類型，它們是：0型文法，又稱短語文法；1型文法，又稱上下文有關(guān)文法；2型文法，又稱 ；3型文法，又稱 。上下文無關(guān)文法，正規(guī)文法歡迎下載 2精品文庫8．最右推導稱為，由規(guī)范推導產(chǎn)生的句型稱為規(guī)范句型。規(guī)范推導9．設(shè)G是一個文法，S是它的開始符號，如果S=>*α，則稱α是一個 。僅由終結(jié)符號組成的句型是一個 。句型，句子10對于一個文法 G而言，如果L(G)中存在某個句子對應(yīng)兩棵不同，那么該文法就稱為是二義的。語法樹11．通常程序設(shè)計語言的單詞符號分為五種：基本字、、常數(shù)、算符、界限符。歡迎下載 3精品文庫標識符12．在自底向上分析法中， LR分析法把“可歸約串”定義為 。句柄13．編譯中常用的中間代碼形式有逆波蘭式、三元式、 和四元式等。樹代碼14．對中間代碼優(yōu)化按涉及的范圍分為 ， 和全局優(yōu)化。局部優(yōu)化，循環(huán)優(yōu)化15．局部優(yōu)化主要包括、利用公共子表達式和刪除無用賦值等內(nèi)容。合并已知量16．為了構(gòu)造不帶回溯的遞歸下降分析程歡迎下載 4精品文庫序，我們通常要消除 和提取左遞歸，左公共因子17.計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑： 和。解釋執(zhí)行，編譯執(zhí)行18.掃描器是詞法分析，它接收輸入的 ，對源程序進行詞法分析并識別出一個個 ，供語法分析器使用。源程序，單詞符號19.自下而上分析法采用 ， ，和 等四種操作。移進、規(guī)約、錯誤處理、接受20.一個LR分析器包括兩部分： 一個總控程歡迎下載 5精品文庫序， 和分析棧。一張分析表21.后綴式abc-/所代表的表達式是 。a/(b-c)22.局部優(yōu)化是在 范圍內(nèi)進行的一種優(yōu)化?；緣K不同的編譯程序關(guān)于數(shù)據(jù)空間的存儲分配策略可能不同，但大部分編譯中采用的方案有兩種：靜態(tài)存儲分配方案和動態(tài)存儲分配方案，而后者又分為和 。棧式動態(tài)存儲分配，堆式動態(tài)存儲分配24.規(guī)范規(guī)約是 。歡迎下載 6精品文庫最左規(guī)約25.編譯程序的工作過程一般劃分為 5個階段：詞法分析、 、語義分析與中間代碼生成，代碼優(yōu)化及目標代碼生成。另外還有 和出錯處理。語法分析，表格管理26．表達式x+y*z/(a+b)的后綴式為 。xyz*ab+/+27．文法符號的屬性有綜合屬性和 。繼承屬性28．假設(shè)二位數(shù)組按行存放，而且每個元素占用一個存儲單元，則數(shù)組a[1..15,1..20]歡迎下載 7精品文庫某個元素a[i，j]的地址計算公式為 。a+(i-1)*20+j-129．局部優(yōu)化是局限于一個 范圍內(nèi)的一種優(yōu)化。基本塊二選擇題1．語言是A．句子的集合 B．產(chǎn)生式的集合C．符號串的集合 D．句型的集合A2．編譯程序前三個階段完成的工作是歡迎下載 8精品文庫．詞法分析、語法分析和代碼優(yōu)化B．代碼生成、代碼優(yōu)化和詞法分析C．詞法分析、語法分析、語義分析和中間代碼生成D．詞法分析、語法分析和代碼優(yōu)化C3．一個句型中稱為句柄的是該句型的最左A．非終結(jié)符號B．短語C．句子D．直接短語D4．下推自動機識別的語言是A．0型語言B．1型語言C．2型語言D．3型語言C5．掃描器所完成的任務(wù)是從字符串形式的源程序中識別出一個個具有獨立含義歡迎下載 9精品文庫的最小語法單位即A．字符B．單詞 C．句子 D．句型B6．對應(yīng)Chomsky四種文法的四種語言之間的關(guān)系是A.L0 L1 L2 L3B.L3 L2 L1 L0C.L3=L2 L1 L0D．L0 L1 L2=L3B7．詞法分析的任務(wù)是A．識別單詞 B．分析句子的含義C．識別句子 D．生成目標代碼A8．常用的中間代碼形式不含A．三元式 B．四元式歡迎下載 10精品文庫C．逆波蘭式 D．語法樹D9．代碼優(yōu)化的目的是A．節(jié)省時間 B．節(jié)省空間C．節(jié)省時間和空間D．把編譯程序進行等價交換C10．代碼生成階段的主要任務(wù)是．把高級語言翻譯成匯編語言B．把高級語言翻譯成機器語言C．把中間代碼變換成依賴具體機器的目標代碼D．把匯編語言翻譯成機器語言C一個上下文無關(guān)文法G包括四個組成部分：一組終結(jié)符，一組非終結(jié)符，一個歡迎下載 11精品文庫（），以及一組（）。A．字符串 B．產(chǎn)生式C．開始符號 D． 文法C,B12.程序的基本塊是指（ ）。A．一個子程序 B．一個僅有一個入口和一個出口的語句C．一個沒有嵌套的程序段 D．一組順序執(zhí)行的程序段，僅有一個入口和一個出口D高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于（）分析方法。A．自左向右 B．自頂向下C．自底向上 D．自右向左歡迎下載 12精品文庫C14．在通常的語法分析方法中，（）特別適用于表達式的分析。A．算符優(yōu)先分析法 B. LR分析法C．遞歸下降分析法 D. LL（1）分析法A15．經(jīng)過編譯所得到的目標程序是（ ）。A．四元式序列 B．間接三元式序列C．二元式序列 D．機器語言程序或匯編語言程序D16．一個文法所描述的語言是（）；描述一個語言的文法是（）。A．唯一的B．不唯一的C．可能唯一，也可能不唯一歡迎下載 13精品文庫A,C17.詞法分析器的輸出結(jié)果是（） 。A.單詞的種別,編碼B.單詞在符號表的位置C.單詞的種別編碼和自身值D.單詞自身值C18.正規(guī)式M1和M2等價是指（）。A.M1和M2的狀態(tài)相等B.M1和M2的有向邊條數(shù)相等C.M1和M2所識別的語言集相等D.M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等C19.文法G:S→xSx|y所識別的語言是（）。A.xyx B.(xyx)* C.xnyxnD.x*yx*C20.如果文法G是二義的，則它的任何句子歡迎下載 14精品文庫α（）最左推導和最右推導對應(yīng)的語法樹必定相同B.最左推導和最右推導對應(yīng)的語法樹可能不同C.最左推導和最右推導必定相同D.可能存在兩個不同的最左推導但是他們對應(yīng)的語法樹相同。A21.構(gòu)造編譯程序應(yīng)掌握（）A.編譯程序 B.目標語言 C.編譯方法 D.以上三項都是D22.四元式之間的聯(lián)系是通過（）實現(xiàn)的。A.指示器 B.臨時變量C.符號表 D.程序變量歡迎下載 15精品文庫B23.程序的基本塊是指（）A.一個子程序 B.一個僅有一個入口和一個出口C.一個沒有嵌套的程序段 D.一組順序執(zhí)行的程序段，僅有一個入口和一個出口D24.優(yōu)化可生成（）的目標代碼。運行時間較短B.占用存儲空間較小C.運行時間短但占用內(nèi)存空間大D.運行時間短且占用存儲空間小D25.下列（）優(yōu)化方法不是針對循環(huán)優(yōu)化進行的。歡迎下載 16精品文庫A.強度削弱 B.刪除歸納變量C.刪除多余運算 D.代碼外提C26.編譯程序使用（）區(qū)別標識符的作用域說明標識符的過程或者函數(shù)名B.說明標識符的過程或函數(shù)的靜態(tài)層次C.說明標識符的過程或函數(shù)的動態(tài)層次D.標示符的行號B三名詞解釋1．詞法分析詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號，按照詞法規(guī)則從構(gòu)成源程序的字符串中識別出一個個具有獨立意義的歡迎下載 17精品文庫最小語法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。2．LL(1)文法若文法的任何兩個產(chǎn)生式 A | 都滿足下面兩個條件：（1）FIRST( ) FIRST( )= ；2）若*，那么FIRST()FOLLOW(A)= 。我們把滿足這兩個條件的文法叫做LL(1)文法，其中的第一個L代表從左向右掃描輸入，第二個L表示產(chǎn)生最左推導，1代表在決定分析器的每步動作時向前看一個輸入符號。除了沒有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。3．語言和文法文法就是語言結(jié)構(gòu)的定義和描述， 是有窮非歡迎下載 18精品文庫空的產(chǎn)生式集合。文法G定義為四元組的形式：G=(VN，VT，P，S)其中：VN是非空有窮集合，稱為非終結(jié)符號集合；VT是非空有窮集合，稱為終結(jié)符號集合；P是產(chǎn)生式的集合(非空)；S是開始符號(或識別符號)。這里，VN∩VT=，SVN。V=VN∪VT，稱為文法G的字母表，它是出現(xiàn)文法產(chǎn)生式中的一切符號的集合。文法 G所描述的語言用L(G)表示，它由文法G所產(chǎn)生的全部句子組成，即L(G)={x|S*x，其中S為文法開始符號，且xVT}簡單的說，文法描述的語言是該文法一切句子的集合。4．簡述代碼優(yōu)化的目的和意義。代碼優(yōu)化是盡量生成“好”的代碼的編譯階段。也就是要對程序代碼進行一種等價變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目標程序運行時所需要的時間短，同時所占用的存儲空間少。歡迎下載 19精品文庫5.編譯過程通常分為哪幾個階段？每個過程的主要功能？編譯過程通常分為詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標代碼生成六個主要階段。各個階段的主要功能如下：詞法分析階段：讀入源程序，對構(gòu)成源程序的字符流進行掃描和分解，識別出一個個單詞，并表示成計算機內(nèi)部的形式。語法分析階段：在詞法分析的基礎(chǔ)上，將單詞序列分解成各類語法短語，如“表達式”、“語句”、“程序”等，確定整個輸入串是否構(gòu)成語法上正確的程序。語義分析階段：審查源程序有無語義錯誤，為代碼生成階段收集類型信息。中間代碼生成階段：將源程序翻譯成一種復(fù)雜性介于源程序與目標程序之間的內(nèi)部形式（中間代碼）。代碼優(yōu)化：對前階段產(chǎn)生的中間代碼進行等價變換，目的是使將來生成的目標代碼更為高效。目標代碼生成：把中間代碼變換成特定機器歡迎下載 20精品文庫上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。簡述代碼優(yōu)化的原則和目標原則：對中間代碼進行等價變換，使代碼變換后功能不變。目標：變換后的代碼運行速度更快，占用的存儲空間更少。7.試為表達式w+(a+b)*(c+d/(e-10)+8)寫出相應(yīng)的逆波蘭表示。wab+cde10-/+8+*+寫出表達式a＋b*(c-d)/e的逆波蘭式和三元序列。歡迎下載 21精品文庫逆波蘭式:abcd-*e/+三元序列:op arg1 arg2(1)-cd(2)*b(1)(3)/(2)e(4)+a(3)四．判斷題請在括號內(nèi)，正確的劃√，錯誤的劃×）編譯程序是對高級語言程序的解釋執(zhí)行。（）×一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)（）×目標代碼生成時，應(yīng)考慮如何充分利用歡迎下載 22精品文庫計算機的寄存器的問題。()√語法分析時必須先消除文法中的左遞歸（）×自頂向下LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準確的指出出錯地點（）√逆波蘭表示法表示表達式時無需使用括號。（）√靜態(tài)數(shù)組的存儲空間可以在編譯時確歡迎下載 23精品文庫定。（ ）×靜態(tài)鏈接的情況下 ,鏈接器可以確定 ,編譯只是把文本文件編譯成為 obj文件并不確定地址進行代碼優(yōu)化時應(yīng)該著重考慮循環(huán)的代碼優(yōu)化，這對提高代碼的效率將起更大作用。（）×兩個正規(guī)集相等的必要條件是他們對應(yīng)的正規(guī)式等價。（）應(yīng)該說正規(guī)式等價的必要條件是正規(guī)集相等一個語義子程序描述了一個文法所對應(yīng)的翻譯工作。（）歡迎下載 24精品文庫×1審查每個語法結(jié)構(gòu)的靜態(tài)語義， 2進行制導翻譯一個上下文無關(guān)文法的開始符，可以是終結(jié)符或非終結(jié)符。（ ）×已經(jīng)證明文法的二義性是可判定的。（ ）×每個基本塊可用一個DAG表示。（ ）√一個句型一定是句子。( )歡迎下載 25精品文庫×算符優(yōu)先分析法每次都是對句柄進行歸約。( )√采用三元式實現(xiàn)三地址代碼時，不利于對中間代碼進行優(yōu)化。（ ）√編譯過程中，語法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。( )×目標代碼生成時，應(yīng)考慮如何充分利用計算機的寄存器的問題。歡迎下載 26精品文庫( )√19.并不是每個文法都能改寫成LL(1)文法。()√一個LL(1)文法一定是無二義的。( )√四簡單題1．設(shè)有文法 G1:S→SaQ∣QQ →QbR∣RR →cSd∣e1）證明句型QbRae是規(guī)范句型2）給出句型QbRae的語法樹和句柄：解答： 證明：歡迎下載 27精品文庫1）因為句型QbRae可由文法開始符S經(jīng)過規(guī)范推導產(chǎn)生，推導過程如下：S=>SaQ=>SaR=>Sae=>Qae=>QbRae所以句型QbRae是規(guī)范句型（2分）（2）、語法樹（1分）SS a QQ RQ b R

e句柄：QbR設(shè)有非確定的有限自動機NFAM=({A,B,C},{0，1},,{A},{C})其中：（A,0）={C}, (A,1)={A,B}, (B，1)={C} (C，1)={C}。請畫出狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖。歡迎下載 28精品文庫解答：狀態(tài)轉(zhuǎn)換距陣為：符號01狀態(tài)ACA，BBCCC狀態(tài)轉(zhuǎn)換圖為：1 111A B 1C03.構(gòu)造正規(guī)式 1（0|1）*101相應(yīng)的DFA.解：X1101ABCY4.設(shè)有基本塊：T1：＝2T2：＝10/T1歡迎下載 29精品文庫T3：＝S－RT4：＝S＋RA：＝T2*T4B：＝AT5：＝S＋RT6：＝T3*T5B：＝T6畫出DAG圖假設(shè)基本塊出口時只有A，B還被引用，請寫出優(yōu)化后的四元序列。4、（1）DAG圖A B T6 B* *T4T5T3+-T125T2SR10（2）優(yōu)化后的四元式序列：T3:=S-RT4:=S+R歡迎下載 30精品文庫A:=5*T4B:=T4*T3考慮一下文法：D→TVT → int|floatV →id,V|id1）在該文法中提取左公共因子。2）為所得的文法的非終結(jié)符構(gòu)造First集合和Follow 集合。3）說明所得的文法是LL(1)文法。4）為所得的文法構(gòu)造LL(1)分析表。解答：1）文法存在左公因子，提取左公因子后的文法為：D→ TVT→ int|floatV→idV'V'→,V| ε(2)歡迎下載 31精品文庫非終結(jié)符First集合Follow集合D{int,float}{#}T{int,float}{id}V{id}{#}V'{,,ε}{#}（3）(a)First(T → int) ∩First(T → float)=φ;(b) V'=> ε,First(V '→,V) ∩Follow(V)={,, ε}∩{#}=φ根據(jù)LL(1)文法的定義判斷，此文法是 LL(1)文法；LL(1)分析表為：intfloatid,#DD→TVD→TVTT→intT→floatVV→idV'V'V'→,VV'→ε歡迎下載 32精品文庫考慮下面的程序：?procedurep(x,y,z)；beginy:=y+2;z:=z+x;endbegina:=5;b:=2;p(a+b,a-b,a);printaend.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出a的值是什么?解答：傳值 a=5傳地址 a=127．證明下述文法G：SaSbS|aS|d是二義性文法。歡迎下載 33精品文庫證明：一個文法，如果存在某個句子有不只一棵語法分析樹與之對應(yīng)，那么稱這個文法是二義性文法。句子aadbd有兩棵語法樹。如下圖：SSaSbaSSaSdaSbSddd(1)(2)設(shè)有基本塊如下：T1:=S+RT2:=3T3:=12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6歡迎下載 34精品文庫1）畫出DAG圖；2）設(shè)A,B是出基本塊后的活躍變量，請給出優(yōu)化后的四元式序列。解答：（1）DAG如右圖：n7 A n8 T6,B_ *n3T1,T5,Bn6T4+ /n1n2n4T2n5T3SR34四元式序列：T1:=S+RT4:=S/R=T1-T4=T1*4設(shè)文法G(S):S→(T)|aS|aT→T,S|S（1）消除左遞歸和提公共左因子；歡迎下載 35精品文庫2）構(gòu)造相應(yīng)的FIRST和FOLLOW集合；3）構(gòu)造預(yù)測分析表。解答：(1)S →(T)|aS’S’→S|εT →ST’T ’→,ST’|ε(2)FIRST( S)={a,(} FIRST(S ’)={a,(, ε}FIRST(T)={a,(} FIRST(T ’)={,, ε}FOLLOW(S)={,,),#} FOLLOW(S ’)={,,),#}FOLLOW(T)={)} FOLLOW(T ’)={)}(3)( ) a , #S S→(T) S→aS’S’ S’→S S’→ε S’→S S’→ε S’→εT T→ST’ T→ST’ T’→,ST’T’→εT’歡迎下載 36精品文庫11.已知文法 G[S]為S→aSb|Sb|b，試證明文法G[S]為二義文法。證明：由文法G[S]：S→aSb|Sb|b，對句子aabbbb對應(yīng)的兩棵語法樹為：因此，文法 G[S]為二義文法?？紤]下面的程序：?procedure p(x,y,z) ；beginy:=y+2;z:=z+x;end歡迎下載 37精品文庫begina:=5;b:=2;p(a+b,a-b,a);printaend.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出a的值是什么?答案：傳值 a=2傳地址 a=15寫出表達式a:=(b+c)*e+(b+c)/f的逆波蘭式和三元序列。逆波蘭式 abc+e*bc+f/+:=三元序列oparg1arg2(1)+bc(2)*(1)e歡迎下載 38精品文庫(3)+bc(4)/(3)f(5)+(2)(4)(6):=a(5)14．什么是句柄？什么是素短語？一個句型的最左直接短語稱為該句型的句柄。素短語是這樣的一個短語，它至少包含一個終結(jié)符并且不包含更小的素短語。已知文法G[S]S→S*aF|aF|*aFF→+aF|+a消除文法左遞歸和提公共左因子。解答：消除左遞歸S→aFS’|*aFS’S’→*aFS’| εF→+aF|+a提公共左因子,文法 G’(S)S→aFS’|*aFS’歡迎下載 39精品文庫S’→*aFS’| εF→+aF’F’→F|ε16．對于文法 G[S]：S AB，A Aa|bB，a|Sb求句型baSb的全部短語、直接短語和句柄？句型baSb的語法樹如圖五(2)所示。SA Bb B S ba圖:句型baSb的的語法樹解：baSb為句型baSb的相對于S的短語，ba為句型baSb的相對于A的短語，Sb為句型baSb的相對于B的短語，且為直接短語，a為句歡迎下載 40精品文庫型baSb的相對于B的短語，且為直接短語和句柄。已知文法G(S)S→aAcBeA→Ab|b→d給出句子abbcde的最左推導及畫出語法樹；給出句型aAbcde的短語、素短語。解答：(1)S=>aAcBe=>aAbcBe=>abbcBe=>abbcde短語:aAbcde,Ab,d素短語:Ab,d已知文法G(S)E→E+T|TT→T*F|FF→(E)|i(1) 給出句型(i+i)*i+i 的最左推導及歡迎下載 41精品文庫畫出語法樹；給出句型(E+T)*i+F的短語，素短語和最左素短語。解答：(1)E=>E+T=>T+T=>T*F+T=>F*F+T=>(E)*F+T=>(E+T)*F+T=>(T+T)*F+T=>(F+T)*F+T=>(i+T)*F+T=>(i+F)*F+T=>(i+i)*F+T=>(i+i)*i+T=>(i+i)*i+F=>(i+i)*i+i短語i,F,E+T,(E+T),(E+T)*i,(E+T)*i+F素短語i,E+T最左素短語 E+T何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？優(yōu)化：對程序進行各種等價變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標代歡迎下載 42精品文庫碼。三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化目標代碼有哪幾種形式？生成目標代碼時通常應(yīng)考慮哪幾個問題？目標代碼通常采用三種形式：機器語言，匯編語言，待裝配機器語言模塊。應(yīng)著重考慮的問題：如何使生成的目標代碼較短；如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；如何充分利用指令系統(tǒng)的特點。一字母表Σ={a,b}，試寫出Σ上所有以a為首的字組成的正規(guī)集相對應(yīng)的正規(guī)式。解答：正規(guī)式 a(a|b)* 。歡迎下載 43精品文庫設(shè)有基本塊D:=A