編譯原理與技術(shù)講義-第1章

1、青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)第第1章章 概論概論青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)2主要內(nèi)容主要內(nèi)容u為什么學習編譯為什么學習編譯u什么叫編譯程序什么叫編譯程序 u編譯過程概述編譯過程概述u編譯程序的構(gòu)成編譯程序的構(gòu)成u與編譯有關的概念和技術(shù)與編譯有關的概念和技術(shù) u如何開發(fā)編譯程序如何開發(fā)編譯程序 u編譯系統(tǒng)以及其它相關程序編譯系統(tǒng)以及其它相關程序青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)31.1 為什么學習編譯為什么學習編譯u編譯程序構(gòu)造的原理和技術(shù)一直屬于計算編譯程序構(gòu)造的原理和技術(shù)一直屬

2、于計算機科學必備的專業(yè)基礎知識。機科學必備的專業(yè)基礎知識。u是計算機科學中一個非常成功的分支，也是計算機科學中一個非常成功的分支，也是最早獲得成功的分支之一。是最早獲得成功的分支之一。u它所建立的理論、技術(shù)和方法值得深入研它所建立的理論、技術(shù)和方法值得深入研究和學習。究和學習。編譯構(gòu)造正確地建立了研究的問題領域和研編譯構(gòu)造正確地建立了研究的問題領域和研究方式。究方式。青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)41.1 為什么學習編譯為什么學習編譯針對編譯程序構(gòu)造的某些部分已經(jīng)開發(fā)了標針對編譯程序構(gòu)造的某些部分已經(jīng)開發(fā)了標準的形式化技術(shù)，包括有限自動機理論、上準的形式化

3、技術(shù)，包括有限自動機理論、上下文無關文法、正規(guī)表達式、屬性文法、機下文無關文法、正規(guī)表達式、屬性文法、機器代碼描述、數(shù)據(jù)流分析方程式等。器代碼描述、數(shù)據(jù)流分析方程式等。 編譯程序包含許多普遍使用的數(shù)據(jù)結(jié)構(gòu)和算編譯程序包含許多普遍使用的數(shù)據(jù)結(jié)構(gòu)和算法，例如散列法（哈希算法）、棧機制、堆法，例如散列法（哈希算法）、棧機制、堆機制、垃圾收集、集合算法、表驅(qū)動算法。機制、垃圾收集、集合算法、表驅(qū)動算法。編譯程序的許多構(gòu)造技術(shù)已經(jīng)得到了廣泛的編譯程序的許多構(gòu)造技術(shù)已經(jīng)得到了廣泛的應用。應用。學習編譯原理和技術(shù)還有助于我們理解程序?qū)W習編譯原理和技術(shù)還有助于我們理解程序設計語言，編寫優(yōu)秀的軟件。設計語言，編

4、寫優(yōu)秀的軟件。 青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)51.2 什么叫編譯程序什么叫編譯程序u概念概念翻譯程序或翻譯器是把一種語言（翻譯程序或翻譯器是把一種語言（源語言源語言）轉(zhuǎn)換成等價的另外一種語言（轉(zhuǎn)換成等價的另外一種語言（目標語言目標語言）的）的程序。程序。如果源語言是高級編程語言，目標語言是機如果源語言是高級編程語言，目標語言是機器代碼和匯編語言這樣的低級語言，這類翻器代碼和匯編語言這樣的低級語言，這類翻譯程序就叫做譯程序就叫做編譯程序編譯程序或或編譯器編譯器。 青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)61.2 什么叫編譯程序什

5、么叫編譯程序編譯執(zhí)行方式：把源程序用編譯程序翻譯成編譯執(zhí)行方式：把源程序用編譯程序翻譯成機器可以執(zhí)行的目標程序或目標代碼，然后機器可以執(zhí)行的目標程序或目標代碼，然后才能接受輸入數(shù)據(jù)運行。才能接受輸入數(shù)據(jù)運行。 編譯程序源程序輸入數(shù)據(jù)目標程序計算機系統(tǒng)計算機系統(tǒng)目標程序運行結(jié)果青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)71.2 什么叫編譯程序什么叫編譯程序解釋程序：解釋程序不產(chǎn)生源程序的目標代解釋程序：解釋程序不產(chǎn)生源程序的目標代碼，而是對源程序逐條語句的分析，根據(jù)每碼，而是對源程序逐條語句的分析，根據(jù)每個語句的含義執(zhí)行產(chǎn)生結(jié)果。個語句的含義執(zhí)行產(chǎn)生結(jié)果。 解釋程序解釋

