編譯原理期末考試習(xí)題及答案(桂電)

1、桂 林 電 子 科 技 大 學(xué) 試 卷 2012-2013 學(xué)年第 2 學(xué)期 課號 課程名稱 編譯原理試題、答案和評分標(biāo)準(zhǔn) （A卷;閉卷） 適用班級（或年級、專業(yè)） 01應(yīng)本 考試時間 120 分鐘 班級 學(xué)號 姓名 題 號一二三四五六七八九十成績滿 分208661510101510100得 分評卷人一、填空題|（每題4分，共20分）1. 喬母斯基定義的3型文法（線性文法）產(chǎn)生式形式 AàBa|a,或AàaB|a，A，BVn,a,bVt 。2.語法分析程序的輸入是 單詞符號，其輸出是 語法單位 。3 型為 B à .aB 的LR（0）項(xiàng)目被稱為 移進(jìn) 項(xiàng)目，型為

2、B à a.B 的LR（0）項(xiàng)目被稱為 待約 項(xiàng)目，4.在屬性文法中文法符號的兩種屬性分別為 繼承屬性 和 綜合屬性 。5、運(yùn)行時存貯管理方案有 靜態(tài)存儲分配、動態(tài)存儲分配 和 堆式存儲分配 和方案。 二.已知文法 G(S)(1) E à T | E+T(2) T à F | F*F(3) F à （E）| i （1）寫出句型（T*F+i）的最右推到并畫出語法樹。（4分） （2）寫出上述句型的短語，直接短語和句柄。（4分）答：（1）最右推到（2分） E => T => F => (E) => (E+T) => (E+F) =

3、> (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* 最

4、小的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 (#

5、 , )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）項(xiàng)目集規(guī)范族

6、劃分； （2）填寫相應(yīng)的SLR（1）的分析表。（15分）答：（1）LR（0）項(xiàng)目集規(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

7、à 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

8、 = $2.Tc (2) S à R S1 Backpatch（$2.chain ， nxq ）桂 林 電 子 科 技 大 學(xué) 試 卷 2012-2013 學(xué)年第 2 學(xué)期 課號 122239 課程名稱 編譯原理試題、答案和評分標(biāo)準(zhǔn) （B卷;閉卷） 適用班級（或年級、專業(yè)） 01應(yīng)本 考試時間 120 分鐘 班級 學(xué)號 姓名 題 號一二三四五六七八九十成績滿 分208661510101510100得 分評卷人一、填空題|（每題4分，共20分）1. 喬母斯基定義的2型文法（上下文無關(guān)文法）產(chǎn)生式形式 Aà,AVn, V+。2.詞法分析程序的輸入是 字符串 ，其輸出是 單詞符號

9、 。3 算符有限分析方法每次都是對 最左素短語 進(jìn)行規(guī)約。型為 B à aB. 的LR（0）項(xiàng)目被稱為 規(guī)約 項(xiàng)目。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）=> (

10、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

11、 | 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 ()

12、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）項(xiàng)目集規(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) R à do