1、東南大學(xué)1997編譯原理試題 一:文法G1: EET+|T TTF*|F FFP|P PE|i 1.試證明符號(hào)串TET+*i是G1的一個(gè)句型(要求畫(huà)出語(yǔ)法樹(shù)). 2.寫(xiě)出該句型的所有短語(yǔ),簡(jiǎn)單短句和句柄. 二: 1.給出下圖FA的正規(guī)式. a b a b 2.已知正規(guī)文法G2: SaS|A AbB BaB| 試構(gòu)造一確定有限自動(dòng)機(jī)DFA(要求化簡(jiǎn)),使得它接受的語(yǔ)言正是該文法產(chǎn)生的語(yǔ)言,要求畫(huà)出狀態(tài)圖. 三: 1.試寫(xiě)出一個(gè)上下文無(wú)關(guān)文法G3,它能產(chǎn)生配對(duì)的圓括號(hào)串(例如,(),(),()()等,甚至包含0對(duì)括號(hào)). 2.使用文法G3給出輸入串()()#的自上而下分析過(guò)程. 四:已知文法G4:

2、 SaAb|Sc| AaAb| 1.給出G4文法的LR(0)項(xiàng)目集規(guī)范族; 2.構(gòu)造SLR分析表; 3.G4文法所定義的語(yǔ)言; 4.已知有如下文法及相應(yīng)的LR分析表,試給出語(yǔ)句01001#的LR分析過(guò)程(填寫(xiě)下表). SAAA A1A A0 LR分析表: 狀態(tài) 1 0 # S A 0 S3 S4 1 2 1 acc 2 S3 S4 5 3 S3 S4 6 4 r3 r3 r3 5 S3 S4 7 6 r2 r2 r2 7 r1 分析過(guò)程: 狀態(tài)棧 符號(hào)棧 輸入串 五: 1.翻譯下面語(yǔ)句成四元式中間代碼序列和后綴式(逆波蘭式); while x+ya do if ab) or (c=d) and

