《編譯原理》期末復(fù)習(xí)資料(完整版)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上1. 給出語言a n b n a mb m | n,m 0的一個上下文無關(guān)文法。(6分)解：GS：SAB AaAb | BaBb |2. 給出語言1 n 0 m 1 m0 n | n,m 0的一個上下文無關(guān)文法。解：GS：S1S0 | AA0A1 |3. P48 第6題（5）、（6）.畫語法樹6、已知文法G：:=:=*:=（）i（）i+(i+i)（）i+i*i解：(5)語法樹： （6）語法樹： 4. P48第13題直接短語等13、 一個上下文無關(guān)文法生成句子abbaa的推導(dǎo)樹如下：(3)求直接短語解：直接短語有：abP102例題6.1及其分析.( 后加畫語法樹) 例6

2、.1 設(shè)文法GS為：(1)SaAcBe (2)Ab (3)AAb (4)Bd對輸入串a(chǎn)bbcde#進(jìn)行分析，檢查該符號串是否是GS的句子。解：設(shè)一個先進(jìn)后出的符號符，并把句子左括號“#”號放入棧底，其分析過程如下：步驟符號棧輸入符號串動作（1）#abbcde#移進(jìn)（2）#abbcde#移進(jìn)（3）#abbcde#歸約（Ab）（4）#aAbcde#移進(jìn)（5）#aAbcde#歸約（AAb）（6）#aAcde#移進(jìn)（7）#aAcde#移進(jìn)（8）#aAcde#歸約（Bd）（9）#aAcBe#移進(jìn)（10）#aAcBe#歸約（SaAcBe）（11）#S#接受語法樹如下： 一、 計(jì)算分析題（60%）1、正規(guī)式

3、 NFA DFA 最簡DFAP72第1題（1）、（4）；第一題1、構(gòu)造下列正規(guī)式相應(yīng)的DFA. （1）1(0|1)*101解：先構(gòu)造NFA用子集法將NFA確定化01SAAAABABACABACAABZABZACAB除S，A外，重新命名其他狀態(tài)，令A(yù)B為B、AC為C、ABZ為D，因?yàn)镈含有Z（NFA的終態(tài)），所以D為終態(tài),因此有：01SAAABBCBCADDCB得到DFA如下所示：(4) b(ab)*|bb)*ab解：先構(gòu)造NFA得到DFA如下所示：P72第4題（a）4、把下圖確定化和最小化解：確定化：用子集法將NFA確定化ab00110101110重新命名，以、代替0、01、1，其中A為初態(tài)，

4、A，B為終態(tài)，因此有：abABCBBCCA最小化：初始分劃得終態(tài)組A,B，非終態(tài)組C0：A,B，C，對終態(tài)組進(jìn)行審查，判斷A和B是等價的，故這是最后的劃分。重新命名，以A、C代替A,B、C，因此有：abAACCA即DFA最小化如下：第7題 7、給文法GS：SaA|bQAaA|bB|bBbD|aQQaQ|bD|bDbB|aAEaB|bFFbD|aE|b構(gòu)造相應(yīng)的最小的DFA。解：先構(gòu)造NFA：用子集法將NFA確定化：abSAQAABZBZQDBQDQQDZDZABDAB將S、A、BZ、B、Q、DZ、D重新命名，分別用0、1、2、3、4、5、6表示。因?yàn)?、5中含有Z，所以它們?yōu)榻K態(tài)。因此有：ab

5、014112246346445513613初始分劃得：終態(tài)組2,5，非終態(tài)組0,1,3,460：2,5,0,1,3,4,6對0,1,3,4,6進(jìn)行審查：1,4輸入b到達(dá)2,5，而0,3,6輸入b到達(dá)3,4,6，故得到新分劃1,4,0,3,61：2,5,1,4,0,3,6對0,3,6進(jìn)行審查：0經(jīng)過b到達(dá)2，3,6經(jīng)過b到達(dá)3,6，故得到新分劃0，3,63：得到最后劃分0，1,4，2,5，3,6重新命名，以A，B，C，D分別代替0，1,4，2,5，3,6,其中A為始態(tài)，C為終態(tài)，可得到最小DFA如下：2、自頂向下方法(一) 設(shè)文法G(E)： E E + T |T T T * F |F F i |

