華東交通大學(xué)編譯原理試題庫試卷九

1、一、填空題(每題2分，共20分)1、 語法分析是依據(jù)語言的 規(guī)則進行的，中間代碼產(chǎn)生是依據(jù)語言的 規(guī)則進行的 。2、程序語言的單詞符號一般可以分為 等等。 3、語法分析器的輸入是 ，其輸出是 。4、所謂自上而下分析法是指 。5、如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是 。 6、對于文法G，僅含終結(jié)符號的句型稱為 。7、逆波蘭式ab+c+d*e-所表達式為 。 8、一個名字的屬性包括 和 。9、對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用 策略，PASCAL采用 策略。 10、所謂優(yōu)化是指 。 二、名詞解釋(每題2分，共10分)    1

2、、詞法分析器    2、語法    3、最右推導(dǎo)    4、語法制導(dǎo)翻譯    5、基本塊三、簡述題(每題4分，共24分)    1、考慮下面程序      .     Var i:integer;     a:array1.2 of integer;

3、60;   procedure Q(b);     Var b:integer;     begin     i:=1;b:=b+2;     i:=2;b:=b+3     End;     begin     a1:=5;a2:=6;     i

4、:=1;     Q(ai);print(a1,a2)     END.     試問：若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出a1,    a2的值是什么?       2、畫出Pascal中實數(shù)(不帶正負號，可帶指數(shù)部分)的狀態(tài)轉(zhuǎn)換圖。    3、已知文法G(S): Sa|(T)   TT,S|S 的

5、優(yōu)先關(guān)系表如下： 關(guān)系a(),a-;(<<=<)->>,<<>>請計算出該優(yōu)先關(guān)系表所對應(yīng)的優(yōu)先函數(shù)表。    4、寫出表達式(a+b)/(a-b)-a(a+b*c)的三元式序列及四元序列。    5、符號表的作用是什么？符號表的查找的整理技術(shù)有哪幾種?     6、所謂DISPLAY表？其作用是什么? 四、計算題(共41分)    1、寫一個文法，使其語言是偶數(shù)集，且每個

6、偶數(shù)不以0開頭。(5分)    2、已知文法G(S):         Sa|(T)         TT,S|S      給出句子(a,(a,a)的最左推導(dǎo)并畫出語法樹；      給出句型(T,S),a)的短語、直接短語、句柄。(8分)     3、把語句  &#

7、160;      if x>0y>0 then z:=x+y         else begin         x:=x+2;         y:=y+3         END;  

8、60;  翻譯成四元式序列。(6分)     4、設(shè)某語言的for語句的形式為         for i:=E(1) TO E(2) do S         其語義解釋為         i:=E(1);        

9、60;LIMIT:=E(2);         again:if i<=LIMIT then         BEGIN         S;         i:=i+1;         g

10、oto again         END;     寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；     寫出每個產(chǎn)生式對應(yīng)的語義動作。(6分)     5、 設(shè)文法G(S):         SS+aF|aF|+aF         F*aF|*a

11、     消除左遞歸和回溯；      構(gòu)造相應(yīng)的FIRST和FOLLOW集合；      構(gòu)造預(yù)測分析表(10分)         6、對以下基本塊         T1:=2         T2:=A-B    &

12、#160;    T3:=A+B         T4:=T2*T3         T5:=3*T1         T6:=A-B         L:=A+B        

13、 T7:=T6*L         T8:=T5*4         M:=T8+T7         L:=M     畫出DAG圖；      假設(shè)只有L在基本塊出口之后還被引用，請寫出優(yōu)化后的四元式序列。(6分) 參考答案一、填空題1、語法、語義2、基本字、標(biāo)識符、常量、算符、界符3、單詞符號

