第1章編譯原理概述

1、編譯原理編譯原理第2頁教材及主要參考資料教材及主要參考資料o 教材教材：編譯原理及實踐教程，黃賢英，清華大學(xué)出版社o 主要參考資料：主要參考資料：o 編譯原理，陳火旺，國防工業(yè)出版社o 編譯原理(原書第2版)(龍書) ，ALFRED V.AHO etc著，趙建華 鄭滔等譯 ，機械工業(yè)出版社 ,2008.12o 程序設(shè)計語言編譯方法，肖軍模，大連理工大學(xué)出版社o 編譯原理，張素琴，呂映芝，清華大學(xué)出版社o更多教材及參考資料參見編譯原理精品課程網(wǎng)站。C語言程序void main( ) int x,y,z; x=3; y=2; z=x+y;內(nèi)存地址內(nèi)存地址 內(nèi)存內(nèi)容內(nèi)存內(nèi)容單元名字單元名字200H3

2、x：局部變量202H2y：局部變量204H5z：局部變量300H3A03302H3AE1304H3A02306H3AE2308HDA6C.3A71匯編語言程序mov ax,3mov x,axmov bx,2mov y,bxadd ax,bxmov z,ax.序言在內(nèi)存中：在內(nèi)存中：數(shù)據(jù)區(qū)代碼區(qū) ？編譯原理概述編譯原理概述第一章第一章 第5頁本章要求本章要求o 主要內(nèi)容主要內(nèi)容：各種翻譯程序的概念，編譯各種翻譯程序的概念，編譯過程和階段劃分，編譯程序的組成和結(jié)過程和階段劃分，編譯程序的組成和結(jié)構(gòu)，編譯程序的構(gòu)造方法構(gòu)，編譯程序的構(gòu)造方法o 重點掌握：重點掌握：編譯程序工作的基本過程及編譯程序工作

3、的基本過程及其各階段的基本任務(wù)，編譯程序總框。其各階段的基本任務(wù)，編譯程序總框。第6頁1.1 程序設(shè)計語言與翻譯程序程序設(shè)計語言與翻譯程序o 機器語言機器語言 (machine language) C7 06 0000 0002o 匯編語言匯編語言 (assembler language) MOV X , 2o 高級語言高級語言 (high-level language) X = 2為什么要使用編譯程序？為什么要使用編譯程序？2022年3月17日星期四第7頁o 機器語言機器語言 (machine language) C7 06 0000 0002o 匯編語言匯編語言 (assembler la

4、nguage) MOV X , 2o 高級語言高級語言 (high-level language) X = 2為什么要使用編譯程序？為什么要使用編譯程序？2022年3月17日星期四第8頁計算機中的語言層次和翻譯程序計算機中的語言層次和翻譯程序2022年3月17日星期四第9頁什么叫翻譯程序什么叫翻譯程序o 翻譯程序翻譯程序：能夠?qū)⒛撤N語言寫的程序轉(zhuǎn)換成另一種語言的程序，而且后者與前者在邏輯上是等價的。o 編譯程序編譯程序：將高級程序設(shè)計語言程序翻譯成邏輯上等價的低級語言(匯編語言,機器語言)程序的翻譯程序。o 解釋程序解釋程序：將高級程序設(shè)計語言寫的源程序作為輸入，邊解釋邊執(zhí)行源程序本身，而不產(chǎn)

5、生目標(biāo)程序的翻譯程序。2022年3月17日星期四第10頁高級語言語言處理程序操作系統(tǒng)匯編語言翻譯程序所處的層次翻譯程序所處的層次計算機硬件C編譯程序C語言Basic解釋程序Basic語言Fortran編譯程序Fortran語言.2022年3月17日星期四第11頁編譯程序編譯程序編譯程序編譯程序源程序源程序目標(biāo)程序目標(biāo)程序計算機運行計算機運行輸入數(shù)據(jù)輸入數(shù)據(jù)結(jié)果結(jié)果解釋程序解釋程序解釋程序解釋程序源程序源程序輸入數(shù)據(jù)輸入數(shù)據(jù)結(jié)果結(jié)果2022年3月17日星期四第12頁對編譯程序的一些說明對編譯程序的一些說明o 編譯程序?qū)嵸|(zhì)上是一個翻譯程序翻譯程序，要注意等價等價變換o 本課程的任務(wù)任務(wù)就是講解在這

