編譯原理引論

1、武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌編譯原理編譯原理課程簡介課程簡介 總學(xué)時：總學(xué)時：64 學(xué)時學(xué)時 其中含實驗：其中含實驗：12學(xué)時學(xué)時 主講：陳天煌主講：陳天煌 聯(lián)系電話：聯(lián)系電話漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌課程內(nèi)容課程內(nèi)容 v 詳細(xì)介紹程序設(shè)計語言的編譯程序構(gòu)造的一般詳細(xì)介紹程序設(shè)計語言的編譯程序構(gòu)造的一般原理和基本實現(xiàn)方法原理和基本實現(xiàn)方法v 重點介紹形式語言和自動機(jī)理論、重點介紹形式語言和自動機(jī)理論、 語法分析方法、語法分析方法、 屬性文法、屬性文法、 語法制導(dǎo)方法等理論知識語法制導(dǎo)方法等理論知識武漢理工

2、大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌課程要求課程要求v目標(biāo)：師生共同努力，學(xué)懂弄通目標(biāo)：師生共同努力，學(xué)懂弄通v本課程自學(xué)難度大，講課進(jìn)展較快，如果平本課程自學(xué)難度大，講課進(jìn)展較快，如果平時不復(fù)習(xí)并加深理解，后面將聽不懂，時不復(fù)習(xí)并加深理解，后面將聽不懂，必須必須不缺課不缺課v作業(yè)、上機(jī)實驗要求獨立完成作業(yè)、上機(jī)實驗要求獨立完成v學(xué)期總評學(xué)期總評 = = 考試成績占考試成績占70%70%，平時成績占，平時成績占30%30%武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌學(xué)習(xí)要求學(xué)習(xí)要求 編譯系統(tǒng)是現(xiàn)代計算機(jī)系統(tǒng)的基本組成之一，編譯系統(tǒng)是現(xiàn)代計算機(jī)系統(tǒng)的基本組成之一，

3、編譯程序構(gòu)造的基本原理和實現(xiàn)技術(shù)不僅應(yīng)用于編編譯程序構(gòu)造的基本原理和實現(xiàn)技術(shù)不僅應(yīng)用于編譯程序的設(shè)計，也廣泛應(yīng)用于一般軟件的設(shè)計和實譯程序的設(shè)計，也廣泛應(yīng)用于一般軟件的設(shè)計和實現(xiàn)。本課程是計算機(jī)類專業(yè)的一門重要的核心專業(yè)現(xiàn)。本課程是計算機(jī)類專業(yè)的一門重要的核心專業(yè)課。課。先修課程：先修課程： 高級程序設(shè)計語言、匯編語言、離散數(shù)學(xué)、高級程序設(shè)計語言、匯編語言、離散數(shù)學(xué)、 數(shù)據(jù)結(jié)構(gòu)、計算機(jī)組成原理數(shù)據(jù)結(jié)構(gòu)、計算機(jī)組成原理要求：要求：提前預(yù)習(xí)，上課認(rèn)真聽講；提前預(yù)習(xí)，上課認(rèn)真聽講； 課后即時復(fù)習(xí)，認(rèn)真完成作業(yè)。課后即時復(fù)習(xí)，認(rèn)真完成作業(yè)。 武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌

4、學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo) 通過本課程的學(xué)習(xí)，旨在使同學(xué)們掌握程序設(shè)計通過本課程的學(xué)習(xí)，旨在使同學(xué)們掌握程序設(shè)計語言的形式化描述和編譯的基本理論、原理和技術(shù)，語言的形式化描述和編譯的基本理論、原理和技術(shù)，并對編譯程序有較為具體的認(rèn)識。使同學(xué)們能運用所并對編譯程序有較為具體的認(rèn)識。使同學(xué)們能運用所學(xué)過的基本知識、著手開發(fā)系統(tǒng)程序，為今后的工作學(xué)過的基本知識、著手開發(fā)系統(tǒng)程序，為今后的工作（理論研究和技術(shù)開發(fā)）打下基礎(chǔ)。（理論研究和技術(shù)開發(fā)）打下基礎(chǔ)。具體為：具體為：（1 1）掌握編譯）掌握編譯( (翻譯翻譯) )程序基本結(jié)構(gòu)及構(gòu)造的基本原程序基本結(jié)構(gòu)及構(gòu)造的基本原理和技術(shù)；理和技術(shù)；（2 2）掌握文法、形

5、式語言及自動機(jī)的基本概念和在）掌握文法、形式語言及自動機(jī)的基本概念和在編譯程序構(gòu)造中的應(yīng)用；編譯程序構(gòu)造中的應(yīng)用；武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌（3 3）掌握典型的幾種語法分析方法的基本原理）掌握典型的幾種語法分析方法的基本原理和實現(xiàn)方法；和實現(xiàn)方法；（4 4）掌握屬性文法及語法制導(dǎo)方法在語義分析）掌握屬性文法及語法制導(dǎo)方法在語義分析中的應(yīng)用和中間代碼生成方法以及計算機(jī)程中的應(yīng)用和中間代碼生成方法以及計算機(jī)程序的自動構(gòu)造或生成原理與方法；序的自動構(gòu)造或生成原理與方法；（5 5）掌握存儲分配的基本思想和實現(xiàn)方法；）掌握存儲分配的基本思想和實現(xiàn)方法；（6 6）掌握代碼

