編譯程序概論

1、1任課教師：湛 燕Email: 數(shù)學與計算機學院2 名名 稱稱 作作 者者 出版社出版社 出版時間出版時間 編譯原理編譯原理 何炎祥何炎祥 華中理工大學華中理工大學 2000.102000.10 編譯原理編譯原理 陳火旺等陳火旺等 國防工業(yè)出版社國防工業(yè)出版社 2000.12000.1 編譯原理編譯原理 蔣立源蔣立源 西北工業(yè)大學西北工業(yè)大學 1999.91999.9編譯原理（第二版）編譯原理（第二版）. 張素琴，呂映芝，蔣維杜，戴桂蘭編張素琴，呂映芝，蔣維杜，戴桂蘭編著，清華大學出版社，著，清華大學出版社，2005.2. . 教教 材材 與與 參參 考考 書書編譯原理及實踐3第一章 編譯程序

2、概論主要介紹編譯程序的主要介紹編譯程序的、。1.1 什么是編譯程序什么是編譯程序1.2 編譯過程及編譯程序結(jié)構(gòu)編譯過程及編譯程序結(jié)構(gòu)1.2.1 編譯過程編譯過程1.2.2 編譯程序的基本結(jié)構(gòu)編譯程序的基本結(jié)構(gòu)1.3 編譯技術(shù)和軟件工具編譯技術(shù)和軟件工具1.4 程序設計語言范型程序設計語言范型41.1 什么是編譯程序（compilercompiler）v 源程序的加工過程源程序的加工過程v 與編譯程序相關(guān)的程序與編譯程序相關(guān)的程序 編譯程序是現(xiàn)代計算機系統(tǒng)的基本組成部分之一，而且多數(shù)編譯程序是現(xiàn)代計算機系統(tǒng)的基本組成部分之一，而且多數(shù)計算機系統(tǒng)計算機系統(tǒng)尤其是嵌入式系統(tǒng)和高性能體系結(jié)構(gòu)尤其是嵌入

3、式系統(tǒng)和高性能體系結(jié)構(gòu)都含有不止一個都含有不止一個高級語言的編譯程序，對有些高級語言甚至配置了幾個不同性能高級語言的編譯程序，對有些高級語言甚至配置了幾個不同性能的編譯程序。的編譯程序。 從功能上看，一個編譯程序就是一個語言翻譯程序。從功能上看，一個編譯程序就是一個語言翻譯程序。5翻譯程序翻譯程序翻譯程序是指這樣一個程序，它把一種語言（翻譯程序是指這樣一個程序，它把一種語言（）所）所寫的程序（寫的程序（）翻譯成與之）翻譯成與之的另一種語言（的另一種語言（）的程序（）的程序（）。）。n源語言：源語言：source languagesource languagen源程序：源程序：source pr

4、ogramsource programn目標語言：目標語言：object or target languageobject or target languagen目標程序：目標程序：object or target programobject or target program6編譯程序（編譯器編譯程序（編譯器compiler）如果源語言是高級語言，目標語言是低級語言，那么稱這如果源語言是高級語言，目標語言是低級語言，那么稱這樣的翻譯程序為樣的翻譯程序為。q高級語言：高級語言：C C、PASCALPASCAL、C+C+、FORTRANFORTRAN、JAVAJAVAq低級語言：匯編語言、機器語

5、言低級語言：匯編語言、機器語言高級語言高級語言所寫程序所寫程序匯編語言或匯編語言或機器語言程序機器語言程序7匯編程序（匯編程序（Assembler）如果源語言是匯編語言，目標語言是機器語言，那么稱這如果源語言是匯編語言，目標語言是機器語言，那么稱這樣的翻譯程序為樣的翻譯程序為。匯編語言匯編語言所寫程序所寫程序機器語言程序機器語言程序8源程序的加工過程源程序的加工過程采用編譯方式在計算機上執(zhí)行高級語言編寫的程序，一般采用編譯方式在計算機上執(zhí)行高級語言編寫的程序，一般分兩大階段，分兩大階段，和和。9如果編譯階段生成的目標程序不是機器程序，而是匯編程如果編譯階段生成的目標程序不是機器程序，而是匯編程

