《編譯原理實踐及應用》第1章編譯原理概述

1、編譯原理實踐及應用編譯原理實踐及應用編譯原理實踐及應用 -清華大學出版社編譯原理實踐及應用2022年5月6日星期五第2頁教材及主要參考資料教材及主要參考資料 教材教材：編譯原理實踐及應用：編譯原理實踐及應用，黃賢英，清華大學出版黃賢英，清華大學出版社社 主要參考資料：主要參考資料： 編譯原理，編譯原理，陳火旺，國防工業(yè)出版社陳火旺，國防工業(yè)出版社 編譯原理編譯原理(原書第原書第2版版)(龍書龍書) ，ALFRED V.AHO etc著，著，趙建華趙建華 鄭滔等譯鄭滔等譯 ，機械工業(yè)出版社，機械工業(yè)出版社 ,2008.12 程序設計語言編譯方法程序設計語言編譯方法，肖軍模，大連理工大學出版社肖軍

2、模，大連理工大學出版社 編譯原理，編譯原理，張素琴，張素琴，呂映芝呂映芝，清華大學出版社清華大學出版社 更多教材及參考資料參見更多教材及參考資料參見編譯原理精品課程網站編譯原理精品課程網站。C語言程序語言程序void main( ) int x,y,z; x=3; y=2; z=x+y;內存地址內存地址內存內容內存內容單元名字單元名字200H3x：局部變量202H2y：局部變量204H5z：局部變量300H3A03302H3AE1304H3A02306H3AE2308HDA6C.3A71匯編語言程序mov ax,3mov x,axmov bx,2mov y,bxadd ax,bxmov z,a

3、x.序言在內存中：在內存中：數據區(qū)代碼區(qū) ？編譯原理實踐及應用編譯原理概述第1章 編譯原理實踐及應用第5頁本章要求 主要內容主要內容：各種翻譯程序的概念，編譯過：各種翻譯程序的概念，編譯過程和階段劃分，編譯程序的組成和結構，程和階段劃分，編譯程序的組成和結構，編譯程序的構造方法編譯程序的構造方法 重點掌握：重點掌握：編譯程序工作的基本過程及其編譯程序工作的基本過程及其各階段的基本任務，編譯程序總框。各階段的基本任務，編譯程序總框。編譯原理實踐及應用第6頁1.1 程序設計語言與編譯程序 機器語言機器語言 (machine language) C7 06 0000 0002 匯編語言匯編語言 (a

4、ssembler language) MOV X , 2 高級語言高級語言 (high-level language) X = 2為什么要使用編譯程序？為什么要使用編譯程序？編譯原理實踐及應用第7頁 機器語言機器語言 (machine language) C7 06 0000 0002 匯編語言匯編語言 (assembler language) MOV X , 2 高級語言高級語言 (high-level language) X = 2為什么要使用編譯程序？為什么要使用編譯程序？編譯原理實踐及應用2022年5月6日星期五第8頁計算機中的語言層次和翻譯程序計算機中的語言層次和翻譯程序編譯原理實踐

5、及應用第9頁什么叫翻譯程序 翻譯程序翻譯程序：能夠將某種語言寫的程序轉換成能夠將某種語言寫的程序轉換成另一種語言的程序，而且后者與前者在另一種語言的程序，而且后者與前者在邏輯邏輯上上是是等價等價的。的。 編譯程序編譯程序：將高級程序設計語言程序翻譯成將高級程序設計語言程序翻譯成邏輯上等價的低級語言邏輯上等價的低級語言(匯編語言匯編語言,機器語言機器語言)程序的翻譯程序。程序的翻譯程序。 解釋程序：解釋程序：將高級程序設計語言寫的源程序將高級程序設計語言寫的源程序作為輸入，邊解釋邊執(zhí)行源程序本身，而不作為輸入，邊解釋邊執(zhí)行源程序本身，而不產生目標程序的翻譯程序。產生目標程序的翻譯程序。編譯原理實

