講義編譯原理

1、編譯原理汪志華 課程目標(biāo)編譯原理是計算機(jī)科學(xué)與技術(shù)專業(yè)與軟件工程專業(yè)的專業(yè)課。使學(xué)生學(xué)習(xí)并掌握設(shè)計和構(gòu)造編譯程序過程中所涉及的基本理論、基本方法和典型技術(shù)，具備分析、設(shè)計和實現(xiàn)編譯程序的基本能力為什么要學(xué)習(xí)編譯原理通過對本課程的學(xué)習(xí)，不僅可以掌握編譯程序本身的基本實現(xiàn)原理和技術(shù)，同時也有助于提高對程序設(shè)計語言的理解，提高語言設(shè)計及程序設(shè)計的能力。編譯程序構(gòu)造的基本原理、技術(shù)、方法對其他軟件的設(shè)計具有參考和借鑒的意義編譯原理課程蘊(yùn)含著計算機(jī)學(xué)科中解決問題的思路、抽象問題和解決問題的方法詞法分析器的串匹配技術(shù)-文本編輯器、信息檢索系統(tǒng)、模式識別器上下文無關(guān)文法、語法制導(dǎo)-排版、繪圖系統(tǒng)代碼優(yōu)化技術(shù)

2、-程序驗證器高級語言設(shè)計、計算機(jī)系統(tǒng)結(jié)構(gòu)的優(yōu)化（并行、內(nèi)存分層）、新型計算機(jī)系統(tǒng)結(jié)構(gòu)設(shè)計、程序翻譯、提高軟件開發(fā)效率的工具#include #include void func() char s4; strcpy(s,12345678); printf(%sn,s); int main() func(); printf(Return from funcn);return 0;編譯器技術(shù)的應(yīng)用高級語言的實現(xiàn)每一輪編程語言新特征的出現(xiàn)都刺激編譯器優(yōu)化的新研究針對計算機(jī)體系結(jié)構(gòu)的優(yōu)化并行化 編譯器重新整理指令，使得指令級并行更有效 編譯器從傳統(tǒng)的串行程序自動生成并行代碼，使之運(yùn)行于多處理器上內(nèi)存分層

3、新計算機(jī)體系結(jié)構(gòu)的設(shè)計現(xiàn)在計算機(jī)系統(tǒng)的性能不僅僅取決于它的原始速度，還取決于編譯器是否能生成充分利用其特征的代碼在現(xiàn)代計算機(jī)體系結(jié)構(gòu)的研究中，在處理器的設(shè)計階段就開發(fā)編譯器，并將編譯生成的代碼在模擬器上運(yùn)行，以評價擬采用體系結(jié)構(gòu)的特征程序翻譯二進(jìn)制翻譯數(shù)據(jù)庫查詢解釋器提高軟件開發(fā)效率的工具類型檢查類型檢查是一種捕捉程序中前后不一致的成熟并且有效的技術(shù)邊界檢查數(shù)據(jù)流分析技術(shù)可用來定位緩沖區(qū)溢出內(nèi)存管理自動的內(nèi)存管理刪除內(nèi)存泄漏等內(nèi)存管理錯誤編譯原理是計算機(jī)學(xué)科中較難的一門課程先修課程：程序設(shè)計語言、數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)、匯編語言涉及形式語言、有窮自動機(jī)等抽象內(nèi)容，理論性較強(qiáng)缺乏實踐，基本上沒有完成

4、一個完整的編譯程序的機(jī)會，所以難以深入 注意事項因為課時關(guān)系，講課會有所側(cè)重（重點：第2，3，4章）課后要注意復(fù)習(xí)，否則將很難理解講述的內(nèi)容作業(yè)要按時獨立完成參考書目龍書（Dragon book） 英文名：Compilers: Principles,Techniques,and Tools 作者：Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman 中文名：編譯原理技術(shù)和工具 (編譯原理)虎書（Tiger book） 英文名：Modern Compiler Implementation in C 作者：Andrew W.Appel,with Jens Palsber

5、g 中文名：現(xiàn)代編譯原理-C語言描述鯨書（Whale book） 英文名：Advanced Compiler Design and Implementation 作者：Steven S.Muchnick 中文名：高級編譯器設(shè)計與實現(xiàn) 第一章 引論翻譯器：能夠把一種語言的程序轉(zhuǎn)換成另一種語言的程序的軟件，而后者與前者在邏輯上是等價的。編譯器（編譯程序）：把某一種高級語言程序等價地轉(zhuǎn)換成另一種低級語言程序(如匯編語言或機(jī)器語言程序)的程序源語言翻譯器目標(biāo)語言1.1 編譯器概述英譯與編譯的比較識別出句子中的一個個單詞分析句子的語法結(jié)構(gòu)初步翻譯句子的含意譯文修飾寫出最后譯文詞法分析語法分析語義分析/中

