編譯原理樣題1解析

1、編譯原理是非題（下列各題你認(rèn)為正確的，請在題干的括號內(nèi)打“V，錯的打“X。每題1分,共5分）1、 一個LL（ I）文法一定是無二義的。 （）2、 逆波蘭法表示的表達(dá)式亦稱前綴式。 （）3、 目標(biāo)代碼生成時，應(yīng)考慮如何充分利用計算機的寄存器的問題。（）4、 正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。（）5、一張轉(zhuǎn)換圖只包含有限個狀態(tài)，其中有一個被認(rèn)為是初態(tài)，最多只有一個終態(tài)。（ ）二、填空題（每題 2分，共5分）1、 語法分析是依據(jù)語言的 （）規(guī)則進行的，中間代碼產(chǎn)生是依據(jù)語言的（）規(guī)進行的。2、 程序語言的單詞符號一般可以分為（）等等。3、 語法分析器的輸入是（），其輸出是（）。4、所謂

2、自上而下分析法是指 （）。5、 如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是（）。6、對于文法G,僅含終結(jié)符號的句型稱為 （）。7、逆波蘭式ab十c+ d*e 所表達(dá)的表達(dá)式為（）。8、 一個名字的屬性包括（）和（）。9、 對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用（）策略，PASCAL采用（）策略。10、所謂優(yōu)化是指（）。三、名詞解釋題（每題 2分，共10 分）1、詞法分析器：2、語法：3、最右推導(dǎo)： 4、語法制導(dǎo)翻譯：_5、基本塊：四、簡述題（每題 4分，共24 分）l、考慮下面的程序：Var i:integer ；a： array1 - 2 of integer; prn