6、踐及應用第第10頁頁高高級級語語言言語言處理語言處理程序程序操作系統(tǒng)操作系統(tǒng)匯編語言匯編語言翻譯程序所處的層次翻譯程序所處的層次計算機硬件計算機硬件C編譯編譯程序程序C語語言言Basic解釋程序解釋程序Basic語言語言Fortran編譯程序編譯程序Fortran語語言言.編譯原理實踐及應用2022年5月6日星期五第11頁編譯程序編譯程序編譯程序源程序源程序目標程序目標程序計算機運行計算機運行輸入數據輸入數據結果結果解釋程序解釋程序解釋程序源程序源程序輸入數據輸入數據結果結果編譯原理實踐及應用第12頁對編譯程序的一些說明對編譯程序的一些說明 編譯程序實質上是一個編譯程序實質上是一個翻譯程序翻譯

7、程序，要注意，要注意等價等價變換變換 本課程的本課程的任務任務就是講解在這個轉換過程中所涉及到的一些就是講解在這個轉換過程中所涉及到的一些理論和方法，最后，使用這些理論和方法，自己編寫一個理論和方法，最后，使用這些理論和方法，自己編寫一個小的編譯器小的編譯器 轉換是一個總體的功能，要抓住總體結構，逐層細分，寫轉換是一個總體的功能，要抓住總體結構，逐層細分，寫編譯器時要體現軟件工程中編譯器時要體現軟件工程中軟件設計的原則軟件設計的原則，自頂向下，自頂向下，逐層分解。逐層分解。 編譯器要完成的轉換任務相當復雜，實現編譯器時必須編譯器要完成的轉換任務相當復雜，實現編譯器時必須分分步驟分階段步驟分階段

8、實現。分階段實現的好處是能夠實現。分階段實現的好處是能夠簡化程序的設簡化程序的設計計，當然也可以不分階段實現。，當然也可以不分階段實現。編譯原理實踐及應用第13頁編譯程序的分類編譯程序的分類診斷編譯程序診斷編譯程序優(yōu)化編譯程序優(yōu)化編譯程序可變目標編譯程序可變目標編譯程序交叉編譯程序交叉編譯程序編譯原理實踐及應用第14頁編譯器的伙伴編譯器的伙伴編輯器編輯器(editor)(editor)預處理器預處理器(Preprocessor)(Preprocessor)將源程序匯集到一起，宏展開等將源程序匯集到一起，宏展開等匯編程序匯編程序(assembler)(assembler)連接程序連接程序(lin

9、ker)(linker)連接系統(tǒng)函數與系統(tǒng)資源連接系統(tǒng)函數與系統(tǒng)資源裝入程序裝入程序(loader)(loader)重定位重定位(relocation)(relocation)Debugger,Profiler,Project ManagerDebugger,Profiler,Project Manager編譯原理實踐及應用第15頁編譯原理是討論編譯程序設計的基本理論、編譯原理是討論編譯程序設計的基本理論、基本概念、基本方法基本概念、基本方法 什么是編譯原理什么是編譯原理編譯原理實踐及應用第16頁1.2 編譯過程概述 1 1、邏輯上分五個階段：邏輯上分五個階段：詞法分析、語法分析、語義分析與詞

10、法分析、語法分析、語義分析與中間代碼生成、代碼優(yōu)化、目標代碼生成中間代碼生成、代碼優(yōu)化、目標代碼生成 每個階段把源程序從一種表示變換成另一種表示每個階段把源程序從一種表示變換成另一種表示源 程 序編 譯 器目 標 程 序詞法分析語法分析語義分析與中間代碼生成代碼優(yōu)化目標代碼生成編譯原理實踐及應用第17頁 按照詞法分析、語法分析、語義分析等這種方式來按照詞法分析、語法分析、語義分析等這種方式來劃分階段的原因是：每個階段的復雜程度不同，所劃分階段的原因是：每個階段的復雜程度不同，所依據的依據的理論基礎不同理論基礎不同，實現時采用的，實現時采用的方法也不同方法也不同。主要是方便理解和實現。主要是方便

