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

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

2、。(4 分)2)寫(xiě)出上述句型的短語(yǔ)，直接短語(yǔ)和句柄。(4 分)答：(1)最右推到(2 分)E = T = F = (E) = (E+T) = (E+F) = (E+i) = (T+i) = (T*F+i)(2)語(yǔ)法樹(shù)(2 分)(3) (4 分)短語(yǔ)：(T*F+i)，T*F+i ，T*F， i直接短語(yǔ)：T*F， i句柄：T*F三.證明文法 G(S) : SSaS |是二義的。(6 分) 答：句子 aaa 對(duì)應(yīng)的兩顆語(yǔ)法樹(shù)為：/1 (T)= (T,S) = (S,S) = (a,S) = (a,(T)= (a,(T,S)=(a, (S,S) = (a,(a,S)= (a,(a,a)語(yǔ)法樹(shù)(2 分)

3、(3) (4 分)zzz Z/T a6短語(yǔ)：(a,(a,a) ), a,(a,a),(a,a), a,a , a直接短語(yǔ)：a句柄：a三. 證明文法 G(S) : S aSb| Sb| b 是二義的。(6 分) 答：句子 aabbbb 對(duì)應(yīng)的兩顆語(yǔ)法樹(shù)為：7bb因此，文法是二義文法四. 給定正規(guī)文法 G（S）:(1) SaAAaB | bA(3) BaA | b請(qǐng)構(gòu)造與之等價(jià)的 DFA （6 分） 答：對(duì)應(yīng)的 DFA 為：（6 分）五構(gòu)造識(shí)別正規(guī)語(yǔ)言（ab*|a）*最小的 DFA（要求寫(xiě)出求解過(guò)程）。 （15分） 答：（1）對(duì)應(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)項(xiàng)目集規(guī)滋。(15 分)答：11九.設(shè)某語(yǔ)言的 DO-while 語(yǔ)句的語(yǔ)法形式為:S do Si while E其語(yǔ)義解釋為：針對(duì)自上而下的語(yǔ)法分析器，（1） 分段產(chǎn)生式；（3 分）（2） 寫(xiě)出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng)作。（7 分） 答：（1）分段產(chǎn)生式（3 分）G(S) :(1) R do(2) U RS while（3）S U E（2）產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dò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