編譯原理及其

1、編譯原理及其實(shí)現(xiàn)技術(shù) 授課教師：張紅1參考書(shū)目1 Alfred V.Aho Ravi Sethi Jeffrey D.Ullman Compilers: Principles,Techniques,and Tools 人民郵電出版社。2 Kenneth C. Louden 著 馮博琴 馮嵐等譯 Compiler Construction Principles and Practice 機(jī)械工業(yè)出版社。3 金成植 著 ,編譯原理及實(shí)現(xiàn)，高等教育出版社。4 呂映芝 ，編譯原理，清華大學(xué)教育出版社。2第一章 編譯引論主要內(nèi)容：幾個(gè)基本概念:翻譯程序匯編程序編譯程序源程序目標(biāo)程序編譯器的組成結(jié)構(gòu)、各部

2、分之間的邏輯關(guān)系和主要功能；編譯程序的實(shí)現(xiàn)途徑;與編譯程序相關(guān)的其他程序;編輯器預(yù)處理器連接程序裝配程序調(diào)試程序31.1 程序設(shè)計(jì)語(yǔ)言和編譯程序從第一臺(tái)計(jì)算機(jī)問(wèn)世至今，半個(gè)多世紀(jì)以來(lái)，程序設(shè)計(jì)語(yǔ)言經(jīng)歷了由低級(jí)向高級(jí)的發(fā)展，從最初的機(jī)器語(yǔ)言、匯編語(yǔ)言，發(fā)展到較高級(jí)程序設(shè)計(jì)語(yǔ)言直至今天的第四代、第五代高級(jí)語(yǔ)言。一、程序設(shè)計(jì)語(yǔ)言（一）低級(jí)語(yǔ)言機(jī)器語(yǔ)言由能被計(jì)算機(jī)的硬件系統(tǒng)直接執(zhí)行的機(jī)器指令組成，每條機(jī)器指令是一串二進(jìn)制代碼，用機(jī)器語(yǔ)言編寫(xiě)出來(lái)的程序是一串二進(jìn)制代碼序列。例： x + 15 xy Y= x - 15 否則4用Pentium機(jī)器語(yǔ)言編寫(xiě)如下程序片段：1010 1001 0001 0110

3、 0000 0001 0011 1100 0001 1000 0000 0001 0111 1100 0000 01010010 1101 0001 0101 0000 0000 1110 1010 0000 00110000 0101 0001 0101 0000 0000 0101 0011 0001 1000 0000 0001 .0000 0000 0000 0000 0000 0000 0000 0000 機(jī)器語(yǔ)言的特點(diǎn)：優(yōu)點(diǎn)：執(zhí)行速度快；缺點(diǎn)：難學(xué)、難記憶、難理解;機(jī)器語(yǔ)言程序依賴(lài)于具體的機(jī)器, 不具備移植性；5匯編語(yǔ)言將硬件指令用一些助記符表示。如ADD表示加法操作，SUB表示減

4、法操作等等 。用Pentium匯編語(yǔ)言編程示例： MOV AX , X CMP AX , Y JLS1 SUB AX ,15 JMP S2 S1: ADD AX ,15 S2: MOV Y ,AX . XDWYDW6匯編語(yǔ)言的優(yōu)點(diǎn)：比機(jī)器語(yǔ)言較易學(xué)、易記憶及易理解;匯編語(yǔ)言的缺點(diǎn)：匯編語(yǔ)言程序依賴(lài)于具體的機(jī)器, 不具備移植性； 7（二）高級(jí)語(yǔ)言高級(jí)語(yǔ)言：把便于理解的自然語(yǔ)言和數(shù)學(xué)語(yǔ)言結(jié)合在一起而形成的程序設(shè)計(jì)語(yǔ)言。高級(jí)語(yǔ)言編程示例： if (XY ) then Y:=X + 15 else Y:=X - 15;高級(jí)語(yǔ)言的優(yōu)點(diǎn)：比匯編語(yǔ)言更容易學(xué)，以人為本，面向自然表達(dá)，易學(xué)、易用、易理解、易修

