《編譯原理》期末試卷+參考答案

1、編譯原理軟件工程2005級期終考卷 學號：姓名：說明 :1.本考卷中大寫字母vn ，其他符號vt；2、試卷中一、二兩題請作在考卷上一、 概念題（ 15 分）1、編譯過程一般分為幾個階段？各階段的輸入輸出分別為什么？2、對下列狀態(tài)轉(zhuǎn)換圖，寫出狀態(tài)0 的處理過程：其中：狀態(tài)2 的過程為proc2. 3、文法 g 為：saab aa b|則判斷 g 為 ll （ 1）文法的條件是： 二、判斷題（10 分。注：每答對一題得+2 分；答錯一題得-2 分；不答者得0 分）1、設為 a，b，則 a，ba，? 都是上的正規(guī)式。（）2、對于上下文無關(guān)文法gs ，若s ab則 a一定是一條產(chǎn)生式規(guī)則，其中 , ,

2、 （ vtvn）* （）3、對于逆波蘭后綴式，無論從哪頭開始分析均可得到唯一正確的分解。（）4、 lr（ 0）分析法是一種規(guī)范歸約法。（）5、算符優(yōu)先分析法只能用來分析算符優(yōu)先文法。 （ ） 三、 （10 分）設文法g3 為： saabc aaa|a bb 求句型 aabc 的最左素語。0 1 2 字母其他數(shù)字字母四、 （20 分）設文法gs為 saacb 問：1、該文法是否為算符文法，為什么？ aab|b 2、構(gòu)造算符優(yōu)先關(guān)系表。 bd 3、該文法是否可改造為ll（1）文法，為什么？ 五、 （本題 20 分）設文法g為： eeaf|ebg aaa|a bbb|a 對于輸入串eaaaf，采用l

3、r （0） 、ll（1） 、slr （1）等方法中合適的一種進行分析。 六、 （25 分）有作控制用的布爾表達式文法ge及其語義動作如下： 1、 構(gòu)造 slr （1）分析表（若不是slr(1)）的，則說明理由） 2、 分析布爾式a bc 的四元式生成過程，并畫出最后的真假鏈表。3、 給出語句 if a bc then i:=m*n else i:=m+n的完整四元式序列。文法 ge： (1)ei( )1i( )2 e.tc:=nxq; e.fc=nxq+1; gen(j b c # = 對于#aabc# ，#，則最左素短語為aabc 。 四、 （20 分） 1、該文法是算符文法。因為其任一產(chǎn)生

4、式的右部都不含相繼（并列）的非終結(jié)符，即不含如下形式qr 的產(chǎn)生式右部。（4 分）2、first(s)=a, last(s)=c, first(a)=b, last(a)=b, first(b)=d, last(b)=d。（3 分）構(gòu)造算符優(yōu)先關(guān)系表如下：（5 分）a b c d # a b c d # = 3、該文法可以改造為ll（1）文法。 （8分）原因： 消除左遞歸：saacb aba aba | bd； first(a)=a, follow(a)=c, first(a )=b, , follow(a)=c, first(b)=d, follow(b)=#, first(s)=a, fo

5、llow(s)=#, 對于每個非終結(jié)符的各個產(chǎn)生式的first集兩兩不相交； 對于 a，first （a）follow（a）=。 綜上所述，原文法可以改造成ll（1）文法。 五、 （20 分） 原文法不是 ll（1）文法，故不能直接使用ll（1）分析法進行分析。 步驟如下： 1、拓廣文法：ee eeaf eebg aaa aa bbb ba （2分） 2、項目集規(guī)范族： （6分）由此項目集規(guī)范族可判斷，原文法非lr （0）文法，故不能直接使用lr （0）分析法進行分析。因此，使用slr （1）分析法分析原文法。 3、構(gòu)造 slr （1）分析表如下： follow(a)=f ；follow(b)

6、=b,g ；follow(e)=#。 action goto 狀態(tài) a b e f g # a b e 0 s2 1 1 acc 2 s4 3 5 3 s6 4 s8 r7 r5 r7 7 5 s10 s9 6 r2 7 r4 8 s8 r5 7 9 r3 10 r6 r6 （6分） 4、分析輸入串 eaaaf 如下： 步驟 狀態(tài) 符號 輸入串 動作 1 0 # eaaaf# 預備 2 02 #e aaaf# 移進 3 024 #ea aaf# 移進 4 0248 #eaa af# 移進 5 02488 #eaaa f# 移進 6 02487 #eaaa f# 歸約 7 0247 #eaa f

7、# 歸約 8 023 #aa f# 歸約 9 0236 #aaf # 移進 10 01 #e # 歸約 11 acc 接受 （6分） 六、 （25 分） 1、步驟： （1）拓廣文法：ee ei(1)i(2)eae(1) ab bi （2分）（2）項目集規(guī)范族： （6分） （3）slr （1）分析表如下： follow(e)=#；follow(a)=i ；follow(b)= 。 action goto 狀態(tài) i # e a b 0 s2 1 3 4 1 acc 2 s6 r4 3 s2 7 3 4 4 s5 5 r3 6 s8 7 r2 8 r1 （6分） 2、分析輸入串 abc 如下： 步驟

8、 狀態(tài)棧 符號 輸入串 動作 四元式 1 0 # abc# 預備 2 02 #i bc# 移進 3 04 #b bc# 歸約 b.tc=1,b.fc=2; gen(jnz,a,_,0); gen(j,_,_,3); 4 045 #b bc# 移進 5 03 #a bc# 歸約 a.tc=b.tc=1; backpatch(2,3); 6 032 #ai c# 移進 7 0326 #ai c# 移進 8 03268 #aii # 移進 9 037 #ae # 歸約 e.tc=3,e.fc=4; gen(j,b,c,0); gen(j,_,_,0); 10 01 #e # 歸約 e.fc=4; e.tc=merg(1,3); 11 acc 接受 （6分） 整理： 真出口為 3； 假出口為4。 （2 分）3、四元式： 1、 （jnz,a,_,5 ） 2、(j,_,_,3) 3、(j,b,c,5) 4、(j,_,_,8) 5、(*,