編譯原理復習題(考試)-資料下載頁

　　

【正文】 (b)由0和1組成的串，包括空串。(c)倒數第3個字符為0，由0和1組成的串。(d)含有3個1的所有0和1的串。(e)由偶數個0和偶數個1構成的所有0和1的串。26．已知文法G[S]：S→(L)|aL→L,S|S為句子(a,(a,a))構造最左推導和最右推導。解：句子(a,(a,a))的最左推導為：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))的最右推導為：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[S] 的自動機： SA0 AA0|S1|0 該自動機是確定的嗎？若不確定，則對它確定化。解：由于該文法的產生式SA0，AA0|S1中沒有字符集VT的輸入，所以不是確定的自動機。 要將其他確定化，必須先用代入法得到它對應的正規式。把S?A0代入產生式A?S1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入SA0有該文法的正規式：0(0|01)*0，所以，改寫該文法為確定的自動機為： 由于狀態A有3次輸入0的重復輸入，所以上圖只是NFA，下面將它確定化：下表由子集法將NFA轉換為DFA: 由上表可知DFA為：2．對下面的文法 G ： 　　 ETE39。　　 E39。+E| ε 　　 TFT39。　　 T39。 T| ε 　　 F PF39。　　 F39。 *F39。| ε 　　 P(E)|a|b|^ 　　 (1)計算這個文法的每個非終結符的 FIRST 集和 FOLLOW 集。 　　 (2) 證明這個方法是 LL(1) 的。 　　 (3) 構造它的預測分析表。 解：（1）計算這個文法的每個非終結符的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)證明這個方法是LL(1)的。 各產生式的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)={b} SELECT(P^)={^} 可見，相同左部產生式的SELECT集的交集均為空，所以文法G[E]是LL(1)文法。 (3)構造它的預測分析表。 文法G[E]的預測分析表如下： 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}, 構造相應的DFA并最小化。 解：根據題意有NFA圖: 下表由子集法將NFA轉換為DFA： 下面將該DFA最小化： (1) 首先將它的狀態集分成兩個子集：P1={A,D,E},P2={B,C,F} (2) 區分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等價。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等價（見下步），從而B與C，F可以區分。有P21={C,F},P22={B}。 (3) 區分P1:由于A，E輸入0到終態，而D輸入0不到終態，所以D與A，E可以區分，有P11={A,E},P12={D}。 (4) 由于F(A,0)=B,F(E,0)=F,而B，F不等價，所以A，E可以區分。 (5) 綜上所述，DFA可以區分為P={{A}，{B}，{D}，{E}，{C，F}}。所以最小化的DFA如下： 4．已知文法為： Sa|^|(T) TT,S|S 構造它的 LR(0)分析表。 解：加入非終結符S39。，方法的增廣文法為： S39。S Sa S^ S(T) TT,S TS 下面構造它的LR(0)項目集規范族為： 從上表可看出,不存在移進歸約沖突以及歸約歸約沖突，該文法是LR(0)文法。 從而有下面的LR(0)分析表： 5．已知文法 AaAd|aAb| ε 判斷該文法是否是 SLR(1) 文法，若是構造相應分析表，并對輸入串 ab 給出分析過程。解：增加一個非終結符S/后，產生原文法的增廣文法有： S39。A AaAd|aAb|ε 下面構造它的LR(0)項目集規范族為： 從上表可看出,狀態I0和I2存在移進歸約沖突，該文法不是LR(0)文法。對于I0來說有：FOLLOW(A)∩{a}={b,d,}∩{a}=Φ，所以在I0狀態下面臨輸入符號為a時移進，為b,d,時歸約，為其他時報錯。對于I2來說有也有與I0完全相同的結論。這就是說，以上的移進歸約沖突是可以解決的，因此該文法是SLR(1)文法。 其SLR(1)分析表為： 對輸入串ab給出分析過程為：6．已知文法 G[S] 為： Sa|^|(T) T T,S|S (1) 計算 G[S] 的 FIRSTVT 和 LASTVT 。 (2) 構造 G[S] 的算符優先關系表并說明 G[S] 是否未算符優先文法。 (3) 計算 G[S] 的優先函數。 (4) 給出輸入串 (a,a) 的算符優先分析過程。解：（1）各符號的FIRSTVT和LASTVT：（2）算符優先關系表： （3）對應的算符優先函數為： （4）句子(a,a)分析過程如下： 1