編譯原理清華大學(xué)導(dǎo)論

1、課程簡(jiǎn)介課程簡(jiǎn)介 總學(xué)時(shí)：總學(xué)時(shí)： 72學(xué)時(shí)學(xué)時(shí) 4.5學(xué)分學(xué)分 課堂教學(xué)：課堂教學(xué)： 52學(xué)時(shí)學(xué)時(shí) ； 課內(nèi)實(shí)驗(yàn)：課內(nèi)實(shí)驗(yàn)： 8學(xué)時(shí)學(xué)時(shí)課內(nèi)實(shí)踐：課內(nèi)實(shí)踐： 12學(xué)時(shí)學(xué)時(shí) 主講：林泓主講：林泓課程內(nèi)容課程內(nèi)容 v介紹編譯器構(gòu)造的一般原理和基本實(shí)現(xiàn)方法介紹編譯器構(gòu)造的一般原理和基本實(shí)現(xiàn)方法v理論知識(shí)：形式語(yǔ)言和自動(dòng)機(jī)理論、語(yǔ)法制導(dǎo)翻譯的定理論知識(shí)：形式語(yǔ)言和自動(dòng)機(jī)理論、語(yǔ)法制導(dǎo)翻譯的定義和屬性文法等義和屬性文法等v形式化描述技術(shù)形式化描述技術(shù)v對(duì)編譯原理和技術(shù)的宏觀理解，注意力無(wú)需分散到枝節(jié)對(duì)編譯原理和技術(shù)的宏觀理解，注意力無(wú)需分散到枝節(jié)算法，無(wú)需偏向于某種源語(yǔ)言或目標(biāo)機(jī)器算法，無(wú)需偏向于某種

2、源語(yǔ)言或目標(biāo)機(jī)器學(xué)習(xí)的意義學(xué)習(xí)的意義 v 對(duì)編程語(yǔ)言的設(shè)計(jì)和實(shí)現(xiàn)有深刻的理解，對(duì)和編程語(yǔ)言對(duì)編程語(yǔ)言的設(shè)計(jì)和實(shí)現(xiàn)有深刻的理解，對(duì)和編程語(yǔ)言有關(guān)的理論有所了解，對(duì)宏觀上把握編程語(yǔ)言來(lái)說，起有關(guān)的理論有所了解，對(duì)宏觀上把握編程語(yǔ)言來(lái)說，起一個(gè)奠基的作用。一個(gè)奠基的作用。v 從軟件工程看，編譯器是一個(gè)很好的實(shí)例，所介紹的概從軟件工程看，編譯器是一個(gè)很好的實(shí)例，所介紹的概念和技術(shù)能應(yīng)用到一般的軟件設(shè)計(jì)之中。念和技術(shù)能應(yīng)用到一般的軟件設(shè)計(jì)之中。v 大多數(shù)程序員同時(shí)是簡(jiǎn)單語(yǔ)言的設(shè)計(jì)者，有助于提高對(duì)大多數(shù)程序員同時(shí)是簡(jiǎn)單語(yǔ)言的設(shè)計(jì)者，有助于提高對(duì)這些語(yǔ)言的設(shè)計(jì)水平。這些語(yǔ)言的設(shè)計(jì)水平。v 在軟件逆向工程、軟

3、件的設(shè)計(jì)方法、程序理解和軟件安在軟件逆向工程、軟件的設(shè)計(jì)方法、程序理解和軟件安全等方面有著廣泛的應(yīng)用。全等方面有著廣泛的應(yīng)用。課程要求課程要求v講課進(jìn)展較快，平時(shí)要復(fù)習(xí)并加深理解。講課進(jìn)展較快，平時(shí)要復(fù)習(xí)并加深理解。v作業(yè)較多，要求獨(dú)立完成。作業(yè)較多，要求獨(dú)立完成。v實(shí)驗(yàn)和課內(nèi)實(shí)踐，每次驗(yàn)收檢查。實(shí)驗(yàn)和課內(nèi)實(shí)踐，每次驗(yàn)收檢查。v學(xué)期總評(píng)成績(jī)學(xué)期總評(píng)成績(jī) = = 考試成績(jī)考試成績(jī)60% + 60% + 平時(shí)成績(jī)平時(shí)成績(jī)40%40% 平時(shí)成績(jī)平時(shí)成績(jī)40% = 40% = 作業(yè)實(shí)驗(yàn)考勤作業(yè)實(shí)驗(yàn)考勤30% + 30% + 課內(nèi)實(shí)踐課內(nèi)實(shí)踐10%10% 編譯系統(tǒng)是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成之一，編譯程序

4、編譯系統(tǒng)是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成之一，編譯程序構(gòu)造的基本原理和技術(shù)不僅應(yīng)用于編譯程序的設(shè)計(jì)，也廣泛構(gòu)造的基本原理和技術(shù)不僅應(yīng)用于編譯程序的設(shè)計(jì)，也廣泛應(yīng)用于一般軟件的設(shè)計(jì)和實(shí)現(xiàn)。本課程是計(jì)算機(jī)類專業(yè)的一應(yīng)用于一般軟件的設(shè)計(jì)和實(shí)現(xiàn)。本課程是計(jì)算機(jī)類專業(yè)的一門重要的核心專業(yè)課。門重要的核心專業(yè)課。先修課程：先修課程： 高級(jí)程序設(shè)計(jì)語(yǔ)言、匯編語(yǔ)言、高級(jí)程序設(shè)計(jì)語(yǔ)言、匯編語(yǔ)言、 離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)要求：學(xué)習(xí)要求：不曠課，上課認(rèn)真聽講，課上保持安靜；不曠課，上課認(rèn)真聽講，課上保持安靜； 課后即時(shí)復(fù)習(xí)，認(rèn)真完成作業(yè)；課后即時(shí)復(fù)習(xí)，認(rèn)真完成作業(yè)； 實(shí)驗(yàn)課內(nèi)實(shí)踐程序獨(dú)立設(shè)計(jì)及實(shí)現(xiàn)實(shí)驗(yàn)課

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

6、文法、形式語(yǔ)言及自動(dòng)機(jī)的基本概念和在編譯程序構(gòu)造中的應(yīng)用；）掌握文法、形式語(yǔ)言及自動(dòng)機(jī)的基本概念和在編譯程序構(gòu)造中的應(yīng)用；（3 3）掌握典型的幾種語(yǔ)法分析方法的基本原理和實(shí)現(xiàn)方法；）掌握典型的幾種語(yǔ)法分析方法的基本原理和實(shí)現(xiàn)方法；（4 4）掌握語(yǔ)法制導(dǎo)方法在語(yǔ)義分析中的應(yīng)用和中間代碼生成方法；）掌握語(yǔ)法制導(dǎo)方法在語(yǔ)義分析中的應(yīng)用和中間代碼生成方法；（5 5）掌握存儲(chǔ)分配的基本思想和實(shí)現(xiàn)方法；）掌握存儲(chǔ)分配的基本思想和實(shí)現(xiàn)方法；（6 6）掌握代碼優(yōu)化及代碼生成的方法。）掌握代碼優(yōu)化及代碼生成的方法。學(xué)習(xí)向?qū)W(xué)習(xí)向?qū)?編譯原理編譯原理課程是理論性較強(qiáng)的課程。其特點(diǎn)是概念多、課程是理論性較強(qiáng)的課程。

7、其特點(diǎn)是概念多、內(nèi)容抽象。尤其是文法、形式語(yǔ)言及自動(dòng)機(jī)的概念是計(jì)算機(jī)專內(nèi)容抽象。尤其是文法、形式語(yǔ)言及自動(dòng)機(jī)的概念是計(jì)算機(jī)專業(yè)的理論學(xué)習(xí)和研究的基礎(chǔ)。掌握這些基本理論、原理和技術(shù)，業(yè)的理論學(xué)習(xí)和研究的基礎(chǔ)。掌握這些基本理論、原理和技術(shù)，對(duì)于培養(yǎng)同學(xué)們對(duì)事物的抽象能力以及分析問題和解決問題的對(duì)于培養(yǎng)同學(xué)們對(duì)事物的抽象能力以及分析問題和解決問題的能力大有幫助。能力大有幫助。 編譯原理與方法對(duì)于深刻理解程序設(shè)計(jì)語(yǔ)言、深入了解程編譯原理與方法對(duì)于深刻理解程序設(shè)計(jì)語(yǔ)言、深入了解程序在計(jì)算機(jī)中的運(yùn)行機(jī)制、掌握程序設(shè)計(jì)語(yǔ)言的翻譯方法起到序在計(jì)算機(jī)中的運(yùn)行機(jī)制、掌握程序設(shè)計(jì)語(yǔ)言的翻譯方法起到不可替代的作用。同

