編譯原理及其精品課件

1、編譯原理及其第1頁，共41頁，2022年，5月20日，20點31分，星期二參考書目1 Alfred V.Aho Ravi Sethi Jeffrey D.Ullman Compilers: Principles,Techniques,and Tools 人民郵電出版社。2 Kenneth C. Louden 著 馮博琴 馮嵐等譯 Compiler Construction Principles and Practice 機械工業(yè)出版社。3 金成植 著 ,編譯原理及實現(xiàn)，高等教育出版社。4 呂映芝 ，編譯原理，清華大學教育出版社。第2頁，共41頁，2022年，5月20日，20點31分，星期二第一

2、章 編譯引論主要內(nèi)容：幾個基本概念:翻譯程序匯編程序編譯程序源程序目標程序編譯器的組成結(jié)構(gòu)、各部分之間的邏輯關(guān)系和主要功能；編譯程序的實現(xiàn)途徑;與編譯程序相關(guān)的其他程序;編輯器預處理器連接程序裝配程序調(diào)試程序第3頁，共41頁，2022年，5月20日，20點31分，星期二1.1 程序設(shè)計語言和編譯程序從第一臺計算機問世至今，半個多世紀以來，程序設(shè)計語言經(jīng)歷了由低級向高級的發(fā)展，從最初的機器語言、匯編語言，發(fā)展到較高級程序設(shè)計語言直至今天的第四代、第五代高級語言。一、程序設(shè)計語言（一）低級語言機器語言由能被計算機的硬件系統(tǒng)直接執(zhí)行的機器指令組成，每條機器指令是一串二進制代碼，用機器語言編寫出來的程

3、序是一串二進制代碼序列。例： x + 15 xy Y= x - 15 否則第4頁，共41頁，2022年，5月20日，20點31分，星期二用Pentium機器語言編寫如下程序片段：1010 1001 0001 0110 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 00

4、00 0000 0000 0000 機器語言的特點：優(yōu)點：執(zhí)行速度快；缺點：難學、難記憶、難理解;機器語言程序依賴于具體的機器, 不具備移植性；第5頁，共41頁，2022年，5月20日，20點31分，星期二匯編語言將硬件指令用一些助記符表示。如ADD表示加法操作，SUB表示減法操作等等 。用Pentium匯編語言編程示例： MOV AX , X CMP AX , Y JLS1 SUB AX ,15 JMP S2 S1: ADD AX ,15 S2: MOV Y ,AX . XDWYDW第6頁，共41頁，2022年，5月20日，20點31分，星期二匯編語言的優(yōu)點：比機器語言較易學、易記憶及易理解

5、;匯編語言的缺點：匯編語言程序依賴于具體的機器, 不具備移植性； 第7頁，共41頁，2022年，5月20日，20點31分，星期二（二）高級語言高級語言：把便于理解的自然語言和數(shù)學語言結(jié)合在一起而形成的程序設(shè)計語言。高級語言編程示例： if (XY ) then Y:=X + 15 else Y:=X - 15;高級語言的優(yōu)點：比匯編語言更容易學，以人為本，面向自然表達，易學、易用、易理解、易修改;高級語言程序不依賴于具體的機器, 具備移植性。第8頁，共41頁，2022年，5月20日，20點31分，星期二高級程序設(shè)計語言分類：1、程序設(shè)計語言按功能分類：科學計算用語言商用語言表處理語言圖形語言公

6、式處理語言串處理語言多用途語言 2、按處理問題模式分類：過程式語言函數(shù)式語言邏輯式語言對象式語 3、按執(zhí)行模式分類：順序語言并行語言第9頁，共41頁，2022年，5月20日，20點31分，星期二二、高級語言和匯編語言的執(zhí)行翻譯程序（Translator） ：它把用匯編語言或高級語言編寫的程序轉(zhuǎn)換成等價的機器語言程序。 匯編程序(Assembler) ：匯編語言的翻譯程序稱為匯編程序(Assembler) 編譯程序(Compiler) ：高級語言的翻譯程序稱為編譯程序,也稱為編譯器。第10頁，共41頁，2022年，5月20日，20點31分，星期二源程序（Source program）：編譯程序的

