2014編譯原理練習(xí)題題解.doc

桂 林 電 子 科 技 大 學(xué) 試 卷 2012-2013 學(xué)年第 2 學(xué)期 課號 課程名稱 編譯原理試題、答案和評分標準 （A卷;閉卷） 適用班級（或年級、專業(yè)） 01應(yīng)本 考試時間 120 分鐘 班級 學(xué)號 姓名 題 號一二三四五六七八九十成績滿 分208661510101510100得 分評卷人一、填空題|（每題4分，共20分）1. 喬母斯基定義的3型文法（線性文法）產(chǎn)生式形式 ABa|a,或AaB|a，A，BVn,a,bVt 。2.語法分析程序的輸入是 單詞符號，其輸出是 語法單位 。3 型為 B .aB 的LR（0）項目被稱為 移進 項目，型為 B a.B 的LR（0）項目被稱為 待約 項目，4.在屬性文法中文法符號的兩種屬性分別為 繼承屬性 和 綜合屬性 。5、運行時存貯管理方案有 靜態(tài)存儲分配、動態(tài)存儲分配 和 堆式存儲分配 和方案。 二.已知文法 G(S)(1) E T | E+T(2) T F | T*F(3) F （E）| i （1）寫出句型（T*F+i）的最右推到并畫出語法樹。（4分） （2）寫出上述句型的短語，直接短語和句柄。（4分）答：（1）最右推到（2分） E = T = F = (E) = (E+T) = (E+F) = (E+i) = (T+i) = (T*F+i)(2) 語法樹（2分）（3）（4分） 短語： （T*F+i） ，T*F+i ，T*F ， i 直接短語：T*F ， i 句柄：T*F 三. 證明文法 G(S) ： S SaS | 是二義的。（6分）答：句子 aaa對應(yīng)的兩顆語法樹為：因此，文法是二義文法四.給定正規(guī)文法G（S）： (1) S Sa | Ab |b(2) A Sa 請構(gòu)造與之等價的DFA。（6分）答：對應(yīng)的NFA為： （6分）狀態(tài)轉(zhuǎn)換表：abFSSS,AS,AS,AS五. 構(gòu)造識別正規(guī)語言b*a(bb*a)*b* 最小的DFA（要求寫出求解過程）。（15分）答：（1）對應(yīng)的NFA（5分） （2）將（1）所得的NFA確定化：（5分）ab01，301,32，32,31,32,3（5分）六. 已知文法G(S) :(1) S | a | (T)(2) T T,S | S試：（1）消除文法的左遞歸；（4分） （2）構(gòu)造相應(yīng)的first 和 follow 集合。（6分）答：（1）消除文法的左遞歸后文法 G（S）為： (1) S | a | (T)(2) T ST | S(3) T ,ST | （4分） （2）（6分）firstfollowSa (# , )Ta ()T, )七. 已知文法G(S) :(1) S SiA | A(2) A A+B | B(3) B A* | （試構(gòu)造非終止符的firstVT和lastVT集合。（10分）答：（10分）firstVTlastVTSi , + , * , ( i , + , * , (A+ , * , (+ , * , (B* , (* , (FollowS#Ba,b,#八.已知文法G(S) :(1) S B B(2) B a B(3) B b 的follow集合如表：試：（1）給出該文法的LR（0）項目集規(guī)范族劃分； （2）填寫相應(yīng)的SLR（1）的分析表。（15分）答：（1）LR（0）項目集規(guī)范族劃分(8分)I0S .SS .BBB .aBB .b- I1- I2- I3- I4SBa bI1S S.I2S B.BB .aBB .b- I5- I3- I4Ba bI3B a.BB .aBB .b- I6- I3- I4Ba bI4B b.I5S BB.I6B aB. (2) SLR(1)分析表（7分）狀態(tài)ActionGotoab#SB0S3S4121Acc2S3S453S3S464R3R3R35R16R2R2R2九設(shè)某語言的not-then-else 語句的語法形式為：S not E then S1 其語義解釋為： 針對自上而下的語法分析器，(1) 分段產(chǎn)生式；（3分）(2) 寫出每個產(chǎn)生式對應(yīng)的語義動作。（7分）答：（1）分段產(chǎn)生式（3分）及語義動作(7分) (1) R not E then Backpatch（$2.FC ，nxq ）;$.chain = $2.Tc (2) S R S1 Backpatch（$2.chain ， nxq ）桂 林 電 子 科 技 大 學(xué) 試 卷 2012-2013 學(xué)年第 2 學(xué)期 課號 122239 課程名稱 編譯原理試題、答案和評分標準 （B卷;閉卷） 適用班級（或年級、專業(yè)） 01應(yīng)本 考試時間 120 分鐘 班級 學(xué)號 姓名 題 號一二三四五六七八九十成績滿 分208661510101510100得 分評卷人一、填空題|（每題4分，共20分）1. 喬母斯基定義的2型文法（上下文無關(guān)文法）產(chǎn)生式形式 A,AVn, V+。2.詞法分析程序的輸入是 字符串 ，其輸出是 單詞符號 。3 算符有限分析方法每次都是對 最左素短語 進行規(guī)約。型為 B aB. 的LR（0）項目被稱為 規(guī)約 項目。4、寫出x:=b*(d-e)/(c-d)+e的逆波蘭式_xbde-*cd-/e+:=_。5、常用的兩種動態(tài)存貯分配辦法是_棧式存儲 分配 和 堆式存儲_分配。 二已知文法G(S) :(1) S | a | (T)(2) T T,S | S 試：（1）寫出句型（a,(a,a)的最左推到并畫出語法樹。（4分） （2）寫出上述句子的短語，直接短語和句柄。（4分）答：（1）最左推到（2分） S = （T） = （T,S）= (S,S) = (a,S) = (a,(T) = (a,(T,S) = (a,（S,S) = (a,（a,S) = (a,（a,a)(2) 語法樹（2分）（3）（4分） 短語：（a,(a,a)） ，a,(a,a) ， (a,a) ， a,a , a 直接短語：a 句柄：a三證明文法 G(S) ： S aSb | Sb | b 是二義的。（6分）答：句子 aabbbb對應(yīng)的兩顆語法樹為： 因此，文法是二義文法四.給定正規(guī)文法G（S）： (1) S aA (2) A aB | bA （3）B aA | b 請構(gòu)造與之等價的DFA。（6分）答：對應(yīng)的DFA為：（6分） 五. 構(gòu)造識別正規(guī)語言(ab*|a)* 最小的DFA（要求寫出求解過程）。（15分）答：（1）對應(yīng)的NFA （5分） （2）將（1）所得的NFA確定化：（5分）ab11,21,21,21,2 （5分）六. 已知文法G(S) :(1) S | a | (T)(2) T ST | S(3) T ,ST |試：求first和follow集合，構(gòu)造改文法的LL（1）分析表。（10分）答：文法相應(yīng)的first 和 follow 集合 （5分）firstfollowSa (# , )Ta ()T, )其LL（1）分析表如下：七. 已知文法G(S) :(1) S SiA | A(2) A A+B | B(3) B A* | （非終止符的firstVT和lastVT集合如下:firstVTlastVTSi , + , * , ( i , + , * , (A+ , * , (+ , * , (B* , (* , (試構(gòu)造算符的優(yōu)先關(guān)系表。（10分）答：i+()*I()八已知文法G(S) :(1) S a | aAb | b | bBa(2) A 1A0 | (3) B 1B0 | 求 ：該文法的LR（0）項目集規(guī)范族。（15分）答：九設(shè)某語言的DO-while 語句的語法形式為： S do S1 while E 其語義解釋為：針對自上而下的語法分析器，(1) 分段產(chǎn)生式；（3分）(2) 寫出每個產(chǎn)生式對應(yīng)的語義動作。（7分）答：（1）分段產(chǎn)生式（3分） G(S) : (1)