編譯原理資料

1、變量及其屬性變量是對(duì)一個(gè)(或若干個(gè))存儲(chǔ)單元的抽象，賦值語(yǔ)句則是修改存儲(chǔ)單元內(nèi)容的抽象。變量除名字外,具有四個(gè)屬性:作用域、生存期、值和類(lèi)型1.變量的作用域：變量的作用域是指可以訪問(wèn)該變量的程序范圍。①靜態(tài)作用域綁定：按照程序的語(yǔ)法結(jié)構(gòu)定義變量的作用域。②動(dòng)態(tài)作用域綁定：按照程序的執(zhí)行動(dòng)態(tài)地定義變量的作用域。2.變量的生存期：一個(gè)存儲(chǔ)區(qū)綁定于一個(gè)變量的時(shí)間區(qū)間,稱(chēng)為變量的生存期。數(shù)據(jù)對(duì)象：存儲(chǔ)區(qū)和它保存的值分配：變量獲得存儲(chǔ)區(qū)的活動(dòng)長(zhǎng)度：變量所分配的存儲(chǔ)單元的個(gè)數(shù)3.變量的值——存儲(chǔ)區(qū)單元的內(nèi)容匿名變量的訪問(wèn)通過(guò)指針實(shí)現(xiàn)變量與它的值的綁定是動(dòng)態(tài)的符號(hào)常數(shù)的值不能修改變量的初始化不初始化則出錯(cuò)；隨機(jī)；缺省值0。4.變量的類(lèi)型①類(lèi)型：變量的類(lèi)型可以看成與變量相關(guān)聯(lián)的值的類(lèi),以及對(duì)這些值進(jìn)行的操作的說(shuō)明。類(lèi)型可用來(lái)解釋變量綁定的存儲(chǔ)區(qū)的內(nèi)容(二進(jìn)制位串)的意義；語(yǔ)言定義時(shí),類(lèi)型名通常綁定于某一個(gè)值類(lèi)和某一組操作；語(yǔ)言實(shí)現(xiàn)時(shí),值和操作綁定于某種機(jī)器二進(jìn)制表示。②靜態(tài)綁定：通過(guò)說(shuō)明語(yǔ)句完成如：Pascal、Fortran③動(dòng)態(tài)綁定：執(zhí)行時(shí)隱式說(shuō)明，且動(dòng)態(tài)變化如：APLA?5整型?A標(biāo)號(hào)、轉(zhuǎn)到AA?12510一維數(shù)組 (A?0)A[2:3]?0二維數(shù)組 A?B+C2、虛擬機(jī)的概念：虛擬機(jī)是由軟件實(shí)現(xiàn)的機(jī)器3、程序單元及單元實(shí)例 1.程序單元:程序執(zhí)行過(guò)程中的獨(dú)立調(diào)用單元。如子程序,分程序,過(guò)程等。 2.單元表示 編譯時(shí)，一個(gè)單元的源程序。 運(yùn)行時(shí)，單元表示由一個(gè)代碼段和一個(gè)活動(dòng)記錄組成，稱(chēng)為單元實(shí)例。 3.活動(dòng)記錄:執(zhí)行單元所需要的信息,以及該單元的局部變量所綁定的數(shù)據(jù)對(duì)象的存儲(chǔ)區(qū)。 4.非局部變量:一個(gè)程序單元可以引用未被本單元說(shuō)明而被其它單元說(shuō)明的變量。 5.引用環(huán)境:局部變量+非局部變量。 6.別名:同一單元的引用環(huán)境中有兩個(gè)變量綁定于同一數(shù)據(jù)對(duì)象，稱(chēng)這些變量具有別名。 7.副作用的產(chǎn)生:對(duì)綁定于一個(gè)非局部變量的對(duì)象進(jìn)行修改。 8.程序單元可以遞歸激活,從而一個(gè)單元可以有很多個(gè)實(shí)例,但代碼段相同。不同的僅僅是活動(dòng)記錄。 9.靜態(tài)分配和動(dòng)態(tài)分配FortranPascal或C4、數(shù)據(jù)類(lèi)型的作用實(shí)現(xiàn)了數(shù)據(jù)抽象使程序員從機(jī)器的具體特征中解脫出來(lái)提高了編程效率5、數(shù)據(jù)聚合的幾種方式（6種）1.笛卡爾積N個(gè)集合A1,A2,…,An的笛卡爾積表示為A1′A2′…′An，它是一個(gè)集合,其元素為(a1,a2,…,an),ai?任意正多邊形可表示為integer′real2.有限映像①定義：從定義域類(lèi)型DT的值的有限集合，到值域類(lèi)型RT的值的有限集合的函數(shù)稱(chēng)為有限映像。vara:array[1..50]ofchar;表示：整數(shù)1至50到字符集的有限映像②值域?qū)ο笸ㄟ^(guò)下標(biāo)選取。③下標(biāo)越界會(huì)出錯(cuò)，動(dòng)態(tài)檢查④下標(biāo)可用來(lái)選取值域的多個(gè)元素⑤SNOBOL4的ARRAY構(gòu)造符并不要求值域集的所有元素是同一類(lèi)型的⑥D(zhuǎn)T到相應(yīng)值的特定子集的綁定策略：編譯時(shí)綁定(靜態(tài)數(shù)組)對(duì)象建立時(shí)綁定(執(zhí)行到分程序時(shí),動(dòng)態(tài)數(shù)組)對(duì)象處理時(shí)綁定(對(duì)APL，子集范圍可變)3.序列①序列由任意多個(gè)數(shù)據(jù)項(xiàng)組成,這些數(shù)據(jù)項(xiàng)稱(chēng)為該序列的成分,且類(lèi)型相同②串是序列③順序文件的思想也是來(lái)自序列的概念,只能順序讀寫(xiě)4.遞歸若數(shù)據(jù)類(lèi)型T包含屬于同一類(lèi)型T的成分，那么類(lèi)型T稱(chēng)為遞歸類(lèi)型。①允許在類(lèi)型定義中使用被定義類(lèi)型的名字②指針是建立遞歸數(shù)據(jù)對(duì)象的重要手段5.判定或判定或是一個(gè)選擇對(duì)象結(jié)構(gòu)的構(gòu)造機(jī)制,規(guī)定在兩個(gè)不同選擇對(duì)象之間作出適當(dāng)?shù)倪x擇。每一選擇對(duì)象結(jié)構(gòu)稱(chēng)為變體。例如：PASCAL的變體記錄;C的聯(lián)合。6.冪集類(lèi)型T的元素所有子集的集合，稱(chēng)為冪集,記為Powerset(T),T稱(chēng)為基類(lèi)型。應(yīng)用：每次的操作對(duì)象僅僅是某個(gè)集合的子集。6、類(lèi)型檢查及其分類(lèi) 1.類(lèi)型檢查：對(duì)數(shù)據(jù)對(duì)象的類(lèi)型和使用的操作是否匹配的一致性檢查稱(chēng)為類(lèi)型檢查 2.靜態(tài)檢查和動(dòng)態(tài)檢查 ①靜態(tài)檢查使程序更正確更有效②動(dòng)態(tài)檢查使編程方便,但影響了可讀性,且降低了執(zhí)行效率 3.強(qiáng)類(lèi)型語(yǔ)言若一個(gè)語(yǔ)言允許所有的類(lèi)型靜態(tài)檢查4.Pascal是非強(qiáng)類(lèi)型語(yǔ)言 ①編譯時(shí),不能確定一個(gè)過(guò)程中的過(guò)程參數(shù)和子程序參數(shù)類(lèi)型 ②Pascal的子界不能靜態(tài)檢查 如:a:=b+c;且a、b、c均屬于子界類(lèi)型1..10 ③變體記錄的標(biāo)識(shí)符可以在運(yùn)行時(shí)改變 ④Pascal沒(méi)有嚴(yán)格規(guī)定類(lèi)型的一致性規(guī)則7、何謂類(lèi)型等價(jià)：T1和T2是相容的：T1可賦給T2，T1可對(duì)應(yīng)T2的形參；反之亦然。 1.名字等價(jià)：兩個(gè)變量的類(lèi)型名相同。 2.結(jié)構(gòu)等價(jià)：兩個(gè)變量的類(lèi)型具有相同的結(jié)構(gòu)。驗(yàn)證法：用用戶定義類(lèi)型的定義來(lái)代替用戶定義名，重復(fù)這一過(guò)程，直到?jīng)]有用戶定義類(lèi)型名為止。 3.兩種相容性實(shí)現(xiàn)時(shí)的比較①名字等價(jià)的實(shí)現(xiàn)比較簡(jiǎn)單②結(jié)構(gòu)等價(jià)的實(shí)現(xiàn)需要的模式匹配過(guò)程可能十分復(fù)雜8、語(yǔ)句級(jí)控制結(jié)構(gòu)控制結(jié)構(gòu):程序員用來(lái)規(guī)定程序各個(gè)成分的執(zhí)行流程的控制部分。語(yǔ)句級(jí)控制結(jié)構(gòu):語(yǔ)言用來(lái)構(gòu)造各種語(yǔ)句執(zhí)行順序的機(jī)制。傳統(tǒng)語(yǔ)言的三種語(yǔ)句級(jí)控制結(jié)構(gòu):順序、選擇、重復(fù)。9、單元級(jí)控制結(jié)構(gòu)單元級(jí)控制結(jié)構(gòu):規(guī)定程序單元之間控制流程的機(jī)制四種單元級(jí)控制結(jié)構(gòu):顯式調(diào)用,異常處理,協(xié)同程序,并發(fā)單元10、副作用副作用?對(duì)非局部環(huán)境的修改①副作用降低了程序的可讀性②副作用限制了數(shù)學(xué)運(yùn)算律的使用。如:w:=x+f(x,y)+z③副作用影響目標(biāo)代碼的優(yōu)化。如:u:=x+z+f(x,y)+f(x,y)+x+z11、別名別名?在單元激活期間,兩個(gè)變量表示(共享)同一數(shù)據(jù)對(duì)象①FORTRAN的EQUIVALENCE語(yǔ)句②Pascal的變參使得形參和實(shí)參共享同一數(shù)據(jù)對(duì)象③變參和全局變量表示同一數(shù)據(jù)對(duì)象時(shí)，也會(huì)引起別名④別名也影響編譯器生成優(yōu)化的代碼a:=(x-y*z)+w/*若a與x、y或z中任一個(gè)b:=(x-y*z)+u是別名*/⑤別名的消除.廢除可能引起別名的結(jié)構(gòu).限制使用指針、變參、全局變量、數(shù)組等12、語(yǔ)言的定義語(yǔ)言＝語(yǔ)法＋語(yǔ)義語(yǔ)法:用以構(gòu)造程序及其成分的一組規(guī)則的集合語(yǔ)義:用以規(guī)定語(yǔ)法正確的程序或其成分的含義的一組規(guī)則的集合13、文法的定義文法是描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則,必須準(zhǔn)確,易于理解,且描述能力強(qiáng)文法的形式定義G=(VT,VN,S,P)例G0=(VT,VN,S,P):E→E+T|TT→T*F|FF→(E)|i顯然VT={+,*,(,),i}VN={E,T,F}S=EP為上述產(chǎn)生式的集合14、文法的分類(lèi)①0型文法:產(chǎn)生式形如a→b②1型文法:│α│<=│β│（S→e例外）或產(chǎn)生式形如αAβ→αwβ，w?V+(上下文有關(guān)文法)③2型文法:產(chǎn)生式形如A→α(上下文無(wú)關(guān)文法)④3型文法:產(chǎn)生式形如A→α或A→αB(正則文法,右線性文法)?aVT15、抽象機(jī)的結(jié)構(gòu)16、推導(dǎo)、句型、句子、語(yǔ)言 1.推導(dǎo)與歸約①直接推導(dǎo):αβnTαnd即由產(chǎn)生式右邊替換產(chǎn)生式左邊②推導(dǎo):α1Tαn、α1Tαn ③歸約:推導(dǎo)的逆過(guò)程 舉例:已知G(E)E→E+E│E*E│(E)│ii+i*i的推導(dǎo)過(guò)程ETE+ETE+E*ETE+E*iTE+i*iTi+i*iETE+ETi+ETi+E*ETi+i*ETi+i*iETE*ETE*iTE+E*iTE+i*iTi+i*i設(shè)文法G=(VT,VN,S,P),若STα,α?V*,則稱(chēng)α為文法G的一個(gè)句型。 若上述α?VT*，則稱(chēng)α是一個(gè)句子，即只含終結(jié)符的句型是一個(gè)句子 文法G=(VT,VN,S,P)的句子的全體,稱(chēng)為由文法G產(chǎn)生的語(yǔ)言,記為L(zhǎng)(G),即L(G)={α│STαùα?VT}17、語(yǔ)法樹(shù)語(yǔ)法樹(shù)（推導(dǎo)樹(shù)）——以圖的方式表示推導(dǎo)過(guò)程①推導(dǎo)樹(shù)是一棵有序的標(biāo)記樹(shù)每個(gè)結(jié)點(diǎn)的標(biāo)記是文法G的非終結(jié)符或終結(jié)符；標(biāo)記為A的內(nèi)部結(jié)點(diǎn)從左到右有子結(jié)點(diǎn)X1，X2，…,Xn,則A→X1…Xn是一個(gè)產(chǎn)生式;如果有結(jié)點(diǎn)標(biāo)記為e，則它必是葉結(jié)點(diǎn)，且它是該父結(jié)點(diǎn)的唯一子結(jié)點(diǎn)。 G(E)E→E+E│E*E│(E)│i ②推導(dǎo)樹(shù)的構(gòu)造：例（i+i*i）EE（E）EE*EE+iiiEE（E）EE+EEiii*③推導(dǎo)樹(shù)的邊緣：一棵推導(dǎo)樹(shù)所有葉結(jié)點(diǎn)的從左到右的連接。④文法的二義性：一個(gè)句子有兩棵不同的推導(dǎo)樹(shù)。④由推導(dǎo)樹(shù)確定短語(yǔ)18、編譯等概念翻譯程序：它能夠把某一種語(yǔ)言程序（稱(chēng)為源語(yǔ)言程序）轉(zhuǎn)換成另一種語(yǔ)言程序（稱(chēng)為目標(biāo)語(yǔ)言程序），而后者與前者在邏輯上是等價(jià)的。如果源語(yǔ)言是諸如Pascal、C或Java這樣的“高級(jí)語(yǔ)言”，而目標(biāo)語(yǔ)言是諸如匯編語(yǔ)言或機(jī)器語(yǔ)言之類(lèi)的“低級(jí)語(yǔ)言”，這樣的一個(gè)翻譯程序就稱(chēng)為編譯程序解釋程序：它以該語(yǔ)言寫(xiě)的源程序作為輸入，但不產(chǎn)生目標(biāo)程序，而是邊解釋邊執(zhí)行源程序本身。19、詞法分析器的功能掃描源程序的字符串,按照詞法規(guī)則,識(shí)別出單詞符號(hào)作為輸出;對(duì)識(shí)別過(guò)程中發(fā)現(xiàn)的詞法錯(cuò)誤,則輸出有關(guān)的錯(cuò)誤信息。20、狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖的定義有限的有向圖有向邊上標(biāo)記字符唯一初態(tài)若干終態(tài)（至少一個(gè)）21、左遞歸的消除(1)直接左遞歸的消除P→Pα│β改寫(xiě)為:P→bP＇P＇→αP＇│ε一般地A→Aa1|Aa2|…|Aam|b1|b2|…|bn（ai1ε，bj不以A開(kāi)頭）改寫(xiě)為:A→b1P’│b2P’│...│bnP’P’→a1P’│a2P’│...│amP’│ε(2)間接左遞歸的消除PTPα(a)將文法G的所有非終結(jié)符按任一給定的順序排列,設(shè)為A1,A2,…An;(b)消除可能的左遞歸;fori:=1tondobeginforj:=1toi-1do把一個(gè)形如Ai?Aja的產(chǎn)生式改寫(xiě)為Aid?1a|d2a|…|dka其中Ajd?1|d2|…|dk是Aj的所有產(chǎn)生式;消除Ai產(chǎn)生式的直接左遞歸end(c)化簡(jiǎn)以S→Qc│cQ→Rb│bR→Sa│a為例,按S,Q,R排列,或R,Q,S排列按S、Q、R排列,代入后S→Qc│cQ→Rb│bR→Rbca│bca│ca│a消除R中的直接左遞歸R→bcaR’│caR’│aR’R’→bcaR’│e文法產(chǎn)生的語(yǔ)言:(bca|ca|a)(bca)*bc|bc|c按R、Q、S排列,代入后R→Sa│aQ→Sab│ab│bS→Sabc│abc│bc│c消除S中的直接左遞歸S→abcS’│bcS’│cS’S’→abcS’│e文法產(chǎn)生的語(yǔ)言:(abc|bc|c)(abc)*22、FIRST集、FOLLOW集，預(yù)測(cè)分析表的構(gòu)造1．FIRST集定義:對(duì)α?(VTèVN)*,有FIRST（α）＝{a|αTa...,a?VT}若αTε,則ε?FIRST(α)α=X…X?VT,則FIRST(X)={X};X?VN,分三種情形:X?a…X?Y…X?Y1Y2…Yk練習(xí)：X?Y1Y2AY1?y1│eY2?y2│eA?aFIRST(Y1)={y1,e}FIRST(Y2)={y2,e}FIRST(A)={a}FIRST(X)={y1,y2,a}2.FOLLOW集(1)定義:對(duì)A?VN,有FOLLOW(A)={a│ST...Aa...,a?VT}若ST...A,則#?FOLLOW(A),其中S為開(kāi)始符號(hào)(2)求法#?FOLLOW(S)A→αBβ:將FIRST(b)-{e}加入FOLLOW(B)A→αB或者A→αBβ且βTε:將FOLLOW(A)加入FOLLOW(B)注意:求FOLLOW(B)實(shí)際上是考察B在產(chǎn)生式右端的每一次出現(xiàn)FIRSTFOLLOWE(i)#E’+e)#T(i+)#T’*e+)#F(i*+)#例:G(E)E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│i23、短語(yǔ)、直接短語(yǔ)、句柄短語(yǔ):設(shè)αβd是上下文無(wú)關(guān)文法G的一個(gè)句型,如果有STαAd,并且ATβ,則稱(chēng)β是句型αβd關(guān)于非終結(jié)符A的一個(gè)短語(yǔ),或稱(chēng)β是句型αβd的一個(gè)短語(yǔ) 直接短語(yǔ)（簡(jiǎn)單短語(yǔ)）：ATβ 句柄：一個(gè)句型的最左直接短語(yǔ) 例:G(E)E→E+T|T T→T*F|F F→(E)|i 求E+T*F的短語(yǔ)、直接短語(yǔ)、句柄 ETE+TTE+T*F 因?yàn)镋TE+T且TTT*F，所以T*F是關(guān)于T的短語(yǔ) 因?yàn)镋=E且ETT+T*F,所以T+T*F是關(guān)于E的短語(yǔ)直接短語(yǔ):T*F句柄:T*F 例:G(E)E→E+T|T T→T*F|F F→(E)|i 求T*F+i的短語(yǔ)、直接短語(yǔ)、句柄 ETE+TTT+TTT*F+TTT*F+FTT*F+i 因?yàn)镋=E且ETT*F+i，所以T*F+i是關(guān)于E的短語(yǔ) 因?yàn)镋TT＋T且TTT*F，所以T*F是關(guān)于T的短語(yǔ)、直接短語(yǔ)、句柄 為ETE＋T且ETT*F，所以T*F是關(guān)于E的短語(yǔ) 因?yàn)镋TT*F+T且TTi，所以i是關(guān)于T的短語(yǔ) 為ETT*F+F且FTi，所以i是關(guān)于F的短語(yǔ)、直接短語(yǔ) 短語(yǔ):有終結(jié)符的短語(yǔ)，并且它的真子傳不具有這個(gè)特性 最右推導(dǎo)（規(guī)范推導(dǎo)） 最左推導(dǎo)24、FIRSTVT集、LASTVT集，優(yōu)先關(guān)系表的構(gòu)造(1)FIRSTVT集FIRSTVT(P)={a|PTa…,或PTQa…,a?VT,Q?VN}若P?a…或P?Qa…,則a?FIRSTVT(P);若P?Q…,則FIRSTVT(Q)íFIRSTVT(P);直至FIRSTVT(P)不再增大。(2)LASTVT集LASTVT(P)={a|PT...a,或PT…aQ,a?VT,Q?VN}若P?...a或P?…aQ,則a?LASTVT(P);若P?...Q,則LASTVT(Q)íLASTVT(P);FIRSTVTLASTVTE(i+*)i+*T(i*)i*F(i)i直至LASTVT(P)不再增大例G(E)E→E+T│TT→T*F│FF→(E)│i（3）求FIRSTVT集的矩陣規(guī)則若P?a…或P?Qa…,則M[P,a]:=1;若P?Q…,則對(duì)所有的M[Q,a]=1置M[P,a]:=1;重復(fù)上述兩步，直到M矩陣不再變化。（4）求LASTVT集的矩陣規(guī)則若P?…a或P?…aQ,則M[P,a]:=1;若P?…Q,則對(duì)所有的M[Q,a]=1置M[P,a]:=1;重復(fù)上述兩步，直到M矩陣不再變化FIRSTVT+*i()E1111T111F11LASTVT+*I()E1111T111F11例G(E)E→E+T│TT→T*F│FF→(E)│i(5)構(gòu)造優(yōu)先關(guān)系表的算法FOR每條產(chǎn)生式P?X1X2…XnDOFORi:=1TOn-1DOBEGINIFXi和Xi+1均為終結(jié)符THENXi=Xi+1;IFi<=n-2且Xi和Xi+2均為終結(jié)符但Xi+1?VNTHENXi=Xi+2;IFXi?VT,Xi+1THEN"a?FIRSTVT(Xi+1)Xi<a;IFXi?VN,Xi+1?VTTHEN"a?LASTVT(Xi)a>Xi+1END;FIRSTVTLASTVTE(i+*)i+*T(i*)i*F(i)i例G(E)E→E+T│TT→T*F│FF→(E)│i+*i()#+><<<>>*>><<>>i>>>>(<<<<=)>>>>#<<<<=考察E→E+T中的E和+、+和T考察T→T*F中的T和*、*和F考察F→(E)中的(和E、(和)、E和)算符優(yōu)先關(guān)系表25、何謂語(yǔ)法制導(dǎo)翻譯為每個(gè)產(chǎn)生式配上一個(gè)語(yǔ)義子程序,在語(yǔ)法分析過(guò)程中,當(dāng)用一個(gè)產(chǎn)生式進(jìn)行匹配或歸約時(shí),就調(diào)用相應(yīng)的語(yǔ)義程序。上述語(yǔ)義子程序既可能包含了語(yǔ)義檢查,也可能包含了語(yǔ)義處理,其核心是為了生成相應(yīng)的中間代碼。26、某些語(yǔ)句翻譯后的中間代碼序列27、數(shù)據(jù)參數(shù)傳遞的幾種方法 1.引用調(diào)用（傳地址） 將實(shí)參的地址傳遞給相應(yīng)的形參 在單元中對(duì)形參的引用