6、優(yōu)化及代碼生成的方法；）掌握代碼優(yōu)化及代碼生成的方法；（7 7）強(qiáng)調(diào)形式化描述技術(shù)）強(qiáng)調(diào)形式化描述技術(shù)（8 8）強(qiáng)調(diào)對編譯原理和技術(shù)的宏觀理解，不把）強(qiáng)調(diào)對編譯原理和技術(shù)的宏觀理解，不把注意力分散到枝節(jié)算法，不偏向于某種源語注意力分散到枝節(jié)算法，不偏向于某種源語言或目標(biāo)機(jī)器言或目標(biāo)機(jī)器 武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌參考資料參考資料 教材：教材：1 1 編譯原理（第編譯原理（第2版）版） 主編：張素琴等主編：張素琴等 出版社：清華大學(xué)出版社出版社：清華大學(xué)出版社 出版時間：出版時間：2012年年7月月參考書：參考書：11程序設(shè)計語言編譯原理（第程序設(shè)計語言編譯原理

7、（第3版）版） 主編：陳火旺、劉春林、譚慶平、趙克佳、劉越主編：陳火旺、劉春林、譚慶平、趙克佳、劉越 出版社：國防工業(yè)出版社出版社：國防工業(yè)出版社 出版時間：出版時間：2014年年1月月22編譯程序構(gòu)造原理和實現(xiàn)技術(shù)編譯程序構(gòu)造原理和實現(xiàn)技術(shù) 主編：金成植主編：金成植 出版社：高等教育出版社出版社：高等教育出版社 出版時間：出版時間：2011年年6月月33編譯原理編譯原理（第（第3版）版） 主編：何炎祥主編：何炎祥 出版社：華中科技大學(xué)出版社出版社：華中科技大學(xué)出版社 出版時間：出版時間：20102010年年8 8月月武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌參考資料參考資料

8、4 4 編譯原理技術(shù)與工具（英文版）編譯原理技術(shù)與工具（英文版） Compilers:Principles,Techniques,and Tools 主編：主編：Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman 出版社：出版社：機(jī)械工業(yè)機(jī)械工業(yè)出版社出版社 出版時間：出版時間：2009年年2月月 5 5 編譯原理與技術(shù)編譯原理與技術(shù)（第二版）（第二版） 主編：陳意云主編：陳意云 出版社：中國科學(xué)技術(shù)大學(xué)出版社出版社：中國科學(xué)技術(shù)大學(xué)出版社 出版時間：出版時間：2012年年1月月66編譯原理及編譯程序構(gòu)造編譯原理及編譯程序構(gòu)造 主編：高仲儀、金茂忠主編：高仲儀、金

9、茂忠 出版社：北京航空航天大學(xué)出版社出版社：北京航空航天大學(xué)出版社 出版時間：出版時間：20112011年年3 3月月77編譯原理實踐與指導(dǎo)教程編譯原理實踐與指導(dǎo)教程 主編：主編：許暢許暢 出版社：出版社：機(jī)械工業(yè)機(jī)械工業(yè)出版社出版社 出版時間：出版時間：20152015年年6 6月月武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌第第1 1章章 引論引論 本章主要內(nèi)容：本章主要內(nèi)容： v什么是編譯程序什么是編譯程序v編譯過程和編譯程序的結(jié)構(gòu)編譯過程和編譯程序的結(jié)構(gòu)v為什么要學(xué)習(xí)編譯程序為什么要學(xué)習(xí)編譯程序 本章的重點：本章的重點： 本章沒有難以理解的內(nèi)容本章沒有難以理解的內(nèi)容,

10、,主主要是對編譯程序的功能和結(jié)構(gòu)做一要是對編譯程序的功能和結(jié)構(gòu)做一綜合描述綜合描述武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌1.1 1.1 什么叫編譯程序什么叫編譯程序 u 高級語言編譯程序是計算機(jī)系統(tǒng)軟件最重要的組高級語言編譯程序是計算機(jī)系統(tǒng)軟件最重要的組成部分之一，也是用戶最直接關(guān)心的工具之一。成部分之一，也是用戶最直接關(guān)心的工具之一。u 要在計算機(jī)上執(zhí)行用高級語言（或匯編語言）編要在計算機(jī)上執(zhí)行用高級語言（或匯編語言）編寫的程序，必須通過特定的途徑來進(jìn)行，也就是要通寫的程序，必須通過特定的途徑來進(jìn)行，也就是要通過翻譯程序把用高級語言（或匯編語言）編寫的程序過翻譯程序把用