11、理解和實現。 劃分階段的依據是什么？每個階段所實現的劃分階段的依據是什么？每個階段所實現的功能相功能相對獨立對獨立。編譯原理實踐及應用用一個例子說明各階段的功能用一個例子說明各階段的功能第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. 編譯原理實踐及應用第19頁第一階段：詞法分析第一階段：詞法分

12、析任務任務: 從左到右掃描源程序，識別出每個單詞從左到右掃描源程序，識別出每個單詞o 附加任務：附加任務：a、濾掉空格、濾掉空格 b、去掉注釋、去掉注釋o 單詞符號單詞符號是語言的基本組成成分是語言的基本組成成分o 詞法分析的工作主要依據語言中單詞的構成規(guī)則詞法分析的工作主要依據語言中單詞的構成規(guī)則o 單詞的種類：單詞的種類： （1） 標識符標識符 （2） 關鍵字（關鍵字（char、int、if、else、while、for等）等） （3） 運算符（即運算符號運算符（即運算符號 +、*、/、&等）等） （4） 界符（常見的有界符（常見的有 ； ， ： （ ）等）等） （5） 常數常數

13、編譯原理實踐及應用第20頁begin area:=5length*width length *widthend;單詞類型內部形式begin關鍵字$beginarea標識符id1:=界符:=5常數int1+算符+length標識符id1*算符*width標識符id2+算符+length標識符id2*算符*width標識符id3end關鍵字$end;界符;例:編譯原理實踐及應用第21頁第二階段：語法分析第二階段：語法分析任務任務: 在詞法分析的基礎上，根據語言的語法規(guī)則，將單詞符在詞法分析的基礎上，根據語言的語法規(guī)則，將單詞符號串分解成各類語法短語號串分解成各類語法短語(例：程序、語句、表達式例：

14、程序、語句、表達式)。o 確定整個輸入串是否構成語法上正確的程序。確定整個輸入串是否構成語法上正確的程序。o 根據規(guī)則判定：根據規(guī)則判定：賦值語句：賦值語句：標識符標識符:表達式表達式 表達式：表達式：標識符、常數是表達式標識符、常數是表達式 表達式的運算也是表達式表達式的運算也是表達式例：識別符號串例：識別符號串id1:=int1 + id2 * id3 + id2 * id3是一個賦值語句是一個賦值語句（ area:=5length*widthlength *width）而而int1 + id2 * id3 + id2 * id3是一個表達式是一個表達式 （ 5length*widthle

15、ngth *width ）編譯原理實踐及應用第22頁語法分析所依據的是語言的語法規(guī)則id1:=int1 + id2 * id3 + id2 * id3編譯原理實踐及應用第23頁第三階段：語義分析和中間代碼生成第三階段：語義分析和中間代碼生成任務任務：對語法分析所識別出的各類語法短語分析其含義，：對語法分析所識別出的各類語法短語分析其含義，進行初步的翻譯進行初步的翻譯(翻譯成中間代碼翻譯成中間代碼)。o 靜態(tài)語義審查靜態(tài)語義審查 變量定義變量定義 類型匹配類型匹配 類型轉換類型轉換 例：例：C:=A*B (檢查檢查C與、類型與、類型)o 中間代碼的翻譯中間代碼的翻譯 中間代碼有多種形式，如：中間

16、代碼有多種形式，如： 四元式四元式: (運算符，運算對象運算符，運算對象1，運算對象，運算對象2，結果，結果) 編譯原理實踐及應用第24頁例：例：對賦值語句：對賦值語句： id1:=int1 + id2 * id3 + id2 * id3 1. 檢查檢查area、length、width是否定義、類型是否定義、類型 2. 生成中間代碼生成中間代碼(運算符，運算對象運算符，運算對象1，運算對象，運算對象2，結果，結果) (*, id2, id3, T1) (+, int1, T1, T2) (*, id2, id3, T3) (+, T2, T3, T4) (:=, T4, _, id1)id1

