編譯原理期末復(fù)習(xí)題

《編譯原理》復(fù)習(xí)題《編譯原理》復(fù)習(xí)題#表1SLR分析表ACTIONGOTO狀態(tài)ab#S0S1S231S1S2r342S1S253acc4r15r243.給出表達(dá)式-a*b+b*c+d/e的語法樹和三元式序列。⑵識(shí)別該文法所產(chǎn)生的活前綴的 DFA如圖⑵識(shí)別該文法所產(chǎn)生的活前綴的 DFA如圖1所示?！窘狻孔⒁獾綘顟B(tài)IiFOLLOW(S)={#}{a}nnFOLLOW(R)=①可以采用SLR沖突消解法，得到如下的 SLR分析表。從分析表可以看出，表中沒有沖突項(xiàng)，所以該文法是SLR(1)文法。三元式答：語法樹三元式++◎(-,a,-)②。*，①，b)3(*,b,c)+，②，③)⑤(/,d,e)?(+，④，⑤)44.證明下面文法StAaAb|BbBaA宀&B—g是LL(1)文法，但不是SLR(1)文法。證明：(1)first(AaAb)={a}first(BbBb)=，有first(AaAb)Afirst(BbBb)=①所以根據(jù)LL(1)文法的定義，該文法是 LL(1)文法。(2分)(2)為了構(gòu)造識(shí)別活前綴的 DFA，初態(tài)集包含如下四個(gè)項(xiàng)目： S—.AaAb S—.BbBaA—. B—.但該項(xiàng)目中有兩個(gè)可歸約項(xiàng)目： A—. B—.,產(chǎn)生歸約-歸約沖突，而follow(A)={a,b},follow(B)={a,b}，有follow(A)Afollow(B)工①，所以使用向前看一個(gè)終結(jié)符的方法不能解決此沖突，所以該文法不是SLR(1)文法。(3分45.現(xiàn)有文法G[S]S—a|￡|(T)T—T,S|S請(qǐng)給出句子(a,(a,a))的最左、最右推導(dǎo)，并指出最右推導(dǎo)中每一個(gè)句型的句柄。答：最左推導(dǎo)：S=>(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a))最右推導(dǎo)：S=>(T)=>(T,S)=>(T,(H)=>(T,(T,S))=>(T,(T,_a))=>(T,(S,a))=>(T,(a,a))=>(S,(a,a))=>(a,(a,a))句型的句柄是為加下劃線的部分答：初始劃分:46.將下圖的DFA最小化。答：初始劃分:11={{0,1,2},{3,4}}(1分)(1)考查{0,(1)考查{0,1,2},1和2接受a,b后都轉(zhuǎn)向相同的狀態(tài)，且接受b后轉(zhuǎn)向終態(tài)，而0接受b后轉(zhuǎn)向非終態(tài)2向非終態(tài)2,所以0與1,2可分,llnew={{0},{1,2},{3,4}}(1分)考查{3,4}，接受a,b后都轉(zhuǎn)向相同的狀態(tài)，所以3,4不可分。llnew={{0},{1,2},{3,4}}（1分）將1,2合并用1代表，3,4合并用3代表，最終的最小化DFA如下:a47.設(shè)有如下文法： PtDD^D;D|id:T|procid;D;Ttreal|integer給出一個(gè)語法制導(dǎo)定義，打印該程序一共聲明了多少個(gè) ida47.設(shè)有如下文法： PtDD^D;D|id:T|procid;D;Ttreal|integer給出一個(gè)語法制導(dǎo)定義，打印該程序一共聲明了多少個(gè) id。答:文法語法制導(dǎo)定義PtDPrint(D.num)DTD1;D2D.num=D1.num+D2.numdtid:TD.num=1DTprocid;D1;D.num=D1.num+1TtrealTtinteger48.識(shí)別文法G的活前綴的DFA如下圖所示，補(bǔ)充完成狀態(tài)分析表。12和15,然后根據(jù)該圖構(gòu)造SLR(1)G:(4)(0)P'tp (1) PtaPb (2)PtqQtbSc(5)StSa (6)Sta(3)QtbQc答：12,I5分別如下圖所示:Follow(P)={b,$}1分Follow(Q)={b,c,$} 1分四元式序列:Follow(S)={c,a}1分四元式序列:SLR(1)分析表:Action表GOTO表abc$PQS0S2S5131Acc2S2S5433R2R24S75S6S59106R6R67R1R18R3R3R39S810S12S1111R4R4R412R5R549.給出表達(dá)式(a+b)*(c+d/e)的語法樹和四元式序列。*答:語法樹如下:*◎(+，a,b,T1)?(/，d，e，T2)3(+，c，T2，T3)*，T1，T3，T4)50.構(gòu)造文法StAaAb|BbBaA￡B—g的預(yù)測(cè)分析表。答：first(S)={a，b},First(AaAb)={a}，F(xiàn)irst(BbBa)=Follow(A)={a，b}Follow(B)={a，b}ab$SS—AaAbS—BbBaAA—￡A—￡BB—￡B—￡

