編譯原理-習題

第2章習題及解答：試構(gòu)造下述語言L的文法：

L={ambn|m≥0,n≥1};【解1】G1(S):S->ABA->Aa|

B->Bb|bS->ABA->aA|

B->bB|b或G2(S):【解】分析：※產(chǎn)生式形式：1.此語言僅有一種句型：ambn

；2.

ambn

中包含有兩個短語：am和

bn

；于是：設(shè)：S(句子)，A（短語1），B（短語2）第2章習題及解答：試求下述文法G(Z)所定義的語言：

G(Z):Z->b|bB,B->bZ【解】⒈推導運算法：L(G)={x|Zx,x∈VT*

}=>

+文法所定義的語言Z=>bB=>bbZ=>bbbZ=>bB=>bbZ=>bbbB=>bbbbZ=>bbbbbZ=>b∴∵Z=>b2n-1,

n≥1⒉正規(guī)方程式法：∵Z=b|bB,B=bZ即Z=b|bbZ※遞推求解Z=b|bbZ

可得：Z=b2n-1n≥1∴L(G)={b2n-1|n≥1}…第2章習題及解答：【解】根據(jù)文法G[S]:S->(AS)|(b);A->(SaA)|(a)⑵從語法述上，看(A((SaA)(b)))的短語、直接短語和句柄：S(AS)(AS)(SaA)(b)短語：①(A((SaA)(b)))②((SaA)(b))③(SaA)④(b)

直接短語：③(SaA)④(b)句柄：③(SaA)⑴因為(a)不是句子，所以沒有短語問題。已知文法G[S]:S->(AS)|(b);A->(SaA)|(a)試找出符號串(a)和(A((SaA)(b)))的短語、直接短語(即簡單短語)和句柄。SSAS第2章習題及解答：證明下面文法是二義性文法S->iSeS|iS|i【證】因為句型iiSeS

有下述兩棵不同的語法樹：SiSeSiSSiSiSeS和所以所屬文法是二義性文法！【習題

】G(S):S->aAcBe;A->Ab|b;B->d⑴證明

=aAbcde

是一個句型；⑵畫出句型

的語法樹；⑶指出句型

的短語、簡單短語和句柄。第2章習題及解答：已知文法G(S):E->E+T|E-T|T【解】∵消除直接左遞歸公式：整理:E->E+T|E–T|T∴有G`(S):E->T{T}A->A|≡A->{

}A->A`,A`->A`|ε或G`(S):E->TE`E`->TE`|ε令：

=+|-E->ET|T第2章習題及解答：已知文法

G(S):S->aSab|bAB;A->bB|a;B->aA|bC->abB|baA;D->Cbc|abc;【解】刪除無用產(chǎn)生式：自定己；不終結(jié)；不可達。⑴找自定己產(chǎn)生式（如A->A）

無自定己者?、茦?gòu)造可終結(jié)非終結(jié)符集

Vvt={},⑶構(gòu)造可達非終結(jié)符集

