編譯原理 復習

1、3. 文法： S->MH|a H ->LSo|  K ->dML|  L ->eHf M->K|bLM 判斷 G 是否為 LL(1) 文法，如果是，構造 LL(1) 分析表。 解：各符號的 FIRST 集和 FOLLOW集為：         各產(chǎn)生式SELE

2、CT集為：  SELECT S->MH d,b,e,#,o S->a a H ->LSo e H -> #,f,o K ->dML d K -> e,#,o L ->eHf e M->K d,e,#,o M-> bLM b  預測分析表  由于預

3、測分析表中無多重入口，所以可判定文法是 LL(1)的已知文法為：A ->aAd|aAb|        判斷該文法是否是 SLR(1) 文法，若是構造相應分析表，并對輸入串 ab# 給出分析過程。解：增加一個非終結符 S/后，產(chǎn)生原文法的增廣文法有： S'->A A ->aAd|aAb|  下面構造它的 LR(0)項目集規(guī)范族為：      

4、  從上表可看出,  狀態(tài) I0 和 I2 存在移進- 歸約沖突，該文法不是 LR(0)文法。對于 I0 來說有：    FOLLOW(A)a=b,d,#a= ，所以在 I0 狀態(tài)下面臨輸入符號為 a 時移進，為 b,d,#時   歸約，為其他時報錯。對于 I2 來說有也有與 I0 完全相同的結論。這就是說，以上的移 - 歸沖突是可以解決

5、的，因此該文法是 SLR(1)文法。   其 SLR(1)分析表為：   對輸入串 ab#給出分析過程為：     對給定正規(guī)式b*（d|ad）（b|ab）+，構造其NFA M； 解答：首先用A+=AA*改造正規(guī)式得：b*(d|ad)(b|ab)(b|ab)*；其次，構造該正規(guī)式的NFA M，如圖3-6-7所示。  試為表達式 w+(a+b)*(c+d/(e-10)+8) 寫出相應的逆波蘭表示。 解： w a

6、0;b + c d e 10 - / + 8 + * +  構造下述文法  GS 的自動機：  S->A0   A->A0|S1|0   該自動機是確定的嗎？若不確定，則對它確定化。  解：由于該文法的產(chǎn)生式 S->A0 ，A->A0|S1 中沒有字符集VT的輸入，所以不是確定的自動機。  要將其他確定化，必須先用代入法得到它對應的正規(guī)式。把S

7、?A0 代入產(chǎn)生式 A?S1 有：A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入S->A0有該文法的正規(guī)式：0(0|01)*0，所以，改寫該文法為確定的自動機為：    由于狀態(tài)A有3次輸入0的重復輸入，所以上圖只是NFA，面將它確定化： 下表由子集法將NFA轉 換 為 DFA:     由上表可知DFA3.寫出表達式(a+b)/(a-b-(a+b*c)的三元序列及四元序列。解：（1）三元式：（，a，b）（，a，b）（/，）（*，b，c）（，a，） （，）（2）四元式： （，a，b，T1）（，a，b，T2）/

8、，T1，T2，T3）（*，b，c，T4）（，a，T4，T5）（，T3，T5，T6） 4.寫一個文法使其語言為偶數(shù)集，且每個偶數(shù)不以0開頭。解：文法G（S）：SAB|B|A0AAD|CB2|4|6|8C1|3|5|7|9|BD0|C 5.設文法G（S）：SSaF|aF|aFF*aF|*a （1）消除左遞歸和回溯； （2）構造相應的FIRST和Follow集合。1） S->aFS'|aFS'S'->aFS'|F->*aF'F'->F|（2） FIRST（S）a，+FOLLOW（S）FIRST（S'）+，F(xiàn)OLLOW（S'）FIRST（F）*FOLLoW（F）（+，F(xiàn)IRST（F'）*，F(xiàn)OLLOW（+，五.計算題（10分）已知文法為：S->a|(T) T->T,S|S 構造它的LR(0)分析表。 解：加入非終結符S'，方法的