第01章_編譯概述.

1、1234561. 為什么有些語言規(guī)定標識符不能超過為什么有些語言規(guī)定標識符不能超過8個字符？而有些語個字符？而有些語言對標識符的長度無限制？言對標識符的長度無限制？ 2. 為什么有些語言能實現(xiàn)遞歸，而有些語言不能？為什么有些語言能實現(xiàn)遞歸，而有些語言不能？ 3. C語言規(guī)定數(shù)組下界為語言規(guī)定數(shù)組下界為0，上界為聲明的數(shù)減，上界為聲明的數(shù)減1，為什么？，為什么？ 4. 嵌套的嵌套的IF語句規(guī)定語句規(guī)定ELSE與上面最近的與上面最近的IF配對，為什么？配對，為什么？5. 為什么有些程序運行一段時間后會導致內存溢出？為什么有些程序運行一段時間后會導致內存溢出？ 當我們學完編譯后，這些問題就可以得到解

2、答。當我們學完編譯后，這些問題就可以得到解答。78編譯系統(tǒng)：編譯程序和運行程序編譯系統(tǒng)：編譯程序和運行程序編譯程序編譯程序目標程序目標程序源程序源程序91011121314源程序源程序翻譯程序翻譯程序目標程序目標程序SOURCE PROGRAMTRANSLATER OBJECT PROGRAM1516高級語言高級語言源程序源程序 編譯編譯程序程序 機器語言機器語言目標程序目標程序 目標程序目標程序 +運行子程序運行子程序 運行運行結果結果 數(shù)據(jù)數(shù)據(jù) 編譯階段編譯階段 執(zhí)行階段執(zhí)行階段 17高級語言源程序高級語言源程序 編譯程序編譯程序 匯編語言目標程序匯編語言目標程序 匯編程序匯編程序機器語言

3、目標程序機器語言目標程序 運行結果運行結果 目標程序目標程序 + +運行子程序運行子程序 數(shù)據(jù)數(shù)據(jù) 編譯階段編譯階段 匯編階段匯編階段 運行階段運行階段 18源程序源程序 數(shù)據(jù)數(shù)據(jù) 解釋程序解釋程序 結果結果 19詞法詞法分析分析 語法語法分析分析 語義語義分析分析 代碼代碼優(yōu)化優(yōu)化目標代碼目標代碼生成生成分析階段分析階段綜合階段綜合階段 錯誤處理錯誤處理符號表符號表2021S.PO.P語義分析及生成中間代碼程序語義分析及生成中間代碼程序代碼生成程序代碼生成程序代碼優(yōu)化程序代碼優(yōu)化程序語法分析程序語法分析程序詞法分析程序詞法分析程序錯錯誤誤處處理理符符號號表表管管理理22字符序列字符序列編碼形

4、式編碼形式單詞單詞：是語言的基本語法單位是語言的基本語法單位 保留字保留字（如（如:if:if、elseelse、whilewhile） 標識符標識符（如（如:max:max、minmin、strstr） 常數(shù)常數(shù) （如（如:12:12、6.86.8、a a） 分界符分界符（如（如:+:+、- -、* *、/ /、; ;、（、）、（、） ）23例如：例如：a=10+ca=10+c* *2020符號符號記號記號單詞單詞100IDa21=200NUM1022+100IDc25*200NUM20a=10+C*20a=10+C*20a=10+C*202425我們我們是是一家人一家人我我是是大學生大學生

5、26S.PO.P語義分析及生成中間代碼程序語義分析及生成中間代碼程序代碼生成程序代碼生成程序代碼優(yōu)化程序代碼優(yōu)化程序語法分析程序語法分析程序詞法分析程序詞法分析程序錯錯誤誤處處理理符符號號表表管管理理27文法文法 :=:= “= =” :=:= “+ +” | | “* *” :=:=“( (” “) )” | | | | | | 28句子句子 謂語謂語 主語主語 賓語賓語 動詞動詞( (吃吃) ) 名詞名詞( (猴子猴子) ) 名詞名詞( (香蕉香蕉) ) 圖圖1.51.5句子句子“猴子吃香蕉猴子吃香蕉”的語法分析樹的語法分析樹 語法分析與語法分析與語文中分析句子成分語文中分析句子成分相類似