8、時(shí)不可替代的作用。同時(shí)編譯原理編譯原理課程也是實(shí)踐性很強(qiáng)的課課程也是實(shí)踐性很強(qiáng)的課程，要求同學(xué)們?cè)诨菊莆樟司幾g理論和技術(shù)的基礎(chǔ)上，綜合程，要求同學(xué)們?cè)诨菊莆樟司幾g理論和技術(shù)的基礎(chǔ)上，綜合應(yīng)用先修課程及本課程的知識(shí)，完成課程的實(shí)驗(yàn)和課程設(shè)計(jì)。應(yīng)用先修課程及本課程的知識(shí)，完成課程的實(shí)驗(yàn)和課程設(shè)計(jì)。參考資料參考資料 教材：教材：11 編譯原理編譯原理（第三版）（第三版） 主編：王生原、董淵、張素琴、呂映芝主編：王生原、董淵、張素琴、呂映芝 出版社：清華大學(xué)出版社出版社：清華大學(xué)出版社 出版時(shí)間：出版時(shí)間：20152015年年參考書：參考書：11編譯原理編譯原理 主編：何炎祥主編：何炎祥 出版社：

9、華中理工大學(xué)出版社出版社：華中理工大學(xué)出版社 出版時(shí)間：出版時(shí)間：20102010年年1010月月22 程序設(shè)計(jì)語(yǔ)言編譯原理（第程序設(shè)計(jì)語(yǔ)言編譯原理（第3 3版）版） 主編：陳火旺、劉春林、譚慶平、趙克佳、劉越主編：陳火旺、劉春林、譚慶平、趙克佳、劉越 出版社：國(guó)防工業(yè)出版社出版社：國(guó)防工業(yè)出版社 出版時(shí)間：出版時(shí)間：2001220012年年8 8月月33編譯原理技術(shù)與工具（英文版）編譯原理技術(shù)與工具（英文版） Compilers:Principles,Techniques,and Compilers:Principles,Techniques,and ToolsTools 主編：主編：Alf

10、redAlfred V.Aho,RaviV.Aho,Ravi Sethi,JeffreySethi,Jeffrey D.UllmanD.Ullman 出版社：人民郵電出版社出版社：人民郵電出版社 出版時(shí)間：出版時(shí)間：20022002年年2 2月月 參考資料參考資料44編譯原理與技術(shù)編譯原理與技術(shù)（第二版）（第二版） 主編：陳意云主編：陳意云 出版社：中國(guó)科學(xué)技術(shù)大學(xué)出版社出版社：中國(guó)科學(xué)技術(shù)大學(xué)出版社 出版時(shí)間：出版時(shí)間：20022002年年1 1月月55編譯程序構(gòu)造原理和實(shí)現(xiàn)技術(shù)編譯程序構(gòu)造原理和實(shí)現(xiàn)技術(shù) 主編：金成植主編：金成植 出版社：高等教育出版社出版社：高等教育出版社 出版時(shí)間：出版

11、時(shí)間：20022002年年7 7月月66編譯原理及編譯程序構(gòu)造編譯原理及編譯程序構(gòu)造 主編：高仲儀、金茂忠主編：高仲儀、金茂忠 出版社：北京航空航天大學(xué)出版社出版社：北京航空航天大學(xué)出版社 出版時(shí)間：出版時(shí)間：20012001年年3 3月月77編譯原理編譯原理( (第第2 2版版) ) 主編：蔣立源主編：蔣立源, , 康慕寧康慕寧 出版社：西北工業(yè)大學(xué)出版社出版社：西北工業(yè)大學(xué)出版社 出版時(shí)間：出版時(shí)間：19991999年年4 4月月88編譯原理編譯原理 主編：張幸兒主編：張幸兒 出版社：科學(xué)出版社出版社：科學(xué)出版社 出版時(shí)間：出版時(shí)間：19991999年年4 4月月 第第1 1章章 引論引論

12、 本章主要內(nèi)容：本章主要內(nèi)容： v什么是編譯程序什么是編譯程序v編譯過程和編譯程序的結(jié)構(gòu)編譯過程和編譯程序的結(jié)構(gòu)v為什么要學(xué)習(xí)編譯程序?yàn)槭裁匆獙W(xué)習(xí)編譯程序 本章的重點(diǎn)：本章的重點(diǎn)： 本章沒有難以理解的內(nèi)容本章沒有難以理解的內(nèi)容,主要主要是對(duì)編譯程序的功能和結(jié)構(gòu)做一綜是對(duì)編譯程序的功能和結(jié)構(gòu)做一綜合描述合描述1.1 1.1 什么叫編譯程序什么叫編譯程序 使用過現(xiàn)代計(jì)算機(jī)的人都知道，多數(shù)用戶是應(yīng)用高級(jí)語(yǔ)言使用過現(xiàn)代計(jì)算機(jī)的人都知道，多數(shù)用戶是應(yīng)用高級(jí)語(yǔ)言來(lái)實(shí)現(xiàn)他們所需要的計(jì)算的?，F(xiàn)代計(jì)算機(jī)系統(tǒng)一般都含有不止來(lái)實(shí)現(xiàn)他們所需要的計(jì)算的?，F(xiàn)代計(jì)算機(jī)系統(tǒng)一般都含有不止一個(gè)的高級(jí)語(yǔ)言編譯程序，對(duì)有些高級(jí)語(yǔ)言

13、甚至配置了幾個(gè)不一個(gè)的高級(jí)語(yǔ)言編譯程序，對(duì)有些高級(jí)語(yǔ)言甚至配置了幾個(gè)不同性能的編譯程序，供用戶按不同需要進(jìn)行選擇。同性能的編譯程序，供用戶按不同需要進(jìn)行選擇。 要在計(jì)算機(jī)上執(zhí)行用高級(jí)語(yǔ)言（或匯編語(yǔ)言）編寫的程序，要在計(jì)算機(jī)上執(zhí)行用高級(jí)語(yǔ)言（或匯編語(yǔ)言）編寫的程序，必須通過特定的途徑來(lái)進(jìn)行，也就是要通過翻譯程序把用高級(jí)必須通過特定的途徑來(lái)進(jìn)行，也就是要通過翻譯程序把用高級(jí)語(yǔ)言（或匯編語(yǔ)言）編寫的程序語(yǔ)言（或匯編語(yǔ)言）編寫的程序翻譯翻譯成為機(jī)器語(yǔ)言構(gòu)成的程序，成為機(jī)器語(yǔ)言構(gòu)成的程序，計(jì)算機(jī)才能執(zhí)行。計(jì)算機(jī)才能執(zhí)行。 在計(jì)算機(jī)上執(zhí)行一個(gè)高級(jí)語(yǔ)言程序一般要分為兩步：在計(jì)算機(jī)上執(zhí)行一個(gè)高級(jí)語(yǔ)言程序一般要

14、分為兩步： 第一步，用一個(gè)編譯程序把高級(jí)語(yǔ)言翻譯成機(jī)器語(yǔ)言程序；第一步，用一個(gè)編譯程序把高級(jí)語(yǔ)言翻譯成機(jī)器語(yǔ)言程序； 第二步，運(yùn)行所得的機(jī)器語(yǔ)言程序求得計(jì)算結(jié)果。第二步，運(yùn)行所得的機(jī)器語(yǔ)言程序求得計(jì)算結(jié)果。 （1 1）翻譯程序（）翻譯程序（TranslatorTranslator） 通常所說的翻譯程序是指這樣的一個(gè)程序，它能夠把某通常所說的翻譯程序是指這樣的一個(gè)程序，它能夠把某一種語(yǔ)言程序（稱為一種語(yǔ)言程序（稱為源語(yǔ)言程序或源程序源語(yǔ)言程序或源程序）轉(zhuǎn)換成另一種語(yǔ)）轉(zhuǎn)換成另一種語(yǔ)言程序（稱為言程序（稱為目標(biāo)語(yǔ)言程序或目標(biāo)程序目標(biāo)語(yǔ)言程序或目標(biāo)程序），而后者與前者在），而后者與前者在邏輯上是等價(jià)

15、的。邏輯上是等價(jià)的。 源程序源程序（source program）翻譯程序翻譯程序目標(biāo)程序目標(biāo)程序(target program)輸入輸入輸出輸出圖圖1.1 翻譯程序翻譯程序 翻譯程序根據(jù)所處理的對(duì)象和實(shí)現(xiàn)的途徑不同又分為：翻譯程序根據(jù)所處理的對(duì)象和實(shí)現(xiàn)的途徑不同又分為：匯編程序、編譯程序和解釋程序。匯編程序、編譯程序和解釋程序。 （2 2）. . 匯編程序（匯編程序（AssemblerAssembler） 如果源語(yǔ)言是某種匯編語(yǔ)言，而目標(biāo)語(yǔ)言是某種計(jì)算機(jī)的機(jī)如果源語(yǔ)言是某種匯編語(yǔ)言，而目標(biāo)語(yǔ)言是某種計(jì)算機(jī)的機(jī)器語(yǔ)言，這樣的一個(gè)翻譯程序就稱為匯編程序。器語(yǔ)言，這樣的一個(gè)翻譯程序就稱為匯編程序。