6、程序輸入數(shù)據(jù)源程序計算機系統(tǒng)計算機系統(tǒng)運行結(jié)果青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)81.3 編譯過程概述編譯過程概述u詞法分析詞法分析詞法分析的任務是逐步地掃描和分解構(gòu)成源詞法分析的任務是逐步地掃描和分解構(gòu)成源程序的字符串，識別出一個一個的單詞符號程序的字符串，識別出一個一個的單詞符號或符號?；蚍枴＞幾g程序的詞法分析也叫編譯程序的詞法分析也叫詞法掃描詞法掃描或線或線性掃性掃描描。 計算機高級語言的單詞符號通常包括：標識計算機高級語言的單詞符號通常包括：標識符、關鍵字或基本字、標點符號、常數(shù)、運符、關鍵字或基本字、標點符號、常數(shù)、運算符、分隔符等類型。算符、分隔

7、符等類型。 青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)91.3 編譯過程概述編譯過程概述符號符號類型類型while關鍵字(分隔符i標識符運算符100整常數(shù))分隔符sum標識符=運算符sum標識符i標識符+運算符;分隔符例子例子1.1：while (i 100) sum = sum + i 詞法分析的結(jié)果識別出的單詞詞法分析的結(jié)果識別出的單詞 青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)101.3 編譯過程概述編譯過程概述u語法分析語法分析語法分析的任務是在詞法分析基礎上，根據(jù)語法分析的任務是在詞法分析基礎上，根據(jù)語言的語法規(guī)則把單詞符號串分解成

8、各類語語言的語法規(guī)則把單詞符號串分解成各類語法單元（語法范疇、語法短語）法單元（語法范疇、語法短語）l例如例如“短語短語”、“子句子句”、“語句語句”、“程序程序段段”、“函數(shù)函數(shù)”和和“程序程序”等。等。語法分析是把線形序列的單詞符號，根據(jù)語語法分析是把線形序列的單詞符號，根據(jù)語言的語法規(guī)則，按照層次分解，結(jié)果通常表言的語法規(guī)則，按照層次分解，結(jié)果通常表示成語法示成語法分析樹分析樹。 青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)111.3 編譯過程概述編譯過程概述例子例子1.1while (i 100) sum = sum + i 語法分析樹語法分析樹while語句分

9、隔符分隔符(分隔符)表達式表達式；表達式循環(huán)體語句運算符賦值表達式變量常量100i變量表達式復合賦值運算符+sum+=運算符表達式變量i青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)121.3 編譯過程概述編譯過程概述u語義分析和中間代碼生成語義分析和中間代碼生成語義分析的任務是檢查程序語義的正確性，語義分析的任務是檢查程序語義的正確性，解釋程序結(jié)構(gòu)的含義。解釋程序結(jié)構(gòu)的含義。檢查變量是否有定義，變量在使用前是否具檢查變量是否有定義，變量在使用前是否具有值，數(shù)值是否溢出等，其中的一個重要部有值，數(shù)值是否溢出等，其中的一個重要部分是進行類型的檢查和轉(zhuǎn)換。分是進行類型的檢查和

10、轉(zhuǎn)換。 語義分析完成之后，編譯程序通常就依據(jù)語語義分析完成之后，編譯程序通常就依據(jù)語言的語義規(guī)則、利用語法制導技術(shù)把源程序言的語義規(guī)則、利用語法制導技術(shù)把源程序翻譯成某種中間代碼。翻譯成某種中間代碼。 青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)131.3 編譯過程概述編譯過程概述中間代碼是一種定義明確、便于處理、獨立中間代碼是一種定義明確、便于處理、獨立于計算機硬件的記號系統(tǒng)，可以認為是一種于計算機硬件的記號系統(tǒng)，可以認為是一種抽象機的程序。其中一類是三地址代碼，很抽象機的程序。其中一類是三地址代碼，很象機器的匯編語言象機器的匯編語言 Lbegin：if i 100