6、個轉(zhuǎn)換過程中所涉及到的一些理論和方法，最后，使用這些理論和方法，自己編寫一個小的編譯器o 轉(zhuǎn)換是一個總體的功能，要抓住總體結(jié)構(gòu)，逐層細(xì)分，寫編譯器時要體現(xiàn)軟件工程中軟件設(shè)計的原則軟件設(shè)計的原則，自頂向下，逐層分解。o 編譯器要完成的轉(zhuǎn)換任務(wù)相當(dāng)復(fù)雜，實現(xiàn)編譯器時必須分步驟分階段分步驟分階段實現(xiàn)。分階段實現(xiàn)的好處是能夠簡化程序的設(shè)計簡化程序的設(shè)計，當(dāng)然也可以不分階段實現(xiàn)。2022年3月17日星期四第13頁編譯程序的分類編譯程序的分類o診斷編譯程序診斷編譯程序o優(yōu)化編譯程序優(yōu)化編譯程序o可變目標(biāo)編譯程序可變目標(biāo)編譯程序o交叉編譯程序交叉編譯程序2022年3月17日星期四第14頁編譯器的伙伴編譯器的

7、伙伴o 編輯器編輯器(editor)(editor)o 預(yù)處理器預(yù)處理器(Preprocessor)(Preprocessor)n將源程序匯集到一起，宏展開等將源程序匯集到一起，宏展開等o 匯編程序匯編程序(assembler)(assembler)o 連接程序連接程序(linker)(linker)n連接系統(tǒng)函數(shù)與系統(tǒng)資源連接系統(tǒng)函數(shù)與系統(tǒng)資源o 裝入程序裝入程序(loader)(loader)n重定位重定位(relocation)(relocation)o Debugger,Profiler,Project Debugger,Profiler,Project ManagerManager2

8、022年3月17日星期四第15頁編譯原理是討論編譯程序設(shè)計的基本理論、基本概念、基本方法 什么是編譯原理什么是編譯原理2022年3月17日星期四第16頁1.2 編譯過程概述編譯過程概述o 1、邏輯上分五個階段：詞法分析、語法分析、語義分析與中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成 每個階段把源程序從一種表示變換成另一種表示源 程 序編 譯 器目 標(biāo) 程 序詞法分析語法分析語義分析與中間代碼生成代碼優(yōu)化目標(biāo)代碼生成2022年3月17日星期四第17頁o 按照詞法分析、語法分析、語義分析等這種方式來劃分階段的原因是：每個階段的復(fù)雜程度不同，所依據(jù)的理論基礎(chǔ)不同理論基礎(chǔ)不同，實現(xiàn)時采用的方法也不同方法也不

9、同。主要是方便理解和實現(xiàn)。o 劃分階段的依據(jù)是什么？每個階段所實現(xiàn)的功能相功能相對獨立對獨立。用一個例子說明各階段的功能2022年3月17日星期四第18頁/*一個PASCAL語言的源程序*/program test; /*this is an example,computing an area*/ var area, length, width: integer; begin length:=5;width:=5; area := 5length *widthlength *widthend. 2022年3月17日星期四第19頁第一階段：詞法分析第一階段：詞法分析任務(wù)任務(wù): 從左到右掃描源程序

10、，識別出每個單詞從左到右掃描源程序，識別出每個單詞o 附加任務(wù)：a、濾掉空格 b、去掉注釋o 單詞符號是語言的基本組成成分o 詞法分析的工作主要依據(jù)語言中單詞的構(gòu)成規(guī)則o 單詞的種類： （1） 標(biāo)識符 （2） 關(guān)鍵字（char、int、if、else、while、for等） （3） 運算符（即運算符號 +、*、/、&等） （4） 界符（常見的有 ； ， ： （ ）等） （5） 常數(shù) 2022年3月17日星期四第20頁begin area:=5length*width length *widthend;單詞類型內(nèi)部形式begin關(guān)鍵字$beginarea標(biāo)識符id1:=界符:=5常數(shù)in

11、t1+算符+length標(biāo)識符id1*算符*width標(biāo)識符id2+算符+length標(biāo)識符id2*算符*width標(biāo)識符id3end關(guān)鍵字$end;界符;例:2022年3月17日星期四第21頁第二階段：語法分析第二階段：語法分析任務(wù)任務(wù): 在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，將單詞符號串分解成各類語法短語(例：程序、語句、表達(dá)式)。o確定整個輸入串是否構(gòu)成語法上正確的程序。o根據(jù)規(guī)則判定：根據(jù)規(guī)則判定：賦值語句：賦值語句：標(biāo)識符標(biāo)識符:表達(dá)式表達(dá)式 表達(dá)式：表達(dá)式：標(biāo)識符、常數(shù)是表達(dá)式標(biāo)識符、常數(shù)是表達(dá)式 表達(dá)式的運算也是表達(dá)式表達(dá)式的運算也是表達(dá)式例：識別符號串id1:=int1 +