11、高級語言（或匯編語言）編寫的程序翻譯翻譯成為機(jī)器語言構(gòu)成的程序，計算機(jī)才能執(zhí)行。成為機(jī)器語言構(gòu)成的程序，計算機(jī)才能執(zhí)行。 武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌在計算機(jī)上執(zhí)行一個高級語言程序一在計算機(jī)上執(zhí)行一個高級語言程序一般要分為兩步：般要分為兩步：第一步，用一個編譯程序把高級語言第一步，用一個編譯程序把高級語言翻譯成機(jī)器語言程序；翻譯成機(jī)器語言程序；第二步，運行所得的機(jī)器語言程序求第二步，運行所得的機(jī)器語言程序求得計算結(jié)果。得計算結(jié)果。 武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌1 1翻譯程序（翻譯程序（TranslatorTranslator） 通

12、常所說的翻譯程序是指這樣的一個程序，它通常所說的翻譯程序是指這樣的一個程序，它能夠把某一種語言程序（稱為能夠把某一種語言程序（稱為源語言程序或源程序源語言程序或源程序）轉(zhuǎn)換成另一種語言程序（稱為轉(zhuǎn)換成另一種語言程序（稱為目標(biāo)語言程序或目標(biāo)目標(biāo)語言程序或目標(biāo)程序程序），而后者與前者在邏輯上是等價的。），而后者與前者在邏輯上是等價的。 源程序源程序翻譯程序翻譯程序目標(biāo)程序目標(biāo)程序輸入輸入輸出輸出圖圖1.1 翻譯程序翻譯程序 翻譯程序根據(jù)所處理的對象和實現(xiàn)的途徑不同又分為：翻譯程序根據(jù)所處理的對象和實現(xiàn)的途徑不同又分為：匯編程序、編譯程序和解釋程序。匯編程序、編譯程序和解釋程序。 武漢理工大學(xué)計算機(jī)

13、科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌2. 2. 匯編程序（匯編程序（AssemblerAssembler） 如果源語言是某種匯編語言，而目標(biāo)語言是某種計如果源語言是某種匯編語言，而目標(biāo)語言是某種計算機(jī)的機(jī)器語言，這樣的一個翻譯程序就稱為匯編程算機(jī)的機(jī)器語言，這樣的一個翻譯程序就稱為匯編程序。序。源程序源程序（匯編語言）（匯編語言）翻譯程序翻譯程序（匯編程序）（匯編程序）目標(biāo)程序目標(biāo)程序（機(jī)器語言）（機(jī)器語言）輸入輸入輸出輸出圖圖1.2 匯編程序匯編程序武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌3. 3. 編譯程序（編譯程序（CompilerCompiler） 如果源語言

14、是某種高級語言，而目標(biāo)語言是某種如果源語言是某種高級語言，而目標(biāo)語言是某種低級語言（匯編語言或機(jī)器語言），這樣的一個翻譯低級語言（匯編語言或機(jī)器語言），這樣的一個翻譯程序就稱為編譯程序。程序就稱為編譯程序。 源程序源程序（高級語言）（高級語言）翻譯程序翻譯程序（編譯程序）（編譯程序）目標(biāo)程序目標(biāo)程序（低級語言）（低級語言）圖圖1.3 編譯程序編譯程序輸入輸入輸出輸出武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌4. 4. 解釋程序（解釋程序（Interpreter） 這是另外一種類型的翻譯程序，在翻譯過程它按這是另外一種類型的翻譯程序，在翻譯過程它按照高級語言源程序在計算機(jī)上執(zhí)行

15、的動態(tài)順序?qū)υ闯陶崭呒壵Z言源程序在計算機(jī)上執(zhí)行的動態(tài)順序?qū)υ闯绦虻恼Z句逐條翻譯（解釋），邊解釋邊執(zhí)行直至結(jié)束，序的語句逐條翻譯（解釋），邊解釋邊執(zhí)行直至結(jié)束，它不產(chǎn)生目標(biāo)程序，它的工作結(jié)果就是源程序的執(zhí)行它不產(chǎn)生目標(biāo)程序，它的工作結(jié)果就是源程序的執(zhí)行結(jié)果，這樣的一個翻譯程序就稱為解釋程序。結(jié)果，這樣的一個翻譯程序就稱為解釋程序。 源程序源程序（高級語言）（高級語言）翻譯程序翻譯程序（解釋程序）（解釋程序）計算結(jié)果計算結(jié)果輸入輸入輸出輸出圖圖1.4 解釋程序解釋程序初始數(shù)據(jù)初始數(shù)據(jù)武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌 本課程將不對解釋程序作專門的討論。實際上，本課程將不對

