資源描述：
《編譯原理 復(fù)習(xí)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、3.?文法：?S->MH
2、a?H?->LSo
3、?ε?K?->dML
4、?ε?L?->eHf?M->K
5、bLM?判斷?G?是否為?LL(1)?文法，如果是，構(gòu)造?LL(1)?分析表。?解：各符號的?FIRST?集和?FOLLOW集為：?????????各產(chǎn)生式SELECT集為：??SELECT?S->MH?{d,b,e,#,o}?S->a?{a}?H?->LSo?{e}?H?->ε?{#,f,o}?K?->dML?syqd18a?K?->ε?{e,#,o}?L?->eHf?{e}?M->K?{d,e,#,o}?M->?bLM?
6、??預(yù)測分析表??由于預(yù)測分析表中無多重入口，所以可判定文法是?LL(1)的已知文法為：A?->aAd
7、aAb
8、?ε????判斷該文法是否是?SLR(1)?文法，若是構(gòu)造相應(yīng)分析表，并對輸入串?ab#?給出分析過程。解：增加一個非終結(jié)符?S/后，產(chǎn)生原文法的增廣文法有：?S'->A?A?->aAd
9、aAb
10、ε?下面構(gòu)造它的?LR(0)項目集規(guī)范族為：???????從上表可看出,?狀態(tài)?I0?和?I2?存在移進-?歸約沖突，該文法不是?LR(0)文法。對于?I0?來說有：??FOLLOW(A)∩{a}={b,d
11、,#}∩{a}=Φ?，所以在?I0?狀態(tài)下面臨輸入符號為?a?時移進，為?b,d,#時??歸約，為其他時報錯。對于?I2?來說有也有與?I0?完全相同的結(jié)論。這就是說，以上的移?-?歸沖突是可以解決的，因此該文法是?SLR(1)文法。??其?SLR(1)分析表為：???對輸入串?ab#給出分析過程為：????對給定正規(guī)式b*（d
12、ad）（b
13、ab）+，構(gòu)造其NFAM；解答：首先用A+=AA*改造正規(guī)式得：b*(d
14、ad)(b
15、ab)(b
16、ab)*；其次，構(gòu)造該正規(guī)式的NFAM，如圖3-6-7所示。?試為表達式?w+
17、(a+b)*(c+d/(e-10)+8)?寫出相應(yīng)的逆波蘭表示。?解：?w?a?b?+?c?d?e?10?-?/?+?8?+?*?+?構(gòu)造下述文法?G[S]?的自動機：??S->A0??A->A0
18、S1
19、0??該自動機是確定的嗎？若不確定，則對它確定化。?解：由于該文法的產(chǎn)生式S->A0，A->A0
20、S1中沒有字符集VT的輸入，所以不是確定的自動機。?要將其他確定化，必須先用代入法得到它對應(yīng)的正規(guī)式。把S?A0代入產(chǎn)生式A?S1有：A=A0
21、A01
22、0=A(0
23、01)
24、0=0(0
25、01)*。?代入S->A0有該文法
26、的正規(guī)式：0(0
27、01)*0，所以，改寫該文法為確定的自動機為：??由于狀態(tài)A有3次輸入0的重復(fù)輸入，所以上圖只是NFA，面將它確定化：?下表由子集法將NFA轉(zhuǎn)換為DFA:?]?由上表可知DFA3.寫出表達式(a+b)/(a-b-(a+b*c)的三元序列及四元序列。解：（1）三元式：①（＋，a，b）②（－，a，b）③（/，①，②）④（*，b，c）⑤（＋，a，④）⑥（－，③，⑤）（2）四元式：①（＋，a，b，T1）②（－，a，b，T2）③/，T1，T2，T3）④（*，b，c，T4）⑤（＋，a，T4，T5）⑥（－，T3
28、，T5，T6）4.寫一個文法使其語言為偶數(shù)集，且每個偶數(shù)不以0開頭。解：文法G（S）：S→AB
29、B
30、A0A→AD
31、CB→2
32、4
33、6
34、8C→1
35、3
36、5
37、7
38、9
39、BD→0
40、C5.設(shè)文法G（S）：S→S＋aF
41、aF
42、＋aFF→*aF
43、*a（1）消除左遞歸和回溯；（2）構(gòu)造相應(yīng)的FIRST和Follow集合。1）S->aFS'
44、＋aFS'S'->＋aFS'
45、εF->*aF'F'->F
46、ε（2）FIRST（S）＝｛a，+｝FOLLOW（S）＝｛＃｝FIRST（S'）＝｛+，ε｝FOLLOW（S'）＝｛＃｝FIRST（F）＝｛
47、*｝FOLLoW（F）＝（+，＃｝FIRST（F'）＝｛*，ε｝FOLLOW（+，＃｝五.計算題（10分）已知文法為：S->a
48、^
49、(T)T->T,S
50、S構(gòu)造它的LR(0)分析表。解：加入非終結(jié)符S'，方法的增廣文法為：S'->SS->aS->^S->(T)T->T,ST->S下面構(gòu)造它的LR(0)項目集規(guī)范族為：從上表可看出,不存在移進-歸約沖突以及歸約歸約沖突，該文法是LR(0)文法。從而有下面的LR(0)分析表：
