編譯原理期末考試習題集與答案解析

1、、填空題| (每題4分，共20分)1 .喬母斯基定義的3型文法(線性文法)產(chǎn)生式形式 A Ba|a,或A aB|a,A, BNn, a,bt 。2 .語法分析程序的輸入是 單詞符號,其輸出是 語法單位o3型為 B .aB的LR (0)項目被稱為 移進 項目，型為B a.B的LR (0) 項目被稱為待約 項目，4 .在屬性文法中文法符號的兩種屬性分別為繼承屬性和綜合屬性 。5、運行時存貯管理方案有靜態(tài)存儲分配、動態(tài)存儲分配和堆式存儲分配和方案。二.已知文法G(S) ET | E+T(2) TF | F*F(3) F(E) | i(1)寫出句型(T*F+i)的最右推到并畫出語法樹。(4分)(2)寫

2、出上述句型的短語，直接短語和句柄。(4分)答：(1)最右推到(2分)E = T = F = (E) = (E+T) = (E+F) = (E+i) = (T+i) = (T*F+i)(2)語法樹(2分)/|ViX(3) (4 分)短語： (T*F+i), T*F+i , T*F , i直接短語：T*F , i句柄：T*F3 .證明文法 G(S) : S SaS | e是二義的。(6分)答：句子 aaa對應的兩顆語法樹為：因此，文法是二義文法4 .給定正規(guī)文法G (S):(1) SSa | Ab |b(2) ASa請構造與之等價的DFA。(6分)答：對應的NFA為：(6分)FSSS，AS，AS，

3、AS五.構造識別正規(guī)語言b*a（bb*a）*b*最小的DFA （要求寫出求解過程）。（15分）答：（1）對應的NFA （5分）(5分)（2）將（1）所得的NFA確定化：（5分）ab01, 301,32, 32,31,32,3六.已知文法G(S): S 人 I a I (T)(2) T T,S | S試：（1）消除文法的左遞歸；（4分）(2)構造相應的first和follow 集合。(6分)答：(1)消除文法的左遞歸后文法 G (S)為： S 人 I a I (T)(2) T ST | S(3) T ,ST | (4 分)七.已知文法G(S):(1) S SiA | A AA+B|B BA*|

4、(試構造非終止符的firstVT和lastVT集合。(10分)firstVTlastVTSi , + , * ,(i , + , * ,(A+ , * ,(+ , * ,(B* ,(* ,(答：(10分)八.已知文法 G(S):FollowS# 1Ba,b,#(1) S B BB a BB b的follow集合如表: 試：(1)給出該文法的LR (0)項目集規(guī)范族劃分;(2)填寫相應的SLR (1)的分析表。(15分)I 1I 2I 3I 4I 1S S.I4B b.I 3Ba.B-B.aB-B.b-答：(1) LR (0)項目集規(guī)范族劃分(8分)S B.B - I 5 a ,B.aB - b

5、 I 3I 5S BB.B.b- I 4I 6B aB.(2) SLR(1)分析表(7分)狀態(tài)ActionGotoab#SB0S3S4121Acc2S3S453S3S464R3R3R35R16R2R2R2九.設某語言的not-then-else 語句的語法形式為：S not E then Si其語義解釋為：針對自上而下的語法分析器，(1)分段產(chǎn)生式；(3分)(2)寫出每個產(chǎn)生式對應的語義動作。(7分)答：(1)分段產(chǎn)生式(3分)及語義動作(7分)1 1) R not E then Backpatch ($2.FC , nxq );$.chain = $2.Tc 2 2) S R Si Back

6、patch ($2.chain , nxq ) 一、填空題| (每題4分，共20分)3 .喬母斯基定義的2型文法(上下文無關文法)產(chǎn)生式形式A &ANn, B V+。4 .詞法分析程序的輸入是 字符串,其輸出是 單詞符號。3算符有限分析方法每次都是對 最左素短語進行規(guī)約。型為 B aB.的LR (0) 項目被稱為規(guī)約 項目。4、寫出 x:=b*(d-e)/(c-d)+e 的逆波蘭式 xbde-*cd-/e+:=。5、常用的兩種動態(tài)存貯分配辦法是棧式存儲分配和堆式存儲 分配。二.已知文法 G(S): S 人 I a I (T)(2) T T,S | S試：(1)寫出句型(a,(a,a)的最左推到

7、并畫出語法樹。(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分)/l(I ) /l T ， S /l (T ) A /l T ， SS aIa(3) (4 分)短語：(a,(a,a), a,(a,a) , (a,a) , a,a , a直接短語：a句柄：a.證明文法 G(S) : S aSb | Sb | b 是二義的。(6分)答：句子aabbbb對應的兩顆語法樹為:

8、四.給定正規(guī)文法G (S):(1) SaA(2) AaB | bA(3) B aA | b請構造與之等價的DFA。（6分）五.構造識別正規(guī)語言（ab*|a）*最小的DFA （要求寫出求解過程）。（15分）答：（1）對應的NFA （5分）ab11,21,21,21,2（2）將（1）所得的NFA確定化：（5分）a(5分)六.已知文法 G(S): S 人 I a I (T)(2) T ST | ST,ST |e試：求first和follow集合，構造改文法的LL (1)分析表。(10分)答：文法相應的first和follow集合 (5分)firstfollowSa A (# ,)Ta a ()T，,

9、 )其LL (1)分析表如下:ab(sS-CT)TT- STI ST*Tf 5丁rT-它V七.已知文法G(S):(1) S SiA | A AA+B|B BA*| (非終止符的firstVT和lastVT集合如下:firstVTlastVTSi , + , * ,(i , + , * ,(A+ , * ,(+ , * ,(B* ,(* ,(試構造算符的優(yōu)先關系表。(10分)i+()*I()八已知文法 G(S): S a | aAb | b | bBa A1A0| B1B0| 求：該文法的LR(0)項目集規(guī)范族。(15分)L： SI： SF-S-/Io： S5SS fitAS-a AbA IAOaAbSt bBaB?B 5 1BOM SrbBaa I|0： SbBa九.設某語百的DO-while語句的語法形式為:S do Si while E其語義解釋為:針對自上而下的語法分析器,(1)分段產(chǎn)生式；(3分) (2)寫出每個產(chǎn)生式對應的語義動作。(7分)答：(1)分段產(chǎn)生式(3分)G(S) :(1)Rdo(2) UR S