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

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

2、| 下面構(gòu)造它的LR(0)項(xiàng)目集規(guī)范族為： 從上表可看出, 狀態(tài)I0和I2存在移進(jìn)-歸約沖突，該文法不是LR(0)文法。對(duì)于I0來(lái)說(shuō)有： FOLLOW(A)a=b,d,#a=，所以在I0狀態(tài)下面臨輸入符號(hào)為a時(shí)移進(jìn)，為b,d,#時(shí) 歸約，為其他時(shí)報(bào)錯(cuò)。對(duì)于I2來(lái)說(shuō)有也有與I0完全相同的結(jié)論。這就是說(shuō)，以上的移-歸沖突是可以解決的，因此該文法是SLR(1)文法。 其SLR(1)分析表為：對(duì)輸入串a(chǎn)b#給出分析過(guò)程為： 對(duì)給定正規(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的自動(dòng)機(jī)：S-A0 A-A0|S1|0 該自動(dòng)機(jī)是確定的嗎？若不確定，則對(duì)它確定化。 解：由于該文法的產(chǎn)生式 S-A0 ，A-A0|S1 中沒有字符集VT的輸入，所以不是確定的自動(dòng)機(jī)。 要將其他確定化，必須先用代入法得到它對(duì)應(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，所以，改寫該文法為確定的自動(dòng)機(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.寫一個(gè)文法使其語(yǔ)言為偶數(shù)集，且每個(gè)偶數(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（+，五.計(jì)算題（10分）已知文法為：S-a|(T) T-T,S|S 構(gòu)造它的LR(0)分析表。 解：加入非終結(jié)符S，方法的增廣文法為：S-SS-aS-S-(T)T-T,S T-S