16、源程序源程序（匯編語(yǔ)言）（匯編語(yǔ)言）翻譯程序翻譯程序（匯編程序）（匯編程序）目標(biāo)程序目標(biāo)程序（機(jī)器語(yǔ)言）（機(jī)器語(yǔ)言）輸入輸入輸出輸出圖圖1.2 匯編程序匯編程序（3 3）. . 編譯程序（編譯程序（CompilerCompiler） 如果源語(yǔ)言是某種高級(jí)語(yǔ)言，而目標(biāo)語(yǔ)言是某種低級(jí)語(yǔ)言如果源語(yǔ)言是某種高級(jí)語(yǔ)言，而目標(biāo)語(yǔ)言是某種低級(jí)語(yǔ)言（匯編語(yǔ)言或機(jī)器語(yǔ)言），這樣的一個(gè)翻譯程序就稱為編譯程（匯編語(yǔ)言或機(jī)器語(yǔ)言），這樣的一個(gè)翻譯程序就稱為編譯程序。序。 源程序源程序（高級(jí)語(yǔ)言）（高級(jí)語(yǔ)言）翻譯程序翻譯程序（編譯程序）（編譯程序）目標(biāo)程序目標(biāo)程序（低級(jí)語(yǔ)言）（低級(jí)語(yǔ)言）圖圖1.3 編譯程序編譯程序輸入

17、輸入輸出輸出（4 4）. . 解釋程序（解釋程序（Interpreter） 這是另外一種類型的翻譯程序，在翻譯過程它按照高級(jí)語(yǔ)這是另外一種類型的翻譯程序，在翻譯過程它按照高級(jí)語(yǔ)言源程序在計(jì)算機(jī)上執(zhí)行的動(dòng)態(tài)順序?qū)υ闯绦虻恼Z(yǔ)句逐條翻譯言源程序在計(jì)算機(jī)上執(zhí)行的動(dòng)態(tài)順序?qū)υ闯绦虻恼Z(yǔ)句逐條翻譯（解釋），邊解釋邊執(zhí)行直至結(jié)束，它不產(chǎn)生目標(biāo)程序，它的（解釋），邊解釋邊執(zhí)行直至結(jié)束，它不產(chǎn)生目標(biāo)程序，它的工作結(jié)果就是源程序的執(zhí)行結(jié)果，這樣的一個(gè)翻譯程序就稱為工作結(jié)果就是源程序的執(zhí)行結(jié)果，這樣的一個(gè)翻譯程序就稱為解釋程序。解釋程序。 源程序源程序（高級(jí)語(yǔ)言）（高級(jí)語(yǔ)言）翻譯程序翻譯程序（解釋程序）（解釋程序）計(jì)

18、算結(jié)果計(jì)算結(jié)果輸入輸入輸出輸出圖圖1.4 解釋程序解釋程序初始數(shù)據(jù)初始數(shù)據(jù)根據(jù)不同的用途，編譯程序可進(jìn)一步分類根據(jù)不同的用途，編譯程序可進(jìn)一步分類:（1）診斷編譯程序（）診斷編譯程序（Diagnostic Compiler）：）： 專門用于幫助程序開發(fā)和調(diào)試的編譯程序。專門用于幫助程序開發(fā)和調(diào)試的編譯程序。（2）優(yōu)化編譯程序（）優(yōu)化編譯程序（Optimizing Compiler）：）： 著重于提高目標(biāo)代碼效率的編譯程序。著重于提高目標(biāo)代碼效率的編譯程序。（3）交叉編譯程序）交叉編譯程序(Cross Compiler)： 如果一個(gè)編譯程序產(chǎn)生不同于其宿主機(jī)的機(jī)器代碼。如果一個(gè)編譯程序產(chǎn)生不同于

19、其宿主機(jī)的機(jī)器代碼。（4）可變目標(biāo)編譯程序（可變目標(biāo)編譯程序（Retargetable Compiler）：）： 不需重寫編譯程序中與機(jī)器無(wú)關(guān)的部分就能改變目標(biāo)機(jī)。不需重寫編譯程序中與機(jī)器無(wú)關(guān)的部分就能改變目標(biāo)機(jī)。 宿主機(jī)宿主機(jī)（host machine）：）：運(yùn)行編譯程序的計(jì)算機(jī)。運(yùn)行編譯程序的計(jì)算機(jī)。目標(biāo)機(jī)目標(biāo)機(jī)(object machine) ：運(yùn)行編譯程序所產(chǎn)生目標(biāo)代碼的計(jì)算機(jī)。運(yùn)行編譯程序所產(chǎn)生目標(biāo)代碼的計(jì)算機(jī)。1.2 1.2 編譯過程概述編譯過程概述 編譯程序的工作，從輸入源程序開始到輸出目標(biāo)程序?yàn)橹沟木幾g程序的工作，從輸入源程序開始到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)過程，是非常復(fù)雜的。整個(gè)

20、過程，是非常復(fù)雜的。一段英文翻譯為中文時(shí)，通常需經(jīng)下列步驟：一段英文翻譯為中文時(shí)，通常需經(jīng)下列步驟：（1）識(shí)別出句子中的一個(gè)個(gè)單詞；）識(shí)別出句子中的一個(gè)個(gè)單詞；（2）分析句子的語(yǔ)法結(jié)構(gòu)；）分析句子的語(yǔ)法結(jié)構(gòu)；（3）根據(jù)句子的含義進(jìn)行初步翻譯；）根據(jù)句子的含義進(jìn)行初步翻譯；（4）對(duì)譯文進(jìn)行修飾；）對(duì)譯文進(jìn)行修飾；（5）寫出最后的譯文。）寫出最后的譯文。 類似地，編譯程序的工作過程一般也可以劃分為五個(gè)階段：類似地，編譯程序的工作過程一般也可以劃分為五個(gè)階段：詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼產(chǎn)生、優(yōu)化、目標(biāo)詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼產(chǎn)生、優(yōu)化、目標(biāo)代碼生成。代碼生成。 第一階段第一

21、階段: : 詞法分析詞法分析 （Lexical analysisLexical analysis）詞法分析的任務(wù)：詞法分析的任務(wù)： 輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)的單詞。識(shí)別出一個(gè)個(gè)的單詞。 保留字（保留字（beginbegin、endend、ifif、forfor、whilewhile等）、等）、 標(biāo)識(shí)符（標(biāo)識(shí)符（x1x1、s s等變量名）、等變量名）、 常數(shù)常數(shù)(3.14(3.14、100100等等) )、 算符（算符（+ +、- -、andand、oror等）、等）、 界符（標(biāo)點(diǎn)符號(hào)、左右括號(hào)等）。界符（標(biāo)點(diǎn)符

22、號(hào)、左右括號(hào)等）。 例如，對(duì)于例如，對(duì)于PascalPascal的循環(huán)語(yǔ)句：的循環(huán)語(yǔ)句： for I for I：1 to 100 do1 to 100 do詞法分析的結(jié)果是識(shí)別出如下的單詞符號(hào)：詞法分析的結(jié)果是識(shí)別出如下的單詞符號(hào)： 保留字保留字 forfor 標(biāo)識(shí)符標(biāo)識(shí)符 I I 賦值號(hào)：賦值號(hào)： ：= = 整常數(shù)整常數(shù) 1 1 保留字保留字 toto 整常數(shù)整常數(shù) 100100 保留字保留字 dodo 單詞符號(hào)是語(yǔ)言的基本組成成分，是人們理單詞符號(hào)是語(yǔ)言的基本組成成分，是人們理解和編寫程序的基本要素。識(shí)別和理解這些要素解和編寫程序的基本要素。識(shí)別和理解這些要素?zé)o疑也是翻譯的基礎(chǔ)。無(wú)疑也是

