1、3. 文法： S->MH|a H ->LSo|  K ->dML|  L ->eHf M->K|bLM 判斷 G 是否為 LL(1) 文法，如果是，構(gòu)造 LL(1) 分析表。 解：各符號(hào)的 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  預(yù)測分析表  由于預(yù)

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

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

5、的，因此該文法是 SLR(1)文法。   其 SLR(1)分析表為：   對(duì)輸入串 ab#給出分析過程為：     對(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-6-7所示。  試為表達(dá)式 w+(a+b)*(c+d/(e-10)+8) 寫出相應(yīng)的逆波蘭表示。 解： w a

6、0;b + c d e 10 - / + 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

7、?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ù)輸入，所以上圖只是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）/

8、，T1，T2，T3）（*，b，c，T4）（，a，T4，T5）（，T3，T5，T6） 4.寫一個(gè)文法使其語言為偶數(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'|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（+，五.計(jì)算題（10分）已知文法為：S->a|(T) T->T,S|S 構(gòu)造它的LR(0)分析表。 解：加入非終結(jié)符S'，方法的