17、:=int1 + id2 * id3 + id2 * id3編譯原理實踐及應用第25頁第四階段：第四階段： 代碼優(yōu)化代碼優(yōu)化任務任務：對已產生的中間代碼進行加工變換，使生成的目標代碼更為高：對已產生的中間代碼進行加工變換，使生成的目標代碼更為高效效(時間和空間時間和空間)。o 優(yōu)化方法包括：公共子表達式的提取、循環(huán)優(yōu)化、刪除無用代碼等。優(yōu)化方法包括：公共子表達式的提取、循環(huán)優(yōu)化、刪除無用代碼等。o 代碼的優(yōu)化依據的是程序的等價變換規(guī)則。代碼的優(yōu)化依據的是程序的等價變換規(guī)則。序號 四元式1(*, id2, id3, T1)2(+, int1, T1, T2)3(*, id2, id3, T3)4

18、(+, T2, T3, T4)5(:=, T4, _, id1)序號 四元式1(*, id2, id3, T1)2 (+, int1, T1, T2)3(+, T2, T1, id1)編譯原理實踐及應用2022年5月6日星期五第26頁第五階段：目標代碼的生成第五階段：目標代碼的生成任務任務：把中間代碼：把中間代碼(或經優(yōu)化的中間代碼或經優(yōu)化的中間代碼)變換成變換成特定特定機器上的低級語言代碼。機器上的低級語言代碼。o 依賴于機器的硬件系統(tǒng)結構和機器指令的含義依賴于機器的硬件系統(tǒng)結構和機器指令的含義o 目標代碼可以是：絕對指令代碼、可重定位的指目標代碼可以是：絕對指令代碼、可重定位的指令代碼、匯

19、編指令代碼令代碼、匯編指令代碼序號 四元式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, AX編譯原理實踐及應用第27頁1.2編譯程序的結構 由左圖可以看出，詞法分析是實現編譯器的基礎，語法分析是實現編譯器的關鍵。 因此按照這個順序來實現編譯器 每一步的實現都依賴于一定的理論基礎。 數學，尤其是離散數學是程序設計方法學的理論基礎編譯原理實踐及應用第28頁編譯階段的組合編譯階段

20、的組合 幾個概念幾個概念遍：遍：對源程序或源程序的中間結果從頭到尾掃對源程序或源程序的中間結果從頭到尾掃描一次，并作有關的加工處理，生成新的中間描一次，并作有關的加工處理，生成新的中間結果或目標程序。結果或目標程序。編譯前端編譯前端：主要指與源語言有關，與目標語主要指與源語言有關，與目標語言無關的部分，通常包括詞法分析、語法分析、言無關的部分，通常包括詞法分析、語法分析、語義分析和中間代碼生成，與機器無關部分的語義分析和中間代碼生成，與機器無關部分的代碼優(yōu)化代碼優(yōu)化編譯后端編譯后端：指與目標機器有關的部分。如與指與目標機器有關的部分。如與機器有關的優(yōu)化、目標代碼生成機器有關的優(yōu)化、目標代碼生成

21、編譯原理實踐及應用第29頁編譯階段的組合編譯階段的組合編譯原理實踐及應用第30頁為什么生成中間代碼為什么生成中間代碼第第31頁頁編譯程序中的主要數據結構編譯程序中的主要數據結構 (續(xù)續(xù))Token表表符號表符號表常數表常數表錯誤信息錯誤信息語法樹語法樹中間代碼表中間代碼表臨時文件臨時文件目標代碼表目標代碼表編譯原理實踐及應用第32頁(1) Token表表 當掃描程序將字符收集到一個記號中時，它通常當掃描程序將字符收集到一個記號中時，它通常是以符號表示這個記號；這也就是說，作為一個枚是以符號表示這個記號；這也就是說，作為一個枚舉數據類型的值來表示源程序的記號集。舉數據類型的值來表示源程序的記號集