12、id2 * id3 + id2 * id3是一個賦值語句（ area:=5length*widthlength *width）而int1 + id2 * id3 + id2 * id3是一個表達(dá)式 （ 5length*widthlength *width ）2022年3月17日星期四第22頁語法分析所依據(jù)的是語言的語法規(guī)則id1:=int1 + id2 * id3 + id2 * id32022年3月17日星期四第23頁第三階段：語義分析和中間代碼生成第三階段：語義分析和中間代碼生成任務(wù)任務(wù)：對語法分析所識別出的各類語法短語分析其含義，進行初步的翻譯(翻譯成中間代碼)。o靜態(tài)語義審查n 變量定

13、義n 類型匹配n 類型轉(zhuǎn)換 例：C:=A*B (檢查C與、類型)o中間代碼的翻譯 中間代碼有多種形式，如： 四元式: (運算符，運算對象1，運算對象2，結(jié)果) 2022年3月17日星期四第24頁例：對賦值語句： id1:=int1 + id2 * id3 + id2 * id3 1. 檢查area、length、width是否定義、類型 2. 生成中間代碼(運算符，運算對象運算符，運算對象1，運算對象，運算對象2，結(jié)果，結(jié)果) (*, id2, id3, T1) (+, int1, T1, T2) (*, id2, id3, T3) (+, T2, T3, T4) (:=, T4, _, id

14、1)id1:=int1 + id2 * id3 + id2 * id32022年3月17日星期四第25頁第四階段：第四階段： 代碼優(yōu)化代碼優(yōu)化任務(wù)任務(wù)：對已產(chǎn)生的中間代碼進行加工變換，使生成的目標(biāo)代碼更為高效(時間和空間)。o優(yōu)化方法包括：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無用代碼等。o代碼的優(yōu)化依據(jù)的是程序的等價變換規(guī)則。序號 四元式1(*, id2, id3, T1)2(+, int1, T1, T2)3(*, id2, id3, T3)4(+, T2, T3, T4)5(:=, T4, _, id1)序號 四元式1(*, id2, id3, T1)2 (+, int1, T1, T2)3

15、(+, T2, T1, id1)2022年3月17日星期四第26頁第五階段：目標(biāo)代碼的生成第五階段：目標(biāo)代碼的生成任務(wù)任務(wù)：把中間代碼(或經(jīng)優(yōu)化的中間代碼)變換成特定機器上的低級語言代碼。o依賴于機器的硬件系統(tǒng)結(jié)構(gòu)和機器指令的含義o目標(biāo)代碼可以是：絕對指令代碼、可重定位的指令代碼、匯編指令代碼序號 四元式1(*, id2, id3, T1)2 (+, int1, T1, T2)3(+, T2, T1, id1)（1）mov AX, id2（2）mul AX, id3（3）mov BX, AX（4）add AX, int1（5）add AX, BX（6）mov id1, AX2022年3月17日

16、星期四第27頁1.2編譯程序編譯程序的結(jié)構(gòu)的結(jié)構(gòu) 由左圖可以看出，詞法分析是實現(xiàn)編譯器的基礎(chǔ)，語法分析是實現(xiàn)編譯器的關(guān)鍵。 因此按照這個順序來實現(xiàn)編譯器 每一步的實現(xiàn)都依賴于一定的理論基礎(chǔ)。 數(shù)學(xué)，尤其是離散數(shù)學(xué)是程序設(shè)計方法學(xué)的理論基礎(chǔ)2022年3月17日星期四第28頁編譯階段的組合編譯階段的組合o幾個概念n 遍：對源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。n 編譯前端：主要指與源語言有關(guān)，與目標(biāo)語言無關(guān)的部分，通常包括詞法分析、語法分析、語義分析和中間代碼生成，與機器無關(guān)部分的代碼優(yōu)化n 編譯后端：指與目標(biāo)機器有關(guān)的部分。如與機器有關(guān)的優(yōu)化、

17、目標(biāo)代碼生成2022年3月17日星期四第29頁編譯階段的組合編譯階段的組合2022年3月17日星期四第30頁為什么生成中間代碼為什么生成中間代碼2022年3月17日星期四第31頁編譯程序中的主要數(shù)據(jù)結(jié)構(gòu)編譯程序中的主要數(shù)據(jù)結(jié)構(gòu) (續(xù)續(xù))Token表符號表常數(shù)表錯誤信息語法樹中間代碼表臨時文件目標(biāo)代碼表2022年3月17日星期四第32頁(1) Token表表 當(dāng)掃描程序?qū)⒆址占揭粋€記號中時，它通常是以符號表示這個記號；這也就是說，作為一個枚舉數(shù)據(jù)類型的值來表示源程序的記號集。(2) 語法樹（語法樹（syntax tree） 如果分析程序確實生成了語法樹，它的構(gòu)造通常為基于指針的標(biāo)準(zhǔn)結(jié)構(gòu)，在進