3、 not (e 成轉(zhuǎn)移四元式序列(即四元式中僅包含(z,-,-,-)和(j,-,-,-)兩類語(yǔ)句,其中為關(guān)系運(yùn)算符.) 六: 1.有如下Fortran說(shuō)明語(yǔ)句,試借助符號(hào)表登記等價(jià)環(huán)鏈EQ和相對(duì)數(shù)OFFSET,即填寫(xiě)下表的EQ欄和OFFSET欄.設(shè)每個(gè)整型量占1子編址. integer a,b,c(10,10),d(10) equivalence (a,d(8),c(5,5) equivalence (b,c(5,8) 符號(hào)表 name . EQ OFFSET 1 a . 2 b . 3 c . 4 d . 2.有如下pascal語(yǔ)言的程序輪廓,當(dāng)運(yùn)行該程序且第一次遞歸調(diào)用Q過(guò)程(即在過(guò)程Q中

4、又調(diào)用了Q)時(shí),數(shù)據(jù)區(qū)建立情況.假定各數(shù)據(jù)區(qū)首址用SP(i)(i=0,1,)表示,試給出P,Q數(shù)據(jù)區(qū)的display表. main P Q Call Q Call Q R Call P S Call R Call S 七:已知如下流圖,試給出回邊與循環(huán). / / / / / / 東南大學(xué)1998編譯原理試題 一:已知文法G1: SaB| BbC|bD CcB|c Dd 1.試構(gòu)造一個(gè)最小DFA,畫(huà)出狀態(tài)轉(zhuǎn)換圖. 2.由該DFA給出它所識(shí)別的語(yǔ)言(用正規(guī)式表示). 二:已知正規(guī)式=ab*c*d, 1.試構(gòu)造一個(gè)DFAM,其接受的語(yǔ)言為此(畫(huà)出圖); 2.由該DFAM寫(xiě)出對(duì)應(yīng)的正規(guī)文法(古線性).

5、 三:文法G3: SAB AB|Aa Ba 1.求出各非終結(jié)符N的Firstvt(N)和Lastvt(N),構(gòu)造包括語(yǔ)句括號(hào)#在內(nèi)的算符優(yōu)先表; 2.給出語(yǔ)句#aa#的算符優(yōu)先分析過(guò)程,即填寫(xiě)如下格式的表: 步驟 棧內(nèi) 輸入串 動(dòng)作 0 # aa# . 四:已知文法G4: TT*F|F F(T)|i 1.試給出語(yǔ)句(i*i)#的自上而下分析過(guò)程(填下表); 2.畫(huà)出對(duì)應(yīng)的語(yǔ)法樹(shù),指出每一步歸納的句柄. 步驟 棧內(nèi) 輸入 動(dòng)作 0 #T (i*i)# . 五:已知文法G5: 0. EE 1. EE+T 2. ET 3. Ti 列出LR(0)項(xiàng)目集規(guī)范族,求出各非終結(jié)符N的Follow集合,構(gòu)造S

6、LR分析表. 六:翻譯如下語(yǔ)句成四元式序列(由語(yǔ)法制導(dǎo)生成). while ab and a if a=5 then b:=b+1 else repeat a:=a+1 until a=d; 七:按語(yǔ)法制導(dǎo)翻譯下段程序成四元式序列(不要優(yōu)化),設(shè)數(shù)組A: array1.10,1.10 of int;每個(gè)下標(biāo)變量占1字編址,數(shù)組按行存放,Z為函數(shù)名. begin Ai,j:=Ai,j+2; B:=Z(Ai,j)*5 end 八:將如下一段四元式序列進(jìn)行塊內(nèi)優(yōu)化和循環(huán)優(yōu)化(強(qiáng)度減弱及刪除基本歸納變量),寫(xiě)出優(yōu)化后的四元式序列.(要求先劃分基本塊) (1) i:=1 (2) if i100 goto

7、 (10) (3) T1:=20*i (4) M:=J+T1 (5) T2:=20*i (6) N:=K+T2 (7) O:=M+N (8) i:=i+1 (9) goto (2) (10) . 九:已知如下一段程序,試給出運(yùn)行時(shí)整個(gè)數(shù)據(jù)區(qū)結(jié)構(gòu).假定num初值為2,每個(gè)數(shù)據(jù)區(qū)的活動(dòng)記錄包含內(nèi)容如下圖所示,數(shù)據(jù)區(qū)從k單元開(kāi)始編址. program factoral; 函數(shù)返回值 var num,fact:int; function f(n:int):int 變量單元 if n0 then f:=n*f(n-1) else f:=1; display 表 begin read(num); 形參單元

8、 fact:=f(num) end 返回地址 基SP 東南大學(xué)1999編譯原理試題 一:已知正規(guī)文法中的左線性文法 G1:SSa|Sb|c 試構(gòu)造無(wú)產(chǎn)生式的等價(jià)右線性文法,并構(gòu)造相應(yīng)的確定有限自動(dòng)機(jī)DFA,畫(huà)出狀態(tài)轉(zhuǎn)換圖即可. 二:已知正規(guī)文法(X為開(kāi)始符號(hào)) G2: X0Y|1Z|0 Y0X|1Y|1 Z1X 1.該文法產(chǎn)生語(yǔ)言是什么?請(qǐng)用正規(guī)式表示. 2.構(gòu)造最簡(jiǎn)的確定有限自動(dòng)機(jī)DFA,并畫(huà)出狀態(tài)轉(zhuǎn)換圖. 三:已知上下文無(wú)關(guān)文法(E為開(kāi)始符號(hào)) G3: EET+|T TTF*|F FE|i 1.消除文法左遞歸,并給出改寫(xiě)后的文法產(chǎn)生式; 2.給出文法改寫(xiě)以后的各非終結(jié)符X的First(X)

9、與Follow(X)集合,并由此判定它是否是LL(1)文法(按下表填). V(N) First(X) Follow(X) X . 四:已知表達(dá)式文法(已拓廣) G4: EE EE+E|i 1.試構(gòu)造文法G4的LR(0)項(xiàng)目集規(guī)范族; 2.若+服從右結(jié)合率,請(qǐng)給出LR分析表. 五:已知文法(Z為開(kāi)始符號(hào)) G5: ZbMb M(Ma)|a 1.試構(gòu)造算符優(yōu)先分析表(即填下表); a b ( ) # a b ( ) # 2.若某相鄰的終結(jié)符a,b間存在a=b兩種關(guān)系,那么在進(jìn)行算符優(yōu)先分析做歸約動(dòng)作時(shí),在尋找棧頂?shù)乃囟陶Z(yǔ)符號(hào)串時(shí)要察看它與哪個(gè)產(chǎn)生式右部的符號(hào)串匹配. 例如棧頂串.aAb(a,bVT

10、,A(VA),a=b,V*)為已知可歸約,而現(xiàn)有產(chǎn)生式XaAb,則取素短語(yǔ)aAb,若只有產(chǎn)生式Y(jié)Ab,那么就取Ab進(jìn)行歸約.試按此規(guī)定的算法給出語(yǔ)句b(aa)a)b的算符優(yōu)先分析過(guò)程. 六:翻譯成中間代碼. 1.將如下程序段翻譯成后綴式(逆波蘭式),填在一維數(shù)組POSTi中,設(shè)i初值=1. t:=15; b:=20; while tb do if tb then t:=t-b else b:=b-t; 2.翻譯布爾表達(dá)式成轉(zhuǎn)移四元式序列,并指出待填真假鏈序號(hào). (ab+1) and not (c+2 注:f(x)為布爾函數(shù). 七:有如下一個(gè)計(jì)算m*2n的C語(yǔ)言程序,試給出運(yùn)行時(shí)整個(gè)?；驍?shù)據(jù)區(qū)的

11、結(jié)構(gòu).數(shù)據(jù)區(qū)的活動(dòng)記錄結(jié)構(gòu)如圖所示. 函數(shù)f返回值返回結(jié)果值 局部變量區(qū) 局部變量區(qū) 全程變量區(qū) 形參單元區(qū) 主程序main 返回地址 數(shù)據(jù)區(qū) 基SP 函數(shù)數(shù)據(jù)區(qū) int m; f(n) int n; int c; if (n=0) c=m; else c=f(n-1)*2; return (c); main() int n=2; m=5; printf(%dn,f(n); 八:已知如下程序段 a:=1; while a=10 do begin if ab then Aa,b:=Aa,b+2; a:=a+1; end; 1.按語(yǔ)法制導(dǎo)生成四元式中間代碼序列; 2.將中間代碼序列劃分成基本塊,畫(huà)

12、出程序流圖,并指出循環(huán)結(jié)點(diǎn)集; 3.執(zhí)行循環(huán)中代碼外提,強(qiáng)度減弱優(yōu)化和基本塊內(nèi)刪除公共子表達(dá)式優(yōu)化,最后畫(huà)出包含優(yōu)化后的中間代碼的程序流圖. 注:數(shù)組A: array1.10,1.10 of int;按行存放,每個(gè)下標(biāo)變量占1字編址,首地址為addrA 上海交通大學(xué)1998年編譯原理試題一、 生成語(yǔ)言l=albmclanbn l=0,m=1,n=2 的文法是什么？它是chomsky那一型文法？ 二、 文法G1：P aPQR abR RQ QR BQ bb bR bc cR cc 它是chomsky哪一型文法？請(qǐng)證aaabbbccc是G1的一個(gè)句子。三、 文法G2:PaPbQ QbQcbSc S

13、Saa 1、 請(qǐng)構(gòu)造它的SLR分析表以說(shuō)明它是不是SLR文法。 、在消除左遞歸、提取公共因子后可得等價(jià)文法，它是不是ll(1)文法。 四、求與正規(guī)R=(ab)*a(ab)*a(ba)*等價(jià)的min 五、文法3及相應(yīng)翻譯方案為 pbQb print:”1” QcR print:”2” Qa print:”3” RQab print:”4” 1、 該文法是不是算符優(yōu)先文法，請(qǐng)構(gòu)造算符優(yōu)先關(guān)系表證實(shí)之。2、 輸入串為bcccaadadb時(shí)，該翻譯方案的輸出是什么？六、 三維數(shù)組a2:5,-2:2,5:7首址為100,每個(gè)數(shù)組元素占個(gè)存儲(chǔ)單元，2、 求數(shù)組元素a(3,1,6)的地址。 七、 下列程序段

14、若以表示循環(huán)體，表示初始化，表示增量，表示測(cè)試。I:=1; While I = b then x:=a+b*c else x:=b-a; 八、（ 8 分） 給定基本塊： A:=3*5 B:=E+F C:=A+12 D:=E+F A:=D+12 C:=C+1 E:=E+F 假定出基本塊后，只有 A 、 C 、 E 是活躍的，給出用 DAG 圖完成優(yōu)化后的代碼序列。 參考答案： 一、 D A A C G. A B A F A 二、 1 對(duì)于 G 中的每個(gè)產(chǎn)生式 A 1 | 2 | | m ，其各候選式均應(yīng)滿足： （1）不同的候選式不能推出以同一終結(jié)符號(hào)打頭的符號(hào)串，即 FIRST( i ) FIR

15、ST( j )= （ 1 i ， j m ； i j ） （2）若有 j ，則其余候選式 i 所能推出的符號(hào)串不能以 FOLLOW(A) 中的終結(jié)符號(hào)開(kāi)始，即有 FIRST( i ) FOLLOW(A)= （ i 1,2, ,m ； i j ） 2 有三種分配存儲(chǔ)空間的方式：（ 1 ） 靜態(tài)分配 若在編譯階段就能確定源程序中各個(gè)數(shù)據(jù)實(shí)體的存儲(chǔ)空間大小，則可以采用較簡(jiǎn)單的靜態(tài)存儲(chǔ)管理。 適合 靜態(tài)管理 的語(yǔ)言應(yīng)具備條件： 數(shù)組上下界是常數(shù)、過(guò)程調(diào)用不允許遞歸、不允許動(dòng)態(tài)建立數(shù)據(jù)實(shí)體。 （ 2） 棧式分配 適用于允許遞歸調(diào)用的程序設(shè)計(jì)語(yǔ)言 ；（ 3 ） 堆式分配 對(duì)于允許程序在運(yùn)行時(shí)為變量 動(dòng)態(tài)申

16、請(qǐng)和釋放存儲(chǔ)空間 的語(yǔ)言 ， 采用 堆式分配 是最有效的解決方案 。 3 不變運(yùn)算外提；運(yùn)算強(qiáng)度削弱；消除歸納變量；下標(biāo)變量地址計(jì)算優(yōu)化。 4 一個(gè)過(guò)程的一次執(zhí)行所需信息的管理，是通過(guò)稱為 活動(dòng)記錄 的連續(xù)存儲(chǔ)塊來(lái)實(shí)現(xiàn)的?；顒?dòng)記錄的主要內(nèi)容有：（ 1） 臨時(shí)變量域 存放目標(biāo)程序臨時(shí)變量的值；（ 2 ）局部數(shù)據(jù)域 存放過(guò)程本次執(zhí)行時(shí)的局部數(shù)據(jù)、簡(jiǎn)單變量及數(shù)組內(nèi)情向量等；（ 3 ）機(jī)器狀態(tài)域 保存在調(diào)用過(guò)程前有關(guān)機(jī)器狀態(tài)的信息，包括各寄存器的當(dāng)前值及返回地址等；（ 4 ）存取鏈 為訪問(wèn)其它活動(dòng)記錄中所存放的非局部數(shù)據(jù)所提供的鏈地址；（ 5 ）控制鏈 指向主調(diào)過(guò)程的活動(dòng)記錄；（ 6 ）實(shí)參 存放主調(diào)

17、過(guò)程為被調(diào)用過(guò)程所提供的實(shí)參信息；（ 6 ）返回值 為主調(diào)過(guò)程存放被調(diào)過(guò)程的返回值 三、化簡(jiǎn)后： S ASe|AC A Cb C bC | d 四、 DFA 如圖所示。相應(yīng)的正規(guī)式為 (c|acc|bc)* 。 五、 改造后的文法： S PS S aPS| fS | e P qP P bP | e 各候選式的 FIRST 集，各非終結(jié)符的 FOLLOW 集為 產(chǎn)生式 FIRST 集 FOLLOW 集 S PS q # S aPS fS e a f e # P qP q a,f,# P bP e b e a,f,# LL(1) 分析表為 六、分析表如下圖所示 七、（ 1 ）逆波蘭式： ,其中，

18、BLE 表示汪或等于時(shí)的轉(zhuǎn)向指令； 表示標(biāo)號(hào)。 （ 2 ）四元式： (1) ( j, a, b, (3) (2) ( j, , , (7) ) (3) ( *, b, c, T1) (4) ( +, a, T1, T2) (5) ( :=, T2, , x) (6) ( j, , , (9) (7) ( -, b, a, T3) (8) ( :=, T3, , x) (9) ( ) 八、化簡(jiǎn)后的的四元式序列為 A :=D+12 E :=E+F C :=28 模擬試題二一、是非題(下列各題，你認(rèn)為正確的，請(qǐng)?jiān)陬}干的括號(hào)內(nèi)打“”，錯(cuò)的打“”。每題1分,共5分) 1、算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)