11、goto Lbodygoto LendLbody：t1 := sum + isum := t1t2 := i + 1i := t2goto LbeginLend：青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)141.3 編譯過程概述編譯過程概述u中間代碼優(yōu)化中間代碼優(yōu)化主要任務是對前一階段產(chǎn)生的中間代碼進行主要任務是對前一階段產(chǎn)生的中間代碼進行等價變換，以便產(chǎn)生速度快、空間小的目標等價變換，以便產(chǎn)生速度快、空間小的目標代碼。代碼。 Lbegin：if i 100 goto Lbodygoto LendLbody：sum := sum + ii := i + 1goto L

12、beginLend：青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)151.3 編譯過程概述編譯過程概述u目標代碼生成目標代碼生成目標代碼生成的主要任務是把（經(jīng)過優(yōu)化處目標代碼生成的主要任務是把（經(jīng)過優(yōu)化處理的）中間代碼翻譯成特定的機器指令或匯理的）中間代碼翻譯成特定的機器指令或匯編程序。編程序。這個階段的工作依賴于計算機的硬件結(jié)構(gòu)和這個階段的工作依賴于計算機的硬件結(jié)構(gòu)和指令系統(tǒng)，主要涉及到機器指令的選擇、各指令系統(tǒng)，主要涉及到機器指令的選擇、各種類型變量存儲空間的分配，以及寄存器的種類型變量存儲空間的分配，以及寄存器的分配和調(diào)度，等等。分配和調(diào)度，等等。 青島大學信息工程

13、學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)161.3 編譯過程概述編譯過程概述u目標代碼生成目標代碼生成MOV #100, R0/ 把常數(shù)100存入寄存器R0MOV i, R1/ 把變量i的值存入寄存器R1MOVsum，R2 / 把變量m的值存入寄存器R2Lbegin:CMP R1, R0 / 比較R1和R0的值，結(jié)果存入狀態(tài)寄 存器CTJ Lend/ 狀態(tài)寄存器CT1或2，即R1R0，程序轉(zhuǎn)入單元Lend ADDR1, R2/ 把寄存器R1加R2，結(jié)果送入R2INCR1/ 寄存器R1的值加1JLbegin/ 無條件轉(zhuǎn)移到地址LbeginLend:青島大學信息工程學院青島大學信息工程

14、學院編譯原理與技術(shù)編譯原理與技術(shù)171.4 編譯程序的構(gòu)成編譯程序的構(gòu)成 符號表管理錯誤處理詞法分析器語法分析器語義分析與中間代碼生器代碼優(yōu)化器目標代碼生成器目標代碼單詞符號源程序語法單元中間代碼中間代碼青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)181.4 編譯程序的構(gòu)成基本功能編譯程序的構(gòu)成基本功能詞法分析器，又叫掃描器，對輸入的源程序執(zhí)行詞法詞法分析器，又叫掃描器，對輸入的源程序執(zhí)行詞法分析工作，輸出單詞符號序列。分析工作，輸出單詞符號序列。語法分析器，又叫分析器，對單詞符號序列進行語法語法分析器，又叫分析器，對單詞符號序列進行語法分析，識別出各類語法單元，判斷輸

15、入的符號串是否分析，識別出各類語法單元，判斷輸入的符號串是否構(gòu)成語法正確的構(gòu)成語法正確的“程序程序”。語義分析與中間代碼生成器，對語法正確的各類程序語義分析與中間代碼生成器，對語法正確的各類程序單元進行語義分析，并把它們翻譯成一定形式的中間單元進行語義分析，并把它們翻譯成一定形式的中間代碼。代碼。代碼優(yōu)化器，執(zhí)行對中間代碼的優(yōu)化處理，以提高代代碼優(yōu)化器，執(zhí)行對中間代碼的優(yōu)化處理，以提高代碼的執(zhí)行效率。碼的執(zhí)行效率。目標代碼生成器，根據(jù)特定的機器把中間代碼翻譯成目標代碼，目標代碼生成器，根據(jù)特定的機器把中間代碼翻譯成目標代碼，并進行優(yōu)化處理。并進行優(yōu)化處理。青島大學信息工程學院青島大學信息工程學