16、解釋程序作專門的討論。實際上，許多編譯程序的構(gòu)造與實現(xiàn)技術(shù)同樣適用于解釋程序。許多編譯程序的構(gòu)造與實現(xiàn)技術(shù)同樣適用于解釋程序。 武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌 世界上第一個編譯程序世界上第一個編譯程序FORTRAN編譯程序是編譯程序是20世紀(jì)世紀(jì)50年代中期研制成功的。年代中期研制成功的。 本課程主要介紹設(shè)計和構(gòu)造編譯程序的基本原理本課程主要介紹設(shè)計和構(gòu)造編譯程序的基本原理和方法。我們不想羅列太多細(xì)節(jié)性的材料，著重講一和方法。我們不想羅列太多細(xì)節(jié)性的材料，著重講一些原理性的東西，但將反映一些最新的進(jìn)展。些原理性的東西，但將反映一些最新的進(jìn)展。武漢理工大學(xué)計算機(jī)科學(xué)

17、系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌1.2 1.2 編譯過程概述編譯過程概述 編譯程序的工作，從輸入源程序開始到輸出目標(biāo)程編譯程序的工作，從輸入源程序開始到輸出目標(biāo)程序為止的整個過程，是非常復(fù)雜的。但就其過程而言，序為止的整個過程，是非常復(fù)雜的。但就其過程而言，它與人們進(jìn)行自然語言之間的翻譯有許多相近之處。它與人們進(jìn)行自然語言之間的翻譯有許多相近之處。當(dāng)我們把一種文字翻譯為另一種文字，例如把一段英當(dāng)我們把一種文字翻譯為另一種文字，例如把一段英文翻譯為中文時，通常需經(jīng)下列步驟：文翻譯為中文時，通常需經(jīng)下列步驟：（1）識別出句子中的一個個單詞；）識別出句子中的一個個單詞；（2）分析句子的語法結(jié)構(gòu)

18、；）分析句子的語法結(jié)構(gòu)；（3）根據(jù)句子的含義進(jìn)行初步翻譯；）根據(jù)句子的含義進(jìn)行初步翻譯；（4）對譯文進(jìn)行修飾；）對譯文進(jìn)行修飾；（5）寫出最后的譯文。）寫出最后的譯文。 武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌第一階段，詞法分析第一階段，詞法分析 詞法分析的任務(wù)是詞法分析的任務(wù)是： 輸入源程序，對構(gòu)成源程序的字符串進(jìn)行掃描輸入源程序，對構(gòu)成源程序的字符串進(jìn)行掃描和分解，識別出一個個的單詞和分解，識別出一個個的單詞（亦稱單詞符號或簡（亦稱單詞符號或簡稱符號），如基本字（稱符號），如基本字（beginbegin、endend、ifif、forfor、whilewhile等），標(biāo)

19、識符、常數(shù)算符和界符（標(biāo)點符號、等），標(biāo)識符、常數(shù)算符和界符（標(biāo)點符號、左右括號等等）。左右括號等等）。 類似地，編譯程序的工作過程一般也可以劃分類似地，編譯程序的工作過程一般也可以劃分為五個階段：詞法分析、語法分析、語義分析與中為五個階段：詞法分析、語法分析、語義分析與中間代碼產(chǎn)生、優(yōu)化、目標(biāo)代碼生成。間代碼產(chǎn)生、優(yōu)化、目標(biāo)代碼生成。 武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌例如，對于例如，對于PascalPascal語言語言的循環(huán)語句：的循環(huán)語句：for I:for I:1 to 100 do A:=A+I1 to 100 do A:=A+I詞法分析的結(jié)果是識別出如下的

20、單詞符號：詞法分析的結(jié)果是識別出如下的單詞符號：基本字基本字 forfor標(biāo)識符標(biāo)識符 I I賦值號賦值號 : : = =整常數(shù)整常數(shù) 1 1基本字基本字 toto整常數(shù)整常數(shù) 100100基本字基本字 dodo這些單詞是組成上述這些單詞是組成上述Pascal語句的基本符號。語句的基本符號。武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌 單詞符號是語言的基本組成成分，是人們理單詞符號是語言的基本組成成分，是人們理解和編寫程序的基本要素。識別和理解這些要解和編寫程序的基本要素。識別和理解這些要素?zé)o疑也是翻譯的基礎(chǔ)。素?zé)o疑也是翻譯的基礎(chǔ)。 如同將英文翻譯成中文的情形一樣，如果你如同將

21、英文翻譯成中文的情形一樣，如果你對英語單詞不理解，那就談不上進(jìn)行正確的翻對英語單詞不理解，那就談不上進(jìn)行正確的翻譯。譯。 在詞法分析階段的工作中所依循的是語言的在詞法分析階段的工作中所依循的是語言的詞法規(guī)則（或稱構(gòu)詞規(guī)則）。描述詞法規(guī)則的詞法規(guī)則（或稱構(gòu)詞規(guī)則）。描述詞法規(guī)則的有效工具是正規(guī)式和有限自動機(jī)。有效工具是正規(guī)式和有限自動機(jī)。武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌第二階段，語法分析第二階段，語法分析 語法分析的任務(wù)是：語法分析的任務(wù)是： 在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把單詞符號串分解成各類語法單位（語法范疇），