6、，根據(jù)句子相類似，根據(jù)句子由主語、謂語組成，謂語由動詞、賓語組成等語言規(guī)則，由主語、謂語組成，謂語由動詞、賓語組成等語言規(guī)則，可對句子可對句子“猴子吃香蕉猴子吃香蕉”的進行分析，分析過程常用語的進行分析，分析過程常用語法樹來表示句子。法樹來表示句子。29表達式表達式 = ID（a） 項項 + 表達式表達式項項表達式表達式 NUM（20） ID（c） NUM （10） 因子因子 * 因子因子 因子因子項項30S.PO.P語義分析及生成中間代碼程序語義分析及生成中間代碼程序代碼生成程序代碼生成程序代碼優(yōu)化程序代碼優(yōu)化程序語法分析程序語法分析程序詞法分析程序詞法分析程序錯錯誤誤處處理理符符號號表表管

7、管理理3132表達式：表達式：a=10+ca=10+c* *2020表達式表達式 = ID（a） 項項 + 表達式表達式項項表達式表達式 NUM（20） ID（c） NUM （10） 因子因子 * 因子因子 因子因子項項33例如表達式例如表達式 (a+b)*(c+d)翻譯成四元式的中翻譯成四元式的中間代碼如下：間代碼如下：(+ , a , b , t1)(+ , c , d , t2)(* , t1 , t2 , t3)LOAD a 將將a的內容加載到操作數(shù)棧的內容加載到操作數(shù)棧LOAD b 將將a的內容加載到操作數(shù)棧的內容加載到操作數(shù)棧ADD 將操作數(shù)棧頂?shù)膬蓚€單元的內容相加將操作數(shù)棧頂?shù)膬?/p>

8、個單元的內容相加STO t1 將操作數(shù)棧頂?shù)膬热荽嫒雴卧獙⒉僮鲾?shù)棧頂?shù)膬热荽嫒雴卧猼1LOAD c 將將c的內容加載到操作數(shù)棧的內容加載到操作數(shù)棧LOAD d 將將d的內容加載到操作數(shù)棧的內容加載到操作數(shù)棧ADD 將操作數(shù)棧頂?shù)膬蓚€單元的內容相加將操作數(shù)棧頂?shù)膬蓚€單元的內容相加STO t2 將操作數(shù)棧頂?shù)膬热荽嫒雴卧獙⒉僮鲾?shù)棧頂?shù)膬热荽嫒雴卧猼2LOAD t1 將將t1的內容加載到操作數(shù)棧的內容加載到操作數(shù)棧LOAD t2 將將t2的內容加載到操作數(shù)棧的內容加載到操作數(shù)棧MULT 將操作數(shù)棧頂?shù)膬蓚€單元的內容相乘將操作數(shù)棧頂?shù)膬蓚€單元的內容相乘STO t3 將累加器的內容存入單元將累加器的內容

9、存入單元t3 翻譯成某個抽象機的翻譯成某個抽象機的匯編指令代碼：匯編指令代碼：中間代碼生成34S.PO.P語義分析及生成中間代碼程序語義分析及生成中間代碼程序代碼生成程序代碼生成程序代碼優(yōu)化程序代碼優(yōu)化程序語法分析程序語法分析程序詞法分析程序詞法分析程序錯錯誤誤處處理理符符號號表表管管理理35有四元式指令代碼如下：有四元式指令代碼如下：(*，3.14，2，t1)(=,t1,_,x)(*,2,5,t2)(*,t2,a,t3)(=,t3,_,y)(+,x,1,t4)(=,t4,_,z) 而優(yōu)化后的代碼如下：而優(yōu)化后的代碼如下：(=,6.28,_,x)(*,10,a,y)(=,7.28,_,z) 代

