《編譯原理》期末復(fù)習(xí)資料匯總

《編譯原理》期末復(fù)習(xí)資料【題1】（a|b）*（aa|bb）（a|b）*畫出狀態(tài)轉(zhuǎn)換圖。IaIb①1,2,32,3,42,3,5②2,3,42,3,4,6,7,82,3,5③2,3,52,3,42,,3,5,6,7,8④2,3,4,6,7,82,3,4,6,7,82,3,5,7,8⑤2,3,5,6,7,82,3,4,7,82,3,5,6,7,8⑥2,3,5,7,82,3,4,7,82,3,5,6,7,8⑦2,3,4,7,82,3,4,6,7,82,3,5,7,8IaIb123243325446575675746新的狀態(tài)轉(zhuǎn)換圖如下：（1）A={1,2,3}，B={4,5,6,7}Aa={2,4}×（2）A={1,3}，B={2}，C={4,5,6,7}Aa={2}B，Ab={3,5}×（3）A={1}，B={2}，C={3},D={4,5,6,7}（單元素可以不用看，必有，古先看D）Da={4,7}D，Db={5,6}D，Aa={2}B，Ab={3}C，Ba={4}D，Bb={3}C，Ca={2}B，Cb={5}C，則有abABCBDCCBDDDD（a*|b*）b（ba）*的狀態(tài)轉(zhuǎn)換圖。IaIb①1,2,3,42,43,4,5,6,8②2,42,45,6,8③3,4,5,6,8---3,4,5,6,7,8④5,6,8---7⑤3,4,5,6,7,86,83,4,5,6,7,8⑥76,8---⑦6,8---7IaIb1232243---54---657567---7---6新的狀態(tài)轉(zhuǎn)換圖如下：化簡：（用終結(jié)狀態(tài)與非終結(jié)狀態(tài)，然后輸出狀態(tài)一致分一類）。（1）A={1,2,6}，B={3,4,5,7}Aa={2}×（2）A={1,2}，B={6}，C={3,4,7}，D={5}Cb={5,6}×（只要有一個不屬于任何一個集合，就不行）（3）A={1,2}，B={6}，C={3}，D={4,7}，E={5}Ab={3,4}×（4）A={1}，B={2}，C={6}，D={3}，E={4,7}，F(xiàn)={5}Aa={2}B，Ab={3}D，Ba={2}B，Bb={4}E，Ca={7}E，Db={5}F，Eb={6}C，F(xiàn)a={7}E，F(xiàn)b={5}FabABDBBECE---D---FE---CFEF[注意事項]：[知識要點]：正則表達式：；；；；是最左邊一個字母一定是，其余字母為的任意組合，不包括。{a和若干個a（包括0的情形）后跟一個b構(gòu)成的符號串集合}{a和a后跟若干個（包括0的情形）b構(gòu)成的符號串集合}狀態(tài)轉(zhuǎn)換圖（有窮狀態(tài)自動機）：【題2】1.求如下簡單算術(shù)表達式文法中語法變量的FOLLOW集。[解答]：（1）求表達式文法的語法符號的FIRST集：FIRST(F)={（,id}FIRST(T)=FIRST(F)={（,id}FIRST(E)=FIRST(T)={（,id}FIRST(E')={+，ε}FIRST(T')={*,ε}FIRST(+)={+},FIRST(*)={*}FIRST(（)={（}FIRST(）)={）}FIRST(id)={id}（2）求表達式文法的語法變量的FOLLOW集：FOLLOW(E)={#,)}FOLLOW(E')=FOLLOW(E)={#,)}FOLLOW(T)={FIRST(E')-{ε}}∪FOLLOW(E)∪FOLLOW(E')={+,),#}FOLLOW(T')=FOLLOW(T)={+,),#}FOLLOW(F)=FIRST(T’)∪FOLLOW(T)∪FOLLOW(T')={*,+,),#}6[知識點]First集合的求法：First集合最終是對產(chǎn)生式右部的字符串而言的，但其關(guān)鍵是求出非終結(jié)符的First集合，由于終結(jié)符的First集合就是它自己，所以求出非終結(jié)符的First集合后，就可很直觀地得到每個字符串的First集合1.直接收?。簩π稳鏤->a…的產(chǎn)生式（其中a是終結(jié)符），把a收入到First(U)中2.反復(fù)傳送：對形入U->P1P2P3…Pn的產(chǎn)生式（其中P是非終結(jié)符），應(yīng)先把First(P1)中的全部內(nèi)容傳送到First(U)中,如果P1中有ε，把First(P2)中的內(nèi)容傳送到First(U)中,類推直到Pi中無ε。Follow集合的求法：Follow集合是針對非終結(jié)符而言的，F(xiàn)ollow(U)所表達的是句型中非終結(jié)符U所有可能的后隨終結(jié)符號的集合，特別地，“$”是識別符號的后隨符,先直接加入到S中。1.直接收?。鹤⒁猱a(chǎn)生式右部的每一個形如“…Ua…”的組合，把a直接收入到Follow(U)中。2.直接收?。簩π稳纭啊璘P…”(P是非終結(jié)符)的組合，把First(P)中非ε收入到Follow(U)中。3.反復(fù)傳送：對形如U－>aP的產(chǎn)生式（其中P是非終結(jié)符）或U->aPQ(P,Q為非終結(jié)符且Q中含ε)，應(yīng)把Follow(U)中的全部內(nèi)容傳送到Follow(P)中。[例]文法：S→ABcA→a|εB→b|εFirst集合求法:能由非終結(jié)符號推出的所有的開頭符號或可能的ε，但要求這個開頭符號是終結(jié)符號。如此題A可以推導(dǎo)出a和ε，所以FIRST（A）=｛a，ε｝；同理FIRST（B）={b,ε};S可以推導(dǎo)出aBc，還可以推導(dǎo)出bc，還可以推導(dǎo)出c，所以FIRST(S）=｛a，b，c｝Follow集合的求法:緊跟隨其后面的終結(jié)符號或＃。但文法的識別符號包含＃，在求的時候還要考慮到ε。具體做法是把所有包含你要求的符號的產(chǎn)生式都找出來，再看哪個有用。Follow（S）=｛＃｝如求A的，產(chǎn)生式：S→ABcA→a|ε，但只有S→ABc有用。跟隨在A后面的終結(jié)符號是FIRST（B）=｛b，ε｝，當(dāng)FIRST（B）的元素為ε時，跟隨在A后的符號就是c，所以Follow（A）=｛b，c｝同理Follow（B）=｛c｝2.對下面的文法G：(1)計算這個文法的每個非終結(jié)符的FIRST集和FOLLOW集。(2)證明這個方法是LL(1)的。(1)計算這個文法的每個非終結(jié)符的FIRST集和FOLLOW集。(2)證明這個方法是LL(1)的。(3)構(gòu)造它的預(yù)測分析表。解：（1）計算這個文法的每個非終結(jié)符的FIRST集和FOLLOW集。FIRST集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};FIRST(E')={+,ε}FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};FIRST(T')=FIRST(T)∪{ε}={(,a,b,^,ε};FIRST(F)=FIRST(P)={(,a,b,^};FIRST(F')=FIRST(P)={*,ε};FIRST(P)={(,a,b,^};FOLLOW集合有：FOLLOW(E)={),#};FOLLOW(E')=FOLLOW(E)={),#};FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#};//不包含εFOLLOW(T')=FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#};FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#};//不包含εFOLLOW(F')=FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#};FOLLOW(P)=FIRST(F')∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε(2)證明這個方法是LL(1)的。各產(chǎn)生式的SELECT集合有：SELECT(E->TE')=FIRST(T)={(,a,b,^};SELECT(E'->+E)={+};SELECT(E'->ε)=FOLLOW(E/)={),#}SELECT(T->FT')=FIRST(F)={(,a,b,^};SELECT(T'->T)=FIRST(T)={(,a,b,^};SELECT(T'->ε)=FOLLOW(T/)={+,),#};SELECT(F->PF')=FIRST(P)={(,a,b,^};SELECT(F'->*F')={*};SELECT(F'->ε)=FOLLOW(F')={(,a,b,^,+,),#};SELECT(P->(E))={(}SELECT(P->a)={a}SELECT(P->b)=SELECT(P->^)={^}可見，相同左部產(chǎn)生式的SELECT集的交集均為空，所以文法G[E]是LL(1)文法。(3)構(gòu)造它的預(yù)測分析表。文法G[E]的預(yù)測分析表如下：【題3】考慮下面的文法：求出所有語法變量的FIRSTOP集合和LASTOP集合。構(gòu)造文法求出所有語法變量的FIRSTOP集合和LASTOP集合。構(gòu)造文法的算符優(yōu)先關(guān)系表，并判斷是否為算符優(yōu)先文法。計算文法的算符優(yōu)先函數(shù)。給出表達式和id*(id+id)的算符優(yōu)先分析過程。[解答]：所有語法變量的FIRSTOP集合和LASTOP集合如下：（2）文法的算符優(yōu)先關(guān)系表算符關(guān)系算符+-*/()id+EQ\o\ac(○,>)EQ\o\ac(○,>)EQ\o\ac(○,<)EQ\o\ac(○,<)EQ\o\ac(○,<)EQ\o\ac(○,>)EQ\o\ac(○,<)-EQ\o\ac(○,>)EQ\o\ac(○,>)EQ\o\ac(○,<)EQ\o\ac(○,<)EQ\o\ac(○,<)EQ\o\ac(○,>)EQ\o\ac(○,<)*EQ\o\ac(○,>)EQ\o\ac(○,>)EQ\o\ac(○,>)EQ\o\ac(○,>)EQ\o\ac(○,<)EQ\o\ac(○,>)EQ\o\ac(○,<)/EQ\o\ac(○,>)EQ\o\ac(○,>)EQ\o\ac(○,>)EQ\o\ac(○,>)EQ\o\ac(○,<)EQ\o\ac(○,>)EQ\o\ac(○,<)（EQ\o\ac(○,<)EQ\o\ac(○,<)EQ\o\ac(○,<)EQ\o\ac(○,<)EQ\o\ac(○,<)EQ\o\ac(○,≡)EQ\o\ac(○,<)）EQ\o\ac(○,>)EQ\o\ac(○,>)EQ\o\ac(○,>)EQ\o\ac(○,>)EQ\o\ac(○,>)idEQ\o\ac(○,>)EQ\o\ac(○,>)EQ\o\ac(○,>)EQ\o\ac(○,>)EQ\o\ac(○,>)因為文法中任意兩個終結(jié)符之間只存在一種關(guān)系，因此該文法為算符優(yōu)先文法。文法的算符優(yōu)先函數(shù)優(yōu)先函數(shù)算符+-*/（）id#（棧內(nèi)優(yōu)先函數(shù)）22440440（棧外優(yōu)先函數(shù)）11335050表達式的算符優(yōu)先分析過程步驟棧輸入串優(yōu)先關(guān)系動作1#+#2#+##EQ\o\ac(○,<)移進3#F+##EQ\o\ac(○,<)EQ\o\ac(○,>)#用歸約4#F+#EQ\o\ac(○,<)移進+5#F+#EQ\o\ac(○,<)移進6#F+F#+EQ\o\ac(○,<)EQ\o\ac(○,>)#用歸約7#E##EQ\o\ac(○,<)+EQ\o\ac(○,>)#用歸約表達式id*(id+id)的算符優(yōu)先分析過程步驟棧S優(yōu)先關(guān)系當(dāng)前輸入字符R輸入字符串0#EQ\o\ac(○,<)id*(id+id)#1#idEQ\o\ac(○,>)*(id+id)#2#NEQ\o\ac(○,<)*(id+id)#3#N*EQ\o\ac(○,<)（id+id)#4#N*(EQ\o\ac(○,<)id+id)#5#N*(idEQ\o\ac(○,>)+id)#6#N*(NEQ\o\ac(○,<)+id)#7#N*(N+EQ\o\ac(○,<)id)#8#N*(N+idEQ\o\ac(○,>))#9#N*(N+NEQ\o\ac(○,>))#10#N*(NEQ\o\ac(○,≡))#11#N*(N)EQ\o\ac(○,>)#12#N*NEQ\o\ac(○,>)#13#N停止#2.已知文法G[S]為：S->a|^|(T)T->T,S|S(1)計算G[S]的FIRSTVT和LASTVT。(2)構(gòu)造G[S]的算符優(yōu)先關(guān)系表并說明G[S]是否為算符優(yōu)先文法。(3)計算G[S]的優(yōu)先函數(shù)。(4)給出輸入串(a,a)#的算符優(yōu)先分析過程。解：（1）各符號的FIRSTVT和LASTVT：（2）算符優(yōu)先關(guān)系表：因為文法中任意兩個終結(jié)符之間只存在一種關(guān)系，因此該文法為算符優(yōu)先文法。（3）對應(yīng)的算符優(yōu)先函數(shù)為：（4）句子(a,a)#分析過程如下：[知識點]FIRSTVT及LASTVT求法構(gòu)造集合FIRSTVT（P）的兩條規(guī)則。（i）若有產(chǎn)生式P→a…，或P→Qa…，則a∈FIRSTVT（P）。（ii）若a∈FIRSTVT（P），且有產(chǎn)生式P→Q…，則a∈FIRSTVT（P）。構(gòu)造集合FIRSTVT（P）的兩條規(guī)則（i）有產(chǎn)生式P→…a，或P→…aQ，則a∈LASTVT（P）。（ii）若a∈LASTVT（Q），且有產(chǎn)生式P→Q…，則a∈FIRSTVT（P）?！绢}4】令文法G：S→BBB→aBB→b判斷該文法是否LR（1）文法，若是構(gòu)造LR（1）分析表。解1）將文法G拓廣為G`：（0）S`→S（1）S→BB（2）B→Ab（3）B→b2)求出G`的非終結(jié)符的FOLLOW和FIRST集AFOLLOW(A)FIRST(A)S`#a,bS#a,bBa,b,#a,b3）構(gòu)造個G`的LR(1)的項目集族及GO函數(shù)I5:S→I5:S→BB.,#I2:S→B.B,#B→.Ab,#B→.b,#I1:S`→S.,#I7:BI7:B→b.,#I6:B→a.B,#B→.Ab,#B→.b,#I0:S`I0:S`→.S,#S→.BB,#B→.aB,a|bB→.b,a|bI9:B→aB.,#BI9:B→aB.,#I3:B→a.B,a|bI3:B→a.B,a|bB→.aB,a|bB→.b,a|baaI8:B→I8:B→aB.,a|bbI4I4:B→b.,a|b3)判斷文法是否為LR（1）文法。該文法構(gòu)出的C＝{I0,I1,I2,I3,I4,I5,I6,I7,I8,I9}中，每個狀態(tài)集均無沖突，所以該文法是LR（1）文法。4）構(gòu)造LR(1)分析表狀態(tài)ACTIONGOTOab#SB0S3S4121acc2S6S753S3S484r3r35r16S6S77r38r2r29r2填空題1.消除左遞歸（P124）文法左遞歸問題:一個文法是含有左遞歸的，如果存在非終結(jié)符P。直接消除見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符P的規(guī)則為P→Pa|b,其中b不以P開頭。那么，我們可以把P的規(guī)則等價地改寫為如下的非直接左遞歸形式：P→bP￠P￠→aP￠|e一般而言，假定關(guān)于P的全部產(chǎn)生式是P→Pa1|Pa2|…|Pam|b1|b2|…|bn,其中，每個a都不等于e，而每個b都不以P開頭,那么，消除P的直接左遞歸性就是把這些規(guī)則改寫成： P→b1P￠|b2P￠|…|bnP￠P￠→a1P￠|a2P￠|…|amP￠|e[例]文法E→E＋T|TT→T*F|FF→(E)|i經(jīng)消去直接左遞歸后變成：E→TE￠E￠→+TE￠|eT→FT￠T￠→*FT￠|eF→(E)|i 例如文法S→Qc|cQ→Rb|bR→Sa|a雖沒有直接左遞歸，但S、Q、R都是左遞歸的STQcTRbcTSabc一個文法消除左遞歸的條件：不含以e為右部的產(chǎn)生式（無空產(chǎn)生式）；不含回路。消除左遞歸的算法：1.把文法G的所有非終結(jié)符按任一種順序排列成P1，P2，…，Pn；按此順序執(zhí)行；2.FORi:=1TOnDOBEGINFORj:=1TOi-1DO把形如Pi→Pjg的規(guī)則改寫成Pi→d1g|d2g|…|dkg;(其中Pj→d1|d2|…|dk是關(guān)于Pj的所有規(guī)則)消除關(guān)于Pi規(guī)則的直接左遞歸性END3.化簡由2所得的文法。即去除那些從開始符號出發(fā)永遠無法到達的非終結(jié)符的產(chǎn)生規(guī)則。[例]考慮文法G(S)S→Qc|cQ→Rb|bR→Sa|a令它的非終結(jié)符的排序為R、Q、S。對于R，不存在直接左遞歸。把R代入到Q的有關(guān)候選后，把Q的規(guī)則變?yōu)镼→Sab|ab|b，現(xiàn)在的Q不含直接左遞歸。把Q代入到S的有關(guān)候選后，S變成S→Sabc|abc|bc|c，由于S→Sabc|abc|bc|c存在直接左遞歸，消除S的直接左遞歸后： S→abcS￠|bcS￠|cS￠ S￠→abcS￠|e Q→Sab|ab|b R→Sa|a關(guān)于Q和R的規(guī)則已是多余的，化簡為： S→abcS￠|bcS￠|cS￠ S￠→abcS￠|e注意：由于對非終結(jié)符排序的不同，最后所得的文法在形式上可能不一樣。但不難證明，它們都是等價的。同樣：[例]考慮文法G(S)S→Qc|cQ→Rb|bR→Sa|a非終結(jié)符排序選為S、Q、R，那么，R→Qca|ca|aR→Rbca|bca|ca|a最后所得的無左遞歸文法是： S→Qc|c Q→Rb|b R→bcaR￠|caR￠|aR￠ R￠→bcaR￠|e 不同排序所得的文法的等價性是顯然的。文法的分類(Chomsky體系)（P41）（1）短語結(jié)構(gòu)文法（PSG）如果G滿足文法定義的要求，則Ｇ是０型文法（短語結(jié)構(gòu)文法PSG:PhraseStructureGrammar）。L(G)為PSL。（1）上下文有關(guān)文法(CSG)如果對于，均有|β|≥|α|成立(Ｓ→ε除外)，則稱Ｇ為１型文法。即：上下文有關(guān)文法（CSG）L(G)為1型/上下文有關(guān)/敏感語言(CSL)。其他定義方法：設(shè)文法G[S]，若P中任一產(chǎn)生式α→β的形式為→,其中,β,∈(V∪T）*,β≠ε,A∈V。上下文無關(guān)文法(CFG)如果對于，均有|β|≥|α|，并且α∈V成立，則稱G為２型文法。即：上下文無關(guān)文法(CFG:)L(G)為2型/上下文無關(guān)語言（CFL），CFG能描述程序設(shè)計語言的多數(shù)語法成分。（3）正規(guī)（則）文法(RG)設(shè)Ａ,Ｂ∈Ｖ，w∈T+或為，如果對于,均具有如下形式：右線性(RightLinear)文法：或左線性(LeftLinear)文法：或都是３型文法(正規(guī)文法RG)，L(G)為3型/正規(guī)集/正則集/正則語言（RL），能描述程序設(shè)計語言的多數(shù)單詞。左、右線性文法不可混用。[例]正規(guī)文法（RG）：G1：S0|1|00|11G3：S0|1|0A|1B，A0，B1G5：S0|0SG8：AaS|bS|cS|a|b|c上下文無關(guān)文法（CFG）：G2：SA|B|AA|BB,A0，B1G4：SA|B|BB,A0，B1G14：S0|1|2|3|0S0|1S1|2S2|3S3上下文有關(guān)文法（CSG）：G： S→CD C→aCA CA→Ca CaD→daD dAc→decＧ=(Ｖ，T，Ｐ，Ｓ)是一個文法,α→β∈P* G是0型文法，L(G)是0型語言；---其能力相當(dāng)于圖靈機* |α|≤|β|:G是1型文法，L(G)是1型語言(除Ｓ→ε);---其識別系統(tǒng)是線性界限自動機* α∈ＶN:G是2型文法，L(G)是2型語言;---其識別系統(tǒng)是不確定的下推自動機* A→aB或A→a:G是右線性文法，L(G)是3型語言 A→Ba或A→ａ:G是左線性文法，L(G)是3型語言---其識別系統(tǒng)是有窮自動機3.逆波蘭表示法逆波蘭表達式又叫做后綴表達式。在通常的表達式中，二元運算符總是置于與之相關(guān)的兩個運算對象之間，所以，這種表示法也稱為中綴表示。波蘭邏輯學(xué)家J.Lukasiewicz于1929年提出了另一種表示表達式的方法。按此方法，每一運算符都置于其運算對象之后，故稱為后綴表示。將一個普通的中序表達式轉(zhuǎn)換為逆波蘭表達式的一般算法是：首先構(gòu)造一個運算符棧，此運算符在棧內(nèi)遵循越往棧頂優(yōu)先級越高的原則。讀入一個用中綴表示的簡單算術(shù)表達式，為方便起見,設(shè)該簡單算術(shù)表達式的右端多加上了優(yōu)先級最低的特殊符號“#”。從左至右掃描該算術(shù)表達式，從第一個字符開始判斷，如果該字符是數(shù)字，則分析到該數(shù)字串的結(jié)束并將該數(shù)字串直接輸出。如果不是數(shù)字，該字符則是運算符，此時需比較優(yōu)先關(guān)系。做法如下：將該字符與運算符棧頂?shù)倪\算符的優(yōu)先關(guān)系相比較。如果，該字符優(yōu)先關(guān)系高于此運算符棧頂?shù)倪\算符，則將該運算符入棧。倘若不是的話，則將棧頂?shù)倪\算符從棧中彈出，直到棧頂運算符的優(yōu)先級低于當(dāng)前運算符，將該字符入棧。(5)重復(fù)上述操作(3)-(4)直至掃描完整個簡單算術(shù)表達式，確定所有字符都得到正確處理，我們便可以將中綴式表示的簡單算術(shù)表達式轉(zhuǎn)化為逆波蘭表示的簡單算術(shù)表達式。逆波蘭表達式，它的語法規(guī)定，表達式必須以逆波蘭表達式的方式給出。逆波蘭表達式又叫做后綴表達式。這個知識點在數(shù)據(jù)結(jié)構(gòu)和編譯原理這兩門課程中都有介紹，下面是一些例子：正常的表達式逆波蘭表達式a+b--->a,b,+a+(b-c)--->a,b,c,-,+a+(b-c)*d--->a,b,c,-,d,*,+a+d*(b-c)--->a,d,b,c,-,*,+a=1+3--->a=1,3+http=(smtp+http+telnet)/1024--->http=smtp,http,telnet,+,+,1024,/三地址碼的幾種表示（１）四元式（op，arg1，arg2，result）例：x:=yopz的四元式(op，y，z，x)例：a:=b*-c+b*-c(@，c，_，T1)(*，b，T1，T2)(@，c，_，T3)(*，b，T3，T4)(+，T2，T4，T5)(:=，T5，_，a)（２）三元式為了避免把臨時變量填入符號表，用中間代碼地址（指針）代表運算對象。（op，arg1，arg2）例：a:=b*-c+b*-c(0)(@，c，_)(1)(*，b，(0))(2)(@，c，_)(3)(*，b，(2))(4)(+，(1)，(3))(5)(:=，a，(4))例：x[i]:=y(0)(=[]，x，i)(1)(:=，y,（0）)用兩條三元式表示索引賦值。例：x:=y[i](0)([]=，y，i)