6、序，則程序的執(zhí)行需分三個階段，序，則程序的執(zhí)行需分三個階段，、和和。10編譯程序的發(fā)展歷史編譯程序的發(fā)展歷史第一個編譯程序第一個編譯程序FortranFortran編譯程序（編譯程序（2020世紀世紀5050年代年代）編譯程序自動生成工具（編譯程序自動生成工具（2020世紀世紀5050年代末年代末） 以任一語言的詞法規(guī)則、語法規(guī)則和語義解釋出發(fā)，自動產(chǎn)生該語言的以任一語言的詞法規(guī)則、語法規(guī)則和語義解釋出發(fā)，自動產(chǎn)生該語言的編譯程序。編譯程序。 LEXLEX是一個詞法分析器的自動產(chǎn)生系統(tǒng)是一個詞法分析器的自動產(chǎn)生系統(tǒng) YACCYACC是一個語法分析程序的自動產(chǎn)生器是一個語法分析程序的自動產(chǎn)生器應

7、用自展技術(shù)構(gòu)造編譯程序（應用自展技術(shù)構(gòu)造編譯程序（2020世紀世紀6060年代年代） 自展技術(shù)就是用被編譯的語言來書寫該語言自身的編譯程序。首先對語自展技術(shù)就是用被編譯的語言來書寫該語言自身的編譯程序。首先對語言的核心部分構(gòu)造一個小小的編譯程序，再以它為工具構(gòu)造一個能夠編譯更言的核心部分構(gòu)造一個小小的編譯程序，再以它為工具構(gòu)造一個能夠編譯更多語言成分的較大的編譯程序。如此繼續(xù)下去，最后形成所期望的整個編譯多語言成分的較大的編譯程序。如此繼續(xù)下去，最后形成所期望的整個編譯程序。這種通過一系列自展途徑而形成編譯程序的過程，叫做自編譯過程。程序。這種通過一系列自展途徑而形成編譯程序的過程，叫做自編譯

8、過程。 并行編譯技術(shù)并行編譯技術(shù)需進一步研究的問題需進一步研究的問題 處理并行語言的并行編譯技術(shù)、串行程序轉(zhuǎn)換成并行程序的自動并行編處理并行語言的并行編譯技術(shù)、串行程序轉(zhuǎn)換成并行程序的自動并行編譯技術(shù)等。譯技術(shù)等。111.2 編譯過程和編譯程序的結(jié)構(gòu)編譯過程和編譯程序的結(jié)構(gòu)編譯過程是一種語言的翻譯過程，它的工作過程類似于編譯過程是一種語言的翻譯過程，它的工作過程類似于外外文文的翻譯過程。的翻譯過程?！纠坑⑽木渥臃g成中文句子的大致過程是：【例】英文句子翻譯成中文句子的大致過程是：v 詞法分析：根據(jù)英語的詞法規(guī)則，從由字母、空格字符和各詞法分析：根據(jù)英語的詞法規(guī)則，從由字母、空格字符和各種標點

9、符號所組成的字符串中識別出一個一個的英文單詞。種標點符號所組成的字符串中識別出一個一個的英文單詞。v 語法分析：根據(jù)英語的語法規(guī)則，對詞法分析后的單詞串進語法分析：根據(jù)英語的語法規(guī)則，對詞法分析后的單詞串進行分析、識別，并做語法正確性檢查，看其是否組成一個符行分析、識別，并做語法正確性檢查，看其是否組成一個符合英語語法的句子。合英語語法的句子。v 語義分析：對正確的英文句子分析其含義并用漢語表示出來語義分析：對正確的英文句子分析其含義并用漢語表示出來.v 根據(jù)上下文的關(guān)系以及漢語語法的有關(guān)規(guī)則對詞句作必要的根據(jù)上下文的關(guān)系以及漢語語法的有關(guān)規(guī)則對詞句作必要的修飾工作。修飾工作。v 最后翻譯成中

