鄭州大學(xué)編譯原理試卷及答案(往年試題整合)

1、二填空題1 .不同的編譯程序關(guān)于數(shù)據(jù)空間的存儲(chǔ)分配策略可能不同， 但大部分編譯中采用的方案有兩種：靜態(tài)存儲(chǔ)分配方案和動(dòng)態(tài)存儲(chǔ)分配方案，而后者又分為( 1) 和 ( 2) 。 2. 規(guī)范規(guī)約是最(3)規(guī)約。3. 編譯程序的工作過程一般劃分為 5 個(gè)階段：詞法分析、 ( 4) 、語義分析與中間代碼生成，代碼優(yōu)化及(5) 。另外還有( 6)和出錯(cuò)處理。4.表達(dá)式x+y*z/(a+b)的后綴式為 。5.文法符號(hào)的屬性有綜合屬性和 ( 8) 。6假設(shè)二位數(shù)組按行存放，而且每個(gè)元素占用一個(gè)存儲(chǔ)單元，則數(shù)組a1.15,1.20某個(gè)元素ai, j的地址計(jì)算公式為(9)。7 局部?jī)?yōu)化是局限于一個(gè)(10)范圍內(nèi)的

2、一種優(yōu)化。答案(1) 棧式動(dòng)態(tài)存儲(chǔ)分配(2) 堆式動(dòng)態(tài)存儲(chǔ)分配(3) 左 (4) 語法分析 (5) 目標(biāo)代碼生成(6)表格管理(7) xyz*ab+/+ (8)繼承屬性 (9) a+(i-1)*20+j-1 (10)基本塊8 詞法規(guī)則通?？梢杂?正規(guī)式 ， 正規(guī)文法、 自動(dòng)機(jī)描述；語法規(guī)則通常用_2型文法_來描述；語義規(guī)則通常用 _屬性文法 來描述。9編譯原理的工作過程一般劃分為：詞法分析、語法分析、語義分析、 優(yōu)化和目標(biāo)代碼生成五個(gè)階段。1 .（ 稱為規(guī)范推導(dǎo)。2 .編譯過程可分為（），（），（），（）和（）五個(gè) 階段。3 .如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是（）。

3、4 .從功能上說，程序語言的語句大體可分為（）語句和（）語句兩大類。5 .語法分析器的輸入是（），其輸出是（）。6 .掃描器的任務(wù)是從（）中識(shí)別出一個(gè)個(gè)（）。7 .符號(hào)表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如（穹穹°8 .一個(gè)過程相應(yīng)的DISPLA法的內(nèi)容為（）。9 .一個(gè)句型的最左直接短語稱為句型的（）。10 .常用的兩種動(dòng)態(tài)存貯分配辦法是（）動(dòng)態(tài)分配和（）動(dòng)態(tài)分配。11 .一個(gè)名字的屬性包括（和（）12 .常用的參數(shù)傳遞方式有（），（）和（）。13 .根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（），（）和（）三個(gè)級(jí)別。14.語法分析的方法大致可分為兩類，一類是（）分析法，另一類

4、是（ ）分析法。）和一個(gè)（）進(jìn)行聯(lián)合控制15 .預(yù)測(cè)分析程序是使用一張（的。16 .常用的參數(shù)傳遞方式有（） ， （ ）和（ ）。17 .一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài),其中有一個(gè)被認(rèn)為是（ ）態(tài) ;而且實(shí)際上至少要有一個(gè)（ ）態(tài)。18 .根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（） ， （ ）和（ ）三個(gè)級(jí)別。19 .語法分析是依據(jù)語言的（） 規(guī)則進(jìn)行。 中間代碼產(chǎn)生是依據(jù)語言的（ ）規(guī)則進(jìn)行的。20 .一個(gè)句型的最左直接短語稱為句型的（） 。21 .一個(gè)文法G， 若它的預(yù)測(cè)分析表M 不含多重定義， 則該文法是（）文法。22 .對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN用（ 策略，PASCAL!用

5、（ 策略。）23 .如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是 （）。24 .最右推導(dǎo)亦稱為（） ，由此得到的句型稱為（ ）句型。25 .語法分析的方法大致可分為兩類，一類是（ ）分析法，另一類是（ ）分析法。26 .對(duì)于文法G,僅含終結(jié)符號(hào)的句型稱為（）27 .所謂自上而下分析法是指（ ） 。28 .語法分析器的輸入是（） ，其輸出是（ ） 。29 .局限于基本塊范圍的優(yōu)化稱（） 。30 .預(yù)測(cè)分析程序是使用一張（）和一個(gè)（ ）進(jìn)行聯(lián)合控制的。 31.2 型文法又稱為（ ）文法； 3 型文法又稱為（ ） 文法。 32.每條指令的執(zhí)行代價(jià)定義為 （） 。 33.算符優(yōu)先分析法