VAR={},G`(S):S->aSab|bAB;A->bB|a;B->aA|b∴刪除不可達非終結(jié)符：C,D后得：無不終結(jié)者！A,B,C,D,SS,A,B第3章習題及解答：試構(gòu)造確定自動機DFA:⑴e=1(0|1)*101①+011-②1③④⑤01⑵e=(a|b)*(aa|bb)(a|b)*①+ab-②③④aabbabA{1}ba+DFA變換表DFA狀態(tài)圖ABCDE+--aaabbbbabaE{1,3,4}D{1,2,4}E{1,3,4}D{1,2,4}E{1,3,4}B{1,2}C{1,3}D{1,2,4}C{1,3}B{1,2}D{1,2,4}E{1,3,4}C{1,3}B{1,2}--確定化第3章習題及解答：試構(gòu)造一個DFA,它接收∑={0,1}上所有滿足如下條件的字符串：每一個1都有0直接跟在右邊?！窘狻竣?01-②0③1-0①+-②010或給定正規(guī)語言，構(gòu)造有限自動機：

A={an,ban|n≥0}【解】①+-②baa-①+-②baa-第3章習題及解答：把下述NFA轉(zhuǎn)換為DFA:①②③abab+-FA1:①②③abab+-FA2:ab+-DFA2:ABA{1}ba+B{2,3}B{2,3}B{2,3}-aab+-DFA1:ABCbC{2,3}B{2}C{2,3}B{2}C{2,3}B{2}-A{1}ba+第3章習題及解答消除

NFA的

邊：②③①+a-

ab③④-①+②ba

b

aFA3:FA4:【算法】⑶逆序刪

邊,并補充新邊。⑴

閉路合而為一；⑵標記隱含初態(tài)和終態(tài)；②①+-abaDFA1③④-①+②bab

aab③-①+②aabbaDFA2無用狀態(tài)第3章習題及解答：已知符號串集合，構(gòu)造正規(guī)式、自動機和正規(guī)文法：A={,an,ban|n≥1}【解】

正規(guī)式:e=|a+|ba+或e=a*|ba+

自動機DFA:

aa+-12b-3a

正規(guī)文法:

SABS->aA|bB|

A->aA|

B->aA已知自動機DFA:②ab③⑤bcc①④bb-+-⑴擴展DFA(加入結(jié)束標記#),構(gòu)造壓縮變換表；⑵根據(jù)實現(xiàn)算法，寫出識別abbc#的過程。⑵輸入串a(chǎn)bbc#識別過程：第3章習題及解答：【解】⑴擴展DFA:壓縮變換表④⑤③②①

no④b②a

no④b索引表

no⑤c③b

no⑤c③b

nook#1備注變換剩余chstate②ab③⑤bcc①④bb+--#-#2bbc#a接受ok#5#c3c#b3bc#b5332#b構(gòu)造下述文法的遞歸子程序：

G(S):S->aASb|Bd;A->cS|;B->bB|d

【解】入口出口aerr2NEXT(w)Aerr1NEXT(w)S子程序nnnyySbBdNEXT(w)y第5章習題及解答入口cNEXT(w)出口遇時nySA子程序bNEXT(w)出口nyBdNEXT(w)err3yn入口B子程序已知文法：S->aASb①|(zhì)Bd②A->cS③|④B->bB⑤|d⑥（1）求選擇集合；證明是LL(1)文法；G(S):⑴select(①)={}select(②)={}⑶select(⑤)={}select(⑥)={}⑵select(③)={}select(④)={}【解】（1）求選擇集合（2）LL(1)分析表:∵三對選擇集合兩兩不相交!∴G(S)是LL(1)文法!dBAS＃cbaab,dc=follow(A)a,b,dbd⑥④②⑤③④④②①（2）構(gòu)造LL(1)分析表?！呷龑x擇集合中，兩兩不相交！∴G`(S)是LL(1)文法！