10、文。最后翻譯成中文。121.2.1 編譯過程概述編譯過程概述編譯過程一般分為以下六個階段編譯過程一般分為以下六個階段（與自然語言翻譯過程對比）：（與自然語言翻譯過程對比）： 詞法分析詞法分析 語法分析語法分析 語義分析語義分析 中間代碼生成中間代碼生成 代碼優(yōu)化代碼優(yōu)化 目標代碼生成目標代碼生成13對于對于PASCAL程序段程序段通過詞法分析，可識別出如下的單詞符號序列：通過詞法分析，可識別出如下的單詞符號序列：基本字基本字: begin,var,real,end 標識符標識符:sum,first,count整數(shù)：整數(shù)：10 界符：界符：。 逗號：逗號：， 冒號：冒號：分號：分號：； 賦值號：

11、賦值號：:= 加號：加號：+ 乘號：乘號：* 機內(nèi)碼為：機內(nèi)碼為：id1:=id2+id3*101、詞法分析（掃描器）、詞法分析（掃描器）v 任務任務：源程序：源程序 單詞符號串單詞符號串 從左至右一個字符一個字符地讀入源程序，對構(gòu)成源程序的從左至右一個字符一個字符地讀入源程序，對構(gòu)成源程序的字符流進行掃描和分解，從而識別出一個個單詞符號字符流進行掃描和分解，從而識別出一個個單詞符號. .v 依據(jù)依據(jù)：語言的詞法規(guī)則：語言的詞法規(guī)則 v 描述詞法規(guī)則的工具描述詞法規(guī)則的工具：正則式、正則文法、有限自動機：正則式、正則文法、有限自動機142、語法分析、語法分析例如：符號串例如：符號串 id1:=

12、id2+id3*10經(jīng)過語法分析知它代表一個賦值語句經(jīng)過語法分析知它代表一個賦值語句. .v 任務任務：單詞符號串：單詞符號串 各類語法單位各類語法單位 在詞法分析的基礎上將單詞序列分解成各類語法短語在詞法分析的基礎上將單詞序列分解成各類語法短語.通常通常用語法樹表示這種語法短語用語法樹表示這種語法短語.v 依據(jù)依據(jù)：語言的語法規(guī)則：語言的語法規(guī)則 v 描述語法規(guī)則的工具描述語法規(guī)則的工具：上下文無關(guān)文法、確定的下推自動機：上下文無關(guān)文法、確定的下推自動機15對應的語法樹如下：對應的語法樹如下： 語句語句id1:=id2+id3*10的語法樹的語法樹16定義表達式的規(guī)則：定義表達式的規(guī)則：任何

13、標識符是表達式。任何標識符是表達式。任何常數(shù)（整常數(shù)、實常數(shù)）是表達式。任何常數(shù)（整常數(shù)、實常數(shù)）是表達式。1.1. 若表達式若表達式1 1和表達式和表達式2 2都是表達式，那么都是表達式，那么 表達式表達式1+1+表達式表達式2 2 表達式表達式1 1* *表達式表達式2 2 （表達式（表達式1 1）都是表達式。都是表達式。程序結(jié)構(gòu)（程序結(jié)構(gòu)（1）程序結(jié)構(gòu)通常采用遞歸規(guī)則表示，也就是用來描述程序結(jié)構(gòu)程序結(jié)構(gòu)通常采用遞歸規(guī)則表示，也就是用來描述程序結(jié)構(gòu)的規(guī)則。的規(guī)則。例如：定義表達式的規(guī)則、定義語句的規(guī)則例如：定義表達式的規(guī)則、定義語句的規(guī)則17語句的表示：語句的表示： 是語句。是語句。1.

14、和和都是語句。都是語句。程序結(jié)構(gòu)（程序結(jié)構(gòu)（2）183、語義分析（、語義分析（1）語義語義 定義語言的單詞符號和語法單位的意義定義語言的單詞符號和語法單位的意義. .一個語言的一個語言的語義是指這樣的一組規(guī)則，使用它可以定義一個程序的語義是指這樣的一組規(guī)則，使用它可以定義一個程序的意義意義. .這些規(guī)則稱為語義規(guī)則這些規(guī)則稱為語義規(guī)則. . 離開語義，語言只不過是一堆符號的集合離開語義，語言只不過是一堆符號的集合. .語義分析階段的主要任務語義分析階段的主要任務審查源程序有無語義錯誤，為代碼生成階段收集類型信審查源程序有無語義錯誤，為代碼生成階段收集類型信息息. .193、語義分析（、語義分析