23、翻譯的基礎(chǔ)。 如同將英文翻譯成中文的情形一樣，如果你如同將英文翻譯成中文的情形一樣，如果你對(duì)英語(yǔ)單詞不理解，那就談不上進(jìn)行正確的翻譯。對(duì)英語(yǔ)單詞不理解，那就談不上進(jìn)行正確的翻譯。 在詞法分析階段的工作中所依循的是語(yǔ)言在詞法分析階段的工作中所依循的是語(yǔ)言的詞法規(guī)則（或稱構(gòu)詞規(guī)則）。描述詞法規(guī)則的的詞法規(guī)則（或稱構(gòu)詞規(guī)則）。描述詞法規(guī)則的有效工具是有效工具是正規(guī)式和有限自動(dòng)機(jī)。正規(guī)式和有限自動(dòng)機(jī)。第二階段，語(yǔ)法分析第二階段，語(yǔ)法分析(Syntax Analysis)(Syntax Analysis) 語(yǔ)法分析的任務(wù)是：語(yǔ)法分析的任務(wù)是： 在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把單詞符號(hào)在詞法分析

24、的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把單詞符號(hào)串分解成各類語(yǔ)法單位（語(yǔ)法范疇），如串分解成各類語(yǔ)法單位（語(yǔ)法范疇），如“短語(yǔ)短語(yǔ)”、“子句子句”、“句子句子”（“語(yǔ)句語(yǔ)句”）、）、“程序段程序段”和和“程序程序”等。等。通過語(yǔ)法通過語(yǔ)法分析，確定整個(gè)輸入串是否構(gòu)成語(yǔ)法上正確的分析，確定整個(gè)輸入串是否構(gòu)成語(yǔ)法上正確的“程序程序”。 語(yǔ)法分析所依循的是語(yǔ)言的語(yǔ)法分析所依循的是語(yǔ)言的語(yǔ)法規(guī)則語(yǔ)法規(guī)則。語(yǔ)法規(guī)則通常用上。語(yǔ)法規(guī)則通常用上下文無(wú)關(guān)文法描述。下文無(wú)關(guān)文法描述。 詞法分析是一種線性分析，而語(yǔ)法分析是一種層次結(jié)構(gòu)分析。詞法分析是一種線性分析，而語(yǔ)法分析是一種層次結(jié)構(gòu)分析。例如，在很多語(yǔ)言中，符號(hào)串例

25、如，在很多語(yǔ)言中，符號(hào)串 z：=X十十0.618*Y代表一個(gè)代表一個(gè)“賦值語(yǔ)句賦值語(yǔ)句”，而其中的，而其中的 X0.618*Y代表一個(gè)代表一個(gè)“算術(shù)算術(shù)表達(dá)式表達(dá)式”。因而，語(yǔ)法分析的任務(wù)就是識(shí)別。因而，語(yǔ)法分析的任務(wù)就是識(shí)別 X0.618*Y為算術(shù)為算術(shù)表達(dá)式，同時(shí)，識(shí)別上述整個(gè)符號(hào)串屬于賦值語(yǔ)句這個(gè)范疇。表達(dá)式，同時(shí)，識(shí)別上述整個(gè)符號(hào)串屬于賦值語(yǔ)句這個(gè)范疇。 第三階段，語(yǔ)義分析與中間代碼產(chǎn)生第三階段，語(yǔ)義分析與中間代碼產(chǎn)生(Semantic (Semantic Analysis and Intermediate Generator)Analysis and Intermediate Gen

26、erator) 此階段的任務(wù)是：此階段的任務(wù)是： 對(duì)語(yǔ)法分析所識(shí)別出的各類語(yǔ)法范疇，分析其含義，并進(jìn)對(duì)語(yǔ)法分析所識(shí)別出的各類語(yǔ)法范疇，分析其含義，并進(jìn)行初步翻譯（產(chǎn)生中間代碼）。行初步翻譯（產(chǎn)生中間代碼）。 中間代碼中間代碼是一種獨(dú)立于具體硬件的記號(hào)系統(tǒng)。是一種獨(dú)立于具體硬件的記號(hào)系統(tǒng)。 常用的中間代碼：三地址碼，四元式，三元式、間接三常用的中間代碼：三地址碼，四元式，三元式、間接三元式、逆波蘭式，樹形表示等。元式、逆波蘭式，樹形表示等。 所謂所謂“中間代碼中間代碼”是一種含義明確、便于處理的記號(hào)系統(tǒng)，它通常是一種含義明確、便于處理的記號(hào)系統(tǒng)，它通常獨(dú)立于具體的硬件。這種記號(hào)系統(tǒng)或者與現(xiàn)代計(jì)算

27、機(jī)的指令形式有某種獨(dú)立于具體的硬件。這種記號(hào)系統(tǒng)或者與現(xiàn)代計(jì)算機(jī)的指令形式有某種程度的接近，或者能夠比較容易地把它變換成現(xiàn)代計(jì)算機(jī)的機(jī)器指令。程度的接近，或者能夠比較容易地把它變換成現(xiàn)代計(jì)算機(jī)的機(jī)器指令。 四元式的形式是：四元式的形式是： （ 算符算符 左操作數(shù)左操作數(shù) 右操作數(shù)右操作數(shù) 結(jié)果）結(jié)果） 它的意義是：對(duì)它的意義是：對(duì)“左、右操作數(shù)左、右操作數(shù)”進(jìn)行某種運(yùn)算（由進(jìn)行某種運(yùn)算（由“算符算符”指明），把運(yùn)算所得的值作為指明），把運(yùn)算所得的值作為“結(jié)果結(jié)果”保留下來(lái)。保留下來(lái)。 例如例如 賦值語(yǔ)句賦值語(yǔ)句 Z：（：（X0.418）*YW 翻譯為四元式序列：翻譯為四元式序列： 序號(hào)序號(hào) 算

28、符算符 左操作數(shù)左操作數(shù) 右操作數(shù)右操作數(shù) 結(jié)果結(jié)果 1 十十 X 0.418 T1 2 * T1 Y T2 3 T2 W Z第四階段，優(yōu)化第四階段，優(yōu)化 (Optimization)(Optimization)優(yōu)化的任務(wù)優(yōu)化的任務(wù): : 對(duì)產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生出更為高效對(duì)產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生出更為高效（省時(shí)間和空間）的目標(biāo)代碼。（省時(shí)間和空間）的目標(biāo)代碼。 優(yōu)化的主要方面有：優(yōu)化的主要方面有： 公共子表達(dá)式提取、循環(huán)優(yōu)化、刪除無(wú)用代碼等等。有時(shí)，為了便于公共子表達(dá)式提取、循環(huán)優(yōu)化、刪除無(wú)用代碼等等。有時(shí)，為了便于“并行運(yùn)算并行運(yùn)算”，還

29、可以對(duì)代碼進(jìn)行并行化處理。，還可以對(duì)代碼進(jìn)行并行化處理。優(yōu)化所依循的原則優(yōu)化所依循的原則: : 程序的等價(jià)變換規(guī)則。程序的等價(jià)變換規(guī)則。例如，有程序片斷例如，有程序片斷 for K:1 to 100 dobegin M:=I+10*K N:=J+10*Kend其中間代碼為：其中間代碼為： 序號(hào)序號(hào)OPARG1ARG2RESULT注注 解解（1）（2）（3）（4）（5）（6）（7）（8）（9）:=j*+*+j 110010I10JK KKT1KT21 K（9）T1MT2NK（2） K：1若若100K轉(zhuǎn)至第轉(zhuǎn)至第(9)個(gè)四元式個(gè)四元式T1 :二二10*K; T1為臨時(shí)變量為臨時(shí)變量M :IT1T2

30、 :10*k; T2為臨時(shí)變量為臨時(shí)變量N :J十十T2K :K十十1轉(zhuǎn)至第（轉(zhuǎn)至第（2）個(gè)四元式）個(gè)四元式 轉(zhuǎn)換成如下的等價(jià)代碼：轉(zhuǎn)換成如下的等價(jià)代碼： 序號(hào)序號(hào)OPARG1ARG2RESUL注注 解解（1）（2）（3）（4）（5）（6）（7）（8）（9）：=：=：=j+j IJ1100MNK K10101MNK（9）MNK（4） M：IN：JK：lif（100k）goto（9）M：M10N：N十十 10K：Klgoto（4） 優(yōu)化后目標(biāo)程序的執(zhí)行效率提高很多。因?yàn)?，?duì)于前者，在循環(huán)中需優(yōu)化后目標(biāo)程序的執(zhí)行效率提高很多。因?yàn)?，?duì)于前者，在循環(huán)中需做做300次加法和次加法和200乘法乘法；對(duì)于

31、后者，在循環(huán)中只需做；對(duì)于后者，在循環(huán)中只需做300次加法。次加法。第第五階段，目標(biāo)代碼生成五階段，目標(biāo)代碼生成(Code Generation)(Code Generation)這一階段的任務(wù)是：這一階段的任務(wù)是： 把中間代碼（或經(jīng)優(yōu)化處理之后）變換成特定機(jī)器上的低級(jí)語(yǔ)言代把中間代碼（或經(jīng)優(yōu)化處理之后）變換成特定機(jī)器上的低級(jí)語(yǔ)言代碼。碼。 例例 （*, id3, 10.0, t1） （+, id2, , t1, id1 ）目標(biāo)代碼：目標(biāo)代碼： （1）MOV id3, R2 （2）MUL #10.0, R2 （3）MOV id2, R1 （4）ADD R1, R2 （5）MOV R1, id1

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