10、碼優(yōu)化不是編譯程序的必要組成部分，不同的代碼優(yōu)化不是編譯程序的必要組成部分，不同的編譯程序所進行的代碼優(yōu)化程度差別很大，能夠編譯程序所進行的代碼優(yōu)化程度差別很大，能夠完成代碼優(yōu)化的編譯程序稱為完成代碼優(yōu)化的編譯程序稱為“優(yōu)化編譯程序優(yōu)化編譯程序”。 36S.PO.P語義分析及生成中間代碼程序語義分析及生成中間代碼程序代碼生成程序代碼生成程序代碼優(yōu)化程序代碼優(yōu)化程序語法分析程序語法分析程序詞法分析程序詞法分析程序錯錯誤誤處處理理符符號號表表管管理理3738每個階段中都要有：每個階段中都要有：符號表管理符號表管理和和錯誤處理錯誤處理標識符名標識符名標識符類型標識符類型 類型類型 地址地址 aaa1

11、（表示變量）（表示變量） 1（表示整型）（表示整型） 0001 3940S.PO.P語義分析及生成中間代碼程序語義分析及生成中間代碼程序代碼生成程序代碼生成程序代碼優(yōu)化程序代碼優(yōu)化程序語法分析程序語法分析程序詞法分析程序詞法分析程序錯錯誤誤處處理理符符號號表表管管理理41 第一遍第一遍 第二遍第二遍 S.P中間形式中間形式1S.P中間形式中間形式2C2C1S.PO.P 上一遍的結果是下一遍的輸入，最后一遍生成目標程序。上一遍的結果是下一遍的輸入，最后一遍生成目標程序。42語法分析函數(shù)語法分析函數(shù) 詞法分析子程序；詞法分析子程序； 語義分析子程序；語義分析子程序；43詞法分析詞法分析 源程序源程

12、序 取單詞取單詞 目標程序目標程序 開始開始 語法分析語法分析 語義分析及代碼生成語義分析及代碼生成 送單詞送單詞 典型的單遍編譯程序結構如圖所示典型的單遍編譯程序結構如圖所示 1、當語法分析需要讀進一個新單詞、當語法分析需要讀進一個新單詞時，就調用詞法分析子程序。詞法時，就調用詞法分析子程序。詞法分析子程序則從源程序中依次讀入分析子程序則從源程序中依次讀入字符，組合成單詞符號，并將單詞字符，組合成單詞符號，并將單詞符號返回給語法分析程序。符號返回給語法分析程序。2、當語法分析程序識別出、當語法分析程序識別出一個語法成分時，就調用語一個語法成分時，就調用語義分析子程序進行語義分析，義分析子程序

13、進行語義分析，并生成目標程序。并生成目標程序。3、當源程序處理完后，、當源程序處理完后，進行善后處理，優(yōu)化目進行善后處理，優(yōu)化目標程序。標程序。44詞法詞法分析分析 語法語法分析分析 語義語義分析分析 代碼代碼優(yōu)化優(yōu)化目標代碼目標代碼生成生成錯誤處理錯誤處理符號表符號表目標程序目標程序 源程序源程序 45多遍編譯程序的工作過程如下：多遍編譯程序的工作過程如下：1. 調用詞法分析程序將高級語言源程序轉換成用單詞符號表示調用詞法分析程序將高級語言源程序轉換成用單詞符號表示的程序，即將字符串程序轉換成單詞符號串源程序。的程序，即將字符串程序轉換成單詞符號串源程序。2. 調用語法分析程序對符號串源程序

14、進行語法歸類檢查。調用語法分析程序對符號串源程序進行語法歸類檢查。3. 調語義分析程序進行語義檢查，并生成中間的代碼程序。調語義分析程序進行語義檢查，并生成中間的代碼程序。4. 調用代碼優(yōu)化程序對中間代碼程序進行優(yōu)化。調用代碼優(yōu)化程序對中間代碼程序進行優(yōu)化。5. 調用目標生成程序將優(yōu)化后的中間代碼程序轉換成目標代碼調用目標生成程序將優(yōu)化后的中間代碼程序轉換成目標代碼程序。程序。 詞法詞法分析分析 語法語法分析分析 語義語義分析分析 代碼代碼優(yōu)化優(yōu)化目標代碼目標代碼生成生成錯誤處理錯誤處理符號表符號表目標程序目標程序 源程序源程序 46分遍的缺點：分遍的缺點：每遍都要讀符號、送符號，增加了許多重

