編譯原理答案解析

1、湖北第二師范學院2014-2015學年度第二學期編譯原理課程考試答案（B卷）院 系：計算機學院學生姓名：考試方式:閉卷專業(yè)班級： 學 號： 得分評卷人題號-二三四五總分簽名分數(shù)一.填空題（每空1分，共10分）1. 從編譯系統(tǒng)的方式看，有兩種編譯方式，一種是（解釋 ）方式，另一種是（編譯 ）。2. 編譯的過程一般講，有（詞法分析 ）,（語法分析）,（語義分析），（中間代碼生成），（中間代碼優(yōu)化）和（目標代碼生成）。3. 程序設(shè)計語言的發(fā)展帶來了日漸多變的運行時存儲管理方案，主要分為兩大類，即（靜態(tài)存儲分配 ）方案和（動態(tài)存儲分配）方案。得分評卷人二、綜合題（共90分）1. （5分）構(gòu)造語言a3n

2、|nl的文法答案：苴文法是（5分）P （A）： A-*aaa aaaA2. （5分）給出下面表達式的逆波蘭表示：a*b+（cd）/e答案：ab*cde/+（5 分）3. （30分）給左文法GE:E - E+T TT - T*F FF - （E） | i該文法是LL（1）文法嗎？為什么？不是的能否改造為LL （1）文法，如果能夠改造，給岀改 造后的文法，并給出改造后文法是LL （1）文法的證明過程。無論改造前還是改造后的文法，如果 是LL （1）文法，則給出（i+i） *i的分析過程（要求給出詳細過程，并給出LL （1）的分析表） 答案：（1）該文法不是LL （1）文法，因為文法的產(chǎn)生式含有左遞

3、歸（2分）（2）該文法可改造為LL （1）文法，即消除左遞歸，改造后的文法是（3分）E _ TE，E' - +TE' £T _ FT， 一 *FT £F - （E） i證明改造后的文法是LL （1）文法的過程A.求可達£的非終結(jié)符 可達的是E' ,T'（1分）B.求每個非終結(jié)符的First集合 First (E) = (, iFirst (Ef ) = +First (T) = (, iFirst (Tf ) = *First (F) = (, i（3分）C.求每個產(chǎn)生式右部字符串的First集合First (TE ) = (, i

4、First (+TE, ) = +First (FTJ ) = (, iFirst (*FT, ) = *First(E)= ( First (i) = i First ( e ) = £ （3分）D.求每個非終結(jié)符的Follow集合Fol low (E) = $,)Fol low (E )= Follow (E) = $,)（3分）Follow(T)=First(E, ) U Follow(E) = $,+,)Follow(T' )= Follow(T)=$,+,)Follow(F)= First(T, ) U Follow(T) = $,+, *,)E.求每個非終結(jié)符的S

5、elect集合（5分）Select (E » TE )=First(TE, )=Ci Select(E*-+TE' ) hirst (+TE)= +Select(E*f £ )=First( e )- e ，U Follow(E, ) = $,) Select(T - FT )=First(FT, ) = Ci Select(T*-*FT, )=First(*FTr)= *Select(T 一 £ )二First仁)- e U Follow(T, ) = $,+,) Select(F 一 (E)=First(E)= ( Select(F 一 i)二Firs

6、t(TE )= i F.求有多個產(chǎn)生式的非終結(jié)符Select集合的交集(2分)顯然有Select(E - +TE' ) nSelect(Ef - £)二0>Select(T - *FV ) ASelect(T, - £)二Select(F - (E)= nSelect(F - i)=所以改造后的文法是LL (1)文法(3)、根據(jù)E給出預測分析表(4分)非終 結(jié)符終結(jié)符+()1sE_TE'_TEE，-+TE'f E-* eT-* FT'T，f *FTf E-* eF-(E)f 1符號串(i+i) *i的分析過程(4分)步驟符號棧Si輸入符

7、號串產(chǎn)生式1SE(i+i)*i$E TE，2SE' T(i+i)*i$T- FT'3SE'F(i+i)*i$F- (E)4SE， T ) E (i+i)*i$SE， T ) Ei+i)*i$E_TE，SE' r ) E Ti+i)*i$T- FT't ) e T Fi+i)*i$F-iSE' T ) E T ii+i)*i$SE' T ) E T+i)*iST* £SE， r ) E+i)*iSE' -+TE'SE' T ) E T+i)*iSSE' T ) E Ti)*iST_FVt ) E V