18、行分析時動態(tài)分配該結(jié)構(gòu)，則整棵樹可作為一個指向根節(jié)點的單個變量保存。結(jié)構(gòu)中的每一個節(jié)點都是一個記錄，它的域表示由分析程序和之后的語義分析程序收集的信息。編譯程序中的主要數(shù)據(jù)結(jié)構(gòu)介紹編譯程序中的主要數(shù)據(jù)結(jié)構(gòu)介紹: :2022年3月17日星期四第33頁(3) 符號表（符號表（symbol table） 這個數(shù)據(jù)結(jié)構(gòu)中的信息與標(biāo)識符有關(guān)：函數(shù)、變量、常量以及數(shù)據(jù)類型。符號表幾乎與編譯器的所有階段交互：掃描程序、分析程序或?qū)?biāo)識符輸入到表格中的語義分析程序；語義分析程序?qū)⒃黾訑?shù)據(jù)類型和其他信息；優(yōu)化階段和代碼生成階段也將利用由符號表提供的信息選出恰當(dāng)?shù)拇a。因為對符號表的訪問如此頻繁，所以插入、刪除和

19、訪問操作都必須比常規(guī)操作更有效。盡管可以使用各種樹的結(jié)構(gòu)，但雜湊表卻是達(dá)到這一要求的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)。有時在一個列表或棧中可使用若干個表格。2022年3月17日星期四第34頁(4) 常數(shù)表（常數(shù)表（literal table） 常數(shù)表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常數(shù)表中也十分重要。但是，在其中卻無需刪除，這是因為它的數(shù)據(jù)全程應(yīng)用于程序而且常量或字符串在該表中只出現(xiàn)一次。 (5) 中間代碼（中間代碼（intermediate code） 根據(jù)中間代碼的類型（例如三元式代碼）和優(yōu)化的類型，該代碼可以是文本串的數(shù)組、臨時文本文件或是結(jié)構(gòu)的連接列表。對于進行復(fù)雜優(yōu)化的編譯器

20、，應(yīng)特別注意選擇允許簡單重組的表示。2022年3月17日星期四第35頁(6) 目標(biāo)目標(biāo)代碼（代碼（intermediate code） 存放最終生成的目標(biāo)代碼，該代碼最終是文本形式的文件。(7) 臨時文件（臨時文件（t e m p o r a ry file） 計算機過去一直未能在編譯器時將整個程序保留在存儲器中。這一問題已經(jīng)通過使用臨時文件來保存翻譯時中間步驟的結(jié)果或通過“匆忙地”編譯（也就是只保留源程序早期部分的足夠信息用以處理翻譯）解決了。2022年3月17日星期四第36頁1.3 編譯程序的設(shè)計編譯程序的設(shè)計o 構(gòu)造編譯程序要掌握以下幾方面的內(nèi)容：n 源語言：理解其結(jié)構(gòu)和含義n 目標(biāo)語言

21、：必須清楚硬件的系統(tǒng)結(jié)構(gòu)和指令的格式等n 編譯方法2022年3月17日星期四第37頁1.3 編譯程序的構(gòu)造編譯程序的構(gòu)造o 一般實現(xiàn)編譯程序的方法有：n1.直接用機器語言編寫編譯程序n2.用匯編語言編寫編譯程序o 注：編譯程序核心部分常用匯編語言編寫n3.用高級語言編寫編譯程序o 注：這是普遍采用的方法n4.自編譯n5.用編譯工具自動生成:LEX(詞法分析)與YACC(用于自動產(chǎn)生LALR分析表)n6.移植（同種語言的編譯程序在不同類型的機器之間移植）2022年3月17日星期四第38頁本書構(gòu)成及編譯程序框架本書構(gòu)成及編譯程序框架2022年3月17日星期四第39頁1.4 編譯技術(shù)的發(fā)展編譯技術(shù)的

22、發(fā)展o1954年至1957年間，F(xiàn)ORTRAN語言及其編譯器的開發(fā)?；?8個人年。o幾乎與此同時，Noam Chomsky開始研究語言文法(grammar，結(jié)構(gòu)規(guī)則)的難易程度以及識別它們所需的算法來為語言分類。o在6 0年代和7 0年代進行的分析問題(parsing problem，用于限定上下文無關(guān)語言的識別的有效算法)的研究。o有窮自動機(finite automata)和正規(guī)式(regular expression) 的研究與喬姆斯基的研究幾乎同時開始，引出了表示程序設(shè)計語言的單詞的符號方式。o接著又深化了生成有效的目標(biāo)代碼的方法，這就是最初的編譯器，實際上應(yīng)稱作代碼改進技術(shù)(code improvement techniq