15、（2）類型審查、數(shù)組下標檢查、強制類型轉(zhuǎn)換等類型審查、數(shù)組下標檢查、強制類型轉(zhuǎn)換等例如：例如：增加的語義處理節(jié)點，表示整型轉(zhuǎn)換成實型的一目算符語句語句id1:=id2+id3id1:=id2+id3* *1010的語義分析（類型審查）過程：的語義分析（類型審查）過程：204、中間代碼產(chǎn)生、中間代碼產(chǎn)生序號序號算符算符左操作數(shù)左操作數(shù)右操作數(shù)右操作數(shù)結(jié)果結(jié)果(1)inttoreal10-t1(2)*id3t1t2(3)+id2t2t3(4):=t3-id1v 任務任務：語法單位：語法單位 初步翻譯、產(chǎn)生中間代碼初步翻譯、產(chǎn)生中間代碼v 中間代碼中間代碼：是一種結(jié)構(gòu)簡單含義明確的記號系統(tǒng)：是一種結(jié)

16、構(gòu)簡單含義明確的記號系統(tǒng).例如，四例如，四元式、三元式、逆波蘭式等元式、三元式、逆波蘭式等.v 依據(jù)依據(jù)：語言的語義規(guī)則：語言的語義規(guī)則 v 設計原則：設計原則：1）容易生成）容易生成2）容易翻譯成目標代碼）容易翻譯成目標代碼 在在PASCAL語言中，符號串語言中，符號串: id1:=id2+id3*10 可產(chǎn)生一種四元式形式的中間代碼：可產(chǎn)生一種四元式形式的中間代碼：215、代碼優(yōu)化、代碼優(yōu)化v 任務：任務：中間代碼中間代碼 高效的中間代碼高效的中間代碼 對中間代碼進行變換或進行改造，以便生成高效的中間代碼對中間代碼進行變換或進行改造，以便生成高效的中間代碼（省時間和空間）（省時間和空間）.

17、v 依據(jù)：依據(jù)：等價變換規(guī)則等價變換規(guī)則 v 變換方法：變換方法：公共子表達式的提取、循環(huán)優(yōu)化、刪除無用代碼等公共子表達式的提取、循環(huán)優(yōu)化、刪除無用代碼等序號序號算符算符左操作數(shù)左操作數(shù)右操作數(shù)右操作數(shù)結(jié)果結(jié)果(1)*id310.0t1(2)+id2t1id1優(yōu)化后的中間代碼：優(yōu)化后的中間代碼：226、目標代碼生成v 任務：任務：中間代碼中間代碼依賴于機器的目標代碼（匯編語言或機器語言）依賴于機器的目標代碼（匯編語言或機器語言）v 涉及的主要問題：涉及的主要問題：指令的選擇指令的選擇內(nèi)存的分配內(nèi)存的分配寄存器的分配寄存器的分配目標代碼的形式：目標代碼的形式：絕對指令代碼絕對指令代碼匯編指令代碼

18、匯編指令代碼可重定位的指令代碼可重定位的指令代碼23目標代碼生成目標代碼生成賦值語句賦值語句中間代碼四元式中間代碼四元式目標代碼目標代碼241.2.2 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)詞法分析器詞法分析器語法分析器語法分析器語義分析及中間代碼生成器語義分析及中間代碼生成器優(yōu)化器優(yōu)化器目標代碼生成器目標代碼生成器 出出 錯錯 處處 理理 程程 序序 表表 格格 管管 理理 程程 序序源程序源程序單詞符號單詞符號語法單位語法單位中間代碼中間代碼中間代碼中間代碼目標代碼目標代碼n 編譯程序總框編譯程序總框25 表格與表格管理表格與表格管理用途：登記源程序的各類信息和編譯程序各階段的進用途：登記源程序的各

