編譯原理復(fù)習(xí)題答案

1、二、概念題1、設(shè)有文法：P-P+QIQQ Q*R|RR-(P)|i(1) 證明Q*R+Q+Q 是它的一個句型。(3分)(2) 給出Q*R+Q+Q的所有短語，直接短語和句柄。(4分)(3) 給出句子i + i * i的最右推導(dǎo)。(4分)(4) 給出句子i + i * i的最左推導(dǎo)。(4分)2、 設(shè)有文法： E+T|TT-T*F|FF-(E)|i(1) 證明E+T*F是它的一個句型。(3分)答案：E E T E T*F(2) 給出E+T*F的所有短語，直接短語和句柄。(4分)短語：E+T*F, T*F,直接短語：T*F句柄:T*F(3) 給出句子i + i * i的最右推導(dǎo)。(4分)3、寫出表達(dá)式

2、a+b*(c-d)對應(yīng)的逆波蘭式和三元式序列。答案：逆波蘭式：(abcd-*+)三元式序列：OPARG1ARG2(1)-cd*b(1)+a(2)三、詞法分析題給出下面語言的相應(yīng)文法L1=anbnambm|n,m >0答案：S-AB|A|B|刀A aAb|abB aBb|ab給出下面語言的相應(yīng)文法L2=anbnci|n >1,i»答案：S AB|BA a|aAB bBc|bc給出下面語言的相應(yīng)文法L3=anbncm| m,n> n,為奇數(shù)，m 為偶數(shù)答案：文法G(S):SACAaaAbb/abC ccCcc/cc四、詞法分析題專業(yè)word可編輯1、構(gòu)造下面正規(guī)式相應(yīng)的