5、改;高級(jí)語(yǔ)言程序不依賴(lài)于具體的機(jī)器, 具備移植性。8高級(jí)程序設(shè)計(jì)語(yǔ)言分類(lèi)：1、程序設(shè)計(jì)語(yǔ)言按功能分類(lèi)：科學(xué)計(jì)算用語(yǔ)言商用語(yǔ)言表處理語(yǔ)言圖形語(yǔ)言公式處理語(yǔ)言串處理語(yǔ)言多用途語(yǔ)言 2、按處理問(wèn)題模式分類(lèi)：過(guò)程式語(yǔ)言函數(shù)式語(yǔ)言邏輯式語(yǔ)言對(duì)象式語(yǔ) 3、按執(zhí)行模式分類(lèi)：順序語(yǔ)言并行語(yǔ)言9二、高級(jí)語(yǔ)言和匯編語(yǔ)言的執(zhí)行翻譯程序（Translator） ：它把用匯編語(yǔ)言或高級(jí)語(yǔ)言編寫(xiě)的程序轉(zhuǎn)換成等價(jià)的機(jī)器語(yǔ)言程序。 匯編程序(Assembler) ：匯編語(yǔ)言的翻譯程序稱(chēng)為匯編程序(Assembler) 編譯程序(Compiler) ：高級(jí)語(yǔ)言的翻譯程序稱(chēng)為編譯程序,也稱(chēng)為編譯器。10源程序（Source pr

6、ogram）：編譯程序的輸入對(duì)象, 它是高級(jí)語(yǔ)言編寫(xiě)的程序；目標(biāo)程序（Object program）: 編譯程序的輸出對(duì)象稱(chēng)為目標(biāo)程序。目標(biāo)程序可以是機(jī)器語(yǔ)言程序、匯編語(yǔ)言程序或用戶(hù)自定義某種中間語(yǔ)言程序。11三、高級(jí)語(yǔ)言的執(zhí)行方式1. 編譯方式編譯階段：將源程序改造成另一種在邏輯上等價(jià)的目標(biāo)語(yǔ)言程序；運(yùn)行階段：在運(yùn)行子程序的支持下執(zhí)行目標(biāo)程序。運(yùn)行子程序是為了支持目標(biāo)程序的運(yùn)行而開(kāi)發(fā)的程序，如系統(tǒng)提供的標(biāo)準(zhǔn)庫(kù)函數(shù)和目標(biāo)程序所調(diào)用的其它子程序。 目標(biāo)程序程序的輸入數(shù)據(jù)運(yùn)行結(jié)果高級(jí)語(yǔ)言 源程序 編譯程序 （器）122. 解釋方式接受某程序語(yǔ)言編寫(xiě)的源程序，按源程序語(yǔ)句運(yùn)行時(shí)的動(dòng)態(tài)結(jié)構(gòu)，直接逐句地

7、分析、翻譯并執(zhí)行。解釋程序相當(dāng)于源程序的抽象執(zhí)行機(jī)，是語(yǔ)言的實(shí)現(xiàn)系統(tǒng)。 運(yùn)行結(jié)果 解釋程序 （器）程序的輸入數(shù)據(jù)高級(jí)語(yǔ)言源程序13解釋器和編譯器的比較解釋器是執(zhí)行系統(tǒng)，編譯器是轉(zhuǎn)換系統(tǒng)。 基于解釋執(zhí)行的程序可以動(dòng)態(tài)修改自身， 而基于編譯執(zhí)行的程序不易勝任，因其需要?jiǎng)討B(tài)編譯技術(shù)，難度較大。 基于解釋方式有利于人機(jī)交互。 執(zhí)行速度:解釋器執(zhí)行速度要慢。 空間開(kāi)銷(xiāo): 解釋器需要保存的信息較多，空間開(kāi)銷(xiāo)大。 利用解釋器可自動(dòng)生成編譯器。二者實(shí)現(xiàn)技術(shù)相似。143、語(yǔ)言的轉(zhuǎn)換執(zhí)行方式假如要實(shí)現(xiàn)L語(yǔ)言，現(xiàn)在已有L語(yǔ)言的編譯程序，就可以先把用L語(yǔ)言編寫(xiě)的程序轉(zhuǎn)換成等價(jià)的L語(yǔ)言的程序，再利用L語(yǔ)言的編譯程序?qū)崿F(xiàn)