22、如單詞符號串分解成各類語法單位（語法范疇），如“短語短語”、“子句子句”、“語句語句”、“程序段程序段”和和“程程序序”等。通過語法分析，等。通過語法分析，確定整個輸入串是否構(gòu)成語確定整個輸入串是否構(gòu)成語法上正確的法上正確的“程序程序”。 武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌語法分析所依循的是語言的語法規(guī)則。語法語法分析所依循的是語言的語法規(guī)則。語法規(guī)則通常用上下文無關(guān)文法描述。詞法分析是一規(guī)則通常用上下文無關(guān)文法描述。詞法分析是一種線性分析，而語法分析是一種層次結(jié)構(gòu)分析。種線性分析，而語法分析是一種層次結(jié)構(gòu)分析。例如，在很多語言中，符號串例如，在很多語言中，符號串 z

23、: :=X十十0.618*Y代表一個代表一個“賦值語句賦值語句”，而其中的，而其中的 X0.618*Y代表一個代表一個“算術(shù)表達(dá)式算術(shù)表達(dá)式”。因而，語法。因而，語法分析的任務(wù)就是識別分析的任務(wù)就是識別 X0.618*Y為算術(shù)表達(dá)式，為算術(shù)表達(dá)式，同時，識別上述整個符號串屬于賦值語句這個范同時，識別上述整個符號串屬于賦值語句這個范疇。疇。 武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌第三階段，語義分析與中間代碼產(chǎn)生第三階段，語義分析與中間代碼產(chǎn)生 這一階段的任務(wù)是：這一階段的任務(wù)是： 對語法分析所識別出的各類語法范疇，分析其含對語法分析所識別出的各類語法范疇，分析其含義，并進(jìn)行

24、初步翻譯（產(chǎn)生中間代碼）。義，并進(jìn)行初步翻譯（產(chǎn)生中間代碼）。 “翻譯翻譯”僅僅在這里才開始涉及到。所謂僅僅在這里才開始涉及到。所謂“中間中間代碼代碼”是一種含義明確、便于處理的記號系統(tǒng)，它是一種含義明確、便于處理的記號系統(tǒng)，它通常獨立于具體的硬件。這種記號系統(tǒng)或者與現(xiàn)代通常獨立于具體的硬件。這種記號系統(tǒng)或者與現(xiàn)代計算機(jī)的指令形式有某種程度的接近，或者能夠比計算機(jī)的指令形式有某種程度的接近，或者能夠比較容易地把它變換成現(xiàn)代計算機(jī)的機(jī)器指令。較容易地把它變換成現(xiàn)代計算機(jī)的機(jī)器指令。 武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌 例如，許多編譯程序采用了一種與例如，許多編譯程序采用

25、了一種與“三地址指令三地址指令”非常近似的非常近似的“四元式四元式”作為中間代碼。這種四元式作為中間代碼。這種四元式的形式是：的形式是： 算符算符 左操作數(shù)左操作數(shù) 右操作數(shù)右操作數(shù) 結(jié)果結(jié)果 它的意義是：對它的意義是：對“左、右操作數(shù)左、右操作數(shù)”進(jìn)行某種運進(jìn)行某種運算（由算（由“算符算符”指明），把運算所得的值作為指明），把運算所得的值作為“結(jié)結(jié)果果”保留下來。在采用四元式作為中間代碼的情形保留下來。在采用四元式作為中間代碼的情形下，中間代碼產(chǎn)生的任務(wù)就是按語言的語義規(guī)則把下，中間代碼產(chǎn)生的任務(wù)就是按語言的語義規(guī)則把各類語法成份翻譯成四元式序列。各類語法成份翻譯成四元式序列。武漢理工大學(xué)計

26、算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌例如，下面的賦值句例如，下面的賦值句Z: :（X0.418）*YW可被翻譯為如下的四元式序列：可被翻譯為如下的四元式序列： 序號序號 算符算符 左操作數(shù)左操作數(shù) 右操作數(shù)右操作數(shù) 結(jié)果結(jié)果 1 十十 X 0.418 T1 2 * T1 Y T2 3 T2 W Z 一般而言，中間代碼是一種獨立于具體硬件的一般而言，中間代碼是一種獨立于具體硬件的記號系統(tǒng)。記號系統(tǒng)。武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌第四階段，優(yōu)化第四階段，優(yōu)化 優(yōu)化的任務(wù)優(yōu)化的任務(wù): : 對前述階段產(chǎn)生的中間代碼進(jìn)行加工變換，以期對前述階段產(chǎn)生的中間代碼進(jìn)行加

