編譯原理與技術講義-第1章.ppt

青島大學信息工程學院 編譯原理與技術 第1章概論 編譯原理與技術 2 主要內(nèi)容 為什么學習編譯什么叫編譯程序編譯過程概述編譯程序的構成與編譯有關的概念和技術如何開發(fā)編譯程序編譯系統(tǒng)以及其它相關程序 編譯原理與技術 3 1 1為什么學習編譯 編譯程序構造的原理和技術一直屬于計算機科學必備的專業(yè)基礎知識 是計算機科學中一個非常成功的分支 也是最早獲得成功的分支之一 它所建立的理論 技術和方法值得深入研究和學習 編譯構造正確地建立了研究的問題領域和研究方式 編譯原理與技術 4 1 1為什么學習編譯 針對編譯程序構造的某些部分已經(jīng)開發(fā)了標準的形式化技術 包括有限自動機理論 上下文無關文法 正規(guī)表達式 屬性文法 機器代碼描述 數(shù)據(jù)流分析方程式等 編譯程序包含許多普遍使用的數(shù)據(jù)結構和算法 例如散列法 哈希算法 棧機制 堆機制 垃圾收集 集合算法 表驅(qū)動算法 編譯程序的許多構造技術已經(jīng)得到了廣泛的應用 學習編譯原理和技術還有助于我們理解程序設計語言 編寫優(yōu)秀的軟件 編譯原理與技術 5 1 2什么叫編譯程序 概念翻譯程序或翻譯器是把一種語言 源語言 轉換成等價的另外一種語言 目標語言 的程序 如果源語言是高級編程語言 目標語言是機器代碼和匯編語言這樣的低級語言 這類翻譯程序就叫做編譯程序或編譯器 編譯原理與技術 6 1 2什么叫編譯程序 編譯執(zhí)行方式 把源程序用編譯程序翻譯成機器可以執(zhí)行的目標程序或目標代碼 然后才能接受輸入數(shù)據(jù)運行 編譯程序 源程序 輸入數(shù)據(jù) 目標程序 計算機系統(tǒng) 目標程序 運行結果 編譯原理與技術 7 1 2什么叫編譯程序 解釋程序 解釋程序不產(chǎn)生源程序的目標代碼 而是對源程序逐條語句的分析 根據(jù)每個語句的含義執(zhí)行產(chǎn)生結果 解釋程序 輸入數(shù)據(jù) 源程序 計算機系統(tǒng) 運行結果 編譯原理與技術 8 1 3編譯過程概述 詞法分析詞法分析的任務是逐步地掃描和分解構成源程序的字符串 識別出一個一個的單詞符號或符號 編譯程序的詞法分析也叫詞法掃描或線性掃描 計算機高級語言的單詞符號通常包括 標識符 關鍵字或基本字 標點符號 常數(shù) 運算符 分隔符等類型 編譯原理與技術 9 1 3編譯過程概述 例子1 1 while i 100 sum sum i詞法分析的結果識別出的單詞 編譯原理與技術 10 1 3編譯過程概述 語法分析語法分析的任務是在詞法分析基礎上 根據(jù)語言的語法規(guī)則把單詞符號串分解成各類語法單元 語法范疇 語法短語 例如 短語 子句 語句 程序段 函數(shù) 和 程序 等 語法分析是把線形序列的單詞符號 根據(jù)語言的語法規(guī)則 按照層次分解 結果通常表示成語法分析樹 編譯原理與技術 11 1 3編譯過程概述 例子1 1while i 100 sum sum i語法分析樹 編譯原理與技術 12 1 3編譯過程概述 語義分析和中間代碼生成語義分析的任務是檢查程序語義的正確性 解釋程序結構的含義 檢查變量是否有定義 變量在使用前是否具有值 數(shù)值是否溢出等 其中的一個重要部分是進行類型的檢查和轉換 語義分析完成之后 編譯程序通常就依據(jù)語言的語義規(guī)則 利用語法制導技術把源程序翻譯成某種中間代碼 編譯原理與技術 13 1 3編譯過程概述 中間代碼是一種定義明確 便于處理 獨立于計算機硬件的記號系統(tǒng) 可以認為是一種抽象機的程序 其中一類是三地址代碼 很象機器的匯編語言 Lbegin ifi 100gotoLbodygotoLendLbody t1 sum isum t1t2 i 1i t2gotoLbeginLend 編譯原理與技術 14 1 3編譯過程概述 中間代碼優(yōu)化主要任務是對前一階段產(chǎn)生的中間代碼進行等價變換 以便產(chǎn)生速度快 空間小的目標代碼 Lbegin ifi 100gotoLbodygotoLendLbody sum sum ii i 1gotoLbeginLend 編譯原理與技術 15 1 3編譯過程概述 目標代碼生成目標代碼生成的主要任務是把 經(jīng)過優(yōu)化處理的 中間代碼翻譯成特定的機器指令或匯編程序 這個階段的工作依賴于計算機的硬件結構和指令系統(tǒng) 主要涉及到機器指令的選擇 各種類型變量存儲空間的分配 以及寄存器的分配和調(diào)度 等等 編譯原理與技術 16 1 3編譯過程概述 目標代碼生成 MOV 100 R0 把常數(shù)100存入寄存器R0MOVi R1 把變量i的值存入寄存器R1MOVsum R2 把變量m的值存入寄存器R2Lbegin CMPR1 R0 比較R1和R0的值 結果存入狀態(tài)寄存器CTJ Lend 狀態(tài)寄存器CT 1或2 即R1 R0 程序轉入單元LendADDR1 R2 把寄存器R1加R2 結果送入R2INCR1 寄存器R1的值加1JLbegin 無條件轉移到地址LbeginLend 編譯原理與技術 17 1 4編譯程序的構成 符號表管理 錯誤處理 詞法分析器 語法分析器 語義分析與中間代碼生器 代碼優(yōu)化器 目標代碼生成器 目標代碼 單詞符號 源程序 語法單元 中間代碼 中間代碼 編譯原理與技術 18 1 4編譯程序的構成 基本功能 詞法分析器 又叫掃描器 對輸入的源程序執(zhí)行詞法分析工作 輸出單詞符號序列 語法分析器 又叫分析器 對單詞符號序列進行語法分析 識別出各類語法單元 判斷輸入的符號串是否構成語法正確的 程序 語義分析與中間代碼生成器 對語法正確的各類程序單元進行語義分析 并把它們翻譯成一定形式的中間代碼 代碼優(yōu)化器 執(zhí)行對中間代碼的優(yōu)化處理 以提高代碼的執(zhí)行效率 目標代碼生成器 根據(jù)特定的機器把中間代碼翻譯成目標代碼 并進行優(yōu)化處理 編譯原理與技術 19 1 4編譯程序的構成 輔助功能 符號表管理 把編譯程序中的各種符號合理地組織和管理 方便符號信息的添加 查詢 更新和刪除 錯誤診斷和報告 有效地識別 診斷 分析和報告程序中的各種錯誤 分類 語法錯誤 詞法錯誤和句法錯誤 和語義錯誤這兩類 編譯原理與技術 20 1 5其它與編譯有關的概念和技術 遍 趟 在編譯的具體實現(xiàn)時 往往根據(jù)不同的源語言 設計要求 使用對象以及編譯程序所在宿主機的內(nèi)存等硬件條件 將編譯過程組織為若干遍 趟 一個編譯程序最終經(jīng)過幾遍完成 就稱為幾遍編譯 編譯原理與技術 21 1 5其它與編譯有關的概念和技術 編譯的前端和后端編譯前端只依賴于源程序 獨立于目標計算機 編譯前端的工作包括詞法分析 語法分析 語義分析 中間代碼生成及其優(yōu)化 文法錯誤的處理和符號表的組織也在編譯前端完成 編譯后端的工作主要是目標代碼的生成和優(yōu)化 獨立于源程序 完全依賴于目標機器和中間代碼 把編譯程序分成前端和后端已經(jīng)成為目前編譯程序的設計實踐 其顯著優(yōu)點是 可以優(yōu)化配置不同的編譯程序組合 實現(xiàn)編譯的重用 保持語言與機器的獨立性 編譯原理與技術 22 1 5其它與編譯有關的概念和技術 編譯程序的分類診斷型編譯程序 專門用于幫助程序的開發(fā)和調(diào)試 它們系統(tǒng)地分析程序 發(fā)現(xiàn)程序中的錯誤 智能地校正一些錯誤 優(yōu)化型編譯程序 這類編譯程序著重于提高目標代碼的時空效率 使得產(chǎn)生的目標代碼既占用較少的存儲空間 又運行的快 編譯原理與技術 23 1 5其它與編譯有關的概念和技術 交叉型編譯程序 運行目標程序的計算機和運行編譯程序的計算機的型號不相同 利用編譯前端和后端的技術 可以設計與目標機無關的編譯程序 利用編譯后端就可以改變目標計算機 這樣編譯方便移植 稱為可變目標型編譯程序 編譯原理與技術 24 1 6編譯技術和軟件工具 語法制導編輯器這類工具運用程序語言的語法知識 在用戶編寫程序的時候按照詞法和語法分析的信息提供智能的幫助 包括自動地提供關鍵字及其匹配的關鍵字 左右括號的配對 對象的屬性和操作 等等 程序調(diào)試工具調(diào)試的目的是根據(jù)程序的異常 追蹤和確定錯誤在程序中的具體位置 并且修改程序 消除錯誤 編譯原理與技術 25 1 6編譯技術和軟件工具 程序測試工具程序測試是為了發(fā)現(xiàn)錯誤而執(zhí)行程序的過程 基于編譯技術的測試輔助工具可以分為靜態(tài)分析器和動態(tài)測試工具 程序理解工具在軟件測試 軟件維護以及軟件的再向工程和逆向工程等工作中 需要人們理解和分析程序 得到需要的軟件信息 這類工具稱為程序理解工具 編譯原理與技術 26 1 7如何開發(fā)編譯程序 手工編寫編譯程序編譯程序的自動生成技術編譯程序的自展技術 編譯原理與技術 27 1 7如何開發(fā)編譯程序 編譯程序的移植技術用宿主計算機上的高級語言編寫一個能在另外類型目標機上運行的編譯程序 AB H HK M AB K 圖1 7把機器H上的編譯移植到機器K上 編譯原理與技術 28 1 7編譯系統(tǒng)以及其它相關程序 編譯系統(tǒng) 預處理器 源程序 編輯器 修改后的源程序 匯編程序 可重定位的目標程序 可執(zhí)行的目標程序 函數(shù)庫 可重定位的目標文件 連接器與加載器 特性器 調(diào)試器 解釋器 配置與版本控制器 源程序 匯編器 編譯器 源程序 編譯原理與技術 29 1 7編譯系統(tǒng)以及其它相關程序 編輯器 程序員借助編輯器編寫源程序 由編輯器產(chǎn)生出標準的正文文件 如ASCII文件 作為編譯程序的輸入 預處理器 它是在編譯程序真正開始翻譯源程序之前調(diào)用的一個獨立的程序 以便加快和簡化翻譯工作 匯編器 匯編器把匯編語言代碼翻譯成一個特定的機器指令序列 連接器 搜集和組織程序所需要的不同代碼和數(shù)據(jù) 把它們連接成可以執(zhí)行的