16、院編譯原理與技術(shù)編譯原理與技術(shù)191.4 編譯程序的構(gòu)成輔助功能編譯程序的構(gòu)成輔助功能符號表管理：把編譯程序中的各種符號合理符號表管理：把編譯程序中的各種符號合理地組織和管理，方便符號信息的添加、查詢、地組織和管理，方便符號信息的添加、查詢、更新和刪除。更新和刪除。錯誤診斷和報告錯誤診斷和報告 ：有效地識別、診斷、分析：有效地識別、診斷、分析和報告程序中的各種錯誤。和報告程序中的各種錯誤。分類：語法錯誤（詞法錯誤和句法錯誤）和分類：語法錯誤（詞法錯誤和句法錯誤）和語義錯誤這兩類。語義錯誤這兩類。青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)201.5 其它與編譯有關的概念

17、和技術(shù)其它與編譯有關的概念和技術(shù) u遍（趟）遍（趟）在編譯的具體實現(xiàn)時，往往根據(jù)不同的源語在編譯的具體實現(xiàn)時，往往根據(jù)不同的源語言、設計要求、使用對象以及編譯程序所在言、設計要求、使用對象以及編譯程序所在宿主機的內(nèi)存等硬件條件，將編譯過程組織宿主機的內(nèi)存等硬件條件，將編譯過程組織為若干遍（趟）。一個編譯程序最終經(jīng)過幾為若干遍（趟）。一個編譯程序最終經(jīng)過幾遍完成，就稱為幾遍編譯。遍完成，就稱為幾遍編譯。 青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)211.5 其它與編譯有關的概念和技術(shù)其它與編譯有關的概念和技術(shù) u編譯的前端和后端編譯的前端和后端 編譯前端只依賴于源程序，

18、獨立于目標計算機。編譯編譯前端只依賴于源程序，獨立于目標計算機。編譯前端的工作包括詞法分析、語法分析、語義分析、中前端的工作包括詞法分析、語法分析、語義分析、中間代碼生成及其優(yōu)化，文法錯誤的處理和符號表的組間代碼生成及其優(yōu)化，文法錯誤的處理和符號表的組織也在編譯前端完成?？椧苍诰幾g前端完成。編譯后端的工作主要是目標代碼的生成和優(yōu)化，獨立編譯后端的工作主要是目標代碼的生成和優(yōu)化，獨立于源程序，完全依賴于目標機器和中間代碼。于源程序，完全依賴于目標機器和中間代碼。把編譯程序分成前端和后端已經(jīng)成為目前編譯程序的把編譯程序分成前端和后端已經(jīng)成為目前編譯程序的設計實踐，其顯著優(yōu)點是，可以優(yōu)化配置不同的編

19、譯設計實踐，其顯著優(yōu)點是，可以優(yōu)化配置不同的編譯程序組合，實現(xiàn)編譯的重用，保持語言與機器的獨立程序組合，實現(xiàn)編譯的重用，保持語言與機器的獨立性。性。 青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)221.5 其它與編譯有關的概念和技術(shù)其它與編譯有關的概念和技術(shù)u編譯程序的分類編譯程序的分類 診斷型編譯程序：專門用于幫助程序的開發(fā)診斷型編譯程序：專門用于幫助程序的開發(fā)和調(diào)試，它們系統(tǒng)地分析程序，發(fā)現(xiàn)程序中和調(diào)試，它們系統(tǒng)地分析程序，發(fā)現(xiàn)程序中的錯誤，智能地校正一些錯誤。的錯誤，智能地校正一些錯誤。優(yōu)化型編譯程序：這類編譯程序著重于提高優(yōu)化型編譯程序：這類編譯程序著重于提高目