19、先函數(shù)。 2、數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。3、僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無(wú)用的。4、每個(gè)文法都能改寫(xiě)為L(zhǎng)L(1)文法。5、對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動(dòng)態(tài)貯存分配策略。二、填空題(每題2分，共20分) 1、從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為_(kāi)語(yǔ)句和_語(yǔ)句兩大類。 2、掃描器的任務(wù)是從_中識(shí)別出一個(gè)個(gè)_。 3、所謂最右推導(dǎo)是指：_。 4、語(yǔ)法分析最常用的兩類方法是_和_分析法。 5、一個(gè)上下文無(wú)關(guān)文法所含四個(gè)組成部分是_。 6、所謂語(yǔ)法制導(dǎo)翻譯方法是_。 7、符號(hào)表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如_等等。 8、一個(gè)過(guò)程相應(yīng)的DISPLAY表的

20、內(nèi)容為_(kāi)。 9、常用的兩種動(dòng)態(tài)存貯分配辦法是_動(dòng)態(tài)分配和_動(dòng)態(tài)分配。 10、產(chǎn)生式是用于定義_的一種書(shū)寫(xiě)規(guī)則。 三、名詞解釋(每題2分，共10分) 1、遍 2、無(wú)環(huán)路有向圖(DAG) 3、語(yǔ)法分析 4、短語(yǔ) 5、后綴式四、簡(jiǎn)述題(每題4分，共24分) 1、考慮下面程序 Var a：integer； Procedure S(X)； Var X：integer； Begin a：a1； X：aX End； Begin a：5； S(a)； Print(a) End 試問(wèn)：若參數(shù)傳遞方式分別采取傳名和傳值時(shí)，程序執(zhí)行后輸出a的值是什么？ 2、畫(huà)出Pascal中實(shí)數(shù)(不帶正負(fù)號(hào)，可帶指數(shù)部分)的狀態(tài)轉(zhuǎn)