8、L語(yǔ)言。L語(yǔ)言編譯器 轉(zhuǎn)換器 L語(yǔ)言程序 L語(yǔ)言程序 目標(biāo)程序 151.2 編譯程序的邏輯結(jié)構(gòu)編譯程序的基本任務(wù)是將源語(yǔ)言程序翻譯成等價(jià)的目標(biāo)語(yǔ)言程序。源語(yǔ)言的種類(lèi)成千上萬(wàn)，從常用的諸如FORTEAN,PASCAL和C語(yǔ)言，到各種各樣的計(jì)算機(jī)應(yīng)用領(lǐng)域的專(zhuān)用語(yǔ)言，而目標(biāo)語(yǔ)言也是成千上萬(wàn)的，加上編譯程序根據(jù)它們構(gòu)造的不同、所執(zhí)行的具體功能的差異又分成多種類(lèi)型，比如：一趟編譯的、多趟編譯的、具有調(diào)試和優(yōu)化功能的等等。盡管存在這些明顯的復(fù)雜因素，任何編譯程序所必需執(zhí)行的主要任務(wù)基本是一樣的，通過(guò)理解這些任務(wù)，使用同樣的基本技術(shù)，我們可以為各種各樣的源語(yǔ)言和目標(biāo)語(yǔ)言設(shè)計(jì)和構(gòu)造編譯程序。161.2.1 編

9、譯器的邏輯結(jié)構(gòu)表 處 理 目標(biāo)代碼生成中間代碼優(yōu)化中間代碼生成語(yǔ)義分析語(yǔ)法分析詞法分析目標(biāo)程序源程序錯(cuò) 誤 處 理 17詞法分析(Lexical Analysis) 依據(jù)語(yǔ)言的詞法規(guī)則，掃描源程序的字符序列，識(shí)別每 一個(gè)單詞及其種類(lèi)，并將其表示成所謂的機(jī)內(nèi)表示TOKEN形式。單詞種類(lèi): 關(guān)鍵字: if、then、for、while等; 標(biāo)識(shí)符; 常數(shù); 運(yùn)算符 特殊符 分界符: 標(biāo)點(diǎn)符號(hào)、左右括號(hào)等等. 單詞的機(jī)內(nèi)表示，即TOKEN形式，一般包括單詞屬性標(biāo)識(shí)和單詞內(nèi)碼兩個(gè)部分。 在詞法分析階段還要檢查括號(hào)類(lèi)配對(duì)等詞法錯(cuò)誤并去掉源程序中注釋。詞法分析階段不依賴(lài)于語(yǔ)言的語(yǔ)法定義。18詞法分析的示例

10、某程序片段如下：VAR sum, first, count: real; BEGIN sum:=first + count * 10 END.詞法分析程序掃描該程序段的字符序列，應(yīng)識(shí)別出下列單詞序列：1.關(guān)鍵字 VAR 2.標(biāo)識(shí)符 sum 3.特殊符 , 4.標(biāo)識(shí)符 first 5.特殊符 , 6.標(biāo)識(shí)符 count 7.特殊符 : 8.關(guān)鍵字 real 9.特殊符 ; 10. 關(guān)鍵字 BEGIN 11.標(biāo)識(shí)符 sum 12.特殊符 := 13.標(biāo)識(shí)符 first 14.特殊符 + 15.標(biāo)識(shí)符 count 16.特殊符 * 17.整形常數(shù) 10 18 .關(guān)鍵字 END 19.特殊符 .19假