6、每次都是對(duì)（ ）進(jìn)行歸約。 答案 參考答案 ：1.（最右推導(dǎo)）2.（詞法分析）， （語法分析） ， （中間代碼生成） ， （代碼優(yōu)化） ， （目標(biāo)代碼生成）3.（二義性的）4.（執(zhí)行性）， （說明性）5.（單詞符號(hào)） ， （語法單位） 。 6.（源程序）， （單詞符號(hào)）7 .（類型、種屬、所占單元大小、地址）8 .（現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址） 9.（句 柄）10.（棧式）， （堆式）11.（類型）， （作用域）12.（傳地址）， （傳值） ，（傳名）13.（局部?jī)?yōu)化）， （循環(huán)優(yōu)化） ， （全局優(yōu)化）14.（自上而下），（自下而上）15.（分析表）， （符號(hào)棧）16.（傳地

7、址）， （傳值） ， （傳名）17.（初） ， （終）18.（局部?jī)?yōu)化）， （循環(huán)優(yōu)化） ， （全局優(yōu)化）19.（語法） ， （語義）20.（句柄）21.（LL（1）文法）22.（靜態(tài)），（動(dòng)態(tài)）23.仁義性文法）24.（規(guī)范推導(dǎo)）， （規(guī)范）25.（自上而下）， （自下而上）26.（句子）27.（從開始符號(hào)出發(fā)，向下推導(dǎo)，推出句子）28.（單詞符號(hào)）， （語法單位）29.（局部?jī)?yōu)化）30.（分析表）， （符號(hào)棧）31.（上下文無關(guān)文法），（正規(guī)）32.（指令訪問主存次數(shù)加1） 33.（最左素短語）三 解答題（共60 分）1 （共 15 分）已知文法 GE:-ETE|（E） |i T7 *|+

8、（1）將文法G改造成LL （1）文法；（5分）（2）構(gòu)造文法G中每個(gè)非終結(jié)符的FIRST#合及FOLLOW集合；（5分）（3）構(gòu)造LL （1）分析表。（5分）2.（共12分）給定文法GS: AS（S）|e（ 1） 給出句子（）（）（）（）的規(guī)范推導(dǎo)過程；（ 4 分）（ 2 ） 指出每步推導(dǎo)所得句型的句柄； （ 4 分）（ 3） 畫出該句子的語法推導(dǎo)樹。 （ 4 分）答案1 （ 1）文法存在左遞歸，消除左遞歸后的文法為：一（E）E |i E' （2 分）E' -TEE | £（2 分）戶*|十（1分）（2） （5 分）沒考慮#扣 0.5分，其它錯(cuò)或少寫一個(gè)扣0.5分FI

9、RST（E尸（,iFIRST（E '尸色+,FIRST（T尸口+FOLLOW（E）=）,*,+,# FOWLLOW（ E）=）,*,+,#FOLLOW（T）=（,i2.已知文法G(S及相應(yīng)翻譯方案5 aAb print "1” S aprint "2” A AS print "3” Ac print "4” 輸入acab,輸出是什么？3 . 已知文法 G(S)A bAaA7 (B | a B Aa)寫出句子 b(aa)b 的規(guī)范歸約過程。4 . 考慮下面的程序：procedure p(x, y, z；) begin y:=x+y; z:=z*z;

10、 end beginA:=2; B:=A*2; P(A, A, B); Print A, B end.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出A, B的值是什么？5 .文法 G(S) S>dAB aA| a B Bb| £描述的語言是什么？6 .證明文法G(S) S>SaS| £ 是二義性的。7 .已知文法 G(S) S>BA Z BS| d8 aA| bS | c的預(yù)測(cè)分析表如下a b c d # S>SA S BA S BA A A BS Z BS 2 BS A-d B B aA B bS B c給出句子 adccd 的分析過