21、換圖。 3、寫(xiě)出表達(dá)式(ab*c)/(ab)d的逆波蘭表示及三元式序列。 4、已知文法G(S) Sa|(T) TT，S|S 寫(xiě)出句子(a，a)，a)的規(guī)范歸約過(guò)程及每一步的句柄。 5、何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級(jí)優(yōu)化？ 6、目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問(wèn)題？ 五、計(jì)算題(共41分) 1、寫(xiě)一個(gè)文法，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(shù)不以0開(kāi)頭。(5分) 2、設(shè)文法G(S)： S(L)|a S|a LL，S|S (1)消除左遞歸和回溯； (2)計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW； (3)構(gòu)造預(yù)測(cè)分析表。 3、Whilea0 b0do Begin X：X1；

22、if a0 then a：a1 else b：b1 End； 翻譯成四元式序列。(7分) 4、已知文法G(E) ET|ET TF|T *F F(E)|i (1)給出句型(T *Fi)的最右推導(dǎo)及畫(huà)出語(yǔ)法樹(shù)； (2)給出句型(T *Fi)的短語(yǔ)、素短語(yǔ)。(7分) 5、設(shè)布爾表達(dá)式的文法為 E E(1)E(2) E E(1)E(2) E i 假定它們將用于條件控制語(yǔ)句中，請(qǐng) (1)改寫(xiě)文法，使之適合進(jìn)行語(yǔ)法制導(dǎo)翻譯和實(shí)現(xiàn)回填； (2)寫(xiě)出改寫(xiě)后的短個(gè)產(chǎn)生式的語(yǔ)義動(dòng)作。(6分) 6、設(shè)有基本塊 T1：2 T2：10/T T3：SR T4：SR A：T2 *T4 B：A T5：SR T6：T3 *T5