11、定單詞的機(jī)內(nèi)表示，即TOKEN結(jié)構(gòu)如下：假定關(guān)鍵字VAR、 real、 BEGIN及END的屬性標(biāo)識(shí)分別為15、20、 23 和 24, 特殊符“,” 、“:” 、“:=”、“*”、“+” 、“.”及“;”的屬性標(biāo)識(shí)分別為30 、31、32、33、34、35及36。20詞法分析程序掃描該程序段的字符序列，生成下列TOKEN序列： 1.( 15, ) 2. ( 1, sum ) 3. ( 30, ) 4. ( 1, first ) 5. ( 30, ) 6. ( 1, count ) 7. ( 31, ) 8. ( 20, ) 9. ( 36, )10. ( 23, ) 11. ( 1, sum

12、 ) 12. ( 32, ) 13. ( 1, first ) 14. ( 34, ) 15. ( 1, count )16. ( 33, ) 17. ( 2, 10 ) 18 . ( 24, ) 19. ( 35, ) 21語(yǔ)法分析（Syntax Analysis) 依據(jù)源語(yǔ)言的語(yǔ)法規(guī)則，掃描源程序的字符序列（當(dāng)詞法分析程序是語(yǔ)法分析程序的子程序時(shí)）或Token序列（當(dāng)詞法分析程序是獨(dú)立的一遍時(shí)），確定整個(gè)輸入串是否構(gòu)成一個(gè)語(yǔ)法上正確的程序。一般來(lái)說(shuō)分析時(shí)發(fā)現(xiàn)錯(cuò)誤輸出錯(cuò)誤位置及類(lèi)型，如未發(fā)現(xiàn)錯(cuò)誤則將源程序轉(zhuǎn)換成語(yǔ)法樹(shù)的形式，目的是把詞法分析的結(jié)果分解成各種語(yǔ)法單位 。22語(yǔ)法分析的示例sum

13、:=first + count * 10 +:=*賦值語(yǔ)句表達(dá)式表達(dá)式標(biāo)識(shí)符( 1, sum )表達(dá)式標(biāo)識(shí)符( 1, first )表達(dá)式標(biāo)識(shí)符( 1, count )表達(dá)式常數(shù)( 2 , 10 )23+:=*( 1, sum )( 1, count )( 1, first )( 2, 10 )24語(yǔ)義分析（Semantic Analysis） 審查源程序有無(wú)語(yǔ)義錯(cuò)誤，為代碼生成 階段收集類(lèi)型信息。語(yǔ)義錯(cuò)誤檢查又可分為類(lèi)型檢查和一般的語(yǔ)義檢查。類(lèi)型檢查主要包含以下內(nèi)容：各種條件表達(dá)式的類(lèi)型是不是boolean型?運(yùn)算符的分量的類(lèi)型是否相容?賦值語(yǔ)句的左右部的類(lèi)型是否相容?形參和實(shí)參的類(lèi)型是否相

14、容?下標(biāo)表達(dá)式的類(lèi)型是否為所允許的類(lèi)型?變體記錄中表示情形的常量是否為合法類(lèi)型?函數(shù)說(shuō)明中的函數(shù)類(lèi)型和返回值的類(lèi)型是否一致?25除了上述類(lèi)型檢查外，語(yǔ)義分析還要進(jìn)行如下一些語(yǔ)義檢查：VE中的V是不是變量,而且是數(shù)組類(lèi)型？V. id中的V是不是變量,而且是記錄類(lèi)型? id是不是該記錄類(lèi)型中的域名?V中的V是不是指針或文件變量？y + f(.)中的f是不是函數(shù)名?形參個(gè)數(shù)和實(shí)參個(gè)數(shù)是否一致?p(.)語(yǔ)句中的p是不是過(guò)程名?形參個(gè)數(shù)和實(shí)參個(gè)數(shù)是否一致?每個(gè)使用性標(biāo)識(shí)符是否都有聲明?在同層內(nèi)有無(wú)標(biāo)識(shí)符被聲明多次?標(biāo)號(hào)是否有聲明?有無(wú)重復(fù)聲明和重復(fù)定位錯(cuò)誤?有無(wú)非法轉(zhuǎn)入錯(cuò)誤？子界類(lèi)型中的下界和上界類(lèi)型是