7、輸入對象, 它是高級語言編寫的程序；目標程序（Object program）: 編譯程序的輸出對象稱為目標程序。目標程序可以是機器語言程序、匯編語言程序或用戶自定義某種中間語言程序。第11頁，共41頁，2022年，5月20日，20點31分，星期二三、高級語言的執(zhí)行方式1. 編譯方式編譯階段：將源程序改造成另一種在邏輯上等價的目標語言程序；運行階段：在運行子程序的支持下執(zhí)行目標程序。運行子程序是為了支持目標程序的運行而開發(fā)的程序，如系統(tǒng)提供的標準庫函數(shù)和目標程序所調(diào)用的其它子程序。 目標程序程序的輸入數(shù)據(jù)運行結(jié)果高級語言 源程序 編譯程序 （器）第12頁，共41頁，2022年，5月20日，20點

8、31分，星期二2. 解釋方式接受某程序語言編寫的源程序，按源程序語句運行時的動態(tài)結(jié)構(gòu)，直接逐句地分析、翻譯并執(zhí)行。解釋程序相當于源程序的抽象執(zhí)行機，是語言的實現(xiàn)系統(tǒng)。 運行結(jié)果 解釋程序 （器）程序的輸入數(shù)據(jù)高級語言源程序第13頁，共41頁，2022年，5月20日，20點31分，星期二解釋器和編譯器的比較解釋器是執(zhí)行系統(tǒng)，編譯器是轉(zhuǎn)換系統(tǒng)。 基于解釋執(zhí)行的程序可以動態(tài)修改自身， 而基于編譯執(zhí)行的程序不易勝任，因其需要動態(tài)編譯技術(shù)，難度較大。 基于解釋方式有利于人機交互。 執(zhí)行速度:解釋器執(zhí)行速度要慢。 空間開銷: 解釋器需要保存的信息較多，空間開銷大。 利用解釋器可自動生成編譯器。二者實現(xiàn)技術(shù)

9、相似。第14頁，共41頁，2022年，5月20日，20點31分，星期二3、語言的轉(zhuǎn)換執(zhí)行方式假如要實現(xiàn)L語言，現(xiàn)在已有L語言的編譯程序，就可以先把用L語言編寫的程序轉(zhuǎn)換成等價的L語言的程序，再利用L語言的編譯程序?qū)崿F(xiàn)L語言。L語言編譯器 轉(zhuǎn)換器 L語言程序 L語言程序 目標程序 第15頁，共41頁，2022年，5月20日，20點31分，星期二1.2 編譯程序的邏輯結(jié)構(gòu)編譯程序的基本任務(wù)是將源語言程序翻譯成等價的目標語言程序。源語言的種類成千上萬，從常用的諸如FORTEAN,PASCAL和C語言，到各種各樣的計算機應用領(lǐng)域的專用語言，而目標語言也是成千上萬的，加上編譯程序根據(jù)它們構(gòu)造的不同、所執(zhí)

10、行的具體功能的差異又分成多種類型，比如：一趟編譯的、多趟編譯的、具有調(diào)試和優(yōu)化功能的等等。盡管存在這些明顯的復雜因素，任何編譯程序所必需執(zhí)行的主要任務(wù)基本是一樣的，通過理解這些任務(wù)，使用同樣的基本技術(shù)，我們可以為各種各樣的源語言和目標語言設(shè)計和構(gòu)造編譯程序。第16頁，共41頁，2022年，5月20日，20點31分，星期二1.2.1 編譯器的邏輯結(jié)構(gòu)表 處 理 目標代碼生成中間代碼優(yōu)化中間代碼生成語義分析語法分析詞法分析目標程序源程序錯 誤 處 理 第17頁，共41頁，2022年，5月20日，20點31分，星期二詞法分析(Lexical Analysis) 依據(jù)語言的詞法規(guī)則，掃描源程序的字符序