23、 B：T6 (1)畫(huà)出DAG圖； (2)假設(shè)基本塊出口時(shí)只有A，B還被引用，請(qǐng)寫(xiě)出優(yōu)化后的四元序列。(6分) 參考答案： 一、 二、 1 執(zhí)行性、 說(shuō)明性 2、 源程序、 單詞符號(hào) 3、 任何一步都是對(duì)中最右非終結(jié)符進(jìn)行替換的 4 自上而下、 自下而上 5、 一組終結(jié)符號(hào)，一組非終結(jié)符號(hào)、一個(gè)開(kāi)始符號(hào)、一組產(chǎn)生式 6、 為每個(gè)產(chǎn)生式配上一個(gè)翻譯子程序，并在語(yǔ)法分析的同時(shí)執(zhí)行這些子程序 7、 類型、種屬、所占單元大小、地址 8、 現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址 9、 棧式、 堆式 10、 語(yǔ)法范疇 三、名詞解釋1遍指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。 2無(wú)環(huán)路有向圖(

24、DAG)如果有向圖中任一通路都不是環(huán)路，則稱廬有向圖為 無(wú)環(huán)路有向圖，簡(jiǎn)稱DAG。 3語(yǔ)法分析按文法的產(chǎn)生式識(shí)別輸入的符號(hào)串是否為一個(gè)句子的分析過(guò)程。 4短語(yǔ)令G是一個(gè)文法。S劃文法的開(kāi)始符號(hào)，假定是文法G的一個(gè)句 型，如果有SA且AB，則稱是句型相對(duì)非終結(jié)符A的短語(yǔ)。 5后綴式一種把運(yùn)算量寫(xiě)在前面，把算符寫(xiě)在后面的表示表達(dá)式的方法。 四、簡(jiǎn)述題1、答：傳名：a12(2分) 傳值：a6 (2分) 3、答：逆波蘭表示： abc*ab/d(2分) 三元式序列： (*，b，c) (，a，) (，a，b) (/，) (，d)(2分) 4、答： 句型歸約規(guī)則句柄 (a，a)，a)Saa (S，a)，a)

