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

1、一、填空題(每題2分，共20分)1、 語法分析是依據(jù)語言的 規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語言的 規(guī)則進(jìn)行的 。2、程序語言的單詞符號(hào)一般可以分為 等等。 3、語法分析器的輸入是 ，其輸出是 。4、所謂自上而下分析法是指 。5、如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是 。 6、對于文法G，僅含終結(jié)符號(hào)的句型稱為 。7、逆波蘭式ab+c+d*e-所表達(dá)式為 。 8、一個(gè)名字的屬性包括 和 。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ù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出a1,    a2的值是什么?       2、畫出Pascal中實(shí)數(shù)(不帶正負(fù)號(hào)，可帶指數(shù)部分)的狀態(tài)轉(zhuǎn)換圖。    3、已知文法G(S): Sa|(T)   TT,S|S 的

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

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)生式；     寫出每個(gè)產(chǎn)生式對應(yīng)的語義動(dò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)識(shí)符、常量、算符、界符3、單詞符號(hào)

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

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)的各種名字及其信息，以及編譯各階段的進(jìn)展?fàn)顩r。(2分)          主要技術(shù)：線性表，對折查找與二叉樹，雜湊技術(shù)。(2 分) 6、 答： display表是層次顯示表。    

19、60;     由于過程嵌套允許內(nèi)層過程引用外層過程定義的數(shù)據(jù)，因此，當(dāng)一個(gè)過程運(yùn)行時(shí)必須跟蹤它的所有外層過程的最新活動(dòng)記錄起始地址，而display表就是用于登記每個(gè)外層過程的最新活動(dòng)記錄起始地址。四、計(jì)算題 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)          (每個(gè)語義動(dòng)作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' &