?寫出C語言標(biāo)識(shí)符集(字母或下劃線開頭的由字母、數(shù)字、下劃線構(gòu)成的串)的正規(guī)式。解答：用D表示數(shù)字0-9，用L表示字母a-z|A-Z，則C語言標(biāo)識(shí)符的正規(guī)式為：(L|_)(L|D|_)*?有一語法制導(dǎo)定義如下，其中 +表示符號(hào)連接運(yùn)算：StBBtaBtbBtBaBtBbprintB.versB.vers=aB.vers=bB.vers=a+B.versB.vers=b+B.vers若輸入序列為abab，且采用自底向上的分析方法，則輸出序列為( _baba_ )。用分析樹表示求解過程。PrintbabaBtBB.vers=baba*B.vers=aba+B.vers=ba+B.vers=a53?假設(shè)第一個(gè)四元式的序號(hào)是 100,寫出布爾表達(dá)式a<bVcAd>e的四元式序列。100(j<,a,b,106)101(j,_,_,102)102(jnz,c,_,104)103(j,_,_,q)104(j>,d,e,106)105(j,_，一，q)T:106F：q54?設(shè)有如下文法：G[E]:iEWT|TT tT/F|FF E)|a|b|cWt+|-證明符號(hào)串a(chǎn)/(b-c)是句子。解答：有推導(dǎo)E:T：T/F二F/F=a/F二a/(E)=a/(EWT)二a/(TWT)二a/(FWT)二a/(bWT)=a/(b-T)二a/(b-c)，即從文法開始符號(hào)E能夠推導(dǎo)出a/(b-c)，所以a/(b-c)是文法G[E]的句子。55?對(duì)于下列文法G[S]:StSb|bAA taA|a構(gòu)造一個(gè)與G等價(jià)的LL(1)文法G'。對(duì)于文法G,構(gòu)造相應(yīng)的LL(1)分析表。解：(1)(5分)G':StbAS'S'tbS'|&AtaA'A'tA|&(2)(1分)FIRST(S)=FIRST(S')={b,&}FIRST(A)={a}FIRST(A'):={a,&}FOLLOW(S)={#}FOLLOW(S，)={#}FOLLOW(A)={b,#}FOLLOW(A')=(b,#)LL(1)分析表:ab#SStbAS'S'S'tbS'S'T&AataA'A'A'taA't&A'T&56.構(gòu)造下述文法的SLR(1)分析表。G[S]:St(A)A tABB|BB tb解：拓丿乂法：(1分)S'TS(0)St(A)(1)ATabb(2)AtB(3)Btb(4)識(shí)別活前綴的DFA:（4分）

FIRST集和follow集：(1分)follow(S)={#}follow(A)={b,)}follow(B)={b,)}First(S)={(,c}follow(S)={#}follow(A)={b,)}follow(B)={b,)}First(A)=First(B)=StbAbStbAbprint“1”At(Bprint“2”Ataprint“3”BtaA)printa▲”4若輸入序列為b(a(a(aa)))b,且米用自下而上的分析方法，則輸出序列為(57.有一語法制導(dǎo)定義如下:34242421 )。SLR⑴分析表：(4分)ACTIONGOTO()b#SAB0S211Acc2S4353S6S474R4R45R3R36R17S488R2R258.寫出賦值語句X=-(a+b)/(c-d)-(a+b*c)的逆波蘭表示。Xab+-cd-/abc*+-=59.為文法G[S]:S~(L)|aLtL,S|S寫一語法制導(dǎo)定義，它輸出句子中括號(hào)嵌套的最大層次數(shù)。

解:使用num屬性描述括號(hào)的嵌套最大層次數(shù)解:S—S print (S.num)S^(L) S.num=L.num+1S—a S.num=O—L,S L.num=ifL .num>S.numthenL.numelseS.numL—S L.num=S.num每個(gè)式子1分。60.設(shè)有文法G[S]:S—aAcB|BdA—AaB|