19、類信息和編譯程序各階段的進展情況，如符號表。展情況，如符號表。管理：構(gòu)造、查找、或更新。管理：構(gòu)造、查找、或更新。 出錯處理出錯處理任務：發(fā)現(xiàn)并指出源程序中錯誤的性質(zhì)和位置；任務：發(fā)現(xiàn)并指出源程序中錯誤的性質(zhì)和位置； 自動校正錯誤。自動校正錯誤。26遍（遍（pass)pass)：對源程序或源程序的中間結(jié)果從頭至尾掃描一次，并作對源程序或源程序的中間結(jié)果從頭至尾掃描一次，并作有關(guān)的加工處理，生成新的有關(guān)的加工處理，生成新的中間結(jié)果或目標程序中間結(jié)果或目標程序的處理的處理過程稱為一遍。過程稱為一遍?？梢园岩粋€階段分為若干遍，也可以把多個階段合為一可以把一個階段分為若干遍，也可以把多個階段合為一遍，

20、通常有一遍和多遍編譯程序。遍，通常有一遍和多遍編譯程序。1.2.3 編譯階段的組合編譯階段的組合27詞法分析詞法分析語法分析語法分析語義分析與中間代碼生成語義分析與中間代碼生成優(yōu)化優(yōu)化目標代碼生成目標代碼生成編譯的前端與后端：編譯的前端與后端：由與源語言有關(guān)但與目標機無關(guān)的部分組成。由與源語言有關(guān)但與目標機無關(guān)的部分組成。包括與目標機有關(guān)的部分。包括與目標機有關(guān)的部分。而一般不依賴于源語言，只而一般不依賴于源語言，只與中間代碼有關(guān)的編譯階段。與中間代碼有關(guān)的編譯階段。28一個語言的一個語言的是這樣的程是這樣的程序：序：它以該語言寫的源程序作為輸入，它以該語言寫的源程序作為輸入，但但，而是，而是

21、源程序本身。源程序本身。-與編譯程序相關(guān)的程序與編譯程序相關(guān)的程序v 解釋程序（解釋程序（interpreter）v 匯編程序（匯編程序（assembler）v 連接程序（連接程序（linker）v 預處理程序（預處理程序（preprocessor）v 編輯器（編輯器（editor）v 調(diào)試程序（調(diào)試程序（debugger）匯編程序是用于特定計算機上的匯編程序是用于特定計算機上的的翻譯程序。的翻譯程序。有時編譯器把匯編語言作為目標有時編譯器把匯編語言作為目標語言，然后再由匯編程序?qū)⑺Z言，然后再由匯編程序?qū)⑺g成目標代碼。譯成目標代碼。連接程序?qū)⒎謩e在不同的目標文連接程序?qū)⒎謩e在不同的目標

22、文件中編譯或匯編的代碼收集到一件中編譯或匯編的代碼收集到一個可直接執(zhí)行的文件中。個可直接執(zhí)行的文件中。在這種情況下，目標代碼（即還在這種情況下，目標代碼（即還未被連接的機器代碼）與可執(zhí)行未被連接的機器代碼）與可執(zhí)行代碼的機器代碼之間有了區(qū)別。代碼的機器代碼之間有了區(qū)別。連接程序還連接目標程序和用于連接程序還連接目標程序和用于標準庫函數(shù)的代碼，以及連接目標準庫函數(shù)的代碼，以及連接目標程序和計算機的操作系統(tǒng)提供標程序和計算機的操作系統(tǒng)提供的資源的資源(存儲分配程序及存儲分配程序及IO設備設備)預處理程序是在真正的編譯開始預處理程序是在真正的編譯開始之前由編譯器調(diào)用的獨立程序。之前由編譯器調(diào)用的獨立

23、程序。預處理程序可以刪除預處理程序可以刪除、以及執(zhí)行以及執(zhí)行。編譯器通常接受由任何生成標準編譯器通常接受由任何生成標準文件（例如文件（例如ASCII）的編輯器編）的編輯器編寫的源程序。最近，編譯器已與寫的源程序。最近，編譯器已與一個編輯器和其它程序捆綁進一一個編輯器和其它程序捆綁進一個交互的開發(fā)環(huán)境個交互的開發(fā)環(huán)境IDE中。中。調(diào)試程序是可在被編譯了的程序調(diào)試程序是可在被編譯了的程序中判定執(zhí)行錯誤的程序。中判定執(zhí)行錯誤的程序。運行一個帶有調(diào)試程序的程序與運行一個帶有調(diào)試程序的程序與直接執(zhí)行不同，因為調(diào)試程序保直接執(zhí)行不同，因為調(diào)試程序保存著大多數(shù)的源代碼信息。存著大多數(shù)的源代碼信息。1.3.1

