第01章_編譯概述

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

2、就可以得到解答。78編譯系統(tǒng)：編譯程序和運(yùn)行程序編譯系統(tǒng)：編譯程序和運(yùn)行程序編譯程序編譯程序目標(biāo)程序目標(biāo)程序源程序源程序91011121314源程序源程序翻譯程序翻譯程序目標(biāo)程序目標(biāo)程序SOURCE PROGRAMTRANSLATER OBJECT PROGRAM1516高級語言高級語言源程序源程序 編譯編譯程序程序 機(jī)器語言機(jī)器語言目標(biāo)程序目標(biāo)程序 目標(biāo)程序目標(biāo)程序 +運(yùn)行子程序運(yùn)行子程序 運(yùn)行運(yùn)行結(jié)果結(jié)果 數(shù)據(jù)數(shù)據(jù) 編譯階段編譯階段 執(zhí)行階段執(zhí)行階段 17高級語言源程序高級語言源程序 編譯程序編譯程序 匯編語言目標(biāo)程序匯編語言目標(biāo)程序 匯編程序匯編程序機(jī)器語言目標(biāo)程序機(jī)器語言目標(biāo)程序 運(yùn)行

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

4、本語法單位是語言的基本語法單位 保留字保留字（如（如:if:if、elseelse、whilewhile） 標(biāo)識符標(biāo)識符（如（如:max:max、minmin、strstr） 常數(shù)常數(shù) （如（如:12:12、6.86.8、a a） 分界符分界符（如（如:+:+、- -、* *、/ /、; ;、（、）、（、） ）23符號符號記號記號單詞單詞100IDa21=200NUM1022+100IDc25*200NUM20a=10+C*20a=10+C*20a=10+C*202425我們我們是是一家人一家人我我是是大學(xué)生大學(xué)生26S.PO.P語義分析及生成中間代碼程序語義分析及生成中間代碼程序代碼生成程序

5、代碼生成程序代碼優(yōu)化程序代碼優(yōu)化程序語法分析程序語法分析程序詞法分析程序詞法分析程序錯(cuò)錯(cuò)誤誤處處理理符符號號表表管管理理27文法文法 :=:= “= =” :=:= “+ +” | | “* *” :=:=“( (” “) )” | | | | | | 28句子句子 謂語謂語 主語主語 賓語賓語 動(dòng)詞動(dòng)詞( (吃吃) ) 名詞名詞( (猴子猴子) ) 名詞名詞( (香蕉香蕉) ) 圖圖1.51.5句子句子“猴子吃香蕉猴子吃香蕉”的語法分析樹的語法分析樹 語法分析與語法分析與語文中分析句子成分語文中分析句子成分相類似，根據(jù)句子相類似，根據(jù)句子由主語、謂語組成，謂語由動(dòng)詞、賓語組成等語言規(guī)則，由主

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

7、式 NUM（20） ID（c） NUM （10） 因子因子 * 因子因子 因子因子項(xiàng)項(xiàng)33例如表達(dá)式例如表達(dá)式 (a+b)*(c+d)翻譯成四元式的中翻譯成四元式的中間代碼如下：間代碼如下：(+ , a , b , t1)(+ , c , d , t2)(* , t1 , t2 , t3)LOAD a 將將a的內(nèi)容加載到操作數(shù)棧的內(nèi)容加載到操作數(shù)棧LOAD b 將將a的內(nèi)容加載到操作數(shù)棧的內(nèi)容加載到操作數(shù)棧ADD 將操作數(shù)棧頂?shù)膬蓚€(gè)單元的內(nèi)容相加將操作數(shù)棧頂?shù)膬蓚€(gè)單元的內(nèi)容相加STO t1 將操作數(shù)棧頂?shù)膬?nèi)容存入單元將操作數(shù)棧頂?shù)膬?nèi)容存入單元t1LOAD c 將將c的內(nèi)容加載到操作數(shù)棧的內(nèi)容加