27、工變換，以期在最后代碼生成階段能產(chǎn)生出更為高效（省時間和空在最后代碼生成階段能產(chǎn)生出更為高效（省時間和空間）的目標(biāo)代碼。間）的目標(biāo)代碼。 優(yōu)化的主要方面有：優(yōu)化的主要方面有： 公共子表達(dá)式提取、循環(huán)優(yōu)化、刪除無用代碼等公共子表達(dá)式提取、循環(huán)優(yōu)化、刪除無用代碼等等。等。優(yōu)化所依循的原則優(yōu)化所依循的原則: : 是程序的等價變換規(guī)則。是程序的等價變換規(guī)則。武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌第第五階段，目標(biāo)代碼生成五階段，目標(biāo)代碼生成這一階段的任務(wù)是：這一階段的任務(wù)是： 把中間代碼（或經(jīng)優(yōu)化處理之后）變換成特定把中間代碼（或經(jīng)優(yōu)化處理之后）變換成特定機(jī)器上的低級語言代碼。機(jī)器

28、上的低級語言代碼。 這階段實現(xiàn)了最后的翻譯，它的工作有賴于硬這階段實現(xiàn)了最后的翻譯，它的工作有賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義。這階段工作非常復(fù)雜，件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義。這階段工作非常復(fù)雜，涉及到硬件系統(tǒng)功能部件的運用，機(jī)器指令的選擇，涉及到硬件系統(tǒng)功能部件的運用，機(jī)器指令的選擇，各種數(shù)據(jù)類型變量的存儲空間分配，以及寄存器和后各種數(shù)據(jù)類型變量的存儲空間分配，以及寄存器和后援寄存器的調(diào)度，等等。如何產(chǎn)生出足以充分發(fā)揮硬援寄存器的調(diào)度，等等。如何產(chǎn)生出足以充分發(fā)揮硬件效率的目標(biāo)代碼是一件非常不容易的事情。件效率的目標(biāo)代碼是一件非常不容易的事情。 武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科

29、學(xué)系陳天煌 上述編譯過程的五個階段是一種典型的分法。上述編譯過程的五個階段是一種典型的分法。 事實上，并非所有編譯程序都分成這五階段。事實上，并非所有編譯程序都分成這五階段。 有些編譯程序?qū)?yōu)化沒有什么要求，優(yōu)化階段有些編譯程序?qū)?yōu)化沒有什么要求，優(yōu)化階段就可省去。在某些情況下，為了加快編譯速度，中就可省去。在某些情況下，為了加快編譯速度，中間代碼產(chǎn)生階段也可以去掉。間代碼產(chǎn)生階段也可以去掉。 有些最簡單的編譯程序是在語法分析的同時產(chǎn)有些最簡單的編譯程序是在語法分析的同時產(chǎn)生目標(biāo)代碼。但是，多數(shù)實用編譯程序的工作過程生目標(biāo)代碼。但是，多數(shù)實用編譯程序的工作過程大致都像上面所說的那五個階段。大致

30、都像上面所說的那五個階段。武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌1.3 1.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu) 1.3.1 1.3.1 編譯程序總框編譯程序總框 上述編譯過程的五個階段是編譯程序工作時的動上述編譯過程的五個階段是編譯程序工作時的動態(tài)特征。編譯程序的結(jié)構(gòu)可以按照這五階段的任務(wù)分態(tài)特征。編譯程序的結(jié)構(gòu)可以按照這五階段的任務(wù)分模塊進(jìn)行設(shè)計。圖模塊進(jìn)行設(shè)計。圖1.5給出了編譯程序總框。給出了編譯程序總框。 圖圖1.5 編譯程序總框編譯程序總框詞法分析器詞法分析器語法分析器語法分析器語義分析與中間代碼生成器語義分析與中間代碼生成器中間代碼優(yōu)化器中間代碼優(yōu)化器目標(biāo)代碼生

31、成器目標(biāo)代碼生成器表表格格管管理理出出錯錯處處理理目標(biāo)代碼程序目標(biāo)代碼程序源程序源程序單詞符號串單詞符號串語法單位語法單位中間代碼串中間代碼串中間代碼串中間代碼串武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌 詞法分析器，詞法分析器，又稱掃描器，輸入源程序，進(jìn)行又稱掃描器，輸入源程序，進(jìn)行詞法分析，輸出單詞符號。詞法分析，輸出單詞符號。 語法分析器，語法分析器，簡稱分析器，對單詞符號串進(jìn)行簡稱分析器，對單詞符號串進(jìn)行語法分析（根據(jù)語法規(guī)則進(jìn)行推導(dǎo)或歸約），識別語法分析（根據(jù)語法規(guī)則進(jìn)行推導(dǎo)或歸約），識別出各類語法單位，最終判斷輸入串是否構(gòu)成語法上出各類語法單位，最終判斷輸入串是否