22、。(2) 語法樹（語法樹（syntax tree） 如果分析程序確實生成了語法樹，它的構造通常如果分析程序確實生成了語法樹，它的構造通常為基于指針的標準結構，在進行分析時動態(tài)分配該為基于指針的標準結構，在進行分析時動態(tài)分配該結構，則整棵樹可作為一個指向根節(jié)點的單個變量結構，則整棵樹可作為一個指向根節(jié)點的單個變量保存。結構中的每一個節(jié)點都是一個記錄，它的域保存。結構中的每一個節(jié)點都是一個記錄，它的域表示由分析程序和之后的語義分析程序收集的信息。表示由分析程序和之后的語義分析程序收集的信息。編譯程序中的主要數據結構介紹:編譯原理實踐及應用第33頁(3) 符號表（符號表（symbol table）

23、這個數據結構中的信息與標識符有關：函數、變量、常量這個數據結構中的信息與標識符有關：函數、變量、常量以及數據類型。符號表幾乎與編譯器的所有階段交互：掃描以及數據類型。符號表幾乎與編譯器的所有階段交互：掃描程序、分析程序或將標識符輸入到表格中的語義分析程序；程序、分析程序或將標識符輸入到表格中的語義分析程序；語義分析程序將增加數據類型和其他信息；優(yōu)化階段和代碼語義分析程序將增加數據類型和其他信息；優(yōu)化階段和代碼生成階段也將利用由符號表提供的信息選出恰當的代碼。因生成階段也將利用由符號表提供的信息選出恰當的代碼。因為對符號表的訪問如此頻繁，所以插入、刪除和訪問操作都為對符號表的訪問如此頻繁，所以插

24、入、刪除和訪問操作都必須比常規(guī)操作更有效。盡管可以使用各種樹的結構，但雜必須比常規(guī)操作更有效。盡管可以使用各種樹的結構，但雜湊表卻是達到這一要求的標準數據結構。有時在一個列表或湊表卻是達到這一要求的標準數據結構。有時在一個列表或棧中可使用若干個表格。棧中可使用若干個表格。編譯原理實踐及應用第34頁(4) 常數表（常數表（literal table） 常數表的功能是存放在程序中用到的常量和字符常數表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常數表中也十分重要。但串，因此快速插入和查找在常數表中也十分重要。但是，在其中卻無需刪除，這是因為它的數據全程應用是，在其中卻無需刪除，這是

25、因為它的數據全程應用于程序而且常量或字符串在該表中只出現一次。于程序而且常量或字符串在該表中只出現一次。(5) 中間代碼（中間代碼（intermediate code） 根據中間代碼的類型（例如三元式代碼）和優(yōu)化根據中間代碼的類型（例如三元式代碼）和優(yōu)化的類型，該代碼可以是文本串的數組、臨時文本文件的類型，該代碼可以是文本串的數組、臨時文本文件或是結構的連接列表。對于進行復雜優(yōu)化的編譯器，或是結構的連接列表。對于進行復雜優(yōu)化的編譯器，應特別注意選擇允許簡單重組的表示。應特別注意選擇允許簡單重組的表示。編譯原理實踐及應用第35頁(6) 目標目標代碼（代碼（intermediate code） 存

26、放最終生成的目標代碼，該代碼最終是文本形式的文件。存放最終生成的目標代碼，該代碼最終是文本形式的文件。(7) 臨時文件（臨時文件（t e m p o r a ry file） 計算機過去一直未能在編譯器時將整個程序保留在存儲器中。計算機過去一直未能在編譯器時將整個程序保留在存儲器中。這一問題已經通過使用這一問題已經通過使用臨時文件來保存翻譯時中間步驟的結臨時文件來保存翻譯時中間步驟的結果或通過果或通過“匆忙地匆忙地”編譯編譯（也就是只保留源程序早期部分的（也就是只保留源程序早期部分的足夠信息用以處理翻譯）解決了。足夠信息用以處理翻譯）解決了。編譯原理實踐及應用第36頁1.3 編譯程序的設計 構