11、程。8.寫一個(gè)文法G,使其語言為L(zhǎng)(G尸albmclanbn| l>=0, m>=1, n>=29 .已知文法 G(S): S>a| (T) T-T,S|S的優(yōu)先關(guān)系表如下： 關(guān)系 a ( ) , a - - .> .> ( <. <. =. <. ) - - .> .> , <. <. .> .>請(qǐng)計(jì)算出該優(yōu)先關(guān)系表所對(duì)應(yīng)的優(yōu)先函數(shù)表。10 .何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級(jí)優(yōu)化？11 .目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問題？12 .一字母表2 =a, b,試寫出2上所有以a

12、為首的字組成的正規(guī)集相對(duì)應(yīng)的正規(guī)式13 .基本的優(yōu)化方法有哪幾種？14 .寫一個(gè)文法G, 使其語言為 L(G)=abncn| n >0 15考慮下面的程序：，procedure p(x, y, z); begin y:=y+z; z:=y*z+x end; begin a:=2; b:=3;p(a+b, b, a); print a end.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出 a 的值是什么?16 .寫出表達(dá)式a b*(c-d)/e 的逆波蘭式和三元序列。17 .證明文法G(A) ZAA | (A)| £是二義性的。18 .令 2=a,b,則正規(guī)式 a

13、*b|b*a表示的正規(guī)集是什么？19 .何謂DISPLAYS?其作用是什么?procedure p(x, y, z；) begin y:=y+2; z:=z+x; end begina:=5; b:=2;p(a+b, a-b, a); print a end.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出 a 的值是什么?21 .寫一個(gè)文法G, 使其語言為L(zhǎng)(G)=anbncm| n>0為奇數(shù)，m>0為偶數(shù)22 .寫出表達(dá)式a:=(b+c)*e+(b+c)/f 的逆波蘭式和三元序列。23 .一個(gè)文法G別是LL(1成:法的充要條件是什么？24 .已知文法 GSSH S*

14、aF | aF | *aF 曰+aF | +a消除文法左遞歸和提公共左因子。25 .符號(hào)表的作用是什么？符號(hào)表查找和整理技術(shù)有哪幾種？答案：.1 所求文法是GS:S- AB |B A0 2AD |CB- 2 |4 |6 |8C- 1 |3 |5 |7 |9 |B D -0 |C2.輸出是42314 .傳地址A=6, B=16傳值 A=2, B=45 .L(G)=danbm|n>0, m >06 .證明：因?yàn)槲姆℅S府在句子aa有兩個(gè)不同的最左推導(dǎo)，所以文法GSM是二義性的。S=>SaS=>SaSaS=>aSaS=>aaS=>aa S=>SaS=&

15、gt;aS=>aSaS=>aaS=>aa8.所求文法是GS:S>ABZ aAc | D A bD | b BaBb | aabb10 .優(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ī)器語言，匯編語言，待裝配機(jī)器語言模塊。應(yīng)著重考慮的問題：(1)如何使生成的目標(biāo)代碼較短；(2)如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；(3)如何充分利用指令系統(tǒng)的特點(diǎn)。12 .正規(guī)式a ( a | b )* 。13 .刪除多余運(yùn)算，代碼外提，強(qiáng)度削弱，變換循環(huán)控制條件，合并已知量，復(fù)寫

16、傳播和刪除無用賦值。14.文法 GS:SH aB | aBH bc |bBc15.傳值a=2 傳地址 a=1516 .逆波蘭式 : abcd-*e/+三元列 : op arg1 arg2 (1) -(3) /(2) e17 .證明：序c d (2) * b (1)(4) + a (3)因?yàn)槲姆℅S存在句子()有兩個(gè)不同的最左推導(dǎo)，所以文法GS層是二義性的。A=>AA=>(A)A=>()A=>()A=>AA=>A=>(A)=>()18 .(a*b|b*a)=a,b,ab,ba,aab,bba, 19 .Display表：嵌套層次顯示表由于過程嵌套允

17、許內(nèi)層過程引用外層過程定義的數(shù)據(jù)， 因此， 當(dāng)一個(gè)過程運(yùn)行時(shí)必須跟蹤它的所有外層過程的最新活動(dòng)記錄起始地址， display 表就是用于登記每個(gè)外層過程的最新活動(dòng)記錄起始地址。20 .傳地址a=12 傳值a=521 .所求文法是 GS:SACZ aaAbb | ab C ccC | cc23 .一個(gè)文法 G別是LL(1)文法的充要 條件是：(1) FIRST ( ) AFIRST-(尸(2)如果(3 =* > & , FIRST( ) A FOLLOW(A) 24.消除左遞歸AaFS | *aFS'a*aFS' | £ 曰 +aF |+a提公共左因子，文法G' (S) S>aFS | *aFS'a7*aFS' | £ 曰+aF' F7F | £25.作用：登記源程序中出現(xiàn)的各種名字及其信息，以及了解各階段 的進(jìn)展?fàn)顩r。主要技術(shù)：線性表，對(duì)折查找，雜奏技術(shù)。三、簡(jiǎn)答題：(每題7分，共28分)(說明：將答案寫在試卷后面的答題紙上)1、已知文法GEE->E+T|E-T|T T->T*F|T/F|F F->(E)|i證明(F+T -T*(E-T謔文法的句型，