32、構(gòu)成語法上正確的正確的“程序程序”。 語義分析與中間代碼產(chǎn)生器，語義分析與中間代碼產(chǎn)生器，按照語義規(guī)則按照語義規(guī)則對語法分析器歸約出（或推導(dǎo)出）的語法單位進(jìn)行對語法分析器歸約出（或推導(dǎo)出）的語法單位進(jìn)行語義分析并把它們翻譯成一定形式的中間代碼。語義分析并把它們翻譯成一定形式的中間代碼。 武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌中間代碼優(yōu)化器，中間代碼優(yōu)化器，對中間代碼進(jìn)行優(yōu)化處理。對中間代碼進(jìn)行優(yōu)化處理。 目標(biāo)代碼生成器，目標(biāo)代碼生成器，把中間代碼翻譯成目標(biāo)程序。把中間代碼翻譯成目標(biāo)程序。 除了上述五個功能模塊外，一個完整的編譯程序除了上述五個功能模塊外，一個完整的編譯程序

33、還應(yīng)包括還應(yīng)包括“表格管理表格管理”和和“出錯處理出錯處理”兩部分。兩部分。武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌1.3.2 1.3.2 表格與表格管理表格與表格管理 編譯程序在工作過程中需要保存一系列的表格，編譯程序在工作過程中需要保存一系列的表格，以登記源程序的各類信息和編譯各階段的進(jìn)展?fàn)顩r。以登記源程序的各類信息和編譯各階段的進(jìn)展?fàn)顩r。 合理地設(shè)計和使用表格是編譯程序構(gòu)造的一個重合理地設(shè)計和使用表格是編譯程序構(gòu)造的一個重要問題。要問題。 在編譯程序使用的表格中，最重要的是符號表。在編譯程序使用的表格中，最重要的是符號表。它用來登記源程序中出現(xiàn)的每個名字以及名字的各種

34、它用來登記源程序中出現(xiàn)的每個名字以及名字的各種屬性。屬性。 例如，一個名字是常量名、還是變量名、是過程例如，一個名字是常量名、還是變量名、是過程名等等；如果是變量名，它的類型是什么、所占內(nèi)存名等等；如果是變量名，它的類型是什么、所占內(nèi)存是多大、地址是多少等等。是多大、地址是多少等等。 武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌 通常，編譯程序在處理到名字的定義性出現(xiàn)時，通常，編譯程序在處理到名字的定義性出現(xiàn)時，要把名字的各種屬性填入到符號表中；當(dāng)處理到名要把名字的各種屬性填入到符號表中；當(dāng)處理到名字的使用性出現(xiàn)時，要對名字的屬性進(jìn)行查證。字的使用性出現(xiàn)時，要對名字的屬性進(jìn)行查

35、證。 當(dāng)掃描器識別出一個名字（標(biāo)識符）后，它把當(dāng)掃描器識別出一個名字（標(biāo)識符）后，它把該名字填入到符號表中。但這時不能完全確定名字該名字填入到符號表中。但這時不能完全確定名字的屬性，它的各種屬性要在后續(xù)的各階段才能填入。的屬性，它的各種屬性要在后續(xù)的各階段才能填入。例如，名字的類型等要在語義分析時才能確定，例如，名字的類型等要在語義分析時才能確定，而名字的地址可能要到目標(biāo)代碼生成才能確定。而名字的地址可能要到目標(biāo)代碼生成才能確定。由此可見，編譯各階段都涉及到構(gòu)造、查找或由此可見，編譯各階段都涉及到構(gòu)造、查找或更新有關(guān)的表格。更新有關(guān)的表格。 武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)

36、系陳天煌1.3.3 1.3.3 出錯處理出錯處理 一個編譯程序不僅應(yīng)能對書寫正確的程序進(jìn)行翻一個編譯程序不僅應(yīng)能對書寫正確的程序進(jìn)行翻譯，而且應(yīng)能對出現(xiàn)在源程序中的錯誤進(jìn)行處理。譯，而且應(yīng)能對出現(xiàn)在源程序中的錯誤進(jìn)行處理。 如果源程序有錯誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯誤，如果源程序有錯誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯誤，把有關(guān)錯誤信息報告給用戶。這部分工作是由專門的把有關(guān)錯誤信息報告給用戶。這部分工作是由專門的一組程序（叫做出錯處理程序）完成的。一組程序（叫做出錯處理程序）完成的。 一個好的編譯程序應(yīng)能最大限度地發(fā)現(xiàn)源程序中一個好的編譯程序應(yīng)能最大限度地發(fā)現(xiàn)源程序中的各種錯誤，準(zhǔn)確地指出錯誤的性質(zhì)和發(fā)生錯誤