33、個(gè)階段。個(gè)階段。1.3 1.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu) 1.3.1 1.3.1 編譯程序總框編譯程序總框 上述編譯過程的五個(gè)階段是編譯程序工作時(shí)的動(dòng)態(tài)特征。編譯程序的上述編譯過程的五個(gè)階段是編譯程序工作時(shí)的動(dòng)態(tài)特征。編譯程序的結(jié)構(gòu)可以按照這五階段的任務(wù)分模塊進(jìn)行設(shè)計(jì)。結(jié)構(gòu)可以按照這五階段的任務(wù)分模塊進(jìn)行設(shè)計(jì)。圖圖1.5 編譯程序總框編譯程序總框詞法分析器詞法分析器語(yǔ)法分析器語(yǔ)法分析器語(yǔ)義分析與中間代碼生成器語(yǔ)義分析與中間代碼生成器中間代碼優(yōu)化器中間代碼優(yōu)化器目標(biāo)代碼生成器目標(biāo)代碼生成器表表格格管管理理出出錯(cuò)錯(cuò)處處理理目標(biāo)代碼程序目標(biāo)代碼程序源程序源程序單詞符號(hào)串單詞符號(hào)串語(yǔ)法單位語(yǔ)法單位

34、中間代碼串中間代碼串中間代碼串中間代碼串 （1）詞法分析器）詞法分析器(lexical analyzer)，也稱掃描器：，也稱掃描器： 輸入源程序，進(jìn)行詞法分析，輸出單詞符號(hào)。輸入源程序，進(jìn)行詞法分析，輸出單詞符號(hào)。 （2）語(yǔ)法分析器）語(yǔ)法分析器(syntax analyzer)，簡(jiǎn)稱分析器：，簡(jiǎn)稱分析器： 對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析（根據(jù)語(yǔ)法規(guī)則進(jìn)行推導(dǎo)或?qū)卧~符號(hào)串進(jìn)行語(yǔ)法分析（根據(jù)語(yǔ)法規(guī)則進(jìn)行推導(dǎo)或歸約），識(shí)別出各類語(yǔ)法單位，最終判斷輸入串是否構(gòu)成語(yǔ)法上歸約），識(shí)別出各類語(yǔ)法單位，最終判斷輸入串是否構(gòu)成語(yǔ)法上正確的正確的“程序程序”。 （3）語(yǔ)義分析與中間代碼產(chǎn)生器）語(yǔ)義分析與中間代碼產(chǎn)生

35、器(semantic analyzer and intermediate code generator)： 按照語(yǔ)義規(guī)則對(duì)語(yǔ)法分析器歸約出（或推導(dǎo)出）的語(yǔ)法按照語(yǔ)義規(guī)則對(duì)語(yǔ)法分析器歸約出（或推導(dǎo)出）的語(yǔ)法單位進(jìn)行語(yǔ)義分析并把它們翻譯成一定形式的中間代碼。單位進(jìn)行語(yǔ)義分析并把它們翻譯成一定形式的中間代碼。 有的編譯程序在識(shí)別出各類語(yǔ)法單位后，構(gòu)造并輸出一棵表示語(yǔ)法有的編譯程序在識(shí)別出各類語(yǔ)法單位后，構(gòu)造并輸出一棵表示語(yǔ)法結(jié)構(gòu)的語(yǔ)法樹，然后，根據(jù)語(yǔ)法樹進(jìn)行語(yǔ)義分析和中間代碼產(chǎn)生。結(jié)構(gòu)的語(yǔ)法樹，然后，根據(jù)語(yǔ)法樹進(jìn)行語(yǔ)義分析和中間代碼產(chǎn)生。 （4）代碼優(yōu)化器）代碼優(yōu)化器(code optimizer)

36、： 對(duì)中間代碼進(jìn)行優(yōu)化處理，以便得到高質(zhì)量的目標(biāo)代對(duì)中間代碼進(jìn)行優(yōu)化處理，以便得到高質(zhì)量的目標(biāo)代碼。碼。 （5）代碼生成器）代碼生成器(code generator)： 將中間代碼翻譯成等價(jià)的目標(biāo)程序。將中間代碼翻譯成等價(jià)的目標(biāo)程序。 除了上述五個(gè)功能模塊外，一個(gè)完整的編譯程序還應(yīng)包括除了上述五個(gè)功能模塊外，一個(gè)完整的編譯程序還應(yīng)包括“表格管理表格管理”和和“出錯(cuò)處理出錯(cuò)處理”兩部分。兩部分。1.3.2 1.3.2 表格管理表格管理 (symbol-table manager)(symbol-table manager) 編譯程序在工作過程中需要保存一系列的表格，以登記源程序的各類編譯程序在工

37、作過程中需要保存一系列的表格，以登記源程序的各類信息和編譯各階段的進(jìn)展?fàn)顩r。信息和編譯各階段的進(jìn)展?fàn)顩r。 合理地設(shè)計(jì)和使用表格是編譯程序構(gòu)造的一個(gè)重要問題。合理地設(shè)計(jì)和使用表格是編譯程序構(gòu)造的一個(gè)重要問題。 在編譯程序使用的表格中，最重要的是符號(hào)表。它用來(lái)登記源程序中在編譯程序使用的表格中，最重要的是符號(hào)表。它用來(lái)登記源程序中出現(xiàn)的每個(gè)名字以及名字的各種屬性。出現(xiàn)的每個(gè)名字以及名字的各種屬性。 例如，一個(gè)名字是常量名、變量名，還是過程名等等；如果是變量名，例如，一個(gè)名字是常量名、變量名，還是過程名等等；如果是變量名，它的類型是什么、所占內(nèi)存是多大、地址是什么等等。它的類型是什么、所占內(nèi)存是多大

38、、地址是什么等等。 通常，編譯程序在處理到名字的定義性出現(xiàn)時(shí)，要把名字的各種屬性通常，編譯程序在處理到名字的定義性出現(xiàn)時(shí)，要把名字的各種屬性填入到符號(hào)表中；當(dāng)處理到名字的使用性出現(xiàn)時(shí)，要對(duì)名字的屬性進(jìn)行查填入到符號(hào)表中；當(dāng)處理到名字的使用性出現(xiàn)時(shí)，要對(duì)名字的屬性進(jìn)行查證。證。 當(dāng)掃描器識(shí)別出一個(gè)名字（標(biāo)識(shí)符）后，它把該名字填入到符號(hào)表中。當(dāng)掃描器識(shí)別出一個(gè)名字（標(biāo)識(shí)符）后，它把該名字填入到符號(hào)表中。但這時(shí)不能完全確定名字的屬性，它的各種屬性要在后續(xù)的各階段才能填但這時(shí)不能完全確定名字的屬性，它的各種屬性要在后續(xù)的各階段才能填入。入。 例如，名字的類型等要在語(yǔ)義分析時(shí)才能確定，而名字的地址可能要