8、載到操作數(shù)棧LOAD d 將將d的內(nèi)容加載到操作數(shù)棧的內(nèi)容加載到操作數(shù)棧ADD 將操作數(shù)棧頂?shù)膬蓚€(gè)單元的內(nèi)容相加將操作數(shù)棧頂?shù)膬蓚€(gè)單元的內(nèi)容相加STO t2 將操作數(shù)棧頂?shù)膬?nèi)容存入單元將操作數(shù)棧頂?shù)膬?nèi)容存入單元t2LOAD t1 將將t1的內(nèi)容加載到操作數(shù)棧的內(nèi)容加載到操作數(shù)棧LOAD t2 將將t2的內(nèi)容加載到操作數(shù)棧的內(nèi)容加載到操作數(shù)棧MULT 將操作數(shù)棧頂?shù)膬蓚€(gè)單元的內(nèi)容相乘將操作數(shù)棧頂?shù)膬蓚€(gè)單元的內(nèi)容相乘STO t3 將累加器的內(nèi)容存入單元將累加器的內(nèi)容存入單元t3 翻譯成某個(gè)抽象機(jī)的翻譯成某個(gè)抽象機(jī)的匯編指令代碼：匯編指令代碼：中間代碼生成34S.PO.P語義分析及生成中間代碼程序語

9、義分析及生成中間代碼程序代碼生成程序代碼生成程序代碼優(yōu)化程序代碼優(yōu)化程序語法分析程序語法分析程序詞法分析程序詞法分析程序錯(cuò)錯(cuò)誤誤處處理理符符號號表表管管理理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) 代碼優(yōu)化不是編譯程序的必要組成部分，不同的代碼優(yōu)化不是編譯程序的必要組成部分，不同的編譯程序所進(jìn)行的代碼優(yōu)化程度差別很大，能夠編譯程序所

10、進(jìn)行的代碼優(yōu)化程度差別很大，能夠完成代碼優(yōu)化的編譯程序稱為完成代碼優(yōu)化的編譯程序稱為“優(yōu)化編譯程序優(yōu)化編譯程序”。 36S.PO.P語義分析及生成中間代碼程序語義分析及生成中間代碼程序代碼生成程序代碼生成程序代碼優(yōu)化程序代碼優(yōu)化程序語法分析程序語法分析程序詞法分析程序詞法分析程序錯(cuò)錯(cuò)誤誤處處理理符符號號表表管管理理3738每個(gè)階段中都要有：每個(gè)階段中都要有：符號表管理符號表管理和和錯(cuò)誤處理錯(cuò)誤處理標(biāo)識符名標(biāo)識符名標(biāo)識符類型標(biāo)識符類型 類型類型 地址地址 aaa1（表示變量）（表示變量） 1（表示整型）（表示整型） 0001 3940S.PO.P語義分析及生成中間代碼程序語義分析及生成中間代碼程

11、序代碼生成程序代碼生成程序代碼優(yōu)化程序代碼優(yōu)化程序語法分析程序語法分析程序詞法分析程序詞法分析程序錯(cuò)錯(cuò)誤誤處處理理符符號號表表管管理理41 第一遍第一遍 第二遍第二遍 S.P中間形式中間形式1S.P中間形式中間形式2C2C1S.PO.P 上一遍的結(jié)果是下一遍的輸入，最后一遍生成目標(biāo)程序。上一遍的結(jié)果是下一遍的輸入，最后一遍生成目標(biāo)程序。42語法分析函數(shù)語法分析函數(shù) 詞法分析子程序；詞法分析子程序； 語義分析子程序；語義分析子程序；43詞法分析詞法分析 源程序源程序 取單詞取單詞 目標(biāo)程序目標(biāo)程序 開始開始 語法分析語法分析 語義分析及代碼生成語義分析及代碼生成 送單詞送單詞 典型的單遍編譯程序

