東南大學(xué)1997編譯原理試題

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

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

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

4、又調(diào)用了Q)時,數(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)造一個最小DFA,畫出狀態(tài)轉(zhuǎn)換圖. 2.由該DFA給出它所識別的語言(用正規(guī)式表示). 二:已知正規(guī)式=ab*c*d, 1.試構(gòu)造一個DFAM,其接受的語言為此(畫出圖); 2.由該DFAM寫出對應(yīng)的正規(guī)文法(古線性).

5、 三:文法G3: SAB AB|Aa Ba 1.求出各非終結(jié)符N的Firstvt(N)和Lastvt(N),構(gòu)造包括語句括號#在內(nèi)的算符優(yōu)先表; 2.給出語句#aa#的算符優(yōu)先分析過程,即填寫如下格式的表: 步驟 棧內(nèi) 輸入串 動作 0 # aa# . 四:已知文法G4: TT*F|F F(T)|i 1.試給出語句(i*i)#的自上而下分析過程(填下表); 2.畫出對應(yīng)的語法樹,指出每一步歸納的句柄. 步驟 棧內(nèi) 輸入 動作 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分析表. 六:翻譯如下語句成四元式序列(由語法制導(dǎo)生成). while ab and a if a=5 then b:=b+1 else repeat a:=a+1 until a=d; 七:按語法制導(dǎo)翻譯下段程序成四元式序列(不要優(yōu)化),設(shè)數(shù)組A: array1.10,1.10 of int;每個下標(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)度減弱及刪除基本歸納變量),寫出優(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ù)據(jù)區(qū)結(jié)構(gòu).假定num初值為2,每個數(shù)據(jù)區(qū)的活動記錄包含內(nèi)容如下圖所示,數(shù)據(jù)區(qū)從k單元開始編址. 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)造無產(chǎn)生式的等價右線性文法,并構(gòu)造相應(yīng)的確定有限自動機(jī)DFA,畫出狀態(tài)轉(zhuǎn)換圖即可. 二:已知正規(guī)文法(X為開始符號) G2: X0Y|1Z|0 Y0X|1Y|1 Z1X 1.該文法產(chǎn)生語言是什么?請用正規(guī)式表示. 2.構(gòu)造最簡的確定有限自動機(jī)DFA,并畫出狀態(tài)轉(zhuǎn)換圖. 三:已知上下文無關(guān)文法(E為開始符號) G3: EET+|T TTF*|F FE|i 1.消除文法左遞歸,并給出改寫后的文法產(chǎn)生式; 2.給出文法改寫以后的各非終結(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é)合率,請給出LR分析表. 五:已知文法(Z為開始符號) 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)先分析做歸約動作時,在尋找棧頂?shù)乃囟陶Z符號串時要察看它與哪個產(chǎn)生式右部的符號串匹配. 例如棧頂串.aAb(a,bVT

10、,A(VA),a=b,V*)為已知可歸約,而現(xiàn)有產(chǎn)生式XaAb,則取素短語aAb,若只有產(chǎn)生式Y(jié)Ab,那么就取Ab進(jìn)行歸約.試按此規(guī)定的算法給出語句b(aa)a)b的算符優(yōu)先分析過程. 六:翻譯成中間代碼. 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)移四元式序列,并指出待填真假鏈序號. (ab+1) and not (c+2 注:f(x)為布爾函數(shù). 七:有如下一個計(jì)算m*2n的C語言程序,試給出運(yùn)行時整個?；驍?shù)據(jù)區(qū)的

11、結(jié)構(gòu).數(shù)據(jù)區(qū)的活動記錄結(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.按語法制導(dǎo)生成四元式中間代碼序列; 2.將中間代碼序列劃分成基本塊,畫

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

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

14、若以表示循環(huán)體，表示初始化，表示增量，表示測試。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 對于 G 中的每個產(chǎn)生式 A 1 | 2 | | m ，其各候選式均應(yīng)滿足： （1）不同的候選式不能推出以同一終結(jié)符號打頭的符號串，即 FIRST( i ) FIR

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

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

17、過程為被調(diào)用過程所提供的實(shí)參信息；（ 6 ）返回值 為主調(diào)過程存放被調(diào)過程的返回值 三、化簡后： 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 表示汪或等于時的轉(zhuǎn)向指令； 表示標(biā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) ( ) 八、化簡后的的四元式序列為 A :=D+12 E :=E+F C :=28 模擬試題二一、是非題(下列各題，你認(rèn)為正確的，請?jiān)陬}干的括號內(nèi)打“”，錯的打“”。每題1分,共5分) 1、算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)

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