把下述文法化為LL(1)文法！S->A;A->B|AiB;B->C|B+C;C->)A*|(※文法變換，消除左遞歸：

A->B|AiB=>A->B{iB}則A->BA`;A`->iBA`|

B->C|B+C=>B->C{+C}則B->CB`;B`->+CB`|

※整理并附加產(chǎn)生是序號后得：G`(S):S->A①；A->BA`②;A`->iBA`③|

④B->CB`⑤;B`->+CB`⑥|

⑦;C->)A*⑧|(⑨select(③)={i};select(④)={*,#};select(⑥)={+};select(⑦)={i,*,#};select(⑧)={)};select(⑨)={(};⑴⑵⑶G(S):Z->S1(0)S->a2A3(1)|b4B5(2)A->06A7(3)|18(4)B->09B10(5)|111(6)

考慮文法：G(S)S->aA|bB;A->0A|1;B->0B|1⑴構(gòu)造活前綴的DFA(即句柄識別器)【解】※擴展文法，編碼：①②③⑥⑦⑧⑨⑩0+SaA0OKr(1)r(3)r(4)r(2)bA1B0④0Br(5)r(6)111011※活前綴的DFA(即句柄識別器):∵句柄識別器(DFA)中無沖突狀態(tài)！∴G(S)是LR(0)文法!⑵是LR(0)文法嗎？⑤B1011109

9r(5)r(5)r(5)r(6)r(5)10

S1

SA7

A3

AOK1r(2)r(2)r(2)r(2)r(2)5b4a20B5111094r(4)r(4)r(4)r(4)r(4)8r(6)r(3)18r(1)18

1r(6)r(3)r(1)

#066r(3)r(3)r(3)7r(6)r(6)r(6)11r(1)r(1)r(1)3

2

B

0

b

a06⑶G(S)的LR(0)分析表：第5章習題及解答

設(shè)有文法G(S):S->rD;D->D,i|i【解】⑴構(gòu)造活前綴的DFA(即句柄識別器)※擴展文法，編碼：Z->S1(0)S->r2D3(1)D->D3,4i5(2)|i6(3)0+SrDOKr(1)r(2)r(3)，ii②③④⑤⑥①#∵在狀態(tài)③處出現(xiàn)(移進、歸約)沖突！∴G(S)不是LR(0)文法！

⑵∵follow(S)={#},可以解決沖突：即若當前單詞為“，”,則移進,4當前單詞為“#”,則歸約

r(1)∴G(S)是SLR(1)文法??！第5章習題及解答：r,i#SD0r2S11ok2i6D33,4r(1)4i55r(2)r(2)r(2)r(2)6r(3)r(3)r(3)r(3)⑶文法G(S)的SLR(1)分析表：第5章習題解答：G(E):E->E+T|TT->(E)|iE`->E1(0)E->E2+3T4(1)|T5(2)T->(6E7)8(3)|i9(4)G`(E`)1.構(gòu)造句柄識別器：-Ti0E①-OKE②+③T④-r(1)T⑤-r(2)(⑥E⑦)⑧-r(3)i⑨r(4)E((i【解】+第7章習題及解答：試

寫出逆波蘭式：⑴a*(-b+c)=>abc+*或a0b-c+*-⑵a+b*(c+d/e)=>abcde/+*+⑶-a+b*(-c+d)=>abcd+*+或0a-b0c-d+*+--⑷

A(CD)=>ACD⑸(AB)(CD)=>ABCD【快速寫出要點】變元順序不變，算符先算在前！※驗證：pos((AB)(CD))=pos((AB))pos((CD))

=pos(AB)pos(CD)

=AB

pos(C)pos(D)

=ABCD第7章習題及解答2：寫出下述語句的四元式序列：

(1)if(x>0)x=(a-b/2)*c；

(2)while(a∨b)b=2*a/5;⑴⑴(>x0t1)⑵(ift1__)⑶(/b2t2)⑷(-at2t3)⑸(*t3ct4)⑹(=t4_x)⑺(ie___)⑴(wh___)⑵(∨abt1)⑶(dot1__)⑷(*2at3)⑸(/t35t4)⑹(=t4_b)⑺(we___)⑵【解】第7章習題及解答3：G`(E)：E->T|E+T{+}|E-T{-}T->F|T*F{*}|T/F{/}F->i{i}|(E)

※試用分別用最左推導法和最左歸約法分析(翻譯)符號串a(chǎn)*(b-c+d)的逆波蘭式生成過程。已知算術(shù)表達式的逆波蘭翻譯文法：【解】最左推導：Z=>T=>T*F{*}=>F*F{*}=>a{a}*F{*}=>a{a}*(E){*}=>a{a}*(E+T{+}){*}=>a{a}*(E-T{-}+T{+}){*}=>+a{a}*(b-c{c}{-}+dsldlllx{+}){*}導出序列※分離導出序列：刪除動作符號：a*(b-c+d)……源表達式刪除文法符號：abc-d+*……逆波蘭式⑴t2=B/C⑶B=A⑴t1=2*3

⑵t2=B/C

⑶t3=t1+t2⑷A=t3

⑸t4=2*3

⑹t5=B/C⑺t6=t4+t5

⑻B=t6

⑼t7=2*3⑽t8=B/C

⑾t9=t7+t8(12)C=t9第8章習題及解答求下述語句片斷的DAG優(yōu)化過程：

A=2*3+B/C;B=2*3+B/C;C=2*3+B/C;ⅰ.根據(jù)四元式序列構(gòu)造優(yōu)化的DAG:16|t12B3C4/t27+,t7|t5,t4|A|C/t86ⅱ.根據(jù)優(yōu)化的DAG重組四元式:+t3A|t35,t6⑵A=6+t2⑷t8=A/C,Bt9C|t9⑸

C=6+t8⑴t1