12、結(jié)構(gòu)如圖所示典型的單遍編譯程序結(jié)構(gòu)如圖所示 1、當(dāng)語法分析需要讀進(jìn)一個(gè)新單詞、當(dāng)語法分析需要讀進(jìn)一個(gè)新單詞時(shí)，就調(diào)用詞法分析子程序。詞法時(shí)，就調(diào)用詞法分析子程序。詞法分析子程序則從源程序中依次讀入分析子程序則從源程序中依次讀入字符，組合成單詞符號，并將單詞字符，組合成單詞符號，并將單詞符號返回給語法分析程序。符號返回給語法分析程序。2、當(dāng)語法分析程序識別出、當(dāng)語法分析程序識別出一個(gè)語法成分時(shí)，就調(diào)用語一個(gè)語法成分時(shí)，就調(diào)用語義分析子程序進(jìn)行語義分析，義分析子程序進(jìn)行語義分析，并生成目標(biāo)程序。并生成目標(biāo)程序。3、當(dāng)源程序處理完后，、當(dāng)源程序處理完后，進(jìn)行善后處理，優(yōu)化目進(jìn)行善后處理，優(yōu)化目標(biāo)程序

13、。標(biāo)程序。44詞法詞法分析分析 語法語法分析分析 語義語義分析分析 代碼代碼優(yōu)化優(yōu)化目標(biāo)代碼目標(biāo)代碼生成生成錯(cuò)誤處理錯(cuò)誤處理符號表符號表目標(biāo)程序目標(biāo)程序 源程序源程序 45多遍編譯程序的工作過程如下：多遍編譯程序的工作過程如下：調(diào)用詞法分析程序?qū)⒏呒壵Z言源程序轉(zhuǎn)換成用單詞符號表示調(diào)用詞法分析程序?qū)⒏呒壵Z言源程序轉(zhuǎn)換成用單詞符號表示的程序，即將字符串程序轉(zhuǎn)換成單詞符號串源程序。的程序，即將字符串程序轉(zhuǎn)換成單詞符號串源程序。調(diào)用語法分析程序?qū)Ψ柎闯绦蜻M(jìn)行語法歸類檢查。調(diào)用語法分析程序?qū)Ψ柎闯绦蜻M(jìn)行語法歸類檢查。調(diào)語義分析程序進(jìn)行語義檢查，并生成中間的代碼程序。調(diào)語義分析程序進(jìn)行語義檢查，并

14、生成中間的代碼程序。調(diào)用代碼優(yōu)化程序?qū)χ虚g代碼程序進(jìn)行優(yōu)化。調(diào)用代碼優(yōu)化程序?qū)χ虚g代碼程序進(jìn)行優(yōu)化。1. 調(diào)用目標(biāo)生成程序?qū)?yōu)化后的中間代碼程序轉(zhuǎn)換成目標(biāo)代碼調(diào)用目標(biāo)生成程序?qū)?yōu)化后的中間代碼程序轉(zhuǎn)換成目標(biāo)代碼程序。程序。 詞法詞法分析分析 語法語法分析分析 語義語義分析分析 代碼代碼優(yōu)化優(yōu)化目標(biāo)代碼目標(biāo)代碼生成生成錯(cuò)誤處理錯(cuò)誤處理符號表符號表目標(biāo)程序目標(biāo)程序 源程序源程序 46分遍的缺點(diǎn)：分遍的缺點(diǎn)：每遍都要讀符號、送符號，增加了許多重復(fù)性工作，每遍都要讀符號、送符號，增加了許多重復(fù)性工作，降低編譯效率。目前的編譯程序中，有單遍的，也有二遍的、三降低編譯效率。目前的編譯程序中，有單遍的，也有