14、串、語法單位4、從開始符號出發(fā)，向下推導(dǎo)，推出句子5、二義的6、句子7、(a+b+c)*d-e8、類型、作用域9、靜態(tài)存儲分配、動態(tài)存儲分配10、對程序進行各種等價變換，使得從變換后的程序出發(fā)，能生成更有效的目標(biāo)代碼二、名詞解釋1詞法分析器指執(zhí)行詞法分析的程序。 2語法一組規(guī)則，用它可以形成和產(chǎn)生一個合式的程序3最右推導(dǎo)指對于一個推導(dǎo)序列中的每一步直接推導(dǎo)，被替換的總是當(dāng)前符號串中的最右非終結(jié)符號。4語法制導(dǎo)翻譯在語法分析過程中，根據(jù)每個產(chǎn)生式所對應(yīng)的語義子程序進行翻譯的辦法叫做語法制導(dǎo)翻譯。5基本塊指程序中一個順序執(zhí)行的語句序列，其中只有一個入口，一個出口，入口即第一個語句。出口即最后一個語

15、句。三、簡述題1、答：傳地址：a=10 , b=6 ；（2分）            傳  值：a=5  , b=6 。（2分）3、答：優(yōu)先函數(shù)表如下(f函數(shù)2分，g函數(shù)2分) 函數(shù)a(),f4244g5523?     4、答： 三元式2分          .(+,a,b)       

16、0;   .(-,a,b)           .(/,)           .(*,b,c)           .(+,a,)           .(-,)         

17、0; 四元式2分           .(+,a,b,T1)           .(-,a,b,T2)           .(/,T1,T2,T3)           .(*,b,c,T4)        

18、0;  .(+,a,T4,T5)           .(-,T3,T5,T6) 5、答：          作用：登記源程序中出現(xiàn)的各種名字及其信息，以及編譯各階段的進展?fàn)顩r。(2分)          主要技術(shù)：線性表，對折查找與二叉樹，雜湊技術(shù)。(2 分) 6、 答： display表是層次顯示表。    

19、60;     由于過程嵌套允許內(nèi)層過程引用外層過程定義的數(shù)據(jù)，因此，當(dāng)一個過程運行時必須跟蹤它的所有外層過程的最新活動記錄起始地址，而display表就是用于登記每個外層過程的最新活動記錄起始地址。四、計算題 1、 答：         文法G(S):         SAB|B|A0         AAD|C &

20、#160;       B2|4|6|8         C1|3|5|7|9|B         D0|C 2、答：         最左推導(dǎo)：(2分)         S=>(T)=>(T,S)

21、=>(S,S)         =>(a,S)=>(a,(T)=>(a,(T,S)         =>(a,(S,S)=>(a,(a,S)         =>(a,(a,a)         語法樹：(2分，此處略) 3、 答： &#

22、160;        (j>,x,0,3)          (j,-,-,8)          (j>,y,0,5)          (j,-,-,8)          (+,x,y,T1

23、)          (:=,T1,-,Z)          (j,-,-,12)          (+,x,2,T2)          (:=,t2,-,X)          (+,Y,3,

24、t3)          (:=,T3,-,y)                  (控制結(jié)構(gòu)3分，其它3分) 4、答：          (2分)         Ffor i:=E (1) to

25、E (2) do         SF S(1)          (每個語義動作2分)         Ffor i:=E (1) to E (2) do         GEN(:=,E (1) .place,-,entry(i);    

26、60;    F.place:=entry(i);         LIMIT:=Newtemp;         GEN(:=,E (2) .place,-,LIMIT);         :=NXQ;         F.QUAD:=q

27、;         GEN(j,entry(i),LIMIT,q+2)         F.chain:=NXQ;         G)j,-,-,0)         SF S (1)        

28、0;BACKPATCH(S (1) .chain,NXQ);         GEN(+,F.place,1,F.place);         GEN(j,-,-,F.QUAD);         S.chain:=F.chain 5、答：          (消除左遞歸2分，提公共左因子2分)          SaFS'|+aFS'          S'+aFS'|          F*aF' &