15、復性工作，每遍都要讀符號、送符號，增加了許多重復性工作，降低編譯效率。目前的編譯程序中，有單遍的，也有二遍的、三降低編譯效率。目前的編譯程序中，有單遍的，也有二遍的、三遍的，還有多到十幾遍的。遍的，還有多到十幾遍的。 編譯程序分為多遍，其優(yōu)點是：編譯程序分為多遍，其優(yōu)點是：1.可以減少內存容量的需求。分遍后，以遍為單位分別調用編譯可以減少內存容量的需求。分遍后，以遍為單位分別調用編譯的各個程序，各遍程序可以相互覆蓋；的各個程序，各遍程序可以相互覆蓋；2.可使各遍的編譯程序相互獨立，結構清晰；可使各遍的編譯程序相互獨立，結構清晰；3.能夠進行充分的優(yōu)化，產生高質量的目標程序；能夠進行充分的優(yōu)化，

16、產生高質量的目標程序； 4.可將編譯程序分為可將編譯程序分為“前端前端”和和“后端后端”，有利于編譯程序的移，有利于編譯程序的移植。植。47 前端：前端：通常將與通常將與源程序源程序有關的編譯部分稱為前端。有關的編譯部分稱為前端。 詞法分析、語法分析、語義分析、中間代碼生成詞法分析、語法分析、語義分析、中間代碼生成 -分析部分分析部分 特點：與特點：與源語言源語言有關有關 后端：后端：與與目標機目標機有關的部分稱為后端。有關的部分稱為后端。 代碼優(yōu)化、代碼生成代碼優(yōu)化、代碼生成 -綜合部分綜合部分 特點：與特點：與目標機目標機有關有關48 同一前端同一前端+ +不同后端不同后端 不同機器構成同

17、一語言的編譯程序不同機器構成同一語言的編譯程序例如例如.NET.NET框架框架 49 不同前端不同前端+ +同一后端同一后端 同一機器生成幾個語言的編譯程序同一機器生成幾個語言的編譯程序例如例如GCCGCC 5051預處理器預處理器編譯程序編譯程序匯編程序匯編程序加載、連接編譯加載、連接編譯框架源程序框架源程序標準源程序標準源程序 目標匯編程序目標匯編程序可重定位的機器代碼可重定位的機器代碼絕對機器代碼絕對機器代碼庫、可重庫、可重定位目標定位目標文件文件程序員編制的程序員編制的程序程序經(jīng)過預處理后經(jīng)過預處理后的程序的程序52編譯之前，預處理器對源程序進行處理，產生標準源程序。不同編譯之前，預處

18、理器對源程序進行處理，產生標準源程序。不同語言的預處理功能有所不同，語言的預處理功能有所不同，C語言編譯系統(tǒng)的預處理器主要完語言編譯系統(tǒng)的預處理器主要完成以下幾個功能：成以下幾個功能：宏處理：宏處理：C語言允許用戶在程序中定義宏，以便提高編程效率，語言允許用戶在程序中定義宏，以便提高編程效率，如如#define PI 3.1415926是一個宏定義，那么在編譯之前，預處理是一個宏定義，那么在編譯之前，預處理器要將源程序中的所有符號器要將源程序中的所有符號PI換成換成3.1415926。文件包含：文件包含：如果如果C源程序中含有源程序中含有#include “stdio.h”，那么預處理器，那么

19、預處理器處理到這條語句時，就用處理到這條語句時，就用stdio.h的實際內容替換該語句。的實際內容替換該語句。條件編譯：條件編譯：并非源程序的每一行都要進行編譯，有時情況不同要并非源程序的每一行都要進行編譯，有時情況不同要編譯不同的語句。編譯不同的語句。C語言預處理器處理條件編譯，將真正要編譯語言預處理器處理條件編譯，將真正要編譯的語句組成標準源程序。的語句組成標準源程序。 53有些編譯程序直接產生可重定位的機器語言目標代碼，而有些編譯程序只有些編譯程序直接產生可重定位的機器語言目標代碼，而有些編譯程序只產生匯編語言目標代碼，這樣就需要匯編程序做進一步翻譯，生成可重定產生匯編語言目標代碼，這樣