15、二遍的、三遍的，還有多到十幾遍的。遍的，還有多到十幾遍的。 編譯程序分為多遍，其優(yōu)點(diǎn)是：編譯程序分為多遍，其優(yōu)點(diǎn)是：可以減少內(nèi)存容量的需求。分遍后，以遍為單位分別調(diào)用編譯可以減少內(nèi)存容量的需求。分遍后，以遍為單位分別調(diào)用編譯的各個(gè)程序，各遍程序可以相互覆蓋；的各個(gè)程序，各遍程序可以相互覆蓋；可使各遍的編譯程序相互獨(dú)立，結(jié)構(gòu)清晰；可使各遍的編譯程序相互獨(dú)立，結(jié)構(gòu)清晰；能夠進(jìn)行充分的優(yōu)化，產(chǎn)生高質(zhì)量的目標(biāo)程序；能夠進(jìn)行充分的優(yōu)化，產(chǎn)生高質(zhì)量的目標(biāo)程序； 1.可將編譯程序分為可將編譯程序分為“前端前端”和和“后端后端”，有利于編譯程序的移，有利于編譯程序的移植。植。47 前端：前端：通常將與通常將與

16、源程序源程序有關(guān)的編譯部分稱為前端。有關(guān)的編譯部分稱為前端。 詞法分析、語法分析、語義分析、中間代碼生成詞法分析、語法分析、語義分析、中間代碼生成 -分析部分分析部分 特點(diǎn)：與特點(diǎn)：與源語言源語言有關(guān)有關(guān) 后端：后端：與與目標(biāo)機(jī)目標(biāo)機(jī)有關(guān)的部分稱為后端。有關(guān)的部分稱為后端。 代碼優(yōu)化、代碼生成代碼優(yōu)化、代碼生成 -綜合部分綜合部分 特點(diǎn)：與特點(diǎn)：與目標(biāo)機(jī)目標(biāo)機(jī)有關(guān)有關(guān)48 同一前端同一前端+ +不同后端不同后端 不同機(jī)器構(gòu)成同一語言的編譯程序不同機(jī)器構(gòu)成同一語言的編譯程序例如例如.NET.NET框架框架 49 不同前端不同前端+ +同一后端同一后端 同一機(jī)器生成幾個(gè)語言的編譯程序同一機(jī)器生成幾

17、個(gè)語言的編譯程序例如例如GCCGCC 5051預(yù)處理器預(yù)處理器編譯程序編譯程序匯編程序匯編程序加載、連接編譯加載、連接編譯框架源程序框架源程序標(biāo)準(zhǔn)源程序標(biāo)準(zhǔn)源程序 目標(biāo)匯編程序目標(biāo)匯編程序可重定位的機(jī)器代碼可重定位的機(jī)器代碼絕對機(jī)器代碼絕對機(jī)器代碼庫、可重庫、可重定位目標(biāo)定位目標(biāo)文件文件程序員編制的程序員編制的程序程序經(jīng)過預(yù)處理后經(jīng)過預(yù)處理后的程序的程序52編譯之前，預(yù)處理器對源程序進(jìn)行處理，產(chǎn)生標(biāo)準(zhǔn)源程序。不同編譯之前，預(yù)處理器對源程序進(jìn)行處理，產(chǎn)生標(biāo)準(zhǔn)源程序。不同語言的預(yù)處理功能有所不同，語言的預(yù)處理功能有所不同，C語言編譯系統(tǒng)的預(yù)處理器主要完語言編譯系統(tǒng)的預(yù)處理器主要完成以下幾個(gè)功能：成

18、以下幾個(gè)功能：宏處理：宏處理：C語言允許用戶在程序中定義宏，以便提高編程效率，語言允許用戶在程序中定義宏，以便提高編程效率，如如#define PI 3.1415926是一個(gè)宏定義，那么在編譯之前，預(yù)處理是一個(gè)宏定義，那么在編譯之前，預(yù)處理器要將源程序中的所有符號器要將源程序中的所有符號PI換成換成3.1415926。文件包含：文件包含：如果如果C源程序中含有源程序中含有#include “stdio.h”，那么預(yù)處理器，那么預(yù)處理器處理到這條語句時(shí)，就用處理到這條語句時(shí)，就用stdio.h的實(shí)際內(nèi)容替換該語句。的實(shí)際內(nèi)容替換該語句。條件編譯：條件編譯：并非源程序的每一行都要進(jìn)行編譯，有時(shí)情況