3、cedure Q( b);Var b： in teger ；Begi ni: = 1; b：= b十 2; i: = 2; b:= b+ 3En d;Begi na1 := 5;a2 ：= 6;i:= 1;Q(ai) ; print(al ,a2)a2的值End.試問，若參數(shù)傳遞的方式分別采用傳地址和傳值時，程序執(zhí)行后輸出al,是什么？2、畫出識別pascaI中實常數(shù)(可帶正負(fù)號，但不含指數(shù)部分)的狀態(tài)轉(zhuǎn)換圖。3、已知文法 G (S):St a| (A)Ttt , S|S的優(yōu)先關(guān)系如下：1a(>>a>(< < <> >< < >

4、 >4、與出表達(dá)式(a+ b) / (ab) (a+ b*c)的三元序列及四元序列。5、符號表的作用是什么？符號表的查找和整理技術(shù)有哪幾種？6、何謂DISPLAY表？其作用是什么？五、計算題(10分)1、 寫一個文法使其語言為偶數(shù)集，且每個偶數(shù)不以0開頭。(5分)2、已知文法G( S):St a|(T)TT , S|S(1) 給出句子(a, (a, a)的最左推導(dǎo)并畫出語法樹；(2) 給出句型(T, s)a )的短語、直接短語、句柄。 (8分)3、把語句if x >0 y>0 then z：= x+ yelse Begi nx: = x+ 2y: = y+ 3 En d;翻譯

5、成四元式序列。(6分)4、設(shè)某語言的 for 語句的形式為 for i: = E to E do S其語義解釋為（1）i： = ELIMIT: = Eagain: if i v= LIMIT thenBeginS;i: = i + 1goto againEnd;（1 ）寫出適合語法制導(dǎo)翻譯的產(chǎn)生式； （2）寫出每個產(chǎn)生式對應(yīng)的語義動作。 （6 分）5、設(shè)文法 G（ S）：SS + aF|aF|+ aFFt *aF|*a（1 ）消除左遞歸和回溯；（2）構(gòu)造相應(yīng)的 FIRST 和 Follow 集合；（3）構(gòu)造預(yù)測分析表。 （10 分）6、對以下基本塊T1 = 2T2 : = A 一 BT3 =

6、A + BT4 = T2*T3T5 = 3*T1T6 = A BT := A + BT7 = T6 + LT8 = T5*4M : = T8 + T7L : = M（1 ）畫出 DAG 圖；6 分）（2）假設(shè)只有 L 在基本塊出口之后還被引用，請寫出優(yōu)化后的四元式序列。編譯原理答案一、是非題（下列各題你認(rèn)為正確的，請在題干的括號內(nèi)打“V，錯的打“X。每題1分,共5分）1. V 2. X 3. V 4. V 5. X、填空題（每題 2分，共5 分）1語法；語義2基本字、標(biāo)識符、常量、算符。界符3單詞符號串；語法單位4.從開始符號出發(fā)，向下推導(dǎo)，推出句子6.句子8.類型；作用域5二義的7. (a+

7、 b+ c)*d e9. 靜態(tài)存儲分配10. 對程序進行各種等價變化，使得從變換后的程序出發(fā)，能生成更有效的目標(biāo)代碼三、名詞解釋題（每題 2分，共10分）1. 指執(zhí)行詞法分析的程序。2. 是一組規(guī)則，用它可以形成和產(chǎn)生一個合法的程序。3. 指任何一步a推出B都是a中的最右非終結(jié)符替換。4. 在語法分析過程中，根據(jù)每個產(chǎn)生式所對應(yīng)的語義子程序進行翻譯的辦法叫做語法制 導(dǎo)翻譯。5. 指程序中一個順序執(zhí)行的語句序列，其中只有一個入口，一個出口，入口即第一個語 句。出口即第二個語句。四、簡述題（每題 4分，共24 分）1. 答：傳地址：a= 10, b = 6（每個值1分）傳值：a= 5, b= 62

8、. 答：3.答：a()f4244g55234. （1）（三元式2分） （+ , a, b） （一，a, b）3（ /,，）*, b, c） （+ , a,） （，）（ 2）（四元式 2 分） （+ , a, b, T1） （,a, b, T2）3（ /, T1 , T2, T3）* , b, c, T4） （+ , a, T4, T5） （，T3, T5, T6）5. 作用：（ 2 分）登記源程序中出現(xiàn)的各種名字及信息，以及編譯各階段的進展?fàn)顩r。 主要技術(shù)： （ 2 分） 線性表，對折查表與二叉樹，雜湊技術(shù)。6. 答： display 表是嵌套層次顯示表。 由于過程嵌套允許內(nèi)層過程引用外層過程

9、定義的數(shù)據(jù)，因此，當(dāng)一個過程運行時必須跟蹤它的所有外層過程的最新活動記錄起始地址，而 display 表就是用于登記每個外層過程 的最新活動記錄起始地址。五、計算題（ 10 分）1. 解：文法 G（ S）：St AB|B|AOA AD|C Bt2|4|6|8 Ct1|3|5|7|9|BDt0|C2.最左推導(dǎo)，分)a(2)短語：(2 分)(T, S), a)(T, S), a(T, S)T, Sa直接短語：(1分)T, Sa句柄：(1分)T, S3. 解:(1) if x>0 goto 3(2) goto 8(3) if y>0 goto 5(4) goto 8(5) t仁x+y(6

10、) z=t1(7) goto 12(8) t2=x+2(9) x=t2(10) t3=y+3(11) y=t3(12)(控制結(jié)構(gòu)3分，其它3分)4. 解：(1) ( 2 分)ifor i : = E to E doSt F Sd)(2)(每個語義動作2分)(1)(2)i for i = E to E doGEN (: = E -place, 一, entry (i);F place := entry (i);LIMIT : = Newtemp;GEN (: =, E place，一, LIMIT ); q: = NXQ ;F QUAD : = q；GEF (j W (entry (i), LI

11、MIT , q + 2) F chain ：= NXQ ;G (j, 0)St F S BACKPATCH (S chain, NXQ );GEN (十，F(xiàn) place, 1, F place);GEN (j, -,-, F QUAD );S chain: = F chain;5解：(1)(消除左遞歸2分，提公因左因子 2分)St aFS'| + aFS'S' t+ aFS'| &Ft *aF'F'tF| £(2) (3分)FIRST (S)= a,十FOLLOW (S)= #FIRST (50) =+, £FOLLOW (S')= #