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

1、1、填空題| (每題 4 分，共 20 分)1.喬母斯基定義的 3 型文法(線性文法)產(chǎn)生式形式ABa|a,或AaB|a,AB Vn,a ,b Vt 。2. 語法分析程序的輸入是 單詞符號，其輸出是 語法單位。3 型為 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)的最右推到并畫出語法樹

2、。(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) : SSaS |是二義的。(6 分) 答：句子 aaa 對應(yīng)的兩顆語法樹為：/1 (T)= (T,S) = (S,S) = (a,S) = (a,(T)= (a,(T,S)=(a, (S,S) = (a,(a,S)= (a,(a,a)語法樹(2 分)

3、(3) (4 分)zzz Z/T a6短語：(a,(a,a) ), a,(a,a),(a,a), a,a , a直接短語：a句柄：a三. 證明文法 G(S) : S aSb| Sb| b 是二義的。(6 分) 答：句子 aabbbb 對應(yīng)的兩顆語法樹為：7bb因此，文法是二義文法四. 給定正規(guī)文法 G（S）:(1) SaAAaB | bA(3) BaA | b請構(gòu)造與之等價的 DFA （6 分） 答：對應(yīng)的 DFA 為：（6 分）五構(gòu)造識別正規(guī)語言（ab*|a）*最小的 DFA（要求寫出求解過程）。 （15分） 答：（1）對應(yīng)的 NFA （5 分）h8將（1）所得的 NFA 確定化：（5 分）

4、ab1P 1,21,21,21,2六.已知文法 G（S）:SA| a | （T）（2） T ST | ST,ST | &試：求 first 和 follow 集合，構(gòu)造改文法的 LL （1）分析表。（10 分）答：文法相應(yīng)的 first 和 follow 集合 （5 分）firstfollowSaA(# , )1TaA()T, )(5 分)9其 LL（1）分析表如下:10ab()TT * ST1T- STfT -ST，T，T， r r, s七.已知文法 G(S):(1)SSiA | AAA+B| BBA* |(非終止符的 firstVT 和 lastVT 集合如下:firstVTlas

5、tVTSi , + , * ,(i , + , * , (A+ , * ,(+ , * , (B* ,(* ,(試構(gòu)造算符的優(yōu)先關(guān)系表。10 分)答：i+()*I()八已知文法G(S):(1) Sa | aAb | b | bBa(2) A1A0 |&(3) B1B0 |&求：該文法的 LR(O)項目集規(guī)滋。(15 分)答：11九.設(shè)某語言的 DO-while 語句的語法形式為:S do Si while E其語義解釋為：針對自上而下的語法分析器，（1） 分段產(chǎn)生式；（3 分）（2） 寫出每個產(chǎn)生式對應(yīng)的語義動作。（7 分） 答：（1）分段產(chǎn)生式（3 分）G(S) :(1) R do(2) U RS while（3）S U E（2）產(chǎn)生式對應(yīng)的語義動作（7 分）(1)Rdo $.loop = nxq UR S1while $.loop = $1.loop SU E backpatch ($2.FC , $1.loop );Backpatch ($2.TC , nxq )h：S a-is：At I*AO A-* AOb：S jSSATJA