1、、填空題| (每題4分，共20分)1 .喬母斯基定義的3型文法(線性文法)產生式形式 A Ba|a,或A aB|a, A, BC Vn, a,b C Vt 。2 .語法分析程序的輸入是 單詞符號,其輸出是 語法單位。3型為B .aB的LR (0)項目被稱為 移進 項目，型為B a.B的LR (0) 項目被稱為待約 項目,4 .在屬性文法中文法符號的兩種屬性分別為 繼承在性和綜合屬性 。5、運行時存貯管理方案有靜態存儲分配、動態存儲分配和堆式存儲分配和方案。2 .已知文法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分)/1(E ) /1 E + T(4) (4分)短語： (T*F+i), T*F+i , T*F , i直接短語：T*F , i句柄：T*F3 .證明文法G(S) : S SaS | £是二義的。(6分) 答：句子aaa對應的兩顆語法樹為：S a S 4后 。上 白因此，文法是二義文法4 .給定正規文法G

3、（S）:（1） SSa | Ab |b（2） ASa請構造與之等價的DFA （6分）答：對應的NFA為：（6分）start狀態轉換表:abFSSS,AS,AS,AS5 .構造識別正規語言b*a（bb*a）*b* 最小的DFA（要求寫出求解過程）。（15分） 答：（1）對應的NFA（5分）Mart()(5分)（2）將（1）所得的NFA確定化：（5分）ab01 , 301,32, 32,31,32,36 .已知文法 G（S）: S 人 | a | （T）（2） T T,S | S試：（1）消除文法的左遞歸；（4分）（2）構造相應的first 和follow 集合。（6分）答：（1）消除文法的左遞歸

4、后文法 G' （S）為： S人 | a | （T）T ST' |S(4分) T ' ,ST ' | e(2) (6分)firstfollowSa A (r # ,)Ta a (), £)7 .已知文法G(S):(1) SSiA | A AA+B | B(3) B A* |(試構造非終止符的firstVT和lastVT集合。(10分)八.已知文法 G(S):(1) SBB(2) BaB(3) Bb的follow集合如表:FollowS#Ba,b,#答：(10分)firstVT1 lastVTSi , + , * , ( i , + , *,(A+ , *

5、 ,(+ , * ,(B* ,(r ,(試：(1)給出該文法的LR (0)項目集規范族劃分;(2)填寫相應的SLR (1)的分析表。(15分)答：(1) LR (0)項目集規范族劃分(8分)II12I I34I 1S' S.I 2SBBB.B .aB .bI 3BBBa.B .aB .bI4Bb.I 5SBB.I 6BaB.(2) SLR(1)分析表(7分)狀態ActionGotoab#SB0S3S4121Acc2S3S453S3S464R3R3R35R16R2R2R2九.設某語言的not-then-else 語句的語法形式為：S not E then S 其語義解釋為：針對自上而下的

6、語法分析器，(1)分段產生式；(3分)(7分)(2)寫出每個產生式對應的語義動作。答：(1)分段產生式(3分)及語義動作(7分)(1) Rnot E then Backpatch ($2.FC , nxq );$.chain = $2.Tc (2) S R S 1 Backpatch ($2.chain , nxq ) 、填空題| (每題4分，共20分)1 .喬母斯基定義的2型文法(上下文無關文法)產生式形式A B ,a e Vn, B e V+。2 .詞法分析程序的輸入是 字符串,其輸出是 單詞符號。3算符有限分析方法每次都是對 最左素短語進行規約。型為B aB.的LR (0)項 目被稱為規

7、約 項目。4、寫出 x:=b*(d-e)/(c-d)+e 的逆波蘭式 xbde-*cd-/e+:= 。5、常用的兩種動態存貯分配辦法是棧式彳儲分配和吊式存儲 分配。2 .已知文法 G(S): S 人 I a I (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) =&g

8、t; (a,(a,a)(2)語法樹(2分)/|I /)U/N(3) (4 分)短語：(a,(a,a) ), a,(a,a), (a,a), a,a , a直接短語：a句柄：a3 .證明文法 G(S) : S aSb | Sb | b 是二義的。(6分) 答：句子aabbbb對應的兩顆語法樹為：8S/NAa S bSb/4ZTa S ba S bA/TS ba S bbb因此，文法是二義文法4 .給定正規文法G (S):(1) S aA A aB | bA(3) B aA | b請構造與之等價的DFA (6分)答：對應的DFA為：(6分)b5 .構造識別正規語言（ab*|a） *最小的DFA（要

9、求寫出求解過程）。（15分）答：（1）對應的NFA （5分）（2）將（1）所得的NFA確定化：（5分）ab11,21,21,21,26 .已知文法G（S）: S A I a I （T）（2） TST | S（3） T ' ,ST ' | e試：求first和follow集合，構造改文法的LL （1）分析表。（10分）答：文法相應的first 和follow 集合 （5分）firstfollowS 1a A (r # ,)Ta a (), £)其LL (1)分析表如下:ab()7sS - aS-*hS- (T)ITf STFt yrTf ST'T - wT

10、9; f + ST'7 .已知文法G(S):(1) SSiA | A AA+B | B(3) B A* |(非終止符的firstVT 和lastVT集合如下:firstVTlastVTSi , + , * , ( i , + , *,(A+ , * ,(+ , * ,(B* ,(* ,(試構造算符的優先關系表。(10分)i+()*I><<<+>><<>(>>>)<<<*>>>八已知文法G(S):(1) S a | aAb | b | bBa(2) A1A0 |£(3) B1B0 |£求：該文法的LR (0)項目集規范族。(15分)九.設某語言的DO-while語句的語法形式為:S do S i while E其語義解釋為：ETC針對自上而下的語法分析器，(1)分段產生式；(3分)(2)寫出每個產生式對應的語義動作。(7分)答：(1)分段產生式(3分)G(S) : (1)Rdo(2) UR Si while(3) SU E(2)產生式對應的語義動作(7分)(1) Rdo $.