39、例如，名字的類型等要在語(yǔ)義分析時(shí)才能確定，而名字的地址可能要到目標(biāo)代碼生成才能確定。到目標(biāo)代碼生成才能確定。由此可見，編譯各階段都涉及到構(gòu)造、查找或更新有關(guān)的表格。由此可見，編譯各階段都涉及到構(gòu)造、查找或更新有關(guān)的表格。 1.3.3 1.3.3 出錯(cuò)處理出錯(cuò)處理(error handler) (error handler) 一個(gè)編譯程序不僅應(yīng)能對(duì)書寫正確的程序進(jìn)行翻譯，而且應(yīng)能對(duì)出現(xiàn)一個(gè)編譯程序不僅應(yīng)能對(duì)書寫正確的程序進(jìn)行翻譯，而且應(yīng)能對(duì)出現(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。在源程序中的錯(cuò)誤進(jìn)行處理。 如果源程序有錯(cuò)誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯(cuò)誤，把有關(guān)錯(cuò)誤信息報(bào)告如果源程序有錯(cuò)誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯(cuò)誤

40、，把有關(guān)錯(cuò)誤信息報(bào)告給用戶。這部分工作是由專門的一組程序（叫做出錯(cuò)處理程序）完成的。給用戶。這部分工作是由專門的一組程序（叫做出錯(cuò)處理程序）完成的。 一個(gè)好的編譯程序應(yīng)能最大限度地發(fā)現(xiàn)源程序中的各種錯(cuò)誤，準(zhǔn)確地一個(gè)好的編譯程序應(yīng)能最大限度地發(fā)現(xiàn)源程序中的各種錯(cuò)誤，準(zhǔn)確地指出錯(cuò)誤的性質(zhì)和發(fā)生錯(cuò)誤的地點(diǎn)，并且能將錯(cuò)誤所造成的影響限制在盡指出錯(cuò)誤的性質(zhì)和發(fā)生錯(cuò)誤的地點(diǎn)，并且能將錯(cuò)誤所造成的影響限制在盡可能小的范圍內(nèi)，使得源程序的其余部分能繼續(xù)被編譯下去，以便進(jìn)一步可能小的范圍內(nèi)，使得源程序的其余部分能繼續(xù)被編譯下去，以便進(jìn)一步發(fā)現(xiàn)其它可能的錯(cuò)誤。發(fā)現(xiàn)其它可能的錯(cuò)誤。 如果不僅能夠發(fā)現(xiàn)錯(cuò)誤，而且還能自

41、動(dòng)校正錯(cuò)誤，那當(dāng)然就更好了。如果不僅能夠發(fā)現(xiàn)錯(cuò)誤，而且還能自動(dòng)校正錯(cuò)誤，那當(dāng)然就更好了。但是，自動(dòng)校正錯(cuò)誤的代價(jià)是非常高的。但是，自動(dòng)校正錯(cuò)誤的代價(jià)是非常高的。 編譯過程的每一階段都可能檢測(cè)出錯(cuò)誤，其中，絕大多數(shù)編譯過程的每一階段都可能檢測(cè)出錯(cuò)誤，其中，絕大多數(shù)錯(cuò)誤可以在編譯的前三階段檢測(cè)出來(lái)。錯(cuò)誤可以在編譯的前三階段檢測(cè)出來(lái)。 源程序中的錯(cuò)誤通常分為語(yǔ)法錯(cuò)誤和語(yǔ)義錯(cuò)誤兩大類。源程序中的錯(cuò)誤通常分為語(yǔ)法錯(cuò)誤和語(yǔ)義錯(cuò)誤兩大類。 語(yǔ)法錯(cuò)誤語(yǔ)法錯(cuò)誤是指源程序中不符合語(yǔ)法（或詞法）規(guī)則的錯(cuò)誤，是指源程序中不符合語(yǔ)法（或詞法）規(guī)則的錯(cuò)誤，它們可在詞法分析或語(yǔ)法分析時(shí)檢測(cè)出來(lái)。它們可在詞法分析或語(yǔ)法分析時(shí)

42、檢測(cè)出來(lái)。 例如，詞法分析階段能夠檢測(cè)出例如，詞法分析階段能夠檢測(cè)出“非法字符非法字符”之類的錯(cuò)誤；之類的錯(cuò)誤；語(yǔ)法分析階段能夠檢測(cè)出諸如語(yǔ)法分析階段能夠檢測(cè)出諸如“括號(hào)不匹配括號(hào)不匹配”、“缺少；缺少；”之之類的錯(cuò)誤。類的錯(cuò)誤。 語(yǔ)義錯(cuò)誤語(yǔ)義錯(cuò)誤是指源程序中不符合語(yǔ)義規(guī)則的錯(cuò)誤，這些錯(cuò)誤是指源程序中不符合語(yǔ)義規(guī)則的錯(cuò)誤，這些錯(cuò)誤一般在語(yǔ)義分析時(shí)檢測(cè)出來(lái)，有的語(yǔ)義錯(cuò)誤要在運(yùn)行時(shí)才能檢一般在語(yǔ)義分析時(shí)檢測(cè)出來(lái)，有的語(yǔ)義錯(cuò)誤要在運(yùn)行時(shí)才能檢測(cè)出來(lái)。測(cè)出來(lái)。 語(yǔ)義錯(cuò)誤通常包括：說明錯(cuò)誤、作用域錯(cuò)誤、類型不一致語(yǔ)義錯(cuò)誤通常包括：說明錯(cuò)誤、作用域錯(cuò)誤、類型不一致等等。關(guān)于錯(cuò)誤檢測(cè)和處理方法，我們將穿插在

43、有關(guān)章節(jié)介紹。等等。關(guān)于錯(cuò)誤檢測(cè)和處理方法，我們將穿插在有關(guān)章節(jié)介紹。1.3.4 1.3.4 遍遍 (Pass(Pass） 前面介紹的編譯過程的五個(gè)階段僅僅是邏輯功能上的一種劃前面介紹的編譯過程的五個(gè)階段僅僅是邏輯功能上的一種劃分。具體實(shí)現(xiàn)時(shí)，受不同源語(yǔ)言、設(shè)計(jì)要求、使用對(duì)象和計(jì)算機(jī)分。具體實(shí)現(xiàn)時(shí)，受不同源語(yǔ)言、設(shè)計(jì)要求、使用對(duì)象和計(jì)算機(jī)條件（如主存容量）的限制，往往將編譯程序組織為若干條件（如主存容量）的限制，往往將編譯程序組織為若干遍遍（Pass）。 所謂所謂“遍遍”就是對(duì)源程序或源程序的中間結(jié)果從頭到尾掃就是對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果

44、或目標(biāo)程序。描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。 通常，每遍的工作由從外存上獲得的前一遍的中間結(jié)果開始通常，每遍的工作由從外存上獲得的前一遍的中間結(jié)果開始（對(duì)于第一遍而言，從外存上獲得源程序），完成它所含的有關(guān)（對(duì)于第一遍而言，從外存上獲得源程序），完成它所含的有關(guān)工作之后，再把結(jié)果記錄于外存。工作之后，再把結(jié)果記錄于外存。 當(dāng)一遍中包含若干階段時(shí)，各階段的工作是穿插進(jìn)行的。當(dāng)一遍中包含若干階段時(shí)，各階段的工作是穿插進(jìn)行的。例如，我們可以把詞法分析、語(yǔ)法分析及語(yǔ)義分析與中間代碼例如，我們可以把詞法分析、語(yǔ)法分析及語(yǔ)義分析與中間代碼產(chǎn)生這三階段安排成一遍。產(chǎn)生這三階段安排成一

45、遍。 這時(shí)，語(yǔ)法分析器處于核心位置，當(dāng)它在識(shí)別語(yǔ)法結(jié)構(gòu)而這時(shí)，語(yǔ)法分析器處于核心位置，當(dāng)它在識(shí)別語(yǔ)法結(jié)構(gòu)而需要下一單詞符號(hào)時(shí)，它就調(diào)用詞法分析器，一旦識(shí)別出一個(gè)需要下一單詞符號(hào)時(shí)，它就調(diào)用詞法分析器，一旦識(shí)別出一個(gè)語(yǔ)法單位時(shí)，它就調(diào)用中間代碼產(chǎn)生器，完成相應(yīng)的語(yǔ)義分析語(yǔ)法單位時(shí)，它就調(diào)用中間代碼產(chǎn)生器，完成相應(yīng)的語(yǔ)義分析并產(chǎn)生相應(yīng)的中間代碼。并產(chǎn)生相應(yīng)的中間代碼。 一個(gè)編譯程序究竟應(yīng)分成幾遍，如何劃分，是與源語(yǔ)言、一個(gè)編譯程序究竟應(yīng)分成幾遍，如何劃分，是與源語(yǔ)言、設(shè)計(jì)要求。硬件設(shè)備等諸因素有關(guān)的，因此難于統(tǒng)一劃定。設(shè)計(jì)要求。硬件設(shè)備等諸因素有關(guān)的，因此難于統(tǒng)一劃定。 遍數(shù)多一點(diǎn)有個(gè)好處，即整個(gè)

46、編譯程序的邏輯結(jié)構(gòu)可能清遍數(shù)多一點(diǎn)有個(gè)好處，即整個(gè)編譯程序的邏輯結(jié)構(gòu)可能清晰一點(diǎn)。但遍數(shù)多勢(shì)必增加輸入輸出所消耗的時(shí)間。因此，晰一點(diǎn)。但遍數(shù)多勢(shì)必增加輸入輸出所消耗的時(shí)間。因此，在主存可能的前提下，一般還是遍數(shù)盡可能少一點(diǎn)為好。應(yīng)當(dāng)在主存可能的前提下，一般還是遍數(shù)盡可能少一點(diǎn)為好。應(yīng)當(dāng)注意的是，并不是每種語(yǔ)言都可以用單遍編譯程序?qū)崿F(xiàn)。注意的是，并不是每種語(yǔ)言都可以用單遍編譯程序?qū)崿F(xiàn)。 1.3.5 1.3.5 編譯前端與后端編譯前端與后端 前端前端主要由與源語(yǔ)言有關(guān)但與目標(biāo)機(jī)無(wú)關(guān)的那些部分組成。主要由與源語(yǔ)言有關(guān)但與目標(biāo)機(jī)無(wú)關(guān)的那些部分組成。這些部分通常包括詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼

47、這些部分通常包括詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼產(chǎn)生，有的代碼優(yōu)化工作也可包括在前端。產(chǎn)生，有的代碼優(yōu)化工作也可包括在前端。 后端后端包括編譯程序中與目標(biāo)機(jī)有關(guān)的那些部分，如與目標(biāo)包括編譯程序中與目標(biāo)機(jī)有關(guān)的那些部分，如與目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。通常，后端不依賴于源機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。通常，后端不依賴于源語(yǔ)言而僅僅依賴于中間語(yǔ)言。語(yǔ)言而僅僅依賴于中間語(yǔ)言。 可以取編譯程序的前端，改寫其后端以生成不同目標(biāo)機(jī)上可以取編譯程序的前端，改寫其后端以生成不同目標(biāo)機(jī)上的相同語(yǔ)言的編譯程序。如果后端的設(shè)計(jì)是經(jīng)過精心考慮的，的相同語(yǔ)言的編譯程序。如果后端的設(shè)計(jì)是經(jīng)過精心考慮的

48、，那么后端的改寫將用不了太大工作量，這樣就可實(shí)現(xiàn)編譯程序那么后端的改寫將用不了太大工作量，這樣就可實(shí)現(xiàn)編譯程序的目標(biāo)機(jī)改變。也可以設(shè)想將幾種源語(yǔ)言編譯成相同的中間語(yǔ)的目標(biāo)機(jī)改變。也可以設(shè)想將幾種源語(yǔ)言編譯成相同的中間語(yǔ)言，然后為不同的前端配上相同的后端，這樣就可為同一臺(tái)機(jī)言，然后為不同的前端配上相同的后端，這樣就可為同一臺(tái)機(jī)器生成不同語(yǔ)言的編譯程序。然而，由于不同語(yǔ)言存在某些微器生成不同語(yǔ)言的編譯程序。然而，由于不同語(yǔ)言存在某些微妙的區(qū)別，因此在這方面所取得的成果還非常有限。妙的區(qū)別，因此在這方面所取得的成果還非常有限。 為了實(shí)現(xiàn)編譯程序可改變目標(biāo)機(jī)，通常需要有一種定義良為了實(shí)現(xiàn)編譯程序可改變

49、目標(biāo)機(jī)，通常需要有一種定義良好的中間語(yǔ)言支持。好的中間語(yǔ)言支持。 著名的著名的AdaAda程序設(shè)計(jì)環(huán)境程序設(shè)計(jì)環(huán)境APSEAPSE中，使用的是一種稱為中，使用的是一種稱為DianaDiana的樹形結(jié)構(gòu)的中間語(yǔ)言。一個(gè)的樹形結(jié)構(gòu)的中間語(yǔ)言。一個(gè)AdaAda源程序通過前端編譯轉(zhuǎn)換為源程序通過前端編譯轉(zhuǎn)換為DianaDiana中間代碼，由編譯后端把中間代碼，由編譯后端把DianaDiana中間代碼轉(zhuǎn)換為目標(biāo)代碼。中間代碼轉(zhuǎn)換為目標(biāo)代碼。編譯前端與不同的編譯后端以編譯前端與不同的編譯后端以DianaDiana為界面，實(shí)現(xiàn)編譯程序的為界面，實(shí)現(xiàn)編譯程序的目標(biāo)機(jī)改變。目標(biāo)機(jī)改變。 在在JavaJava語(yǔ)言

50、環(huán)境中，為了使編譯后的程序從一個(gè)平臺(tái)移到語(yǔ)言環(huán)境中，為了使編譯后的程序從一個(gè)平臺(tái)移到另一個(gè)平臺(tái)執(zhí)行，另一個(gè)平臺(tái)執(zhí)行，JavaJava定義一種虛擬機(jī)代碼定義一種虛擬機(jī)代碼BytecodeBytecode。 只要實(shí)際使用的操作平臺(tái)上實(shí)現(xiàn)了執(zhí)行只要實(shí)際使用的操作平臺(tái)上實(shí)現(xiàn)了執(zhí)行BytecodeBytecode的的JavaJava解解釋器，這個(gè)操作平臺(tái)就可以執(zhí)行各種釋器，這個(gè)操作平臺(tái)就可以執(zhí)行各種JavaJava程序。這就是所謂程序。這就是所謂JavaJava語(yǔ)言的操作平臺(tái)無(wú)關(guān)性。語(yǔ)言的操作平臺(tái)無(wú)關(guān)性。 1.4 1.4 編譯程序與程序設(shè)計(jì)環(huán)境編譯程序與程序設(shè)計(jì)環(huán)境 編譯程序無(wú)疑是實(shí)現(xiàn)高級(jí)語(yǔ)言的一個(gè)最重

51、要的工具。但支持程序設(shè)計(jì)編譯程序無(wú)疑是實(shí)現(xiàn)高級(jí)語(yǔ)言的一個(gè)最重要的工具。但支持程序設(shè)計(jì)人員進(jìn)行程序開發(fā)通常還需要一些其它的工具如編輯程序；連接程序；調(diào)人員進(jìn)行程序開發(fā)通常還需要一些其它的工具如編輯程序；連接程序；調(diào)試工具等。編譯程序與這些程序設(shè)計(jì)工具一起構(gòu)成所謂的程序設(shè)計(jì)環(huán)境。試工具等。編譯程序與這些程序設(shè)計(jì)工具一起構(gòu)成所謂的程序設(shè)計(jì)環(huán)境。 在高級(jí)語(yǔ)言發(fā)展的早期，這些程序設(shè)計(jì)工具往往是獨(dú)立的，缺乏整體在高級(jí)語(yǔ)言發(fā)展的早期，這些程序設(shè)計(jì)工具往往是獨(dú)立的，缺乏整體性，而且也缺乏對(duì)軟件開發(fā)全生命周期的支持。隨著軟件技術(shù)的不斷發(fā)展，性，而且也缺乏對(duì)軟件開發(fā)全生命周期的支持。隨著軟件技術(shù)的不斷發(fā)展，現(xiàn)在人

52、們?cè)絹?lái)越傾向于構(gòu)造集成化的程序設(shè)計(jì)環(huán)境?，F(xiàn)在人們?cè)絹?lái)越傾向于構(gòu)造集成化的程序設(shè)計(jì)環(huán)境。 一個(gè)集成化的程序設(shè)計(jì)環(huán)境的特點(diǎn)是，它將相互獨(dú)立的程序設(shè)計(jì)工具一個(gè)集成化的程序設(shè)計(jì)環(huán)境的特點(diǎn)是，它將相互獨(dú)立的程序設(shè)計(jì)工具集成起來(lái)，以便為程序員提供完整的、一體化的支持，從而進(jìn)一步提高程集成起來(lái)，以便為程序員提供完整的、一體化的支持，從而進(jìn)一步提高程序開發(fā)效率，改善程序質(zhì)量。在一個(gè)好的集成化程序設(shè)計(jì)環(huán)境中，不僅包序開發(fā)效率，改善程序質(zhì)量。在一個(gè)好的集成化程序設(shè)計(jì)環(huán)境中，不僅包含豐富的程序設(shè)計(jì)工具，而且還支持程序設(shè)計(jì)方法學(xué)，支持程序開發(fā)的全含豐富的程序設(shè)計(jì)工具，而且還支持程序設(shè)計(jì)方法學(xué)，支持程序開發(fā)的全生命周期