27、造編譯程序要掌握以下幾方面的內容：構造編譯程序要掌握以下幾方面的內容： 源語言：理解其結構和含義源語言：理解其結構和含義 目標語言：必須清楚硬件的系統(tǒng)結構和指令的目標語言：必須清楚硬件的系統(tǒng)結構和指令的格式等格式等 編譯方法編譯方法編譯原理實踐及應用第37頁1.3 編譯程序的構造 一般實現編譯程序的方法有：一般實現編譯程序的方法有：1.1.直接用機器語言編寫編譯程序直接用機器語言編寫編譯程序2.2.用匯編語言編寫編譯程序用匯編語言編寫編譯程序 注：編譯程序核心部分常用匯編語言編寫注：編譯程序核心部分常用匯編語言編寫3.3.用高級語言編寫編譯程序用高級語言編寫編譯程序 注：這是普遍采用的方法注：

28、這是普遍采用的方法4.4.自編譯自編譯5.5.用編譯工具自動生成用編譯工具自動生成:LEX(:LEX(詞法分析詞法分析) )與與YACC(YACC(用于用于自動產生自動產生LALRLALR分析表分析表) )6.6.移植（同種語言的編譯程序在不同類型的機器之移植（同種語言的編譯程序在不同類型的機器之間移植）間移植）編譯原理實踐及應用第38頁本書構成及編譯程序框架本書構成及編譯程序框架編譯原理實踐及應用第39頁1.4 編譯技術的發(fā)展1954年至年至1957年間，年間，FORTRAN語言及其編譯器的開發(fā)?；苏Z言及其編譯器的開發(fā)。花了18個人年。個人年。幾乎與此同時，幾乎與此同時，Noam Chom

29、sky開始研究語言開始研究語言文法文法(grammar，結構規(guī)則，結構規(guī)則)的難易程的難易程度以及識別它們所需的算法來為語言分類。度以及識別它們所需的算法來為語言分類。在在6 0年代和年代和7 0年代進行的分析問題年代進行的分析問題(parsing problem，用于限定上下文無關語言的，用于限定上下文無關語言的識別的有效算法識別的有效算法)的研究。的研究。有窮自動機有窮自動機(finite automata)和正規(guī)式和正規(guī)式(regular expression) 的研究與喬姆斯基的研的研究與喬姆斯基的研究幾乎同時開始，引出了表示程序設計語言的單詞的符號方式。究幾乎同時開始，引出了表示程序

30、設計語言的單詞的符號方式。接著又深化了生成有效的目標代碼的方法，這就是最初的編譯器，實際上應稱作接著又深化了生成有效的目標代碼的方法，這就是最初的編譯器，實際上應稱作代碼改進技術代碼改進技術(code improvement technique)。當分析問題變得好懂起來時，人們就在開發(fā)程序上花費了很大的功夫來研究這一當分析問題變得好懂起來時，人們就在開發(fā)程序上花費了很大的功夫來研究這一部分的編譯器的自動構造。部分的編譯器的自動構造。Lex與與Yacc。在在70年代后期和年代后期和80年代早期，大量的項目都關注于編譯器其他部分的生成自動化，年代早期，大量的項目都關注于編譯器其他部分的生成自動化，這其中就包括了代碼生成。這些嘗試并未取得多少成功。這其中就包括了代碼生成。這些嘗試并未取得多少成功。 編譯原理實踐及應用第40頁1.4 編譯技術最近的發(fā)展與復雜的程序設計語言的發(fā)展結合在一起。如用于函數語言編譯與復雜的程序設計語言的發(fā)