11、列，識別每 一個單詞及其種類，并將其表示成所謂的機內(nèi)表示TOKEN形式。單詞種類: 關(guān)鍵字: if、then、for、while等; 標識符; 常數(shù); 運算符 特殊符 分界符: 標點符號、左右括號等等. 單詞的機內(nèi)表示，即TOKEN形式，一般包括單詞屬性標識和單詞內(nèi)碼兩個部分。 在詞法分析階段還要檢查括號類配對等詞法錯誤并去掉源程序中注釋。詞法分析階段不依賴于語言的語法定義。第18頁，共41頁，2022年，5月20日，20點31分，星期二詞法分析的示例某程序片段如下：VAR sum, first, count: real; BEGIN sum:=first + count * 10 END.詞

12、法分析程序掃描該程序段的字符序列，應識別出下列單詞序列：1.關(guān)鍵字 VAR 2.標識符 sum 3.特殊符 , 4.標識符 first 5.特殊符 , 6.標識符 count 7.特殊符 : 8.關(guān)鍵字 real 9.特殊符 ; 10. 關(guān)鍵字 BEGIN 11.標識符 sum 12.特殊符 := 13.標識符 first 14.特殊符 + 15.標識符 count 16.特殊符 * 17.整形常數(shù) 10 18 .關(guān)鍵字 END 19.特殊符 .第19頁，共41頁，2022年，5月20日，20點31分，星期二假定單詞的機內(nèi)表示，即TOKEN結(jié)構(gòu)如下：假定關(guān)鍵字VAR、 real、 BEGIN及

13、END的屬性標識分別為15、20、 23 和 24, 特殊符“,” 、“:” 、“:=”、“*”、“+” 、“.”及“;”的屬性標識分別為30 、31、32、33、34、35及36。單詞屬性標識單詞內(nèi)碼關(guān)鍵字一關(guān)鍵字一整數(shù)碼空標識符1標識符常數(shù)2常數(shù)特殊符一特殊符一整數(shù)碼空第20頁，共41頁，2022年，5月20日，20點31分，星期二詞法分析程序掃描該程序段的字符序列，生成下列TOKEN序列： 1.( 15, ) 2. ( 1, sum ) 3. ( 30, ) 4. ( 1, first ) 5. ( 30, ) 6. ( 1, count ) 7. ( 31, ) 8. ( 20, )

14、9. ( 36, )10. ( 23, ) 11. ( 1, sum ) 12. ( 32, ) 13. ( 1, first ) 14. ( 34, ) 15. ( 1, count )16. ( 33, ) 17. ( 2, 10 ) 18 . ( 24, ) 19. ( 35, ) 第21頁，共41頁，2022年，5月20日，20點31分，星期二語法分析（Syntax Analysis) 依據(jù)源語言的語法規(guī)則，掃描源程序的字符序列（當詞法分析程序是語法分析程序的子程序時）或Token序列（當詞法分析程序是獨立的一遍時），確定整個輸入串是否構(gòu)成一個語法上正確的程序。一般來說分析時發(fā)現(xiàn)錯誤輸

15、出錯誤位置及類型，如未發(fā)現(xiàn)錯誤則將源程序轉(zhuǎn)換成語法樹的形式，目的是把詞法分析的結(jié)果分解成各種語法單位 。第22頁，共41頁，2022年，5月20日，20點31分，星期二語法分析的示例sum:=first + count * 10 +:=*賦值語句表達式表達式標識符( 1, sum )表達式標識符( 1, first )表達式標識符( 1, count )表達式常數(shù)( 2 , 10 )第23頁，共41頁，2022年，5月20日，20點31分，星期二+:=*( 1, sum )( 1, count )( 1, first )( 2, 10 )第24頁，共41頁，2022年，5月20日，20點31分

16、，星期二語義分析（Semantic Analysis） 審查源程序有無語義錯誤，為代碼生成 階段收集類型信息。語義錯誤檢查又可分為類型檢查和一般的語義檢查。類型檢查主要包含以下內(nèi)容：各種條件表達式的類型是不是boolean型?運算符的分量的類型是否相容?賦值語句的左右部的類型是否相容?形參和實參的類型是否相容?下標表達式的類型是否為所允許的類型?變體記錄中表示情形的常量是否為合法類型?函數(shù)說明中的函數(shù)類型和返回值的類型是否一致?第25頁，共41頁，2022年，5月20日，20點31分，星期二除了上述類型檢查外，語義分析還要進行如下一些語義檢查：VE中的V是不是變量,而且是數(shù)組類型？V. id中