37、的地的各種錯誤，準(zhǔn)確地指出錯誤的性質(zhì)和發(fā)生錯誤的地點，并且能將錯誤所造成的影響限制在盡可能小的范點，并且能將錯誤所造成的影響限制在盡可能小的范圍內(nèi)，使得源程序的其余部分能繼續(xù)被編譯下去，以圍內(nèi)，使得源程序的其余部分能繼續(xù)被編譯下去，以便進(jìn)一步發(fā)現(xiàn)其它可能的錯誤。便進(jìn)一步發(fā)現(xiàn)其它可能的錯誤。 如果不僅能夠發(fā)現(xiàn)錯誤，而且還能自動校正錯誤，如果不僅能夠發(fā)現(xiàn)錯誤，而且還能自動校正錯誤，那當(dāng)然就更好了。但是，自動校正錯誤的代價是非常那當(dāng)然就更好了。但是，自動校正錯誤的代價是非常高的。高的。 武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌 編譯過程的每一階段都可能檢測出錯誤，其中，編譯過程的

38、每一階段都可能檢測出錯誤，其中，絕大多數(shù)錯誤可以在編譯的前三階段檢測出來。絕大多數(shù)錯誤可以在編譯的前三階段檢測出來。 源程序中的錯誤通常分為語法錯誤和語義錯誤兩源程序中的錯誤通常分為語法錯誤和語義錯誤兩大類。大類。 語法錯誤語法錯誤是指源程序中不符合語法（或詞法）規(guī)是指源程序中不符合語法（或詞法）規(guī)則的錯誤，它們可在詞法分析或語法分析時檢測出來。則的錯誤，它們可在詞法分析或語法分析時檢測出來。 例如，詞法分析階段能夠檢測出例如，詞法分析階段能夠檢測出“非法字符非法字符”之之類的錯誤；語法分析階段能夠檢測出諸如類的錯誤；語法分析階段能夠檢測出諸如“括號不匹括號不匹配配”、“缺少；缺少；”之類的錯

39、誤。之類的錯誤。 武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌語義錯誤語義錯誤是指源程序中不符合語義規(guī)是指源程序中不符合語義規(guī)則的錯誤，這些錯誤一般在語義分析時檢則的錯誤，這些錯誤一般在語義分析時檢測出來，有的語義錯誤要在運行時才能檢測出來，有的語義錯誤要在運行時才能檢測出來。測出來。語義錯誤通常包括：說明錯誤、作用語義錯誤通常包括：說明錯誤、作用域錯誤、數(shù)組元素越界、類型不一致等等。域錯誤、數(shù)組元素越界、類型不一致等等。關(guān)于錯誤檢測和處理方法，我們將穿插在關(guān)于錯誤檢測和處理方法，我們將穿插在有關(guān)章節(jié)介紹。有關(guān)章節(jié)介紹。武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天

40、煌1.3.4 1.3.4 遍遍 前面介紹的編譯過程的五個階段僅僅是邏輯功能上前面介紹的編譯過程的五個階段僅僅是邏輯功能上的一種劃分。具體實現(xiàn)時，受不同源語言、設(shè)計要求、的一種劃分。具體實現(xiàn)時，受不同源語言、設(shè)計要求、使用對象和計算機(jī)條件（如主存容量）的限制，往往將使用對象和計算機(jī)條件（如主存容量）的限制，往往將編譯程序組織為若干編譯程序組織為若干遍（遍（Pass）。 所謂所謂“遍遍”就是對源程序或源程序的中間結(jié)果從就是對源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成新的中間頭到尾掃描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。結(jié)果或目標(biāo)程序。 通常，每遍的工作由從

41、外存上獲得的前一遍的中間通常，每遍的工作由從外存上獲得的前一遍的中間結(jié)果開始（對于第一遍而言，從外存上獲得源程序），結(jié)果開始（對于第一遍而言，從外存上獲得源程序），完成它所含的有關(guān)工作之后，再把結(jié)果記錄于外存。完成它所含的有關(guān)工作之后，再把結(jié)果記錄于外存。 既可以將幾個不同階段合為一遍，也可以把一個階既可以將幾個不同階段合為一遍，也可以把一個階段的工作分為若干遍。段的工作分為若干遍。 武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌武漢理工大學(xué)計算機(jī)科學(xué)系陳天煌 當(dāng)一遍中包含若干階段時，各階段的工作是穿插當(dāng)一遍中包含若干階段時，各階段的工作是穿插進(jìn)行的。例如，我們可以把詞法分析、語法分析及語進(jìn)行的。例如，我們可以把詞法分析、語法分析及語義分析與中間代碼產(chǎn)生這三階段安排成一遍。義分析與中間代碼產(chǎn)生這三階段安排成一遍。 這時，語法分析器處于核心位置，當(dāng)它在識別語這時，語法分析器處于核心位置，當(dāng)它在識別語法結(jié)構(gòu)而需要下一單詞符號時，它就調(diào)用詞法分析器，法結(jié)構(gòu)而需要下一單詞符號時，它就調(diào)用詞法分析器，一旦識別出一個語法單位時，它就調(diào)用中間代碼產(chǎn)生一旦識別出一個語法單位時，它就調(diào)用中間代碼產(chǎn)生器，完成相應(yīng)的語義分析并產(chǎn)生相應(yīng)的中間代碼。器，完