編譯原理復(fù)習(xí)題(考試)-資料下載頁
2025-08-05 15:51本頁面
【正文】 (b)由0和1組成的串，包括空串。(c)倒數(shù)第3個(gè)字符為0，由0和1組成的串。(d)含有3個(gè)1的所有0和1的串。(e)由偶數(shù)個(gè)0和偶數(shù)個(gè)1構(gòu)成的所有0和1的串。26．已知文法G[S]：S→(L)|aL→L,S|S為句子(a,(a,a))構(gòu)造最左推導(dǎo)和最右推導(dǎo)。解：句子(a,(a,a))的最左推導(dǎo)為：S=(L)=(L,S) =(S,S)=(a,S) =(a,(L))=(a,(L,S)) =(a,(S,S))=(a,(a,S))=(a,(a,a))句子(a,(a,a))的最右推導(dǎo)為：S=(L)=(L,S) =(l,(L))=(L,(L,S))=(L,(L,a))=(L,(S,a))=(L,(a,a))=(S,(a,a))=(a,(a,a))1．構(gòu)造下述文法 G[S] 的自動(dòng)機(jī)： SA0 AA0|S1|0 該自動(dòng)機(jī)是確定的嗎？若不確定，則對(duì)它確定化。解：由于該文法的產(chǎn)生式SA0，AA0|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)*。 代入SA0有該文法的正規(guī)式：0(0|01)*0，所以，改寫該文法為確定的自動(dòng)機(jī)為： 由于狀態(tài)A有3次輸入0的重復(fù)輸入，所以上圖只是NFA，下面將它確定化：下表由子集法將NFA轉(zhuǎn)換為DFA: 由上表可知DFA為：2．對(duì)下面的文法 G ： ETE39。 E39。+E| ε TFT39。 T39。 T| ε F PF39?！ ?F39。 *F39。| ε P(E)|a|b|^ (1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的 FIRST 集和 FOLLOW 集。 (2) 證明這個(gè)方法是 LL(1) 的。 (3) 構(gòu)造它的預(yù)測(cè)分析表。 解：（1）計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST集和FOLLOW集。 FIRST集合有： FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}。 FIRST(E39。)={+,ε} FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^}。 FIRST(T39。)=FIRST(T)∪{ε}={(,a,b,^,ε}。 FIRST(F)=FIRST(P)={(,a,b,^}。 FIRST(F39。)=FIRST(P)={*,ε}。 FIRST(P)={(,a,b,^}。 FOLLOW集合有： FOLLOW(E)={),}。 FOLLOW(E39。)=FOLLOW(E)={),}。 FOLLOW(T)=FIRST(E39。)∪FOLLOW(E)={+,),}。//不包含ε FOLLOW(T39。)=FOLLOW(T)=FIRST(E39。)∪FOLLOW(E)={+,),}。 FOLLOW(F)=FIRST(T39。)∪FOLLOW(T)={(,a,b,^,+,),}。//不包含ε FOLLOW(F39。)=FOLLOW(F)=FIRST(T39。)∪FOLLOW(T)={(,a,b,^,+,),}。 FOLLOW(P)=FIRST(F39。)∪FOLLOW(F)={*,(,a,b,^,+,),}。//不包含ε (2)證明這個(gè)方法是LL(1)的。 各產(chǎn)生式的SELECT集合有： SELECT(ETE39。)=FIRST(T)={(,a,b,^}。 SELECT(E39。+E)={+}。 SELECT(E39。ε)=FOLLOW(E/)={),} SELECT(TFT39。)=FIRST(F)={(,a,b,^}。 SELECT(T39。T)=FIRST(T)={(,a,b,^}。 SELECT(T39。ε)=FOLLOW(T/)={+,),}。 SELECT(FPF39。)=FIRST(P)={(,a,b,^}。 SELECT(F39。*F39。)={*}。 SELECT(F39。ε)=FOLLOW(F39。)={(,a,b,^,+,),}。 SELECT(P(E))={(} SELECT(Pa)={a} SELECT(Pb)= SELECT(P^)={^} 可見，相同左部產(chǎn)生式的SELECT集的交集均為空，所以文法G[E]是LL(1)文法。 (3)構(gòu)造它的預(yù)測(cè)分析表。 文法G[E]的預(yù)測(cè)分析表如下： 3．已知 NFA= （ {x,y,z},{0,1},M,{x},{z} ），其中：M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x}, M(y,1)= φ ,M(z,1)={y}, 構(gòu)造相應(yīng)的DFA并最小化。 解：根據(jù)題意有NFA圖: 下表由子集法將NFA轉(zhuǎn)換為DFA： 下面將該DFA最小化： (1) 首先將它的狀態(tài)集分成兩個(gè)子集：P1={A,D,E},P2={B,C,F} (2) 區(qū)分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等價(jià)。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等價(jià)（見下步），從而B與C，F(xiàn)可以區(qū)分。有P21={C,F},P22={B}。 (3) 區(qū)分P1:由于A，E輸入0到終態(tài)，而D輸入0不到終態(tài)，所以D與A，E可以區(qū)分，有P11={A,E},P12={D}。 (4) 由于F(A,0)=B,F(E,0)=F,而B，F(xiàn)不等價(jià)，所以A，E可以區(qū)分。 (5) 綜上所述，DFA可以區(qū)分為P={{A}，{B}，{D}，{E}，{C，F(xiàn)}}。所以最小化的DFA如下： 4．已知文法為： Sa|^|(T) TT,S|S 構(gòu)造它的 LR(0)分析表。 解：加入非終結(jié)符S39。，方法的增廣文法為： S39。S Sa S^ S(T) TT,S TS 下面構(gòu)造它的LR(0)項(xiàng)目集規(guī)范族為： 從上表可看出,不存在移進(jìn)歸約沖突以及歸約歸約沖突，該文法是LR(0)文法。 從而有下面的LR(0)分析表： 5．已知文法 AaAd|aAb| ε 判斷該文法是否是 SLR(1) 文法，若是構(gòu)造相應(yīng)分析表，并對(duì)輸入串 ab 給出分析過程。解：增加一個(gè)非終結(jié)符S/后，產(chǎn)生原文法的增廣文法有： S39。A AaAd|aAb|ε 下面構(gòu)造它的LR(0)項(xiàng)目集規(guī)范族為： 從上表可看出,狀態(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é)論。這就是說，以上的移進(jìn)歸約沖突是可以解決的，因此該文法是SLR(1)文法。 其SLR(1)分析表為： 對(duì)輸入串a(chǎn)b給出分析過程為：6．已知文法 G[S] 為： Sa|^|(T) T T,S|S (1) 計(jì)算 G[S] 的 FIRSTVT 和 LASTVT 。 (2) 構(gòu)造 G[S] 的算符優(yōu)先關(guān)系表并說明 G[S] 是否未算符優(yōu)先文法。 (3) 計(jì)算 G[S] 的優(yōu)先函數(shù)。 (4) 給出輸入串 (a,a) 的算符優(yōu)先分析過程。解：（1）各符號(hào)的FIRSTVT和LASTVT：（2）算符優(yōu)先關(guān)系表： （3）對(duì)應(yīng)的算符優(yōu)先函數(shù)為： （4）句子(a,a)分析過程如下： 1
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1