3、DFA(011)*1(11)*)*(要求：先將正規(guī)式轉(zhuǎn)化為NFA,再將NFA確定化，最小化)2、構(gòu)造下面正規(guī)式相應(yīng)的 DFA1(0|1)*101答案：II011XA,B,CA,B,C B,C B,C,DB,C B,C B,C,DB,C,D B,C,E B,C,DB,C,E B,C B,C,D,yB,C,D,y B,C,E B,C,D3、構(gòu)造一個DFA,它接受二a , b上所有包含ab的字符串。(要求：先將正規(guī)式轉(zhuǎn)化為NFA,再將NFA確定化，最小化)答案：(一)相應(yīng)的正規(guī)式為(a|b)*ab(a|b)*(二) M此正規(guī)式對應(yīng)的NFA為狀態(tài)轉(zhuǎn)換矩陣為:IJO.1,2)11,2.3(lr21<

4、;1,2,3乙丸6占(1,211.2.3JU,乙6罰|l2r3f5f>U,2.51(1,2,3,5,61<lr2,5,6>最小化:0,1, 23, 4, 50,2, 1 ,3, 4, 5所以此等價的DFA為：開始狀態(tài)為0 ,終態(tài)集為3,狀態(tài)集為0,1,3, 輸入字母表是a,b狀態(tài)轉(zhuǎn)換圖如上。4、構(gòu)造與正規(guī)式 b(a|b)*ba 等價的DFA五、語法分析題1、對下面的文法G:Expr * ExprExpr i(Expr)|Var ExprTailExprTaif Expr| eVarid VarTailVarTaiR(Expr) | e(1)構(gòu)造LL(1)分析表(12 分)答案

5、:(1 ) FIRST(Expr)二匕,(,id FIRST(ExprTail)=_ ,& FIRST(Var)二idFIRST(VarTiil)= ( ,0FOLLOW(Expr)二# , ) FOLLOW(ExprTail) =# , ) FOLLOW(Var) =_ , # , ) FOLLOW(VarTail) =_ , # , ) 步驟符號棧輸入串所用產(chǎn)生式id()EzcrEiiCirVarEizpxTai 1EmrfEsprTailExprTail-. EjrEqprTiil-*EzprT'ailVarVar予idVarTailVarTailVarai 1£

6、;Vai'Tai 1 VrTailt(2)給出對句子id id(id)的分析過程。(8分)# Expr# ExprTail Varid_ _id(id) #idid(id) # Expr f Var ExprTail# ExprTail VarTail id id_d(id) # Varf id VarTail# ExprTail VarTail_ _id(id)# ExprTail_ _id(id) #VarTaif£# Expr_ _id(id) #ExprTailf _ Expr# Expr# Expr_id(id) #Expr f _Expr_id(id) # Exp

7、rid(id) #ExpVar ExprTail# ExprTail VarTail id id(id) #VarTid VarTail# ExprTail VarTail(id) # ExprTail )Expr(id) #VarTaiT(Expr)# ExprTail )Expr(id) # ExprTail ) )Expr(id) #ExprT (Expr)# ExprTail ) )Exprid) # ExprTail )ExprTail Varid) #ExprTail# ExprTail )# ExprTail Varid(id) #ExprTail VarTail id id)

8、# ExprTail )ExprTail VarTail )# ExprTail )ExprTail )# ExprTail ) )# ExprTail )# ExprTailExp t VarVarT id VarTailVarTaiT£ExprTailg#ExprTail#分析成功F面的文法G:910111213141516171819202122232、對E'E| £T FT'T'丹F PF'F' *F'| &P(E)|a|b|A(1) 計算這個文法的每個非終結(jié)符的 FIRST和 FOLLOW°( 8分

9、)答案：FIRST(E)=(,a,b,AFIRST(E')二+, jFIRST(T)二(,a,b"FIRST(T')=(,a,b,A, jFIRST(F)=(,a,b,AFIRST(F')二*, jFIRST(P)=(,a,b,AFOLLOW(E)二#,)FOLLOW(E')二#,)FOLLOW(T)二+,),#FOLLOW(T')二+,),#FOLLOW(F)二(,a,b,"+,),#FOLLOW(F')二(,a,b,"+,),#FOLLOW(P)=*,(,a,b,A,+,),#(2) 證明這個文法是LL(1)的。

10、(6分)答案：考慮下列產(chǎn)生式：E E|T T|F *F |P (E)F|a|bFIRST(+E)Q FIRST(滬+ A 護(hù) ©FIRST(+E)Q FOLLOW(E')二+ A#,)= ©FIRST(T)A FIRST(滬(,a,bf A 護(hù) ©FIRST(T)A FOLLOW(T')=(,a,b,A A +,),#= ©FIRST(*F')A FIRST(滬* A = ©FIRST(*F')A FOLLOW(F')二* A (,a,b,A,+,),#= © FIRST(E)AFIRST(a)

11、 AFIRST(b) AFIRST(A)= © 所以該文法式LL(1)文法.(3) 構(gòu)造它的預(yù)測分析表。(6分)2a期班pE fTE'農(nóng)EtTZ*£ ->7ZrEJ+E*E' f耳*Ef THTVT fFTTrFT丁 FT*T'ppa卩T八F T*p &F*apF FFpF PFFf呼FPFf口Fr T &FfF T貝FTF* TFf ->Fr+pF f 2FfbaPS3、已知文法GS為:S->a|(T)T->T,S|S 消除文法GS中的左遞歸，得文法G'S。 文法GfS是否為LL(1)的？若是，給出它

12、的預(yù)測分析表4、對下面的文法G:S S a T | a T | a TT a T | a(1) 消除該文法的左遞歸和提取左公因子；構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合； 構(gòu)造該文法的LL(1)分析表，并判斷該文法是否是LL(1)的答案: 構(gòu)適該文注的LL(1)分析表答：(1)(消除左遞歸2分)St aTS, aTS*SJ yaTS | sT t Ft AdT I a a井判斷該文注是奩是LL的。(提魅左公因子2分)Ft aTS1 | v a TSf S J aTSt | £Tt auF廠 t T I £(4分) FIRST(S)af v； FTRATF尸卜£

13、; FIRST(T) FIRSTS)=a * £ FOLLOW(S)= FOLLOWfS*)FOLLOW(T)f 祁 FOLLOW(T)=,時5、文法G(S)及其LR分析表如下，請給出串baba#的分析過程(1)s J DbB(2)D J d(3)D J e(4)B J a(5)B J Bba (6) B J eLR®»00765432oa£a>£&bACTIONs3Ds00s5aaa>a c c4kS6B2D00765432koosososs4sofl： sfl:D bfl: Dfl:蘋ujnfl:fl:fl:a fl：留

14、 fl:fl:a b a fl：>>4W word£!>>acc專業(yè)word可編輯六、語法分析題考慮文法：SAS|bASA|a（1）列出這個文法的所有LR（0）項目。（5分）答案0.SS1.SS2.SAS 3. S A S4.SAS5.Sb6.Sb7. A SA8. AS A9.ASA10.A a11. A a（2）給出識別文法所有活前綴的 DFA°（ 5分）（3）求所有非終結(jié)符的FOLLOW集。（5分）（4）文法是SLR文法嗎？若是，構(gòu)造出它的SLR分析表，否則說明理 由。（5分） 不是SLR文法狀態(tài)3, 6，7有移進(jìn)歸約沖突狀態(tài)3：FOLLOW(

15、S ')=不包含 a,b狀態(tài)6：FOLLOW（S）=#,a,b包含a,b,；移進(jìn)歸約沖突無法消解狀態(tài)7：FOLLOW（A）=a,b包含a,b ；移進(jìn)歸約沖突消解所以不是SLR文法七、證明題1、證明下面文法是LL(1)的但不是SLR(1)的。St AaAb|BbBaASBt£首先該文法無左遞歸存在，沒有公共左因子。其次對于 St AaAb|BbBa FIRST(AaAb)=a FIRST(BbBa)=bFIRST(AaAb) n FIRST(BbBa)= 所以該文法是LL(1)文法。(2)證明該文法不是 SLR的。文法的LR(0)項目集規(guī)范族為：I0=S' t .s S

16、 t .AaAb S t .BbBa A t . b t .I1= S't s. I2= StA.aAb I3= StB.bBa I4= StAa.Ab At. I5= StBb.Ba Bt. I6= StAaA.b I7= StBbB.a I8= StAaAb. I9= StBbBa. 考察I0:FOLLOW(A)=a,b FOLLOW(B)=a,b FOLLOW(A)n FOLLOW(B)= a,b.專業(yè)word可編輯產(chǎn)生規(guī)約-規(guī)約沖突。所以該文法不是SLR(1)文法。2、證明下面文法是SLR(1但不是LR(0)的S AAAb|bBaB aAc|a|aAb解:文法GS:0:SA1

17、:A Ab2 :A bBa3:BaAc4:Ba5 :B aAb構(gòu)造LR(0)項目集規(guī)范族：狀態(tài)項目集轉(zhuǎn)換函數(shù)0SAGO0 , A = 1A AbGO0 , A = 1A bBaGO0 , b = 21S A ACCEPTA AbGO1 , b = 32At b BaGO2 , B =4B aAcGO2 , a =5B aGO2 , a =5B aAbGO2 , a =53A Ab R14A bB aGO4 , a =65B aAcGO5 , A = 7B a R4B aAbGO5 , A = 7A AbGO5 , A = 7A bBaGO5 , b = 26A bBa R27B aAcGO7

18、, c = 8B aAbGO7 , b = 9A A bGO7 , b = 98B aAc R39B aAb R5A Ab R1狀態(tài)5存在 歸約-移進(jìn)”中突，狀態(tài)9存在 歸約-歸約”沖突，因此該文法不是LR(O)文法。狀態(tài)5 :FOLLOW(B) = a,因此，F(xiàn)OLLOW(B) A b =O狀態(tài)9 :FOLLOW(B) = a, FOLLOW(A) = #, b, c,因此FOLLOW(B) A FOLLOW(A) =O狀態(tài)5和狀態(tài)9的沖突均可用SLR(1)方法解決，構(gòu)造SLR(1)分析表如下：狀態(tài)ACTIONGOTOabc#AB0S211S3ACCEPT2S543R1R1R14S65R4S276R2R2R27S9S88R39R5R1R1R1該SLR(1)分析表無重定義，因此該文法是SLR(1)文法，不是LR(0) 文法。八、語義分析題1、將語句if (A<0)(B>0) the n while (C>0) do C:=C-D翻譯成四元式答案：100 (j<，A，0，104)101 (j， 102)102 (j>，B，0，1