6、間代碼生成優(yōu)化目標(biāo)代碼生成詞法分析器語法分析器語義分析器源程序中間代碼生成器獨立于機(jī)器的代碼優(yōu)化器代碼生成器依賴于機(jī)器的代碼優(yōu)化器目標(biāo)機(jī)器代碼符號表1.1.1 詞法分析任務(wù): 讀入源程序的字符流，按編程語言的詞法規(guī)則把它們組成詞法記號(token)流。描述工具：正規(guī)式和有限自動機(jī)（第二章）記號的表示：記號名是同類詞法單元共用的名稱屬性值是一個詞法單元有別于同類中其他詞法單元的特征值符 號 表 positioninitialrate. . . . . . .123詞法分析器id, 1 = id, 2 + id, 3 60position = initial + rate 601.1.2 語法分析

7、任務(wù):在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則把記號流構(gòu)造成各類語法單位。描述工具：上下文無關(guān)文法（第三章）中間表示：語法樹內(nèi)部結(jié)點表示運(yùn)算，子結(jié)點代表該運(yùn)算的運(yùn)算對象表達(dá)式的語法特征任何一個標(biāo)識符都是表達(dá)式任何一個數(shù)都是表達(dá)式如果e1和e2都是表達(dá)式，那么 e1 + e2 e1 * e2 (e1)也都是表達(dá)式表達(dá)式表達(dá)式表達(dá)式標(biāo)識符表達(dá)式表達(dá)式(initial)標(biāo)識符(rate)數(shù)(60)*+initial + rate * 60的分析樹符 號 表 positioninitialrate. . . . . . .123語法分析器id, 1 = id, 2 + id, 3 60=+60id, 1

8、id, 2id, 3 語法樹1.1.3 語義分析任務(wù)：使用語法樹和符號表中的信息，依據(jù)語言定義來檢查源程序的語義一致性，以保證程序各部分能有意義地結(jié)合在一起。它還收集類型信息，把它們保存在符號表或語法樹中依循的原則：語義規(guī)則描述工具：屬性文法（第四章）符 號 表 positioninitialrate. . . . . . .123語義分析器=+60id, 1id, 2id, 3=+inttorealid, 1id, 2id, 3601.1.4 中間代碼生成所謂“中間代碼”是一種含義明確，便于處理的記號系統(tǒng)，它通常獨立于具體的硬件。這種記號系統(tǒng)或者與現(xiàn)代計算機(jī)的指令形式有某種程度的接近，或者能

9、夠比較容易地把它變換成現(xiàn)代計算機(jī)的機(jī)器指令易于產(chǎn)生易于翻譯成目標(biāo)程序符 號 表 positioninitialrate. . . . . . .123中間代碼生成器t1 = inttoreal(60)t2 = id3 t1t3 = id2 + t2id1 = t3=+inttorealid, 1id, 2id, 3601.1.5 代碼優(yōu)化任務(wù)：對于前階段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段產(chǎn)生更高效的目標(biāo)代碼。注意：代碼優(yōu)化工作會降低編譯程序的編譯速度，因此編譯程序具有控制機(jī)制以允許用戶在編譯速度和目標(biāo)代碼的質(zhì)量間進(jìn)行權(quán)衡。符 號 表 positioninitialrate. . . .

10、 . . .123代碼優(yōu)化器t1 = inttoreal(60)t2 = id3 t1t3 = id2 + t2id1 = t3t1 = id3 * 60.0id1 = id2 + t11.1.6 代碼生成任務(wù)：把中間代碼（或經(jīng)優(yōu)化處理后）變換成目標(biāo)語言。關(guān)鍵問題：寄存器分配符 號 表 positioninitialrate. . . . . . .123代碼生成器MOVF id3, R2MULF #60.0, R2MOVF id2, R1ADDF R2, R1MOVF R1, id1t1 = id3 * 60.0id1 = id2 + t11.1.7 符號表管理符號表中記錄源程序中使用的名字和收集到的每個名字的各種屬性信息，諸如類型、作用域、分配存儲信息。如果是過程名字，還有參數(shù)的個數(shù)、類型 、參數(shù)傳遞方式和返回值類型等信息1.1.8 階段的分組詞法分析器語法分析器語義分析器源程序中間代碼生成器獨立于機(jī)器的代碼優(yōu)化器代碼生成器依賴于機(jī)