20、標代碼的時空效率，使得產(chǎn)生的目標代碼目標代碼的時空效率，使得產(chǎn)生的目標代碼既占用較少的存儲空間，又運行的快。既占用較少的存儲空間，又運行的快。青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)231.5 其它與編譯有關的概念和技術(shù)其它與編譯有關的概念和技術(shù)交叉型編譯程序：運行目標程序的計算機和交叉型編譯程序：運行目標程序的計算機和運行編譯程序的計算機的型號不相同運行編譯程序的計算機的型號不相同 。利用編譯前端和后端的技術(shù)，可以設計與目利用編譯前端和后端的技術(shù)，可以設計與目標機無關的編譯程序，利用編譯后端就可以標機無關的編譯程序，利用編譯后端就可以改變目標計算機，這樣編譯方便移

21、植，稱為改變目標計算機，這樣編譯方便移植，稱為可變目標型編譯程序。可變目標型編譯程序。 青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)241.6 編譯技術(shù)和軟件工具編譯技術(shù)和軟件工具u語法制導編輯器語法制導編輯器 這類工具運用程序語言的語法知識，在用戶這類工具運用程序語言的語法知識，在用戶編寫程序的時候按照詞法和語法分析的信息編寫程序的時候按照詞法和語法分析的信息提供智能的幫助，包括自動地提供關鍵字及提供智能的幫助，包括自動地提供關鍵字及其匹配的關鍵字、左右括號的配對、對象的其匹配的關鍵字、左右括號的配對、對象的屬性和操作，等等。屬性和操作，等等。 u程序調(diào)試工具程序調(diào)試

22、工具 調(diào)試的目的是根據(jù)程序的異常，追蹤和確定調(diào)試的目的是根據(jù)程序的異常，追蹤和確定錯誤在程序中的具體位置，并且修改程序，錯誤在程序中的具體位置，并且修改程序，消除錯誤。消除錯誤。 青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)251.6 編譯技術(shù)和軟件工具編譯技術(shù)和軟件工具u程序測試工具程序測試工具 程序測試是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程，程序測試是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程，基于編譯技術(shù)的測試輔助工具可以分為靜態(tài)基于編譯技術(shù)的測試輔助工具可以分為靜態(tài)分析器和動態(tài)測試工具。分析器和動態(tài)測試工具。u程序理解工具程序理解工具 在軟件測試、軟件維護以及軟件的再向工程在軟件測試

23、、軟件維護以及軟件的再向工程和逆向工程等工作中，需要人們理解和分析和逆向工程等工作中，需要人們理解和分析程序，得到需要的軟件信息，這類工具稱為程序，得到需要的軟件信息，這類工具稱為程序理解工具。程序理解工具。 青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)261.7 如何開發(fā)編譯程序如何開發(fā)編譯程序 u手工編寫編譯程序手工編寫編譯程序 u編譯程序的自動生成技術(shù)編譯程序的自動生成技術(shù) u編譯程序的自展技術(shù) Ln=LL0L1.青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)271.7 如何開發(fā)編譯程序如何開發(fā)編譯程序 u編譯程序的移植技術(shù)編譯程序的移植技術(shù)用宿主計算機上的高級語言編寫一個能在另用宿主計算機上的高級語言編寫一個能在另外類型目標機上運行的編譯程序外類型目標機上運行的編譯程序 A BHH KMA BK圖1.7 把機器H上的編譯移植到機器K上 青島大學信息工程學院青島大學信息工程學院編譯原理與技術(shù)編譯原理與技術(shù)281.7 編譯系統(tǒng)以及其它相關程序編譯系統(tǒng)以及其它相關程序 編譯系統(tǒng) 預處理器源程序 編輯器 修改后的源程序 匯編程序 可重定位的目標程序 可執(zhí)行的目標程序 函數(shù)庫 可重定位的目標文件 連接器與加載器特性器調(diào)試器解釋器配置與版本控制器源程序 匯編器編譯器 源程序 青島大學信息