15、否相容?下界是否小于等于上界？ 26詞義分析的示例VAR first: real; count：char; BEGIN sum:=first + count * 10 END.詞義錯(cuò)誤：1、sum有使用而無(wú)定義；2、 count為字符類(lèi)型變量不能進(jìn)行乘法運(yùn)算。27中間代碼生成（Intermediate Code Generation） 為優(yōu)化源程序、為編譯程序便于移植和修改、將源程序轉(zhuǎn)換成一種稱(chēng)為中間代碼的內(nèi)部表示形式。 中間代碼是一種簡(jiǎn)單的含義明確的記號(hào)系統(tǒng)，形式有多種，常見(jiàn)的有后綴式（棧式）中間代碼、三地址中間代碼（三元式和四元式）、圖結(jié)構(gòu)中間代碼（樹(shù)，DAG）。例： VAR sum, f

16、irst, count: real; BEGIN sum:=first + count * 10 END.畫(huà)線(xiàn)語(yǔ)句部分生成如下四元式形式的中間代碼序列：1、（int-to-real, 10 , - ,t1 )2、（*, count , t1 ,t2 )3、（+, first , t2 ,t3 )4、（:=, t3 ,- , sum )28中間代碼優(yōu)化（ Intermediate Code Optimization） 在不改變?cè)闯绦蛘Z(yǔ)義的前提下變換或改造中間代碼，使生成的目標(biāo)代碼更為高效，即縮短運(yùn)行時(shí)間或節(jié)省存儲(chǔ)空間。 主要的優(yōu)化方式包括：常量表達(dá)式優(yōu)化公共子表達(dá)式優(yōu)化不變表達(dá)式的循環(huán)外提削減運(yùn)

17、算強(qiáng)度等29目標(biāo)代碼生成（Code Generation） 中間代碼變換為特定機(jī)器上的機(jī)器指令代碼（絕對(duì)指令代碼或可重定位的指令代碼）或匯編指令代碼。例：sum:=first + count * 10生成如下匯編代碼：1. MOV count , R22. MULT 10.0 , R23. MOV first , R14. ADD R1, R25. MOV R1, sum 30表格管理（Symbol-Table Management)變編譯程序在對(duì)源程序的分析過(guò)程中，需要?jiǎng)?chuàng)建和管理一系列的表格，以登記源程序的各類(lèi)信息和編譯各階段的進(jìn)展情況。隨著編譯過(guò)程的進(jìn)行需要不斷的建表、查表和填表，或修改表