17、的V是不是變量,而且是記錄類型? id是不是該記錄類型中的域名?V中的V是不是指針或文件變量？y + f(.)中的f是不是函數(shù)名?形參個數(shù)和實參個數(shù)是否一致?p(.)語句中的p是不是過程名?形參個數(shù)和實參個數(shù)是否一致?每個使用性標識符是否都有聲明?在同層內(nèi)有無標識符被聲明多次?標號是否有聲明?有無重復聲明和重復定位錯誤?有無非法轉(zhuǎn)入錯誤？子界類型中的下界和上界類型是否相容?下界是否小于等于上界？ 第26頁，共41頁，2022年，5月20日，20點31分，星期二詞義分析的示例VAR first: real; count：char; BEGIN sum:=first + count * 10 EN

18、D.詞義錯誤：1、sum有使用而無定義；2、 count為字符類型變量不能進行乘法運算。第27頁，共41頁，2022年，5月20日，20點31分，星期二中間代碼生成（Intermediate Code Generation） 為優(yōu)化源程序、為編譯程序便于移植和修改、將源程序轉(zhuǎn)換成一種稱為中間代碼的內(nèi)部表示形式。 中間代碼是一種簡單的含義明確的記號系統(tǒng)，形式有多種，常見的有后綴式（棧式）中間代碼、三地址中間代碼（三元式和四元式）、圖結(jié)構(gòu)中間代碼（樹，DAG）。例： VAR sum, first, count: real; BEGIN sum:=first + count * 10 END.畫線語

19、句部分生成如下四元式形式的中間代碼序列：1、（int-to-real, 10 , - ,t1 )2、（*, count , t1 ,t2 )3、（+, first , t2 ,t3 )4、（:=, t3 ,- , sum )第28頁，共41頁，2022年，5月20日，20點31分，星期二中間代碼優(yōu)化（ Intermediate Code Optimization） 在不改變源程序語義的前提下變換或改造中間代碼，使生成的目標代碼更為高效，即縮短運行時間或節(jié)省存儲空間。 主要的優(yōu)化方式包括：常量表達式優(yōu)化公共子表達式優(yōu)化不變表達式的循環(huán)外提削減運算強度等第29頁，共41頁，2022年，5月20日，

20、20點31分，星期二目標代碼生成（Code Generation） 中間代碼變換為特定機器上的機器指令代碼（絕對指令代碼或可重定位的指令代碼）或匯編指令代碼。例：sum:=first + count * 10生成如下匯編代碼：1. MOV count , R22. MULT 10.0 , R23. MOV first , R14. ADD R1, R25. MOV R1, sum 第30頁，共41頁，2022年，5月20日，20點31分，星期二表格管理（Symbol-Table Management)變編譯程序在對源程序的分析過程中，需要創(chuàng)建和管理一系列的表格，以登記源程序的各類信息和編譯各階

21、段的進展情況。隨著編譯過程的進行需要不斷的建表、查表和填表，或修改表中的某些數(shù)據(jù)，或從表中查找相關(guān)信息，這些活動貫穿整個編譯過程的始終。因此，合理的設(shè)計和使用表格是編譯程序構(gòu)造中的一個非常重要的問題。不少編譯程序都設(shè)立一些專門子程序（稱為表格管理程序）負責管理表格。第31頁，共41頁，2022年，5月20日，20點31分，星期二錯誤處理（Error Detection and Reporting)一個編譯程序不僅應能對書寫正確的程序進行翻譯，而且應能對出現(xiàn)在源程序中的錯誤進行處理。錯誤包括詞法錯誤、語法錯誤、靜態(tài)語義錯誤、動態(tài)語義錯誤,其中動態(tài)語義錯誤只能在運行目標程序時才能發(fā)現(xiàn)。在編譯程序的

