編譯原理樣題1解析

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

2、自上而下分析法是指 （）。5、 如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹，則稱這個(gè)文法是（）。6、對(duì)于文法G,僅含終結(jié)符號(hào)的句型稱為 （）。7、逆波蘭式ab十c+ d*e 所表達(dá)的表達(dá)式為（）。8、 一個(gè)名字的屬性包括（）和（）。9、 對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用（）策略，PASCAL采用（）策略。10、所謂優(yōu)化是指（）。三、名詞解釋題（每題 2分，共10 分）1、詞法分析器：2、語(yǔ)法：3、最右推導(dǎo)： 4、語(yǔ)法制導(dǎo)翻譯：_5、基本塊：四、簡(jiǎn)述題（每題 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ù)傳遞的方式分別采用傳地址和傳值時(shí)，程序執(zhí)行后輸出al,是什么？2、畫出識(shí)別pascaI中實(shí)常數(shù)(可帶正負(fù)號(hào)，但不含指數(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、符號(hào)表的作用是什么？符號(hào)表的查找和整理技術(shù)有哪幾種？6、何謂DISPLAY表？其作用是什么？五、計(jì)算題(10分)1、 寫一個(gè)文法使其語(yǔ)言為偶數(shù)集，且每個(gè)偶數(shù)不以0開頭。(5分)2、已知文法G( S):St a|(T)TT , S|S(1) 給出句子(a, (a, a)的最左推導(dǎo)并畫出語(yǔ)法樹；(2) 給出句型(T, s)a )的短語(yǔ)、直接短語(yǔ)、句柄。 (8分)3、把語(yǔ)句if x >0 y>0 then z：= x+ yelse Begi nx: = x+ 2y: = y+ 3 En d;翻譯

5、成四元式序列。(6分)4、設(shè)某語(yǔ)言的 for 語(yǔ)句的形式為 for i: = E to E do S其語(yǔ)義解釋為（1）i： = ELIMIT: = Eagain: if i v= LIMIT thenBeginS;i: = i + 1goto againEnd;（1 ）寫出適合語(yǔ)法制導(dǎo)翻譯的產(chǎn)生式； （2）寫出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作。 （6 分）5、設(shè)文法 G（ S）：SS + aF|aF|+ aFFt *aF|*a（1 ）消除左遞歸和回溯；（2）構(gòu)造相應(yīng)的 FIRST 和 Follow 集合；（3）構(gòu)造預(yù)測(cè)分析表。 （10 分）6、對(duì)以下基本塊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 在基本塊出口之后還被引用，請(qǐng)寫出優(yōu)化后的四元式序列。編譯原理答案一、是非題（下列各題你認(rèn)為正確的，請(qǐng)?jiān)陬}干的括號(hào)內(nèi)打“V，錯(cuò)的打“X。每題1分,共5分）1. V 2. X 3. V 4. V 5. X、填空題（每題 2分，共5 分）1語(yǔ)法；語(yǔ)義2基本字、標(biāo)識(shí)符、常量、算符。界符3單詞符號(hào)串；語(yǔ)法單位4.從開始符號(hào)出發(fā)，向下推導(dǎo)，推出句子6.句子8.類型；作用域5二義的7. (a+

7、 b+ c)*d e9. 靜態(tài)存儲(chǔ)分配10. 對(duì)程序進(jìn)行各種等價(jià)變化，使得從變換后的程序出發(fā)，能生成更有效的目標(biāo)代碼三、名詞解釋題（每題 2分，共10分）1. 指執(zhí)行詞法分析的程序。2. 是一組規(guī)則，用它可以形成和產(chǎn)生一個(gè)合法的程序。3. 指任何一步a推出B都是a中的最右非終結(jié)符替換。4. 在語(yǔ)法分析過程中，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序進(jìn)行翻譯的辦法叫做語(yǔ)法制 導(dǎo)翻譯。5. 指程序中一個(gè)順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口，一個(gè)出口，入口即第一個(gè)語(yǔ) 句。出口即第二個(gè)語(yǔ)句。四、簡(jiǎn)述題（每題 4分，共24 分）1. 答：傳地址：a= 10, b = 6（每個(gè)值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)的各種名字及信息，以及編譯各階段的進(jìn)展?fàn)顩r。 主要技術(shù)： （ 2 分） 線性表，對(duì)折查表與二叉樹，雜湊技術(shù)。6. 答： display 表是嵌套層次顯示表。 由于過程嵌套允許內(nèi)層過程引用外層過程

9、定義的數(shù)據(jù)，因此，當(dāng)一個(gè)過程運(yùn)行時(shí)必須跟蹤它的所有外層過程的最新活動(dòng)記錄起始地址，而 display 表就是用于登記每個(gè)外層過程 的最新活動(dòng)記錄起始地址。五、計(jì)算題（ 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)短語(yǔ)：(2 分)(T, S), a)(T, S), a(T, S)T, Sa直接短語(yǔ)：(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)(每個(gè)語(yǔ)義動(dòng)作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')= #