編譯原理復(fù)習(xí)重點(diǎn)

編譯原理重點(diǎn)題型填空：10X2'選擇：5X2'簡(jiǎn)答：4X5'計(jì)算：2X25'編譯程序：翻譯程序是指這樣的一個(gè)程序，它能夠把某一種語(yǔ)言程序轉(zhuǎn)換成另一種語(yǔ)言程序。而后者與前者在邏輯上是等價(jià)的。如果源語(yǔ)言是“高級(jí)程序”，而目標(biāo)語(yǔ)言是“低級(jí)程序”，這樣的翻譯程序就是編譯程序編譯過(guò)程，分別任務(wù)，處理方法詞法分析：輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)單詞；詞法分析階段所依循的是語(yǔ)言的詞法規(guī)則,而描述詞法規(guī)則的有效工具是正規(guī)式和有限自動(dòng)機(jī)語(yǔ)法分析：在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把單詞符號(hào)串分解成各類語(yǔ)法單位；通過(guò)語(yǔ)法分析,確定整個(gè)輸入串是否構(gòu)成語(yǔ)法上正確的“程序”.語(yǔ)法分析所依循的是語(yǔ)言的語(yǔ)法規(guī)則.語(yǔ)法規(guī)則通常用上下文無(wú)關(guān)文法描述.語(yǔ)義分析與中間代碼生成：對(duì)語(yǔ)法分析所識(shí)別出的各類語(yǔ)法范疇，分析其含義，并進(jìn)行初步翻譯，即中間代碼；這一階段所依循的是語(yǔ)言的語(yǔ)義規(guī)則,通常使用屬性文法,四元式描述語(yǔ)義規(guī)則.優(yōu)化：對(duì)前段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)出更為高效的目標(biāo)代碼；優(yōu)化的主要方面有:公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無(wú)用代碼等等.有時(shí),為了便于“并行運(yùn)算”,還可以對(duì)代碼進(jìn)行并行化處理.優(yōu)化所依循的原則是程序的等價(jià)變換原則目標(biāo)代碼生成：把中間代碼變換成特定機(jī)器上的低級(jí)語(yǔ)言代碼；這階段實(shí)現(xiàn)了最后的翻譯,它的工作有賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義.這階段工作非常復(fù)雜,涉及到硬件系統(tǒng)功能部件的運(yùn)用,機(jī)器指令的選擇,各種數(shù)據(jù)類型變量的存儲(chǔ)空間分配,以及寄存器和后援寄存器的調(diào)度等.如何產(chǎn)生出足以充分發(fā)揮硬件效率的目標(biāo)代碼是一件非常不容易的事情.編譯程序的結(jié)構(gòu)編譯前端和后端編譯程序可以被劃分為編譯前端和編譯后端.前端主要由與源語(yǔ)言有關(guān)但與目標(biāo)機(jī)無(wú)關(guān)的那些部分組成,通常包括:詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼產(chǎn)生,有的代碼優(yōu)化工作也可包括在前端.后端是由編譯程序中與目標(biāo)機(jī)有關(guān)的那些部分組成,如與目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等.通常,后端不依賴于源語(yǔ)言而僅僅依賴于中間語(yǔ)言上下文無(wú)關(guān)文法(概念，推導(dǎo)方法)文法：是描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則上下文無(wú)關(guān)文法：一種文法，他所定義的語(yǔ)法范疇完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境包括四個(gè)組成部分：一組終結(jié)符號(hào)，一組非終結(jié)符號(hào)，一個(gè)開始符號(hào)，一直產(chǎn)生式1，2，3判斷屬于哪種類型Gl： S-〉bAA-〉aA|a L(Gl)={ba"n|n〉=l}G2： S->ABA->Aa|a|￡ B-〉bB|b L(G2)={a"mb"n|m,n〉=1}G3： S-〉aSb|ab L(G3)={a"nb"n|n〉=1}語(yǔ)法分析樹(語(yǔ)法樹如何生成的，句柄，短語(yǔ))與二義性(概念，判斷方法)P30二義性：一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹形式語(yǔ)言鳥瞰語(yǔ)法分析器的輸出形式二元組(單詞種別，單詞符號(hào)的屬性值)正規(guī)式與正規(guī)集(概念，描述一個(gè)語(yǔ)言)￡和0都是工上的正規(guī)式，它們所表示的正規(guī)集分別為{￡}和0;任何ae￡，a是工上的一個(gè)正規(guī)式，它所表示的正規(guī)集為{a}；假定U和V都是工上的正規(guī)式,它們所表示的正規(guī)集分別為L(zhǎng)(U)和L(V)，那么，(U|V),(U.V)和(U)*也都是正規(guī)式，它們所表示的正規(guī)集分別為L(zhǎng)(U)UL(V)、L(U)L(V)(連接積)和(L(U))*(閉包)僅由有限次使用上述三步驟而得到的表達(dá)式才是工上的正規(guī)式。僅由這些正規(guī)式所表示的字集才是工上的正規(guī)集。(A|B|0|1)*多個(gè)A,B,0,1(結(jié)合題目)確定有限自動(dòng)機(jī)(概念，畫出DFA，化簡(jiǎn))非確定有限自動(dòng)機(jī)(概念)確定與非確定的主要區(qū)別是初態(tài)是否為一個(gè)集合對(duì)正規(guī)式確定化，最小化自上而下分析面臨的問(wèn)題文法的左遞歸問(wèn)題由于回溯，就碰到一大堆麻煩分析過(guò)程中，當(dāng)一個(gè)非終結(jié)符用某一候選匹配成功時(shí)，這種成功可能是暫時(shí)的。當(dāng)最終報(bào)告分析不成功時(shí)，我們難于知道輸入串中出錯(cuò)的確切位置由于帶回溯的自上而下分析實(shí)際上采用了一種窮盡一切可能的試探法，因此，效率很低，代價(jià)極高左遞歸的消除(直接，間接)P69E-〉E+T|T E-〉TE' E'-〉+TE'|￡LL(1)文法定義，如何對(duì)LL(1)文法分析定義：文法不含左遞歸。對(duì)于文法中的每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首兩兩不相交。對(duì)文法中的每A個(gè)終結(jié)符A,若它存在某個(gè)候選首符集包含￡，則First(A)GFollow(A)=0分析：對(duì)于一個(gè)LL(1)文法，可以A對(duì)其輸入串進(jìn)行有效的無(wú)回溯的自上而下分析。假設(shè)要用非終結(jié)符A進(jìn)行匹配，面臨的輸入符號(hào)為a,A的所有產(chǎn)生式為：A-〉a1|a2|?|an若aUFIRST(ai)，則指派ai去執(zhí)行匹配任務(wù)若a不屬于任何一個(gè)候選首符集，則：若￡屬于某個(gè)FIRST?i)且a^FOLLOW(A),則讓A與￡自動(dòng)匹配否則，a的出現(xiàn)是一種語(yǔ)法錯(cuò)誤遞歸下降分析程序構(gòu)造(寫出程序段)預(yù)測(cè)分析程序工作過(guò)程(三種動(dòng)作)若X=a=‘#'則宣布分析成功，停止分析過(guò)程若X=aM'#'則把X從STACK棧頂逐出，讓a指向下一個(gè)輸入符號(hào)。若X是一個(gè)非終結(jié)符，則查看分析表。若M[A,a]中存放著關(guān)于X的一個(gè)產(chǎn)生式，那么，首先把X逐出STACK棧頂，然后，把產(chǎn)生式的右部符號(hào)串按反序一一推進(jìn)STACK棧(若右部符號(hào)為￡，則意味不推進(jìn)什么東西進(jìn)棧)。把產(chǎn)生式的右部符號(hào)推進(jìn)棧的同時(shí)應(yīng)做這個(gè)產(chǎn)生式相應(yīng)的語(yǔ)義動(dòng)作。若M[A,a]中存放著“出錯(cuò)標(biāo)志”，則調(diào)用出錯(cuò)診斷程序ERROR。P774.4偽代碼預(yù)測(cè)分析表的構(gòu)造(first,follow,預(yù)測(cè)分析表)1)用xuvUV構(gòu)造FIRST(X):TN若XUV，則FIRST(X)={X}T若XUV，且有產(chǎn)生式X-a…，則把a(bǔ)加入到FIRST(X)中；N若X-S也是一條產(chǎn)生式，則把￡也加到FIRST(X)中若X-Y…是一個(gè)產(chǎn)生式且YUV，則把FIRST(Y)中的所有非￡-元素都加到FIRST(X)N中；若X-Y：Y2?Yk是一個(gè)產(chǎn)生式…，丫卜都是非終結(jié)符，且對(duì)于任何j(lWjWi-l),FIRST(Y)都含有￡,則把FIRST(Y)中的所有非￡-元素都加到FIRST(X)中；特別ji是，若所有的FIRST(Y.)均含有￡(j=1,2,?,k),則把￡加到FIRST(X)中2)對(duì)于文法G的每個(gè)非終結(jié)符A構(gòu)造FOLLOW(A)的方法：對(duì)于文法的開始符號(hào)5,置#于FOLLOW(S)中；若A-aBP即是一個(gè)產(chǎn)生式，則把FIRST?)\{￡}加至FOLLOW(B)中；若A-aB是一個(gè)產(chǎn)生式，或A-aBP且P=>￡,則把FOLLOW(A)加至FOLLOW(B)中P784.6規(guī)范規(guī)約簡(jiǎn)述：短語(yǔ)，直接短語(yǔ)，句柄，樹短語(yǔ)(結(jié)合題目)令G是一個(gè)文法，S是文法的開始符號(hào)，假定aP6是文法G的一個(gè)句型，如果有S=>aA6且A=>p則稱P是句型ap6相對(duì)于非終結(jié)符A的短語(yǔ)。特別是，如果有A=>p則稱P是句型ap6相對(duì)于規(guī)則A->p的直接短語(yǔ)，一個(gè)句型的最左直接短語(yǔ)稱為改句型的句柄。P86概念，規(guī)范規(guī)約，規(guī)范推導(dǎo)算符優(yōu)先文法及優(yōu)先表構(gòu)造(概念，算符優(yōu)先文法，關(guān)系判斷)算符文法：一個(gè)文法，如果它的任意一產(chǎn)生式的右部都不含兩個(gè)相繼(并列)的非終結(jié)符，即不含如下形式的產(chǎn)生式右部：?QR…，則我們稱該文法為算符文法。如果一個(gè)算符文法G中的任何終結(jié)符對(duì)(a,b)至多只滿足下述三關(guān)系之一:a=b,a〈b,a〉b則稱G是一個(gè)算符優(yōu)先文法。算符優(yōu)先分析算法FirstVt,lastVt,樹短語(yǔ)，最左樹短語(yǔ)FIRSTVT(P)：若有產(chǎn)生式P—a…或P—Qa?，則a^FIRSTVT(P)；若aUFIRSTVT(Q)，且有產(chǎn)生式P-Q?,則a^FIRSTVT(P)同樣我們用下面兩條規(guī)則來(lái)構(gòu)造LASTVT(P):若有產(chǎn)生式P—?a或P—?aQ，貝I」a^LASTVT(P)；若aeLASTVT(Q)，且有產(chǎn)生式P-?Q，則aeLASTVT(P)屬性文法(概念)P136-P139屬性通常分為兩類：綜合屬性和繼承屬性。中間語(yǔ)言(后綴式，圖表示法，三地址代碼：四元式)說(shuō)明語(yǔ)句(分析)賦值語(yǔ)句的翻譯初態(tài)與終態(tài)如何確定？與正規(guī)式等價(jià)的有限自動(dòng)機(jī)自上而下推測(cè)、自下而上規(guī)約

題目：36-7.G(S)Ot113151719Nt21416181ODt0|NDt0|NStO|AOAtAD|NP64-2.(a)a給狀態(tài)編號(hào)確定化:給狀態(tài)編號(hào)ab{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}傘傘傘最小化:{0,1},{2,3}{0,1}={1}{0,1}={2}{2,3}a={0,3}{2,3}={3}{0,1},a{2},{3} b(b)已經(jīng)確定化了,進(jìn)行最小化最小化：{{0,1},{2,3,4,5}}{0,1}={1}a{0，1}b = {2,4}{2,3,4,5}={1,3,0,5} {2,3,4,5}={2,3,4,5}a{2,4}={1,0}a{3,5}={3,5}ab{2,4}={3,5}b{3,5}={2,4}b{{0,1},{2,4},{3,5}}{0,1}={1}a{2,4}={1,0}a{3,5}={3,5}a{0,1}={2,4}b{2,4}={3,5}b{3,5}={2,4}bP81-1(1)按照T,S的順序消除左遞歸G'(S)STalAl(T)TTST'Tt,ST'Is遞歸子程序：procedureS;beginifsym=aorsym=thenabvanceelseifsym='('thenbeginadvance;T;ifsym=')'thenadvance;elseerror;endelseerrorend;procedureT;beginS;Tend;procedureT;beginifsym=','thenbeginadvance;S;TTendend;其中:sym:是輸入串指針I(yè)P所指的符號(hào)advance:是把IP調(diào)至下一個(gè)輸入符號(hào)error:是出錯(cuò)診察程序(2)FIRST(S)={a「，(}FIRST(T)={a「，(}FIRST(T)={,,￡}FOLLOW(S)={)，，，#}FOLLOW(T)={)}FOLLOW(TT)={)}預(yù)測(cè)分析表a()#SS-TaStaST(T)TTTSTTTTSTtTTSTTTTT'T￡TTT,STT是LL(1)文法P81-2文法：ETTETE'T+EI￡TTFTTTTTT|￡FTPFTFTT*FT|￡P(guān)T(E)1aIbI人(1)FIRST(E)={(,a,b「}FIRST(E')={+,￡}FIRST(T)={(,a,b「}FIRST(T')={(,a,b「，￡}FIRST(F)={(,a,b「}FIRST(F')={*,￡}FIRST(P)={(,a,b「}FOLLOW(E)={#,)}FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}F0LL0W(F)={(,a,b「，+,),#}F0LL0W(F')={(,a,b「，+,),#}F0LL0W(P)={*,(,a,b「，+,),#}(2)考慮下列產(chǎn)生式:E'T+EI￡T'tTI￡F'T*F'I￡P(guān)T(E)IAIalbFIRST(+E)GFIRST(￡)={+}G{￡}=QFIRST(+E)HFOLLOW(E')={+}G{#,)}=?FIRST(T)GFIRSTS)={(,a,b「}H{￡}=QFIRST(T)HFOLLOW(T')={(,a,b「}H{+,),#}=?FIRST(*F')HFIRST(s)={*}H{s}=QFIRST(*F')HFOLLOW(F')={*}H{(,a,b「，+,),#}=QFIRST((E))HFIRST(a)HFIRST(b)HFIRST「)=Q所以，該文法式LL(1)文法.(3)+*()ab#EETTE'ETTE'ETTE'ETTE'E'E'T+EE'T￡E'T￡TTTFT'TTFT'TTFT'TTFT'T'T'T￡TTTTT￡T'TTT'TTT'TTT'T￡FFtPF'FtPF'FtPF'FtPF'F'F'T￡F't*F'F'T￡F'T￡F'T￡F'T￡F'T￡F'T￡P(guān)PT(E)PTaPTbPTA(4)procedureE;beginifsym=(orsym=aorsym=borsym=thenbeginT;E'endelseerrorendprocedureE';beginifsym='+'thenbeginadvance;Eendelseifsym<>')'andsym<>'#'thenerrorendprocedureT;beginifsym=(orsym=aorsym=borsym=thenbeginF;T'endelseerrorendprocedureT';beginifsym=(orsym=aorsym=borsym=thenTelseifsym='*'thenerrorendprocedureF;beginifsym=(orsym=aorsym=borsym=thenbeginP;F'endelseerrorendprocedureF';beginifsym='*'thenbeginadvance;F'endendprocedureP;beginifsym=aorsym=borsym=thenadvanceelseifsym='('thenbeginadvance;E;ifsym=')'thenadvanceelseerrorendelseerrorend;P81-3(1)是，滿足三個(gè)條件。(2)不是，對(duì)于A不滿足條件3。不是，A、B均不滿足條件3。是，滿足三個(gè)條件。P133-1EnE+TnE+T*F短語(yǔ):E+T*F,T*F,直接短語(yǔ):T*F句柄:T*FP133-2文法：STalAl(T)TTT,SIS(1)最左推導(dǎo):Sn(T)n(T,S)n(S,S)n(a,S)n(a,(T))n(a,(T,S))n(a,(S,S))n(a,(a,S))n(a,(a,a))Sn(T,S)n(S,S)n((T),S)n((T,S),S)n((T,S,S),S)n((S,S,S),S)n(((T),S,S),S)n(((T,S),S,S)),S)n(((S,S),S,S),S)n(((a,S),S,S),S)n(((a,a),S,S),S)n(((a,a),A,S),S)n(((a,a),A,(T)),S)n(((a,a),A,(S)),S)n(((a,a),A,(a)),S)n(((a,a),A,(a)),a)最右推導(dǎo):Sn(T)n(T,S)n(T,(T))n(T,(T,S))n(T,(T,a))n(T,(S,a))n(T,(a,a))n(S,(a,a))n(a,(a,a))Sn(T,S)n(T,a)n(S,a)n((T),a)n((T,S),a)n((T,(T)),a)n((T,(S)),a)n((T,(a)),a)n((T,S,(a)),a)n((T,A,(a)),a)n((S,A,(a)),a)n(((T),A,(a)),a)n(((T,S),A,(a)),a)n(((T,a),A,(a)),a)n(((S,a),A,(a)),a)n(((a,a),A,(a)),a)(2)((Q,a)「，(a)),a)(((S,a),",(a)),a)(((T,a)「，(a)),a)(((U)「，(a)),a)((!Tl,",(a)),a)((S,",(a)),a)((T,",(a)),a)((T,S,(a)),a)((T,(a)),a)((T,(S)),a)((T,(T)),a)((T,S),a)(IH,a)(S,a)(T,S)S0#(((a,a),,(a)),a)#1#(((a,a),",(a)),a)#2#(((a,a),",(a)),a)#3#(((a,a),",(a)),a)#4#(((a,a),",(a)),a)#5 #(((S,a),",(a)),a)#6 #(((T,a),",(a)),a)#7 #(((T,a),",(a)),a)#8#(((T,a),",(a)),a)#9 #(((T,S),",(a)),a)#10#(((T),",(a)),a)#11#(((T)",(a)),a)#12#((S",(a)),a)#13#((T",(a)),a)#14#((T,",(a)),a)#15#((T「,(a)),a)#16#((T,S,(a)),a)#17#((T,(a)),a)#18#((T,(a)),a)#19#((T,(a)),a)#20#((T,(a)),a)#21#((T,(S)),a)#22#((T,(T)),a)#23#((T,(T)),a)#24#((T,S),a)#25#((T),a)#26#((T),a)#27#(S,a)#28#(T,a)#29#(T,a)#30#(T,a)#31#(T,S)#32#(T)#33#(T)#34#S#“移進(jìn)-歸約”過(guò)程：步驟棧輸入串預(yù)備進(jìn)進(jìn)進(jìn)進(jìn)歸歸進(jìn)進(jìn)歸歸進(jìn)歸歸進(jìn)進(jìn)歸歸進(jìn)進(jìn)進(jìn)歸歸進(jìn)歸歸進(jìn)歸歸進(jìn)進(jìn)歸歸進(jìn)歸動(dòng)作

P133-3(1)g輸入字符串(a,(a,a))#a,(a,a))#,(a,a))#,(a,a))#動(dòng)作預(yù)備FIRSTVT(S)={a「，(}FIRSTVT(T)={,,a「，(}LASTVT(S)={a「，)}LASTVT(T)={,,a「，)}g輸入字符串(a,(a,a))#a,(a,a))#,(a,a))#,(a,a))#動(dòng)作預(yù)備a()a>>>>(<<<=<)>><<<>>G6是算符文法，并且是算符優(yōu)先文法（3）優(yōu)先函數(shù)a()f44244g55523(4)棧##(#(a#(t#(t,(a,a))##(t,（a,a））##(t,（a,a））##(t,（t,a））##(t,(t,a））##(t,(t,a））##(t,(t,s））##(t,（t））##(t,（t））##(t,s）##（t）##（t）##s#success解釋程序：它已該語(yǔ)言寫的源程序作為輸入。但不產(chǎn)生目標(biāo)程序，而是邊解釋邊執(zhí)行原程序本身。診斷編譯程序：專門用于幫助程序開發(fā)和調(diào)試的編譯程序優(yōu)化編譯程序：著重于提高目標(biāo)代碼效率的編譯程序目標(biāo)機(jī)：運(yùn)行編譯程序的計(jì)算機(jī)叫宿主機(jī)，運(yùn)行編譯程序產(chǎn)生目標(biāo)代碼的計(jì)算機(jī)成為目標(biāo)機(jī)交叉編譯程序：一個(gè)編譯程序產(chǎn)生不同于宿主機(jī)的機(jī)器代碼可變目標(biāo)編譯程序：如果不需重寫編譯程序中與機(jī)器無(wú)關(guān)的部分就能改變目標(biāo)機(jī)，則稱該編譯程序?yàn)榭勺兡繕?biāo)編譯程序上下文無(wú)關(guān)文法的限制：（1）文法中不含任何下面形式的產(chǎn)生式P-P（2）每個(gè)非終結(jié)符P必須都有用處S=》aPp語(yǔ)法分析器的基本任務(wù)：在詞法分析識(shí)別出的單詞符號(hào)串的記住上，分析并判斷程序的語(yǔ)法結(jié)構(gòu)是否符合語(yǔ)法規(guī)