編譯原理-復(fù)習(xí)

1、3.文法：S-MH|aH-LSo|K-dML|L-eHfM-K|bLM判斷G是否為LL(1)文法，如果是，構(gòu)造LL(1)分析表。解：各符號的FIRST集和FOLLOW集為：各產(chǎn)生式SELECT集為：SELECTS-MHd,b,e,#,oS-aaH-LSoeH-#,f,oK-dMLdK-e,#,oL-eHfeM-Kd,e,#,oM-bLMb預(yù)測分析表由于預(yù)測分析表中無多重入口，所以可判定文法是LL(1)的已知文法為：A-aAd|aAb| 判斷該文法是否是SLR(1)文法，若是構(gòu)造相應(yīng)分析表，并對輸入串a(chǎn)b#給出分析過程。解：增加一個非終結(jié)符S/后，產(chǎn)生原文法的增廣文法有：S-AA-aAd|aAb

2、| 下面構(gòu)造它的LR(0)項目集規(guī)范族為： 從上表可看出, 狀態(tài)I0和I2存在移進(jìn)-歸約沖突，該文法不是LR(0)文法。對于I0來說有： FOLLOW(A)a=b,d,#a=，所以在I0狀態(tài)下面臨輸入符號為a時移進(jìn)，為b,d,#時 歸約，為其他時報錯。對于I2來說有也有與I0完全相同的結(jié)論。這就是說，以上的移-歸沖突是可以解決的，因此該文法是SLR(1)文法。 其SLR(1)分析表為：對輸入串a(chǎn)b#給出分析過程為： 對給定正規(guī)式b*（d|ad）（b|ab）+，構(gòu)造其NFA M； 解答：首先用A+=AA*改造正規(guī)式得：b*(d|ad)(b|ab)(b|ab)*；其次，構(gòu)造該正規(guī)式的NFA M，如

3、圖3-6-7所示。 試為表達(dá)式w+(a+b)*(c+d/(e-10)+8)寫出相應(yīng)的逆波蘭表示。解：wab+cde10-/+8+*+ 構(gòu)造下述文法 GS的自動機(jī)：S-A0 A-A0|S1|0 該自動機(jī)是確定的嗎？若不確定，則對它確定化。 解：由于該文法的產(chǎn)生式 S-A0 ，A-A0|S1 中沒有字符集VT的輸入，所以不是確定的自動機(jī)。 要將其他確定化，必須先用代入法得到它對應(yīng)的正規(guī)式。把S?A0 代入產(chǎn)生式 A?S1 有：A=A0|A01|0=A(0|01)|0=0(0|01)*。代入S-A0有該文法的正規(guī)式：0(0|01)*0，所以，改寫該文法為確定的自動機(jī)為： 由于狀態(tài)A有3次輸入0的重復(fù)

4、輸入，所以上圖只是NFA，面將它確定化：下表由子集法將NFA轉(zhuǎn) 換 為 DFA: 由上表可知DFA3.寫出表達(dá)式(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，T5，T6） 4.寫一個文法使其語言為偶數(shù)集，且每個偶數(shù)不以0開頭。解：文法G（S）：SAB|B|A0AAD|CB2|4|6|8C1|3|5|7|9|BD0|C 5.設(shè)文法G（S）：SSaF|aF|aFF*aF|*a （1）消除左遞歸和回溯； （2）構(gòu)造相應(yīng)的FIRST和Follow集合。1） S-aFS|aFSS-aFS|F-*aFF-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 構(gòu)造它的LR(0)分析表。 解：加入非終結(jié)符S，方法的增廣文法為：S-SS-aS-S-(T)T-T,S T-S