6、 ( E )(1) 判斷是否為LL(1)文法.(2) 構(gòu)造文法的預(yù)測分析表.解：詳見P93-96例題。(1) 由于文法中含有左遞歸，所以必須先消除左遞歸，使文法變?yōu)椋篍TEE+TE|TFTT*FT|F i | ( E ) FIRST集合如下：FIRST（E）=(,iFIRST（E）=+,FIRST（T）=(,iFIRST（T）=*,FIRST（F）=(,i FOLLOW集合如下：FOLLOW（E）=),#FOLLOW（E）=),#FOLLOW（T）=+,),#FOLLOW（T）=+,),#FOLLOW（F）=+,*,),# 各產(chǎn)生式的SELECT集合如下：SELECT（ETE）=(,iSELE

7、CT（E+TE）=+SELECT（E|）=),#SELECT（TFT）=(,iSELECT（T*FT）=*SELECT（T|）=+,),#SELECT（F i）=i SELECT（F ( E )）=(由上可知有相同左部產(chǎn)生式的SELECT集合的交集為空，故文法是LL(1)文法。（2）構(gòu)造文法的預(yù)測分析表如下：i+*()#ETETEE+TETFTFTT*FTF i ( E )(二) P101 6.(4) 改寫下面文法為LL(1)文法，井對每個LL(1)文法構(gòu)造相應(yīng)的預(yù)測分析表。解：3、自底向上方法已知文法G(E): 0 S E1 E E + T2 E T3 T T * F4 T F5 F ( E

8、 ) 6 F i (1) 證明該文法是SLR(1)文法.(2) 若已給出下面的SLR(1)分析表，試分析句子(i + ( * i )#輸入串出錯的位置。狀態(tài)ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r53、解：（1）：先分析LR（0）項(xiàng)目：由上可見：I1 ,I2 ,I9 存在移進(jìn)歸約沖突. 分析FOLLOW集：因?yàn)椋簩1 FOLLOW(S)= # + =對I2FOLLOW(E)= +, #, ) * =對I

9、9FOLLOW(E)= +, #, ) * =所以是SLR(1)文法。（2）：STEPSX( i + ( * i ) #actiongoto10#( i + ( * i ) #S4204# (i + ( * i ) #S53045# (i+ ( * i ) #r634043# (F+ ( * i ) #r425042# (T+ ( * i ) #r286048# (E+ ( * i ) #S670486# (E+( * i ) #S4804864# (E+ (* i ) #error4、(一) 給出語句 if a+b b+c*d then while x*y3 do x:=x-a*b else

10、 while b+c*d10 do b:=b-(x*y+5) 相應(yīng)的三地址代碼. (1)t1=a+b(12)goto (6)(2)t2=c*d(13)goto (23)(3)t3=b+t2(14)t7=c*d(4)if t1t3 goto (6)(15)t8=b+t7(5)goto (14)(16)if t810 goto (18)(6)t4=x*y(17)goto (23)(7)if t43 goto (9)(18)t9=x*y(8)goto (13)(19)t10=t9+5(9)t5=a*b(20)t11=b-t10(10)t6=x-t5(21)b=t11(11)x=t6(22)goto

11、(14)(23)(二) Whilea0 b0do Begin X：X1； if a0 then a：a1 else b：b1 End； 翻譯成四元式序列. (10分)l 解： (1) (j，a，0，5) (2) (j，3) (3) (j，b，0，5）(4) (j，15) (5) (，x，1，T1) (6) (:= ，T1，x) (7) (j，a，0，9) (8) (j，12) (9) (，a，1，T2) (10) (:= ，T2，a) (11) (j，1) (12) (，b，1， T3) (13) (:= ，T3，b) (14) (j，1) (15) 5、(一)設(shè)有基本塊(10分)T1：2T2

12、：10T1T3：SRT4：SRA：T2 * T4B：AT5：SRT6：T3 * T5B：T6(1) 畫出DAG圖；(2) 假設(shè)基本塊出口時只有A，B還被引用，請寫出優(yōu)化后的四元序列。5(一)、解：(1)DAG：(3分) (2) 優(yōu)化后的四元式 T3：SR T4：SR A：5*T4 B：T3T4(二) P255-257 DAG圖例 試構(gòu)造以下基本塊G的DAG(1) T0：3.14(2) T1：2* T0(3) T2：R+r(4) A：T1 * T2 (5) B：A(6) T3：2* T0(7) T4：R+r(8) T5：T3 * T4(9) T6：R-r(10) B：T5 *T6 (11)if B=10 goto (1)(1) 畫出DAG圖；(2) 假設(shè)基本塊出口時只有A，B還被引用，請寫出優(yōu)化后的四元序列。解：（1）DAG圖如下：（2） 四元序列如下： T2：R+r T6：R-r A：6.28* T2 B：A*T6 四、l 1.1 先給出NFA圖：畫狀態(tài)轉(zhuǎn)換表:I01ABCDEABBCBDCBEBBDBBD