22、各個階段都要有錯誤處理部分，詞法錯誤和語法錯誤都集中一次完成檢查，而語義檢查則分散在以后的各個階段在完成別的工作時順便完成。第32頁，共41頁，2022年，5月20日，20點31分，星期二1.2.2 遍 （Pass） 所謂“遍”就是對源程序或源程序的中間表示形式從頭到尾掃描一次，并作加工處理，生成新的中間結(jié)果或目標程序。 第33頁，共41頁，2022年，5月20日，20點31分，星期二1.2.3 編譯程序的前端和后端前端主要由與源語言有關(guān)但與目標機無關(guān)的那些部分組成。編譯前端通常包括詞法分析、語法分析、語義分析、中間代碼生成，與目標機無關(guān)的中間代碼優(yōu)化部分也可包含在前端,當然前端也包括相應部分

23、的錯誤處理。編譯前端是面向源語言的。編譯后端包括與目標機有關(guān)的中間代碼優(yōu)化部分和目標代碼生成等。一般來說，這些部分與源語言無關(guān)而僅僅依賴于中間語言。編譯后端是面向目標語言的。第34頁，共41頁，2022年，5月20日，20點31分，星期二 源程序文件預處理器標準源程序文件編譯程序 匯編代碼匯編程序可重定位的目標代碼連接/裝配程序絕對目標代碼高級語言程序到可執(zhí)行代碼的轉(zhuǎn)換過程1.3 其它與編譯程序相關(guān)的程序編輯器調(diào)試程序高級語言的翻譯程序(的核心程序)稱為編譯程序,目標程序可以是機器語言程序、匯編語言程序或用戶自定義的某種中間形式的語言。第35頁，共41頁，2022年，5月20日，20點31分，

24、星期二編輯器（editor）為用戶輸入源程序文件提供一般的編輯功能，有的還具有語法制導的結(jié)構(gòu)化功能和其它分析、提示、檢查和自動提供關(guān)鍵字或與當前關(guān)鍵字相匹配的關(guān)鍵字等高級編輯功能等。 預處理器（preprocessor） 預處理器是翻譯工作開始之前由編譯器調(diào)用的獨立程序，它所做的工作包括刪除源程序中的注釋、執(zhí)行宏替換以及包含文件的嵌入等。 連接程序（linker） 連接程序負責將分別在不同的目標文件中編譯或匯編的代碼集中到一個可執(zhí)行文件中，并將目標程序和標準庫函數(shù)的代碼以及計算機操作系統(tǒng)提供的資源連接在一起。連接程序?qū)Σ僮飨到y(tǒng)和目標機有極大的依賴性。第36頁，共41頁，2022年，5月20日，

25、20點31分，星期二裝配程序（loader）裝配程序用來把程序加載到內(nèi)存儲器中，以便執(zhí)行。由于用戶的程序經(jīng)匯編或編譯后生成的目標代碼通常采用相對地址的形式，它的起始地址是不確定的，這樣的代碼被稱為可重定位的。裝入程序可處理所有的與指定的基地址或起始地址有關(guān)的可重定位的地址，它使得可執(zhí)行代碼更加靈活。調(diào)試程序（debugger） 調(diào)試程序是可在被編譯了的程序中判定執(zhí)行錯誤的程序。第37頁，共41頁，2022年，5月20日，20點31分，星期二在高級語言發(fā)展的早期，這些工具都是獨立的，缺乏整體性。隨著程序設(shè)計語言的發(fā)展，編輯器、預處理器、編譯器、連接程序、裝配程序、調(diào)試程序及項目管理程序等這些工具往往被集成在一起，構(gòu)成基于窗口的交互式集成開發(fā)環(huán)境（IDE），集編輯、編譯、調(diào)試、連接、運行等功能于一體。在這種集成開發(fā)環(huán)境中，編譯程序起到核心作用。第38頁，共41頁，2022年，5月20日，20點31分，星期二1.4 編譯程序的實現(xiàn)途徑一、開發(fā)編譯程序的必要條件實現(xiàn)一個編譯程序應從以下三方面入