24、 編譯技術(shù)和軟件工具編譯技術(shù)和軟件工具29301.3.2 編譯技術(shù)和軟件工具（編譯技術(shù)和軟件工具（1）開發(fā)高質(zhì)量與高效率的軟件遵循的要求：開發(fā)高質(zhì)量與高效率的軟件遵循的要求：1 1）軟件工程中要求的規(guī)范化標準）軟件工程中要求的規(guī)范化標準2 2）先進的軟件開發(fā)技術(shù)及其軟件工具）先進的軟件開發(fā)技術(shù)及其軟件工具語言的結(jié)構(gòu)化編輯器語言的結(jié)構(gòu)化編輯器 結(jié)構(gòu)化編輯器是引導用戶在語言的語法制導下編制程結(jié)構(gòu)化編輯器是引導用戶在語言的語法制導下編制程序，能夠自動地提供關(guān)鍵字和與其匹配地關(guān)鍵字序，能夠自動地提供關(guān)鍵字和與其匹配地關(guān)鍵字. .例例如，如，EditplusEditplus、UltraeditUltra

25、edit、JbuilderJbuilder等等語言程序的調(diào)試工具語言程序的調(diào)試工具 對算法的錯誤或程序未能反應算法的功能等錯誤進行對算法的錯誤或程序未能反應算法的功能等錯誤進行調(diào)試調(diào)試. .軟件工具開發(fā)用到的編譯技術(shù)與方法：軟件工具開發(fā)用到的編譯技術(shù)與方法：31語言程序的測試工具：語言程序的測試工具：靜態(tài)分析器與動態(tài)測試器靜態(tài)分析器與動態(tài)測試器 靜態(tài)分析器靜態(tài)分析器 在不運行程序的情況下對源程序進行靜態(tài)地分析，在不運行程序的情況下對源程序進行靜態(tài)地分析，以發(fā)現(xiàn)程序中潛在的錯誤或異常。對源程序進行語以發(fā)現(xiàn)程序中潛在的錯誤或異常。對源程序進行語法分析并制定相應表格，檢查變量定值與引用的關(guān)法分析并制

26、定相應表格，檢查變量定值與引用的關(guān)系。系。 例如：某變量未被賦值就被引用；變量定值后未被例如：某變量未被賦值就被引用；變量定值后未被引用；多余的源代碼等引用；多余的源代碼等. .1.3.2 編譯技術(shù)和軟件工具（編譯技術(shù)和軟件工具（2）32語言程序的測試工具：語言程序的測試工具：靜態(tài)分析器與動態(tài)測試器靜態(tài)分析器與動態(tài)測試器 動態(tài)測試器動態(tài)測試器 在源程序的適當位置插入某些信息，在源程序的適當位置插入某些信息，并用測試用例記錄（顯示語句或函數(shù)）程序運行時并用測試用例記錄（顯示語句或函數(shù)）程序運行時的實際路徑的實際路徑. .將運行結(jié)果與期望結(jié)果進行比較分析，將運行結(jié)果與期望結(jié)果進行比較分析，幫助編程人員查找問題幫助編程人員查找問題. . 1.3.2 編譯技術(shù)和軟件工具（編譯技術(shù)和軟件工具（3）高級語言之間的轉(zhuǎn)換工具高級語言之間的轉(zhuǎn)換工具程序格式化工具程序格式化工具程序理解工具程序理解工具 對程序進行分析，確定模塊間的調(diào)用關(guān)系，記錄程序數(shù)對程序進行分析，確定模塊間的調(diào)用關(guān)系，記錄程序數(shù)據(jù)的靜態(tài)屬性和結(jié)構(gòu)屬性，并畫出控制流程圖，幫助用據(jù)的靜態(tài)屬性和結(jié)構(gòu)屬性，并畫出控制流程圖，幫助用戶理解程序。戶理解程序。33 1.4 程序設計語言范型（程序設計語言范型（1）強制式語言（過程式語言）強制式語言（過程式語言） 面向動作，即一個計算過程就是一系列動作