計算機編譯原理a&k

《計算機編譯原理a&k》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、1．考察文法G[]，其產(chǎn)生式為：→

2、a→if()

3、if()else→0

4、11）試證文法G[]是二義性文法。2）試給出消除二義性規(guī)則，根據(jù)此規(guī)則改造文法G[]為G1[]，使L(G[])=L(G1[])，但G1[]是非二義性文法。分析：1）本題比較簡單，只需找出文法G[]的一個二義性句子即可。2）本題實際上是要求解決所謂“懸掛else問題”。按通常程序設計語言的規(guī)定，消除二義性的規(guī)則是：一個else部分總是與沒有els

5、e部分的最近的if語句相配對，即所謂的“最近原則”，這可以通過增加非終結符、修改和增加產(chǎn)生式來解決。解答：1）考慮G[]的句子if(0)if(1)aelsea，該句子有如下2棵不同的推導樹，如圖1.6和圖1.7所示，因此它是二義性句子，文法G[]是二義性文法。if()elsea0if()1a圖1.6句子if(0)if(1)aelsea的推導樹（1）if()0if()else1aa圖1.7句子if(0)if(1)

6、aelsea的推導樹（2）2）要想實行“最近原則”，關鍵是將有else子句和無else子句的if語句區(qū)分開，出現(xiàn)在else前面的非終結符與無else的if后面的非終結符不同（非終結符后面的非終結符），因此可將G[]改寫為G1[]：→

7、→if()else

8、a→if()

9、if()else→0

10、1這樣對句子if(0)if(1)aelsea就只能有惟一的推導樹，如圖1.8所示。if()0if

11、()else1aa圖1.8句子if(0)if(1)aelsea的推導樹2．設文法G[]的產(chǎn)生式集合為：(1)→ab(2)→ε(3)→d(4)→ε(5)→c(6)→e(7)→ε(8)→f(9)→g(10)→ε(11)→a(12)→εa)試利用布爾矩陣的方法計算每個產(chǎn)生式的右部符號串的頭符號集合FIRST(α)；b)試利用布爾矩陣的方法計算每個可空產(chǎn)生式

12、>→ε的可空非終結符的后繼符號集合FOLLOW()；c)給出每個產(chǎn)生式的選擇集合Select（→α）；d)文法G[]是LL(1)文法嗎?解答：a)觀察各個產(chǎn)生式，立即可知該文法的所有非終結符都是可空的。文法中各符號之間的B關系記錄在下面矩陣M中(表3.10)：Mabcdefg1111111111111表3.10關系B的矩陣M+然后利用Warshall算法求出上述矩陣的傳遞閉包M（表3.11）:+Mabcde

13、fg11111111111111111+表3.11傳遞閉包M由上述矩陣可以知道：FIRST()={a}FIRST()={a,d}FIRST()={a,d,c,e}FIRST()={a,f,g}FIRST()={a}∴該文法各產(chǎn)生式右部的頭符號集合為：FIRST(ab)={a}FIRST(ε)={ε}FIRST(d)={a,d}FIRST(ε)={ε}FIRST(c)={a,d,c}FIRST(e)={e}F

14、IRST(ε)={ε}FIRST(f)={a,f}FIRST(g)={a,f,g}FIRST(ε)={ε}FIRST(a)={a}FIRST(ε)={ε}b)構造E關系，其矩陣Q如表3.12所示：Q11111表3.12關系E的矩陣Q用Warshall算法計算出的Q*如表3.13所示：Q*11111111111表3.13矩陣Q*構造F關系，矩陣P如表3.14所示：P<

15、B>Abcdefg⊥11111111111111表3.14關系F的矩陣PQ*·P的結果如表3.15所示：Q*·PAbcdefg⊥111111111111111111111111111111表3.15Q*·P對應的矩陣∴各可空非終結