8、 Fi)*iSF-iSE， r ) e T ii)*iSSE， t ) E T)*i$T* -* eSE， V ) E)*i$E* _ eSE')*i$SE' V*i$T- *FTSE' V F*i$SE'Fi$F-iSE，$T' -* £SE，E* -* £S4. （10分）對下面的DFA進行最簡化答題：第1步：確左化過程（5分）將7個狀態(tài)分成兩個狀態(tài)集,終態(tài)集q5, q6,非終態(tài)集q0, ql, q2, q3, q4, q7分割前狀態(tài)集lxIy分割后狀態(tài)集IqO, ql, q2, q3, q4, q7ql, q3q5, q6q0,

9、 ql, q2, q3, q4, q7q0, qlqO, ql, lq3, q4, q7Jq0, qllq3, q4, q7qo, q6q3, q4, q7Eq3, q4, q7qo, q6q5, q6q3, q4, q7q5, q6根據(jù)上表命名不可分割的終態(tài)集，及到達狀態(tài)分割前狀態(tài)集lxIyq00ql1q22ql1lq3, q4, q7J3q22q3, q4, q73lq3, q4, q73lq5, q64q3, q4, q73lq5, q64lq5, q64q3, q4, q735. （15分）給定文法GE：T - T*FF - (E)該文法是算符優(yōu)先文法嗎？是，則構(gòu)造該文法的算符優(yōu)先關(guān)系

10、矩陣，并給出（i+i）心的分析 過程（要求給出詳細過程）答案：（1）該文法是算符優(yōu)先文法（1分）（2）構(gòu)造該文法的算符優(yōu)先矩陣扎 求各非終結(jié)符的FirstVT集合（3分）FirstVT （E）二+,*,（, iFirstVT （T）二*, （, iFirstVT （F） = （, iB.求各非終結(jié)符的LasttVT集合(3分)LastVT(E) = +, *, ), i LastVT(T) = LastVT(F) = ), i C.構(gòu)造優(yōu)先關(guān)系表（4分）()1S-><<><>*>><><>(<<<二<

11、;)>>>>1>>>>S<<<<二（3）分析（i+i） *過程（4分）步驟符號棧S關(guān)系輸入符號串最左素短語$<(i+i)*iS$(<i+i)*iS$(i>+i)*i$1$(V<+i)*i$(V+<i)*i$ (V+i>)*i$1$(v+v>)*i$v+v$(V二)*i$(V)>*i$(V)$v<*i$v-<i$V*i<$1$v*v>$v*v$v二s6. (25分)給左文法GE:E - E+T TT - T*F FF - (E) | i該文法是LR (0

12、)文法嗎？是，則構(gòu)造該文法的LR (0)分析表，并給岀(i+i) *i的分析過 程，不是的，是SLR (1)文法嗎，是，則構(gòu)造該文法的SLR (1)分析表，并給出(i+i) *i的分 析過程。(要求給出詳細過程)答案：(1)拓廣文法(2分)0、E'-E1、E-E+T2、E-T3、T-T*F4. T-F5、F-(E)6、F f 1(2) 構(gòu)造LR (0)項目集規(guī)范簇(10分)(3) 在下圖的DFA中，II、12、19均發(fā)生了規(guī)約一一移進沖突，所以該文法不是LR (0)文法。(2分)(4) 在II規(guī)范項目集中規(guī)約項目E' -E.的Follow (E')二$,而移進項目的移進

13、符號 集二 + , Follow (E) C + 二在12規(guī)范項目集中規(guī)約項目E -T.的Follow (E) = $, +,),而移進項目的移進符號集二 *, Follow (E) n * = 0)在19規(guī)范項目集中規(guī)約項目E -E+T.的Follow (E) = $, +,),而移進項目的移進符號集 =*, Follow (E) A * = 0)所以，在3個發(fā)生沖突的項目集中可解決沖突，因此該文法是SLR(1)文法(5分)10EIIE' f.EE，_EE-.E+TE-E +TE-.TT-T*FT-FT12Ff (E)E7F-iT-*T. *FT16E-E+ TT-.T*FT-.FF

14、-(E)Fi19131415FE-E+T.T7 *F7+.1E-E. +TT-T*F13T -F.18F- (E.)TT* FF-(E)14F- (. E)E-E+TE_TT_T*FT 一F F-(E)110IllF一 (E).狀態(tài)ActionGoto1+*()$ETF0S5SI1231S6acc2r2S7r2r23rlr 1rlrlrlrl4S5SiS235r6r6r6r6r6r66S5Si937S5Si108S6SU9rlS7rlrl10r3r3r3r3r3r311r5r5r5ror5r5（5）根據(jù)上面的DFA建立SLR （1）的分析表（4分）（6）分析（i+i）相的過程（4分）棧內(nèi)容輸入符號串動作0(i+i) *i$移進0(4ii) *i$移