04-05第二學(xué)期編譯原理試題

《04-05第二學(xué)期編譯原理試題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、2004∽2005年度第2學(xué)期計算機(jī)學(xué)院02級【編譯原理】考試題（A）考試形式：開卷考試時間：2005年6月24日9:55-11:30學(xué)號姓名1234567附加題總分分?jǐn)?shù)1.（6分）回答下列問題1）在存儲管理中，為什么在活動記錄內(nèi)為臨時變量分配空間？答：在棧式存儲管理方式中，以活動記錄的形式為一次過程調(diào)用（函數(shù)調(diào)用）中的局部數(shù)據(jù)提供存儲空間，該活動記錄隨過程調(diào)用被分配，隨過程調(diào)用的結(jié)束而釋放；臨時變量通常用于保存表達(dá)式計算中的中間結(jié)果，在活動記錄中為臨時變量分配空間，可以保證該空間隨過程調(diào)用被分配，隨活動記錄的釋放被自動釋放。2）在符號表管理中，為什么將變量名保存在符

2、號表中？答：符號表中將保存變量名及其各種屬性，變量名將用于變量的識別、涉及變變量名與存儲空間的綁定、以及類型、作用域、存儲地址等各種變量屬性的設(shè)置、獲取等各種維護(hù)功能。2.(8分)試消除下列文法中的左遞歸。 S→SaA

3、Se

4、BA→BbA

5、BB→cSd

6、e解：消除左遞歸提取左因子改寫后的文法S→SaA

7、Se

8、BA→BbA

9、BS→BS’→S（aA

10、e）

11、B→B(bA

12、e)S’→aAS’

13、eS’

14、e引進(jìn)非終結(jié)符S’引進(jìn)非終結(jié)符A’A→BA’S→BS’A→BA’A’→bA

15、eS’→（aA

16、e）S’

17、eA’→bA

18、eB→cSd

19、e3.(15分)寫出下列文法中各候選式的FIRS

20、T集和各非終結(jié)符的FOLLOW集,構(gòu)造該文法的LL（1）分析表，并說明它是否為LL（1）文法。 S→aA

21、BAA→cB

22、eB→bB

23、e各候選式的FIRST集(4分)FIRST（aA）={a}FIRST（BA）={b，c，e}FIRST（cB）={c}FIRST（e）={e}FIRST（bB）=FIRST（e）={e}各非終結(jié)符的FOLLOW集(4分)FOLLOW(S)={#}FOLLOW(A)={#}FOLLOW(B)={c，#}LL（1）分析表(5分)abc#SS→aAS→BAS→BAS→BAAA→cBA→eBB→bBB→eB→e說明它是否為LL（1）文法(2

24、分)判斷1分，理由1分因為LL（1）分析表無沖突，所以該文法是LL（1）文法。4.（18分）給定文法G[S]S→L+L｜LL→LB

25、BB→0

26、1 (1)構(gòu)造拓廣文法，按LR(0)分析的需要畫出識別這個拓廣文法的所有規(guī)范句型活前綴的DFA。解1：相應(yīng)的DFA如下圖所示。0SI0:Sˊ→.SS→.L+LS→.LL→.LBL→.BB→.0B→.1I8:S→L+L.L→L.BB→.0B→.1I2:S→L.+LS→L.L→L.BB→.0B→.1I3:L→B.I1:Sˊ→S.LL01B0BB01+BI7:L→LB.I6:S→L+.LL→.LBL→.BB→.0B→.1I5:B→1.

27、I4:B→0.11解2：0Sˊ→0S11S→0L2+6L82S→0L23L→0，6L2，8B74L→0，6B35B→0，2，6，8046B→0，2，6，815I0：{（0，0），（1，0），（2，0），（3，0），（4，0），（5，0），（6，0）}I1：{（0，1）}I2：{（1，1），（2，1），（3，1），（5，0），（6，0）}I3：{（4，1）}I4：{（5，1）}I5：{（6，1）}I6：{（1，2），（3，0），（4，0），（5，0），（6，0）}I7：{（3，2）}I8：{（1，3），（3，1），（5，0），（6，0）}0SI0:（0，0），（1，0）

28、，（2，0），（3，0），（4，0），（5，0），（6，0）I8:（1，3），（3，1），（5，0），（6，0）I2:（1，1），（2，1），（3，1），（5，0），（6，0）I3:（4，1）I1:（0，1）LL01B0BB01+BI7:（3，2）I6:（1，2），（3，0），（4，0），（5，0），（6，0）I5:（6，1）I4:（5，1）11(2)求出這個文法的SLR（1）分析表。解：給產(chǎn)生式編號：①S→L+L②S→L③L→LB④L→B⑤B→0⑥B→1FOLLOW(S)={#}FOLLOW(L)={0,1,+,#}FOLLOW(B)={0,1,+,#}狀態(tài)ACTI

29、ONGOTO01+#SLB0S4S51231acc2S4S5S6r273r4r4r4r44r5r5r5r55r6r6r6r66S4S5837r3r3r3r38S4S5r175.（7分）寫出能產(chǎn)生字母表{x,y}上的不含兩個相鄰的x,且不含兩個相鄰的ｙ的全體符號串的有限狀態(tài)自動機(jī)。解：6.（16分）設(shè)文法G[E]:E→RP

30、PP→(E)

31、iR→RP+

32、RP*

33、P+

34、P*畫出句子i+i*(i+i)的語法分析樹，給出其最右推導(dǎo)和最左歸約，并指出它的句柄。解：(1)語法分析樹：（2）最右推導(dǎo)：ETRPTR(E)TR(RP)TR(Ri)TR(P+i)TR(i+