編譯原理總復習市公開課一等獎百校聯賽優(yōu)質課金獎名師賽課獲獎課件

復習綱領1/45一、基礎知識1、經典編譯程序可劃分為幾部分？各部分主要功效是什么？2、什么是句子和什么是句型？3、文法和語言關系？4、二義性文法？5、語法分析慣用方法？6、LL（1）文法、LR(0)文法、SLR(1)文法、LR(1)文法充分必要是什么？2/457、屬性文法中符號屬性分為哪幾個？怎樣設計遞歸下降翻譯？

8、棧式符號表工作過程。9、程序運行時存放分配方法有哪些？動態(tài)存放分配包含兩種方式？10、代碼優(yōu)化慣用三種方法？3/45二、針對語言結構文法

1、L(G)={奇正整數};2、L(G)={anbm|n,m≥1};1、A::=1|3|5|7|9|NAN::=N0|N1|N2|N3|N4|N5|N6|N7|N8|N9N::=0|1|2|3|4|5|6|7|8|92、G[S]:S::=ABA::=aA|aB::=bB|b4/45三、針對文法結構語言1、已知文法G[S]：S∷=ABA∷=aA︱εB∷=bBc︱bc,寫出該文法描述語言。1、A∷=aA︱ε描述語言:{an|n>=0}B∷=bBc︱bc描述語言:{bncn|n>=1}L(G[S])={anbmcm|n>=0,m>=1}2、已知文法G[Z]：Z::=aBaB::=bB|b寫出該文法描述語言。描述語言:{bn|n>=1}L(G[Z])={abna|n>=1}5/451、有正則文法G[Z]：Z::=Ua|Vb，U::=Zb|b，V::=Za|a，畫出該文法狀態(tài)圖，并檢驗句子abba是否正當。SUVZaaabbb2、狀態(tài)圖如圖所表示，S為開始狀態(tài)，Z為終態(tài)。寫出對應正則文法以及V，Vn和Vt。答：G[Z]:Z::=Ab|bA::=Aa|aV={Z,A,a,b},Vn={Z,A},Vt={a,b}答：（1）從開始狀態(tài)到結束狀態(tài)有一條路徑，路徑上字符組合正是abba,即句子abba正當。（2）z=>Ua=>Zba=>Vbba=>abba,即句子abba正當。四、正則文法和狀態(tài)圖SAZabab6/45五、求句型短語、簡單短語以及句柄，依據文法推導句子或者句型。

1、已知文法

E∷=T∣E+T∣E-TT∷=F∣T*F∣T/FF∷=(E)∣x，