19、不同要并非源程序的每一行都要進(jìn)行編譯，有時(shí)情況不同要編譯不同的語句。編譯不同的語句。C語言預(yù)處理器處理?xiàng)l件編譯，將真正要編譯語言預(yù)處理器處理?xiàng)l件編譯，將真正要編譯的語句組成標(biāo)準(zhǔn)源程序。的語句組成標(biāo)準(zhǔn)源程序。 53有些編譯程序直接產(chǎn)生可重定位的機(jī)器語言目標(biāo)代碼，而有些編譯程序只有些編譯程序直接產(chǎn)生可重定位的機(jī)器語言目標(biāo)代碼，而有些編譯程序只產(chǎn)生匯編語言目標(biāo)代碼，這樣就需要匯編程序做進(jìn)一步翻譯，生成可重定產(chǎn)生匯編語言目標(biāo)代碼，這樣就需要匯編程序做進(jìn)一步翻譯，生成可重定位的機(jī)器代碼?？芍囟ㄎ坏臋C(jī)器代碼可以裝載到內(nèi)存的任何地方，這種代位的機(jī)器代碼?？芍囟ㄎ坏臋C(jī)器代碼可以裝載到內(nèi)存的任何地方，這種代碼采

20、用相對地址，起始地址為碼采用相對地址，起始地址為0，各條指令及所訪問的地址都是相對應(yīng)于，各條指令及所訪問的地址都是相對應(yīng)于0的邏輯地址。如果加載到內(nèi)存單元的邏輯地址。如果加載到內(nèi)存單元L處，則所有指令地址及訪問的地址都要處，則所有指令地址及訪問的地址都要加上加上L。匯編語言采用助記符表示操作碼，用標(biāo)識符表示存儲(chǔ)地址，如完成匯編語言采用助記符表示操作碼，用標(biāo)識符表示存儲(chǔ)地址，如完成a=b+5的的80 x86匯編語言程序如下：匯編語言程序如下： MOV a，R1 ADD #2，R1 MOV R1，b其中其中a，b表示存儲(chǔ)地址，表示存儲(chǔ)地址，R1表示寄存器，表示寄存器，#2表示立即常數(shù)。有些匯編語言

21、表示立即常數(shù)。有些匯編語言還提供宏指令來提高匯編語言編程效率，這種匯編語言稱為宏匯編語言。還提供宏指令來提高匯編語言編程效率，這種匯編語言稱為宏匯編語言。 54任何一本關(guān)于編譯結(jié)構(gòu)的書如果不包括編譯過程步驟的示例任何一本關(guān)于編譯結(jié)構(gòu)的書如果不包括編譯過程步驟的示例就不能算完整。因此，寫出一個(gè)完整的編譯器并對其操作進(jìn)就不能算完整。因此，寫出一個(gè)完整的編譯器并對其操作進(jìn)行注釋仍是很必要的。但要描述真實(shí)的編譯器非常困難，行注釋仍是很必要的。但要描述真實(shí)的編譯器非常困難，“真正的真正的”編譯器內(nèi)容太復(fù)雜而且不易在本教材中掌握。編譯器內(nèi)容太復(fù)雜而且不易在本教材中掌握。為了解決上述問題，本教材設(shè)計(jì)了一種非

22、常小的語言為了解決上述問題，本教材設(shè)計(jì)了一種非常小的語言TEST，一旦能明白一旦能明白TESTTEST語言的編譯技術(shù)，就能夠很容易地理解各種語言的編譯技術(shù)，就能夠很容易地理解各種語言的編譯器了。在第語言的編譯器了。在第3 3、4 4、9 9章里，以這種小語言為示例，章里，以這種小語言為示例，講解編譯技術(shù)的具體實(shí)現(xiàn)，而且在附錄講解編譯技術(shù)的具體實(shí)現(xiàn)，而且在附錄B B中列出該語言完整中列出該語言完整的編譯程序代碼。的編譯程序代碼。 55例如，例如，TEST語言，計(jì)算階乘。語言，計(jì)算階乘。 int i; int n; int j; j=1; read n; for (i=1;i=n;i=i+1) j

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