20、內(nèi)容為_。 9、常用的兩種動態(tài)存貯分配辦法是_動態(tài)分配和_動態(tài)分配。 10、產(chǎn)生式是用于定義_的一種書寫規(guī)則。 三、名詞解釋(每題2分，共10分) 1、遍 2、無環(huán)路有向圖(DAG) 3、語法分析 4、短語 5、后綴式四、簡述題(每題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 試問：若參數(shù)傳遞方式分別采取傳名和傳值時，程序執(zhí)行后輸出a的值是什么？ 2、畫出Pascal中實(shí)數(shù)(不帶正負(fù)號，可帶指數(shù)部分)的狀態(tài)轉(zhuǎn)

21、換圖。 3、寫出表達(dá)式(ab*c)/(ab)d的逆波蘭表示及三元式序列。 4、已知文法G(S) Sa|(T) TT，S|S 寫出句子(a，a)，a)的規(guī)范歸約過程及每一步的句柄。 5、何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？ 6、目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時通常應(yīng)考慮哪幾個問題？ 五、計(jì)算題(共41分) 1、寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。(5分) 2、設(shè)文法G(S)： S(L)|a S|a LL，S|S (1)消除左遞歸和回溯； (2)計(jì)算每個非終結(jié)符的FIRST和FOLLOW； (3)構(gòu)造預(yù)測分析表。 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)及畫出語法樹； (2)給出句型(T *Fi)的短語、素短語。(7分) 5、設(shè)布爾表達(dá)式的文法為 E E(1)E(2) E E(1)E(2) E i 假定它們將用于條件控制語句中，請 (1)改寫文法，使之適合進(jìn)行語法制導(dǎo)翻譯和實(shí)現(xiàn)回填； (2)寫出改寫后的短個產(chǎn)生式的語義動作。(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)畫出DAG圖； (2)假設(shè)基本塊出口時只有A，B還被引用，請寫出優(yōu)化后的四元序列。(6分) 參考答案： 一、 二、 1 執(zhí)行性、 說明性 2、 源程序、 單詞符號 3、 任何一步都是對中最右非終結(jié)符進(jìn)行替換的 4 自上而下、 自下而上 5、 一組終結(jié)符號，一組非終結(jié)符號、一個開始符號、一組產(chǎn)生式 6、 為每個產(chǎn)生式配上一個翻譯子程序，并在語法分析的同時執(zhí)行這些子程序 7、 類型、種屬、所占單元大小、地址 8、 現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址 9、 棧式、 堆式 10、 語法范疇 三、名詞解釋1遍指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。 2無環(huán)路有向圖(

24、DAG)如果有向圖中任一通路都不是環(huán)路，則稱廬有向圖為 無環(huán)路有向圖，簡稱DAG。 3語法分析按文法的產(chǎn)生式識別輸入的符號串是否為一個句子的分析過程。 4短語令G是一個文法。S劃文法的開始符號，假定是文法G的一個句 型，如果有SA且AB，則稱是句型相對非終結(jié)符A的短語。 5后綴式一種把運(yùn)算量寫在前面，把算符寫在后面的表示表達(dá)式的方法。 四、簡述題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)化：對程序進(jìn)行各種等價變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。(2分) 三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。(2分) 6、 答：目標(biāo)代碼通常采用三種形式：機(jī)器語言，匯編語言，待裝配機(jī)器語言模塊。(2分) 應(yīng)著重考慮的問題： (1)如何使生成的目標(biāo)代碼較短； (2)如何充分利用寄存器，以減少訪問內(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| 評分細(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) 評分細(xì)則：控制結(jié)構(gòu)4分，其它3分。 4、解：(1) 最右推導(dǎo)： ETF(E)(ET)(EF)(Ei) (Ti)(T*Fi) (2) 短語：(T*Fi)，T*Fi，T*F，i(2分) 素短語：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é)期）一、簡答題（15分）1. 編譯程序與解釋程序有何區(qū)別？2. 何謂素短語？3. 過程調(diào)用時，主調(diào)程序與被調(diào)程序之間的信息傳遞有哪些方式？4.

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

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

31、| if B then E else E其中，第三個候選式稱為條件算術(shù)表達(dá)式，B為布爾表達(dá)式，then及else后的E均為算術(shù)表達(dá)式（即簡單算術(shù)表達(dá)式或條件表達(dá)式），其語義為，當(dāng)B為真時，表達(dá)式的值取then后的E的值，否則取else的E的值。假定所有表達(dá)式是整型的，試將下面關(guān)于條件算術(shù)表達(dá)式的屬性翻譯文法填寫完全：八、 （8分）給定PASCAL程序語句while ab do if a0 then a:=a-1 else a:=a+1; 1. 將該語句翻譯成逆波蘭式； 2. 給出編譯程序掃描到then處及分號處時所得的四元式序列。九、 (7分)用DAG圖對下面的基本塊進(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 參考答案： 一、 簡答題（15分）1. 編譯程序與解釋程序有何區(qū)別？答：二者的工作方法不同，后者是邊解釋邊執(zhí)行，解釋所得的代碼并不保存；前者是先將高級語言翻譯感情上標(biāo)代碼，將其保存到指定的空間中，待需要時再執(zhí)行之，甚至可以在案一個機(jī)器上編譯，而在另一臺機(jī)器上執(zhí)行。2. 何謂素短語？答：素短語是滿足下述條件的短語：（1）它至少含有一個終結(jié)符號（2）滿足條件（1）的“最小”短語3. 過程調(diào)用時，主調(diào)程序與被調(diào)程序之間的信息傳遞有哪些方式？答：形式參數(shù)與實(shí)在參數(shù)結(jié)合方式傳遞（簡稱參數(shù)

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