25、TSS (T，a)，a)Saa (T，S)，a)TT，S T，S (S)，a) TSS (T)，a) SS(T) (T) (S，a) TSS (T，a) Saa (T，S) TT，S T，S (T) S(T)(T) S(4分) 5、 答：優(yōu)化：對(duì)程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。(2分) 三種級(jí)別：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。(2分) 6、 答：目標(biāo)代碼通常采用三種形式：機(jī)器語(yǔ)言，匯編語(yǔ)言，待裝配機(jī)器語(yǔ)言模塊。(2分) 應(yīng)著重考慮的問(wèn)題： (1)如何使生成的目標(biāo)代碼較短； (2)如何充分利用寄存器，以減少訪問(wèn)內(nèi)存次數(shù)； (3)如何充分利用指僅系統(tǒng)的的特點(diǎn)。

26、 (2分)五、計(jì)算題 1、解：文法G(N)： NAB|B AAC|D B1|3|5|7|9 DB|2|4|6|8 C0|D(5分) 2、解:(1) S(L)|aS SS| LSL LSL| 評(píng)分細(xì)則：消除左遞歸2分，提公共因子2分。 (2) FIRST)S)(，aFOLLOW(S)#，) FIRST(S)，a,FOLLOW(S)#，) FIRST(L)(，aFOLLOW(L) ) FIRST(L)，F(xiàn)OLLOW(L ) 3、解： (1) (j，a，0，5) (2) (j，3) (5) (，1，T1) (6) (：，T1，) (7) (j，a，0，9) (8) (j，12) (9) (，a，1，

27、T2) (10) (：，T2，a) (11) (j，1) (12) (，b，1， T3) (13) (：，T3，b) (14) (j，1) (15) 評(píng)分細(xì)則：控制結(jié)構(gòu)4分，其它3分。 4、解：(1) 最右推導(dǎo)： ETF(E)(ET)(EF)(Ei) (Ti)(T*Fi) (2) 短語(yǔ)：(T*Fi)，T*Fi，T*F，i(2分) 素短語(yǔ)：T*F,i (1分) 5、解：(1) E0E(1) EE0E(2) EAE(1) EEAE(2) Ei(3分) (2) EE(1) BACKPATCH(E(1)FC，NXQ)； E0TC：E(1)TC EE0E(2) EFC：E(2)FC； ETC：MERG(

28、E0TC，E(2)TC) EAE(1) BACKPATCH(E(1)TC，NXQ)； E0FC：E(1)FC EEAE(2) ETC：E(2)TC； EFC：MERG(EAFC，E(2)FC Ei ETC：NXQ；EFC：NXQ1； GEN(jn2，entry(i)，0)； GEN(j，0)(3分) 6、解：(1)DAG： (2) 優(yōu)化后的四元式 T3：SR T4：SR A：5*T4 B：T3T4(3分) 西北工業(yè)大學(xué)考試試題（20032004學(xué)年第二學(xué)期）一、簡(jiǎn)答題（15分）1. 編譯程序與解釋程序有何區(qū)別？2. 何謂素短語(yǔ)？3. 過(guò)程調(diào)用時(shí)，主調(diào)程序與被調(diào)程序之間的信息傳遞有哪些方式？4.

29、 何謂語(yǔ)法制導(dǎo)翻譯？5. 何謂算符文法？二、選擇題（10分）1. 描述一個(gè)語(yǔ)言的文法是（ ）A.唯一的 B.不唯一的 C.可能唯一，也可能不唯一2. 若文法G定義的語(yǔ)言是無(wú)限集，則文法必然是（ ）A.前后文無(wú)關(guān)文法 B.正規(guī)文法 C.二義性文法 D.遞歸文法3. 數(shù)組的內(nèi)情向量中肯定不含數(shù)組的（ ）信息A.維數(shù) B.類型 C.各維的上下界 D.各維的界差4. 簡(jiǎn)單優(yōu)先分析每次歸約的是（ ）A. 最左直接短語(yǔ) B.直接短語(yǔ) C.最左素短語(yǔ) D.控制結(jié)點(diǎn)5. 最適合動(dòng)態(tài)建立數(shù)據(jù)實(shí)體的內(nèi)存分配方式是（ ）A. 棧式分配 B.堆式分配 C.編譯時(shí)預(yù)先分配 D.以上三種均可三、（10分）給定文法G=（S

30、,L，a，（，），S(L)|a LL,S|S，S）。給出句型”(S,(a)”的推導(dǎo)和語(yǔ)法樹(shù)并指出此句型的所有短語(yǔ)、直接短語(yǔ)、句柄和素短語(yǔ)。四、（12分）設(shè)語(yǔ)言L是由奇數(shù)個(gè)a和偶數(shù)（可以是0）個(gè)b組成的符號(hào)串之集。1.構(gòu)造識(shí)別L的DFA；2. 給出定義L的正規(guī)文法；五、（10分）將文法GS：SA AAS|B BBi|i 改寫(xiě)為等價(jià)的LL(1)文法，并給出相應(yīng)的LL(1)分析表。六、（20分）給定文法GS： S(S)|a 1.構(gòu)造識(shí)別文法GS活前綴的LR(1)項(xiàng)目的DFA；2. 構(gòu)造LR(1)分析表；3. 合并同心集，構(gòu)造LALR(1)分析表。七、（8分）某語(yǔ)言算術(shù)表達(dá)式的文法定義為 EE+E|i

31、| if B then E else E其中，第三個(gè)候選式稱為條件算術(shù)表達(dá)式，B為布爾表達(dá)式，then及else后的E均為算術(shù)表達(dá)式（即簡(jiǎn)單算術(shù)表達(dá)式或條件表達(dá)式），其語(yǔ)義為，當(dāng)B為真時(shí)，表達(dá)式的值取then后的E的值，否則取else的E的值。假定所有表達(dá)式是整型的，試將下面關(guān)于條件算術(shù)表達(dá)式的屬性翻譯文法填寫(xiě)完全：八、 （8分）給定PASCAL程序語(yǔ)句while ab do if a0 then a:=a-1 else a:=a+1; 1. 將該語(yǔ)句翻譯成逆波蘭式； 2. 給出編譯程序掃描到then處及分號(hào)處時(shí)所得的四元式序列。九、 (7分)用DAG圖對(duì)下面的基本塊進(jìn)行優(yōu)化（假定出基本塊后只

32、有A、G、L是活躍的）：A=B*C D=B/C E=2*3 F=E+2 G=B*C K=E+F G=K*KL=B/C 參考答案： 一、 簡(jiǎn)答題（15分）1. 編譯程序與解釋程序有何區(qū)別？答：二者的工作方法不同，后者是邊解釋邊執(zhí)行，解釋所得的代碼并不保存；前者是先將高級(jí)語(yǔ)言翻譯感情上標(biāo)代碼，將其保存到指定的空間中，待需要時(shí)再執(zhí)行之，甚至可以在案一個(gè)機(jī)器上編譯，而在另一臺(tái)機(jī)器上執(zhí)行。2. 何謂素短語(yǔ)？答：素短語(yǔ)是滿足下述條件的短語(yǔ)：（1）它至少含有一個(gè)終結(jié)符號(hào)（2）滿足條件（1）的“最小”短語(yǔ)3. 過(guò)程調(diào)用時(shí)，主調(diào)程序與被調(diào)程序之間的信息傳遞有哪些方式？答：形式參數(shù)與實(shí)在參數(shù)結(jié)合方式傳遞（簡(jiǎn)稱參數(shù)

33、傳遞）、返回值傳遞、共享數(shù)據(jù)區(qū)傳遞。4. 何謂語(yǔ)法制導(dǎo)翻譯？答：語(yǔ)法制導(dǎo)翻譯是對(duì)前后文無(wú)關(guān)文法的擴(kuò)充，即對(duì)文法中的每個(gè)產(chǎn)生式都附加一個(gè)語(yǔ)義動(dòng)作或語(yǔ)義子程序，且在語(yǔ)法分析過(guò)程中，每當(dāng)需要使用一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，語(yǔ)法分析程序除執(zhí)行相應(yīng)的語(yǔ)法分析動(dòng)作外，還要執(zhí)行相應(yīng)的語(yǔ)義動(dòng)作或調(diào)用相應(yīng)的語(yǔ)義子程序，完成相應(yīng)的語(yǔ)義分析和翻譯工作。5. 何謂算符文法？答：當(dāng)一個(gè)文法的所有產(chǎn)生式的右部均不出現(xiàn)兩個(gè)非終結(jié)符號(hào)相鄰的情況時(shí)，該就被稱為算符文法。二、 選擇題（10分）1. 描述一個(gè)語(yǔ)言的文法是（B ）A.唯一的 B.不唯一的 C.可能唯一，也可能不唯一2. 若文法G定義的語(yǔ)言是無(wú)限集，則文法必然是（D ）A.前后文無(wú)關(guān)文法 B.正規(guī)文法 C.二義性文法 D.遞歸文法3. 數(shù)組的內(nèi)情向量中肯定不含數(shù)組的（B ）