(1)給出句子x+(x*x)最左推導和最右推導。（2）寫出句型（E+T）–F*x短語、簡單短語以及句柄解：（1）最左推導：E=>E+T=>T+T=>F+T=>x+F=>x+(E)=>x+(T)=>x+(T*F)=>x+(F*F)=>x+(x*F)=>x+(x*x)最右推導：E=>E+T=>E+F=>E+（E）=>E+（T）=>E+(T*F)=>E+(T*x)=>E+(F*x)=>E+(x*x)=>T+(x*x)=>F+(x*x)=>x+x*x7/451、短語(1)(E+T)-F*x(2)(E+T)(3)E+T(簡單短語、句柄)(4)F*x(5)F(簡單短語)(6)x(簡單短語）E+ETEE—TTFT*FFx()①②③④⑤⑥8/45六、以下文法G是左遞歸文法，試消除其左遞歸。G[T]：T→T*F|FF→F↑P|PP→（T）|i消除左遞歸后，得到不含左遞歸文法G‘以下：G’[T]:T→FT’T’→*FT’|εF→PF’F’→↑PF‘|εP→（T）|i消除左遞歸后，得到不含左遞歸文法G‘以下：G‘[T]：T→F{*F}F→P{↑P}P→（T）|i9/45七、NFA確實定化

01a,baa解：NFAM'={{0,1},{a,b},0,{0},δ}q0=ε-closure({0})={0}=q0q0a=ε-closure(δ(0,a))=ε-closure({0,1})={0,1}=q1q0b=ε-closure(δ(0,b))=ε-closure({1})={1}=q2q1a=ε-closure(δ(0,a)∪δ(1,a))=ε-closure({0,1})={0,1}=q1q1b=ε-closure(δ(0,b)∪δ(1,b))=

ε-closure({1})={1}=q2q2a=ε-closure({0})={0}=q0q2b=ε-closure(Φ)=Φq0qq2ababa10/45八、依據正則表示式結構對應NFA或DFA

1、1(1|0)*|0NFA2、(ab)*(a*|b*)(ba)*等價DFA02101ε011.2、解析：首先結構正則表示式NFA，其結構過程如圖所表示;(ab)*(a*|b*)(ba)*11/45(ba)*a*|b*(ab)*abεεεεbaa*b*aεεεεεεεεabbba(2)依據ＮＦＡ結構ＤＦＡＮＦＡM’={{0,1,2,3,4,5,6,7,8,9},{a,b},0,{9},δ}12/45q0=ε-closure({0})={0,1,3,4,5,6,7,9};q0a

=ε-closure(δ(q0,a))=ε-closure({2,,4})={2,4,6,7,9}=q1;q0b=ε-closure(δ(q0,b))=ε-closure({5,8})={5,6,7,8,9}=q2;q1a=ε-closure(δ(q1,a))=ε-closure({4})={4,6,7,9}=q3;q1b=ε-closure(δ(q1,b))=

ε-closure({1,8})={1,3,4,5,6,7,8,9}=q4;q2a=ε-closure(δ(q2,a))=ε-closure({7})={7,9}=q5;q2b=ε-closure(δ(q2,b))=

ε-closure({5,8})={5,6,7,8,9}=q2;q3a=ε-closure(δ(q3,a))=ε-closure({4})={4,6,7,9}=q3;13/45q3b=ε-closure(δ(q3,b))=ε-closure({8})={8}=q6;q4a=ε-closure(δ(q4,a))=ε-closure({2,4})={2,4,6,7,9}=q1;q4b=ε-closure(δ(q4,b))=

ε-closure({5,8})={5,6,7,8,9}=q2;q5a=ε-closure(δ(q5,a))=ε-closure({φ})=φ;q5b=ε-closure(δ(q5,b))=ε-closure({8})={8}=q6q6a=ε-closure(δ(q6,a))=ε-closure({7})={7,9}=q5;q6b=ε-closure(δ(q6,b))=ε-closure({φ})=φ；

計算到此，不再有新狀態(tài)。14/45aaaaaabbbbbbDFA狀態(tài)轉換圖以下：15/45十、將右圖DFA化簡。解：(1)將Q狀態(tài)劃分為S1和S2狀態(tài),即Q=S1∪S2,S1={2,3,4,5},S2={0,1}014253aaaaaabbbbbb(2)對于S1={2,3,4,5}劃分：δ(2,a)=1;δ(3,a)=3;δ(4,a)=0;δ(5,a)=5;狀態(tài)0,1和3,5不屬于同一個狀態(tài)集。所以將S1劃分成s3={2,4},s4={3,5}(3）對于s3={2,4}劃分：δ(2,a)=1;δ(2,b)=3;δ(4,a)=0;δ(4,b)=5;即S3不能劃分，說明狀態(tài)2和狀態(tài)4等價。（4）對于S2={0,1}劃分：δ(0,a)=1;δ(0,b)=2;δ(1,a)=1;δ(1,b)=4;即S2不能劃分，說明狀態(tài)0和狀態(tài)1等價。16/45（4）對于s4={3,5}劃分：δ(3,a)=3;δ(3,b)=2;δ(5,a)=5;δ(5,b)=4;即S4不能劃分，說明狀態(tài)3和狀態(tài)5等價.（5）到此，不能再繼續(xù)劃分，最終得到不能劃分狀態(tài)集有S2={0,1}，s3={2,4},s4={3,5}每一個狀態(tài)集中留一個狀態(tài)得:S2={0}，s3={2},s4={3}。將原來轉換函數中狀態(tài)1改成狀態(tài)0，狀態(tài)4改成狀態(tài)2，狀態(tài)5改成狀態(tài)3，得到：δ(0,a)=0;δ(0,b)=2;δ(2,a)=0;δ(2,b)=3;δ(3,a)=3;δ(3,b)=2;最終化簡后DFA如圖右：023baaabb17/45

十一、對下面文法，設計遞歸下降分析程序。S→aAS|(A),A→Ab|c解：首先將左遞歸去掉，將規(guī)則A→Ab|c改成A→c過程SINPUTSYM=’a’INPUTSYM=下一個符號YNINPUTSYM=’(’INPUTSYM=下一個符號YINPUTSYM=’)’INPUTSYM=下一個符號YNN出口錯誤錯誤過程A過程S過程A非終止符號S分析程序18/45Y過程AINPUTSYM=’c’INPUTSYM=下一個符號YINPUTSYM=’b’N錯誤INPUTSYM=下一個符號出口非終止符號A分析程序N19/45十二、遞歸下降分析方法，對此文法來說，在分析過程中，能否防止回溯問題。

1、設有文法G[Z]：Z∷=(A),A∷=a|Bb,B∷=Aab在分析過程中，能否防止回溯？為何？2、怎樣結構遞歸下降分析程序。1、解：若采取遞歸下降分析方法，對此文法來說，在分析過程中不能防止回朔。規(guī)則A::=a|Bb,FIRST(a)={a},FIRST(Bb)={a},即此規(guī)則候選式首符號集有相交。需要經過規(guī)則帶入使候選式第一個符號相同，然后提取公因子。但經過規(guī)則帶入后最終一個候選式總是以B開頭，而FIRST(B)={a},所以無法提取出a,候選式首符號集總是相交。但可將B規(guī)則代入A規(guī)則得：A∷=a|Bb轉換成A∷=a{abb}即可防止回溯。20/452、解：改寫后文法變?yōu)閆∷=(A),A∷=a{abb}Y過程ZINPUTSYM=’(’INPUTSYM=下一個符號YN出口錯誤過程A非終止符號Z分析程序INPUTSYM=’)’N錯誤INPUTSYM=下一個符號21/45NY過程AINPUTSYM=’a’INPUTSYM=下一個符號YINPUTSYM=’a’N錯誤INPUTSYM=下一個符號YINPUTSYM=’b’INPUTSYM=’b’出口N錯誤N出口Y22/45十三、什么是LL(1)文法，怎樣結構LL(1)分析表以及怎樣利用分析表對符號串分析。

1、若有文法G[A]：A∷=aABe|ε，B∷=Bb|b（1）為非終止符號結構FIRST集和FOLLOW集；（2）該文法是不是LL(1)文法？（3）結構LL(1)分析表；設A∈VN，則FOLLOW（A）結構方法以下：①對文法開始符S，令#∈FOLLOW(S)。②若有產生式A→αBβ，則FIRST(β)FOLLOW(B);③若有產生式A→αB或A→αBβ且ε∈FIRST(β),則FOLLOW(A)FOLLOW(B)解：（1）FIRST(A)={a,ε},

FIRST(B)=FOLLOW(A)={b,#},FOLLOW(B)={b,e}

23/45（2）對于A產生式：FIRST(aABe)={a},

FOLLOW(A)={b,#},

∵FIRST(aABe)∩FOLLOW(A)=φ,∴A中無多重定義。又對于B產生式，存在左遞歸，改寫變成：B∷=bB’B’∷=bB’|ε24/45符號輸入符號abe#ABB’abe#POP,PUSH(eBAa)

POP,NEXTSYM

POPPOP,PUSH(B’b)POP,PUSH(B’b)

POP,NEXTSYM

POP

POP,NEXTSYMPOP

ACCEPT(3)改寫后文法變?yōu)锳∷=aABe|εB∷=bB’B’∷=bB’|ε

FIRST(A)={a,ε},

FIRST(B)=,FIRST(B’)={b,ε}FOLLOW(A)={b,#},FOLLOW(B)={e}FOLLOW(B’)={e}25/45十四、若有文法A→（A）A|ε（1）為非終止符A結構FIRST集合和FOLLOW集合（2）說明該文法是LL（1）文法。解：（1）FIRST(A)={(,ε},FOLLOW(A)={),#}.(2)因為此文法不存在左遞歸又因為FIRST(（A）A）＝{(};

FOLLOW(A)∩FIRST(（A）A）＝φ即該文法為LL（1）文法26/45十五、設有以下文法G[E]:E→-E|[E]|VEtEt→-E|εV→tVtVt→[E]|ε解：(1)一個上下文無關文法G是LL(1)文法充要條件是，對任一A∈VN,若A所定義全部產生式為：①A→β1|β2|β3|…|βn；下面條件成立：FIRST(β1)∩FIRST(β2)∩…∩FIRST(βn)=φ；②假若βi=>ε,即FIRST(β1)∩…∩

FOLLOW（A）∩…∩FIRST(βn)=φ；首先求每一個產生式右部FIRST集：對于E→-E|[E]|VEtFIRST(-E)={-};FIRST([E])={[};FIRST(VEt)=FIRST(V)=FIRST(tVt)={t};(1)證實文法G[E]是LL(1)文法。(2)結構G[E]LL(1)分析表。(3)寫出句子t-t[t]分析過程。*27/45對于Et→-E|εFIRST(-E)={-}；FOLLOW（Et）={],#};對于V→tVt產生式；FIRST(tVt)={t};對于Vt→[E]|ε產生式：FIRST([E])={[};FOLLOW(Vt)={-,],#};(說明：E=>VEt=>V-E=>tVt-E;E=>[E]=>[VEt]=>[V]=>[tVt];E=>VEt#=>V#=>tVt#;)FIRST(-E)∩FIRST([E])∩FIRST(VEt)={-}∩{]}∩{t}=φ;FIRST(-E)∩FOLLOW(Et)={-}∩{],#}=φ;FIRST([E])∩FOLLOW(Vt)={[}∩{-,],#}=φ;上述計算結果均為空，即滿足LL(1)文法充要條件，證實該文法G[E]是LL(1)文法。28/45（2）文法G[E]LL(1)分析表以下：符號t-[]#EPOP,PUSH(EtV)POP,PUSH(E-)POP,PUSH(]E[)EtPOP,PUSH(E-)POPPOPVPOP,PUSH(Vtt)VtPOPPOP,PUSH(]E[)POPPOPtPOP,NEXTSYM-POP,NEXTSYM[POP,NEXTSYM]POP,NEXTSYM#ACCEPT29/45(3)句子t-t[t]分析過程以下表：步驟分析棧余留輸入串分析表元素所用產生式1#Et-t[t]#POP,PUSH(EtV)E→VEt2#EtVt-t[t]#POP,PUSH(Vtt)V→tVt3#EtVttt-t[t]#POP,NEXTSYM4#EtVt-t[t]#POPVt→ε5#Et-t[t]#POP,PUSH(E-)Et→-E6#E--t[t]#POP,NEXTSYM7#Et[t]#POP,PUSH(EtV)E→VEt8#EtVt[t]#POP,PUSH(Vtt)V→tVt9#EtVttt[t]#POP10#EtVt[t]#POP,PUSH(]E[)Vt→[E]30/4511#Et]E[[t]#POP,NEXTSYM12#Et]Et]#POP,PUSH(EtV)E→VEt13#Et]EtVt]#POP,PUSH(Vtt)V→tVt14#Et]EtVttt]#POP,NEXTSYM15#Et]EtVt]#POPVt→ε16#Et]Et]#POPEt→ε17#Et]]#POP,NEXTSYM18#Et#POPEt→ε19##ACCEPT步驟分析棧余留輸入串分析表元素所用產生式31/45十六、什么是LR(0)文法，怎樣結構LR(0)項目集規(guī)范族、分析表以及怎樣利用分析表對符號串分析。

1、考慮以下文法：S→S;T|TT→a(1)為這個文法結構LR(0)項目集規(guī)范族；(2)此文法是LR(0)文法嗎？假如是,結構LR(0)分析表；(3)對輸入串“a;a”進行分析。32/45狀態(tài)項目集轉換函數0S’→.SS→.S;TS→.TT→.aGO[0，S]=1GO[0，S]=1GO[0，T]=2

GO[0，a]=3

1S’→S.

S→S.;TACCEPTGO[1，;]=42S→T.R23T→a.R3

4S→S;.TT→.aGO[4，T]=5

GO[4，a]=35S→S;T.R1

解：此文法拓廣文法：0)S’→S1)S→S;T2)S→T3)T→a(1)LR(0)項目集規(guī)范族33/45狀態(tài)ACTIONGOTO；a#ST0S3121S4ACCEPT2R2R2R23R3R3R34S355R1R1R1(2)此文法中沒有“移進-歸約沖突”和“歸約-歸約沖突”項目集，那么該文法為LR(0)文法其LR(0)分析表為：34/45(2)對符號串“a;a”分析過程以下：步驟狀態(tài)棧符號棧輸入符號串ACTIONGOTO說明10#a;a#S3開始時，0入狀態(tài)棧，#入符號棧，符號為a，查動作表0行a列為S3，3入狀態(tài)棧，a入符號棧。203#a;a#R32輸入符號為a，查動作表3行a列為R3，用T→a規(guī)約，a出符號棧、T入符號棧，3出狀態(tài)棧，0為棧頂，查GOTO表0行T列得2，2入狀態(tài)棧302#T;a#R21用S→T規(guī)約401#S;a#S45024#S；a#S360243#S;a#R35用T→a規(guī)約70245#S;T#R11用S’→S;T規(guī)約801#S#ACCEPT35/45十七、證實下面文法是SLR(1)文法，但不是LR(0)文法。S→AA→Ab|BbaB→aAc|a|aAb證實:(1)此文法擴廣文法:0)S→A1)A→Ab2)A→bBa3)B→aAc4)B→a5)B→aAb(2)此文法項目集規(guī)范族：36/45狀態(tài)項目集轉換函數0S→·AA→·AbA→·bBaGO[0,A]=1GO[0,A]=1GO[0,b]=21S→A·A→A·bACCEPTGO[1,b]=32A→b·BaB→·aAcB→·aB→·aAbGO[2,B]=4GO[2,a]=5GO[2,a]=5GO[2,a]=53A→Ab·R14A→bB·aGO[4,a]=65B→a·AcB→a·B→a·AbA→·AbA→·bBaGO[5,A]=7R4GO[5,A]=7GO[5,A]=7GO[5,b]=2狀態(tài)項目集轉換函數6A→bBa·R27B→aA·cB→aA·bA→A·bGO[7,c]=8GO[7,b]=9GO[7,b]=98B→aAc·R39B→aAb·A→Ab·R5R1因為狀態(tài)5出現“移進－歸約”沖突，狀態(tài)9出現“歸約－歸約”沖突。即不是LR(0)文法。FOLLOW(S)={#}，FOLLOW(A)={b,c}FOLLOW(B)={a}即狀態(tài)5中，

FOLLOW(B)∩={a}∩=φ狀態(tài)9中，FOLLOW(B)∩

FOLLOW(A)={a}∩{b,c}=φ37/45十八、考慮以下文法G[S];S→(A)A→Ab|bBaB→aAb|aAc|a(1)證實文法G[S]不是LR(0)文法，是SLR文法。(2)結構文法G[S]SLR(1)分析表。(3)給出句子(baa)分析過程。解：首先將文法G[S]拓廣為G[S']:1.S'→S2.S→(A)3.A→Ab4.A→bBa5.B→aAb6.B→aAc7.B→a38/45(1)假如一個文法G不是LR(0)文法，則它LR(0)項目集規(guī)范族中一定存在包含“移進-歸約”沖突或“歸約-歸約”沖突項目集。所以為證實該文法不是LR(0)文法，首先結構它LR(0)項目集規(guī)范族。以下表：狀態(tài)項目集轉換函數0S'→·SS→·(A)GO[0,(]=1GO[0,S]=71S→(·A)A→·AbA→·bBaGO[1,A]=2GO[1,A]=2GO[1,b]=32S→(A·)A→A·bGO[2,)]=8GO[2,b]=103A→b·BaB→·aAbB→·aAcB→·aGO[3,B]=6GO[3,a]=4GO[3,a]=4GO[3,a]=439/45狀態(tài)項目集轉換函數4B→a·AbB→a·AcB→a·A→·AbA→·bBaGO[4,A]=5GO[4,A]=5R7GO[4,b]=3GO[4,b]=35B→aA·bB→aA·cA→A·bGO[5,b]=12GO[5,c]=11GO[5,b]=126A→bB·aGO[6,a]=97S'→S·ACCEPT8S→(A)·R29A→bBa·R410A→Ab·R311B→aAc·R612B→aAb·A→Ab·R5R340/45逐一檢驗項目集規(guī)范族中每一個項目集，不難發(fā)覺項目集I4和I12是含有項目沖突項目集。項目集I4既含有“B→a·”歸約項目，又含有“B→a·Ab,B→a·AcA→·Ab，A→·bBa”4個移進項目，即存在“移進-規(guī)約”沖突。而項目集I12同時兩個歸約項目“B→aAb·，A→Ab·”，即存在“歸約-歸約”沖突，故該文法不是LR(0)文法。假如文法G不是LR(0)文法，是SLR文法應滿足條件，則對含有沖突項目集IK，設IK同時含有m個移進項目“A1→α1·a1β1,A2→α2·a2β2,…Am→αm·amβm,”和n個歸約項目“B1→γ1·，B2→γ2·,…,Bn→γn·”,若有：{a1，a2，…，am}∩FOLLOE(B1)∩FOLLOE(B2)∩…∩FOLLOE(Bn)=φ.即移進項目“·”右鄰待移進全部終止符組成集協(xié)議全部歸