18、中的某些數(shù)據(jù)，或從表中查找相關(guān)信息，這些活動(dòng)貫穿整個(gè)編譯過(guò)程的始終。因此，合理的設(shè)計(jì)和使用表格是編譯程序構(gòu)造中的一個(gè)非常重要的問(wèn)題。不少編譯程序都設(shè)立一些專(zhuān)門(mén)子程序（稱(chēng)為表格管理程序）負(fù)責(zé)管理表格。31錯(cuò)誤處理（Error Detection and Reporting)一個(gè)編譯程序不僅應(yīng)能對(duì)書(shū)寫(xiě)正確的程序進(jìn)行翻譯，而且應(yīng)能對(duì)出現(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。錯(cuò)誤包括詞法錯(cuò)誤、語(yǔ)法錯(cuò)誤、靜態(tài)語(yǔ)義錯(cuò)誤、動(dòng)態(tài)語(yǔ)義錯(cuò)誤,其中動(dòng)態(tài)語(yǔ)義錯(cuò)誤只能在運(yùn)行目標(biāo)程序時(shí)才能發(fā)現(xiàn)。在編譯程序的各個(gè)階段都要有錯(cuò)誤處理部分，詞法錯(cuò)誤和語(yǔ)法錯(cuò)誤都集中一次完成檢查，而語(yǔ)義檢查則分散在以后的各個(gè)階段在完成別的工作時(shí)順便完成。32

19、1.2.2 遍 （Pass） 所謂“遍”就是對(duì)源程序或源程序的中間表示形式從頭到尾掃描一次，并作加工處理，生成新的中間結(jié)果或目標(biāo)程序。 331.2.3 編譯程序的前端和后端前端主要由與源語(yǔ)言有關(guān)但與目標(biāo)機(jī)無(wú)關(guān)的那些部分組成。編譯前端通常包括詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成，與目標(biāo)機(jī)無(wú)關(guān)的中間代碼優(yōu)化部分也可包含在前端,當(dāng)然前端也包括相應(yīng)部分的錯(cuò)誤處理。編譯前端是面向源語(yǔ)言的。編譯后端包括與目標(biāo)機(jī)有關(guān)的中間代碼優(yōu)化部分和目標(biāo)代碼生成等。一般來(lái)說(shuō)，這些部分與源語(yǔ)言無(wú)關(guān)而僅僅依賴(lài)于中間語(yǔ)言。編譯后端是面向目標(biāo)語(yǔ)言的。34 源程序文件預(yù)處理器標(biāo)準(zhǔn)源程序文件編譯程序 匯編代碼匯編程序可重定位的

20、目標(biāo)代碼連接/裝配程序絕對(duì)目標(biāo)代碼高級(jí)語(yǔ)言程序到可執(zhí)行代碼的轉(zhuǎn)換過(guò)程1.3 其它與編譯程序相關(guān)的程序編輯器調(diào)試程序高級(jí)語(yǔ)言的翻譯程序(的核心程序)稱(chēng)為編譯程序,目標(biāo)程序可以是機(jī)器語(yǔ)言程序、匯編語(yǔ)言程序或用戶(hù)自定義的某種中間形式的語(yǔ)言。35編輯器（editor）為用戶(hù)輸入源程序文件提供一般的編輯功能，有的還具有語(yǔ)法制導(dǎo)的結(jié)構(gòu)化功能和其它分析、提示、檢查和自動(dòng)提供關(guān)鍵字或與當(dāng)前關(guān)鍵字相匹配的關(guān)鍵字等高級(jí)編輯功能等。 預(yù)處理器（preprocessor） 預(yù)處理器是翻譯工作開(kāi)始之前由編譯器調(diào)用的獨(dú)立程序，它所做的工作包括刪除源程序中的注釋、執(zhí)行宏替換以及包含文件的嵌入等。 連接程序（linker）

21、連接程序負(fù)責(zé)將分別在不同的目標(biāo)文件中編譯或匯編的代碼集中到一個(gè)可執(zhí)行文件中，并將目標(biāo)程序和標(biāo)準(zhǔn)庫(kù)函數(shù)的代碼以及計(jì)算機(jī)操作系統(tǒng)提供的資源連接在一起。連接程序?qū)Σ僮飨到y(tǒng)和目標(biāo)機(jī)有極大的依賴(lài)性。36裝配程序（loader）裝配程序用來(lái)把程序加載到內(nèi)存儲(chǔ)器中，以便執(zhí)行。由于用戶(hù)的程序經(jīng)匯編或編譯后生成的目標(biāo)代碼通常采用相對(duì)地址的形式，它的起始地址是不確定的，這樣的代碼被稱(chēng)為可重定位的。裝入程序可處理所有的與指定的基地址或起始地址有關(guān)的可重定位的地址，它使得可執(zhí)行代碼更加靈活。調(diào)試程序（debugger） 調(diào)試程序是可在被編譯了的程序中判定執(zhí)行錯(cuò)誤的程序。37在高級(jí)語(yǔ)言發(fā)展的早期，這些工具都是獨(dú)立的，缺乏整體性。隨著程序設(shè)計(jì)語(yǔ)言的發(fā)展，編輯器、預(yù)處理器、編譯器、連接程序、裝配程序、調(diào)試程序及項(xiàng)目管理程序等這些工具往往被集成在一起，構(gòu)成基于窗口的交互式集成開(kāi)發(fā)環(huán)境（IDE），集編輯、編譯、調(diào)試、連接、運(yùn)行等功能于一體。在這種集成開(kāi)發(fā)環(huán)境中，編譯程序起到核心作用。381.4 編譯程序的實(shí)現(xiàn)途徑一、開(kāi)發(fā)編譯程序的必要條件實(shí)現(xiàn)一個(gè)編譯程序應(yīng)從以下三方面入手：源語(yǔ)言：對(duì)源語(yǔ)言的詞法、語(yǔ)法和語(yǔ)義要有準(zhǔn)確無(wú)誤 的理解，否則難以保證