53、。有代表性的集成化程序設(shè)計(jì)環(huán)境有生命周期。有代表性的集成化程序設(shè)計(jì)環(huán)境有Ada語(yǔ)言程序設(shè)計(jì)環(huán)境語(yǔ)言程序設(shè)計(jì)環(huán)境APSE、LISP語(yǔ)言程序設(shè)計(jì)環(huán)境語(yǔ)言程序設(shè)計(jì)環(huán)境INTERLISP等。廣大讀者所熟悉的等。廣大讀者所熟悉的Turbo Pascal、Turbo C、Visual C+等語(yǔ)言環(huán)境也都可認(rèn)為是集成化的程序設(shè)計(jì)環(huán)境。等語(yǔ)言環(huán)境也都可認(rèn)為是集成化的程序設(shè)計(jì)環(huán)境。 下面以下面以Ada語(yǔ)言的程序設(shè)計(jì)環(huán)境語(yǔ)言的程序設(shè)計(jì)環(huán)境APSE為例，介紹程序設(shè)計(jì)環(huán)境的基本為例，介紹程序設(shè)計(jì)環(huán)境的基本構(gòu)成和主要工具。構(gòu)成和主要工具。 APSE是一個(gè)分層的程序設(shè)計(jì)環(huán)境，如圖是一個(gè)分層的程序設(shè)計(jì)環(huán)境，如圖1.6所示。