20、就需要匯編程序做進一步翻譯，生成可重定位的機器代碼?？芍囟ㄎ坏臋C器代碼可以裝載到內存的任何地方，這種代位的機器代碼?？芍囟ㄎ坏臋C器代碼可以裝載到內存的任何地方，這種代碼采用相對地址，起始地址為碼采用相對地址，起始地址為0，各條指令及所訪問的地址都是相對應于，各條指令及所訪問的地址都是相對應于0的邏輯地址。如果加載到內存單元的邏輯地址。如果加載到內存單元L處，則所有指令地址及訪問的地址都要處，則所有指令地址及訪問的地址都要加上加上L。匯編語言采用助記符表示操作碼，用標識符表示存儲地址，如完成匯編語言采用助記符表示操作碼，用標識符表示存儲地址，如完成a=b+5的的80 x86匯編語言程序如下：匯編

21、語言程序如下： MOV a，R1 ADD #2，R1 MOV R1，b其中其中a，b表示存儲地址，表示存儲地址，R1表示寄存器，表示寄存器，#2表示立即常數(shù)。有些匯編語言表示立即常數(shù)。有些匯編語言還提供宏指令來提高匯編語言編程效率，這種匯編語言稱為宏匯編語言。還提供宏指令來提高匯編語言編程效率，這種匯編語言稱為宏匯編語言。 54任何一本關于編譯結構的書如果不包括編譯過程步驟的示例任何一本關于編譯結構的書如果不包括編譯過程步驟的示例就不能算完整。因此，寫出一個完整的編譯器并對其操作進就不能算完整。因此，寫出一個完整的編譯器并對其操作進行注釋仍是很必要的。但要描述真實的編譯器非常困難，行注釋仍是很

22、必要的。但要描述真實的編譯器非常困難，“真正的真正的”編譯器內容太復雜而且不易在本教材中掌握。編譯器內容太復雜而且不易在本教材中掌握。為了解決上述問題，本教材設計了一種非常小的語言為了解決上述問題，本教材設計了一種非常小的語言TEST，一旦能明白一旦能明白TESTTEST語言的編譯技術，就能夠很容易地理解各種語言的編譯技術，就能夠很容易地理解各種語言的編譯器了。在第語言的編譯器了。在第3 3、4 4、9 9章里，以這種小語言為示例，章里，以這種小語言為示例，講解編譯技術的具體實現(xiàn)，而且在附錄講解編譯技術的具體實現(xiàn)，而且在附錄B B中列出該語言完整中列出該語言完整的編譯程序代碼。的編譯程序代碼。

23、 55例如，例如，TEST語言，計算階乘。語言，計算階乘。 int i; int n; int j; j=1; read n; for (i=1;i=n;i=i+1) j=j*i; write j;TEST語言語言的程序結構很簡單，它在語法上的程序結構很簡單，它在語法上相當于相當于C C的函數(shù)體：是由一對花括號擴起來的函數(shù)體：是由一對花括號擴起來的語句序列。的語句序列。無過程，無函數(shù)，無數(shù)組，只有整型數(shù)值。無過程，無函數(shù)，無數(shù)組，只有整型數(shù)值。一條聲明語句只能聲明一個整型簡單變量。一條聲明語句只能聲明一個整型簡單變量?？刂普Z句三個：控制語句三個： ifif、whilewhile和和forfor語句。語句。只能計算布爾表達式和整型算術表達式。布只能計算布爾表達式和整型算術表達式。布爾表達式由對兩個算術表達式的比較組成，爾表達式由對兩個算術表達式的比較組成，該比較使用該比較使用 、= 、=、=和和!=!=比較算符。比較算符。算術表達式可以包括整型常數(shù)、變量、參數(shù)算術表達式可以包括整型常數(shù)、變量、參數(shù)以及以及4 4個算符個算符+ +、* *、/ /。輸入：輸入：readread語句，輸出：語句，輸出：writewrite語句。語句。注釋用注釋用