54、所示。 圖圖1.6 Ada程序設(shè)計(jì)環(huán)境程序設(shè)計(jì)環(huán)境 最內(nèi)層（第最內(nèi)層（第0層）是宿主計(jì)算機(jī)系統(tǒng)，它包括硬件、宿主操作系統(tǒng)和其層）是宿主計(jì)算機(jī)系統(tǒng)，它包括硬件、宿主操作系統(tǒng)和其它支持軟件。第一層是核心它支持軟件。第一層是核心APSE(KAPSE)。它包括環(huán)境數(shù)據(jù)庫(kù)、通信及運(yùn)。它包括環(huán)境數(shù)據(jù)庫(kù)、通信及運(yùn)行時(shí)支撐功能等。行時(shí)支撐功能等。 第二層，最小第二層，最小APSE(MAPSE)。它包括了。它包括了Ada程序開發(fā)及維護(hù)的基本工程序開發(fā)及維護(hù)的基本工具，這些工具包括編譯程序、編輯程序、連接程序、調(diào)試程序、命令解釋程具，這些工具包括編譯程序、編輯程序、連接程序、調(diào)試程序、命令解釋程序、配置管理程序、

55、美化打印程序、靜態(tài)分析工具，動(dòng)態(tài)分析工具等等。序、配置管理程序、美化打印程序、靜態(tài)分析工具，動(dòng)態(tài)分析工具等等。 第三層，第三層，APSE。在。在MAPSE外面再加上更廣泛的工具就構(gòu)成了完整的外面再加上更廣泛的工具就構(gòu)成了完整的APSE。對(duì)這一層沒有精確規(guī)定工具的類型，它通?？梢园嫦驊?yīng)用的工。對(duì)這一層沒有精確規(guī)定工具的類型，它通常可以包括面向應(yīng)用的工具和支持特定程序設(shè)計(jì)方法的工具等。可以是支持需求分析、設(shè)計(jì)、實(shí)現(xiàn)、具和支持特定程序設(shè)計(jì)方法的工具等?？梢允侵С中枨蠓治?、設(shè)計(jì)、實(shí)現(xiàn)、維護(hù)等軟件開發(fā)全生命周期的工具。維護(hù)等軟件開發(fā)全生命周期的工具。 在一個(gè)程序設(shè)計(jì)環(huán)境中，編譯程序起著中心的作用。連

56、接程序、調(diào)試程在一個(gè)程序設(shè)計(jì)環(huán)境中，編譯程序起著中心的作用。連接程序、調(diào)試程序、程序分析等工具的工作直接依賴于編譯程序所產(chǎn)生的結(jié)果，而其它工具序、程序分析等工具的工作直接依賴于編譯程序所產(chǎn)生的結(jié)果，而其它工具的構(gòu)造也常常要用到編譯的原理、方法和技術(shù)。的構(gòu)造也常常要用到編譯的原理、方法和技術(shù)。1.5 1.5 編譯程序的生成編譯程序的生成 以前人們構(gòu)造編譯程序大多是用機(jī)器語(yǔ)言或匯編語(yǔ)言作工具以前人們構(gòu)造編譯程序大多是用機(jī)器語(yǔ)言或匯編語(yǔ)言作工具的。為了充分發(fā)揮各種不同硬件系統(tǒng)的效率，為了滿足各種不的。為了充分發(fā)揮各種不同硬件系統(tǒng)的效率，為了滿足各種不同的具體要求，現(xiàn)在許多人仍然采用這種工具來(lái)構(gòu)造編譯

57、程序同的具體要求，現(xiàn)在許多人仍然采用這種工具來(lái)構(gòu)造編譯程序（或編譯程序的（或編譯程序的“核心核心”部分）。但是，越來(lái)越多的人已經(jīng)使部分）。但是，越來(lái)越多的人已經(jīng)使用高級(jí)語(yǔ)言作工具來(lái)編譯程序。因?yàn)?，這樣可以大大節(jié)省程序用高級(jí)語(yǔ)言作工具來(lái)編譯程序。因?yàn)?，這樣可以大大節(jié)省程序設(shè)計(jì)時(shí)間，而且所構(gòu)造出來(lái)的編譯程序易于閱讀、維護(hù)和移植。設(shè)計(jì)時(shí)間，而且所構(gòu)造出來(lái)的編譯程序易于閱讀、維護(hù)和移植。 為了便于說明，我們用一種為了便于說明，我們用一種T形圖來(lái)表示源語(yǔ)言形圖來(lái)表示源語(yǔ)言S S、目標(biāo)語(yǔ)、目標(biāo)語(yǔ)言言T和編譯程序?qū)崿F(xiàn)語(yǔ)言和編譯程序?qū)崿F(xiàn)語(yǔ)言I 之間的關(guān)系，如圖之間的關(guān)系，如圖1.7所示。所示。 STI圖圖1.

58、7 T型圖型圖 如果如果A機(jī)器上已有一個(gè)用機(jī)器上已有一個(gè)用A機(jī)器代碼實(shí)現(xiàn)的某高級(jí)語(yǔ)言機(jī)器代碼實(shí)現(xiàn)的某高級(jí)語(yǔ)言L1的的編譯程序，則我們可以用編譯程序，則我們可以用L1語(yǔ)言編寫另一種高級(jí)語(yǔ)言編寫另一種高級(jí)L2的編譯程序，的編譯程序，把寫好的把寫好的L2編譯程序經(jīng)過編譯程序經(jīng)過L1編譯程序編譯后就可得到編譯程序編譯后就可得到A機(jī)器代機(jī)器代碼實(shí)現(xiàn)的碼實(shí)現(xiàn)的L2編譯程序，如圖編譯程序，如圖1.8所示。所示。 圖圖1.8 用用L1語(yǔ)言編寫編譯程序語(yǔ)言編寫編譯程序L2AL1L1AAL2AAA機(jī)器有機(jī)器有C語(yǔ)言，希望實(shí)現(xiàn)語(yǔ)言，希望實(shí)現(xiàn)PASCAL語(yǔ)言的編譯器的語(yǔ)言的編譯器的T型圖如型圖如1.8 采用一種所謂的

59、采用一種所謂的“移植移植”方法，我們可以利用方法，我們可以利用A機(jī)器上已有的高級(jí)語(yǔ)言機(jī)器上已有的高級(jí)語(yǔ)言L編寫一個(gè)能夠在編寫一個(gè)能夠在B機(jī)器上運(yùn)行的高級(jí)語(yǔ)言機(jī)器上運(yùn)行的高級(jí)語(yǔ)言L的編譯程序。做法是，先用的編譯程序。做法是，先用L語(yǔ)語(yǔ)言編寫出在言編寫出在A機(jī)器上運(yùn)行的產(chǎn)生機(jī)器上運(yùn)行的產(chǎn)生B機(jī)器代碼的機(jī)器代碼的L編譯程序源程序，然后把該編譯程序源程序，然后把該源程序經(jīng)過源程序經(jīng)過A機(jī)器上的機(jī)器上的L編譯程序編譯后得到能在編譯程序編譯后得到能在A機(jī)器上運(yùn)行的產(chǎn)生機(jī)器上運(yùn)行的產(chǎn)生B機(jī)器機(jī)器代碼的編譯程序，用這個(gè)編譯程序再一次編譯上述編譯程序源程序就得到了代碼的編譯程序，用這個(gè)編譯程序再一次編譯上述編譯

60、程序源程序就得到了能在能在B機(jī)器上運(yùn)行的產(chǎn)生機(jī)器上運(yùn)行的產(chǎn)生B機(jī)器代碼的編譯程序。用機(jī)器代碼的編譯程序。用T形圖表示為圖形圖表示為圖1.9所示。所示。 圖圖1-9 編譯程序編譯程序“移植移植”LBLLAALBALBLLBB 我們還可以采用我們還可以采用“自編譯方式自編譯方式”產(chǎn)生編譯程序。方法是，產(chǎn)生編譯程序。方法是，先對(duì)語(yǔ)言的核心部分構(gòu)造一個(gè)小小的編譯程序（可用低級(jí)語(yǔ)先對(duì)語(yǔ)言的核心部分構(gòu)造一個(gè)小小的編譯程序（可用低級(jí)語(yǔ)言實(shí)現(xiàn)），再以它為工具構(gòu)造一個(gè)能夠編譯更多語(yǔ)言成分的言實(shí)現(xiàn)），再以它為工具構(gòu)造一個(gè)能夠編譯更多語(yǔ)言成分的較大編譯程序。如此擴(kuò)展下去，就像滾雪球一樣，越滾越大，較大編譯程序。如此