編譯第1章 概述

1、編譯原理 主講：白明E-mail:班級：1308011308022022年4月29日星期五第2頁教材及主要參考資料教材及主要參考資料 教材教材：編譯原理及實(shí)踐教程，：編譯原理及實(shí)踐教程，黃賢英，清華大學(xué)出版社黃賢英，清華大學(xué)出版社 主要參考資料：主要參考資料： 編譯原理，編譯原理，陳火旺，國防工業(yè)出版社陳火旺，國防工業(yè)出版社 編譯原理（原書第編譯原理（原書第2版）（龍書）版）（龍書） ，ALFRED V.AHO etc著，趙建華著，趙建華 鄭滔等譯鄭滔等譯 ，機(jī)械工業(yè)出版社，機(jī)械工業(yè)出版社，2008.12 程序設(shè)計(jì)語言編譯方法程序設(shè)計(jì)語言編譯方法，肖軍模，大連理工大學(xué)出版社，肖軍模，大連理工大

2、學(xué)出版社 編譯原理，編譯原理，張素琴，呂映芝，清華大學(xué)出版社張素琴，呂映芝，清華大學(xué)出版社 更多教材及參考資料參見更多教材及參考資料參見編譯原理精品課程網(wǎng)站編譯原理精品課程網(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)容單元名字單元名字200H3x：局部變量202H2y：局部變量204H5z：局部變量300H3A03302H3AE1304H3A02306H3AE2308HDA6C.3A71匯匯編編語語言言程程序序mov ax,3mov x,axmov bx,2mov y,bxadd ax,bxmov z,a

3、x.序言在內(nèi)存中：在內(nèi)存中：數(shù)據(jù)區(qū)代碼區(qū) ？第4頁第1章 概述 主要內(nèi)容主要內(nèi)容：各種翻譯程序的概念，編譯過：各種翻譯程序的概念，編譯過程和階段劃分，編譯程序的組成和結(jié)構(gòu)，程和階段劃分，編譯程序的組成和結(jié)構(gòu)，編譯程序的構(gòu)造方法。編譯程序的構(gòu)造方法。 重點(diǎn)掌握：重點(diǎn)掌握：編譯程序工作的基本過程及其編譯程序工作的基本過程及其各階段的基本任務(wù)，編譯程序總框。各階段的基本任務(wù)，編譯程序總框。本章要求第5頁1.1 程序設(shè)計(jì)語言與編譯程序 機(jī)器語言機(jī)器語言 (machine language) C7 06 0000 0002 匯編語言匯編語言 (assembler language) MOV X , 2

4、高級語言高級語言 (high-level language) X = 2為什么要使用編譯程序?yàn)槭裁匆褂镁幾g程序？2022年4月29日星期五第6頁計(jì)算機(jī)中的語言層次和翻譯程序計(jì)算機(jī)中的語言層次和翻譯程序第7頁什么叫翻譯程序 翻譯程序翻譯程序：能夠?qū)⒛撤N語言寫的程序轉(zhuǎn)換成另能夠?qū)⒛撤N語言寫的程序轉(zhuǎn)換成另一種語言的程序，而且后者與前者在邏輯上是一種語言的程序，而且后者與前者在邏輯上是等價(jià)等價(jià)的。的。 編譯程序編譯程序：將高級程序設(shè)計(jì)語言程序翻譯成邏將高級程序設(shè)計(jì)語言程序翻譯成邏輯上等價(jià)的低級語言輯上等價(jià)的低級語言(匯編語言，機(jī)器語言匯編語言，機(jī)器語言)程序程序的翻譯程序。的翻譯程序。 解釋程序：解

5、釋程序：將高級程序設(shè)計(jì)語言寫的源程序作將高級程序設(shè)計(jì)語言寫的源程序作為輸入，邊解釋邊執(zhí)行源程序本身，而不產(chǎn)生為輸入，邊解釋邊執(zhí)行源程序本身，而不產(chǎn)生目標(biāo)程序的翻譯程序。目標(biāo)程序的翻譯程序。第第8頁頁高高級級語語言言語言處理語言處理程序程序操作系統(tǒng)操作系統(tǒng)匯編語言匯編語言翻譯程序所處的層次翻譯程序所處的層次計(jì)算機(jī)硬件計(jì)算機(jī)硬件C編譯程編譯程序序C語語言言Basic解釋程序解釋程序Basic語言語言Fortran編譯程序編譯程序Fortran語言語言.2022年4月29日星期五第9頁編譯程序編譯程序編譯程序源程序源程序目標(biāo)程序目標(biāo)程序計(jì)算機(jī)運(yùn)行計(jì)算機(jī)運(yùn)行輸入數(shù)據(jù)輸入數(shù)據(jù)結(jié)果結(jié)果解釋程序解釋程序解釋

6、程序源程序源程序輸入數(shù)據(jù)輸入數(shù)據(jù)結(jié)果結(jié)果第10頁對編譯程序的一些說明對編譯程序的一些說明 編譯程序?qū)嵸|(zhì)上是一個(gè)編譯程序?qū)嵸|(zhì)上是一個(gè)翻譯程序翻譯程序，要注意，要注意等價(jià)等價(jià)變換。變換。 本課程的本課程的任務(wù)任務(wù)就是講解在這個(gè)轉(zhuǎn)換過程中所涉及到的一些就是講解在這個(gè)轉(zhuǎn)換過程中所涉及到的一些理論和方法，最后，理解編譯的原理和實(shí)現(xiàn)方法，高標(biāo)準(zhǔn)：理論和方法，最后，理解編譯的原理和實(shí)現(xiàn)方法，高標(biāo)準(zhǔn)：使用這些理論和方法，自己編寫一個(gè)小的編譯器。使用這些理論和方法，自己編寫一個(gè)小的編譯器。 轉(zhuǎn)換是一個(gè)總體的功能，要抓住總體結(jié)構(gòu)，逐層細(xì)分，寫轉(zhuǎn)換是一個(gè)總體的功能，要抓住總體結(jié)構(gòu)，逐層細(xì)分，寫編譯器時(shí)要體現(xiàn)軟件工程

7、中編譯器時(shí)要體現(xiàn)軟件工程中軟件設(shè)計(jì)的原則軟件設(shè)計(jì)的原則，自頂向下，自頂向下，逐層分解。逐層分解。 編譯器要完成的轉(zhuǎn)換任務(wù)相當(dāng)復(fù)雜，實(shí)現(xiàn)編譯器時(shí)必須編譯器要完成的轉(zhuǎn)換任務(wù)相當(dāng)復(fù)雜，實(shí)現(xiàn)編譯器時(shí)必須分分步驟分階段步驟分階段實(shí)現(xiàn)。分階段實(shí)現(xiàn)的好處是能夠?qū)崿F(xiàn)。分階段實(shí)現(xiàn)的好處是能夠簡化程序的設(shè)簡化程序的設(shè)計(jì)計(jì)，當(dāng)然也可以不分階段實(shí)現(xiàn)。，當(dāng)然也可以不分階段實(shí)現(xiàn)。第11頁編譯程序的分類編譯程序的分類診斷編譯程序診斷編譯程序優(yōu)化編譯程序優(yōu)化編譯程序可變目標(biāo)編譯程序可變目標(biāo)編譯程序交叉編譯程序交叉編譯程序第12頁編譯器的伙伴編譯器的伙伴編輯器編輯器(editor)預(yù)處理器預(yù)處理器(Preprocessor)將

8、源程序匯集到一起，宏展開等將源程序匯集到一起，宏展開等匯編程序匯編程序(assembler)連接程序連接程序(linker)連接系統(tǒng)函數(shù)與系統(tǒng)資源連接系統(tǒng)函數(shù)與系統(tǒng)資源裝入程序裝入程序(loader)重定位重定位(relocation)Debugger,Profiler,Project Manager第13頁1.2 編譯過程和編譯程序的結(jié)構(gòu)源 程 序編 譯 器目 標(biāo) 程 序詞詞法法分分析析語語法法分分析析語義分析語義分析與中間代與中間代碼生成碼生成代代碼碼優(yōu)優(yōu)化化目標(biāo)代目標(biāo)代碼生成碼生成第14頁 按照詞法分析、語法分析、語義分析等這種方式來按照詞法分析、語法分析、語義分析等這種方式來劃分階段的

9、原因是：每個(gè)階段的復(fù)雜程度不同，所劃分階段的原因是：每個(gè)階段的復(fù)雜程度不同，所依據(jù)的依據(jù)的理論基礎(chǔ)不同理論基礎(chǔ)不同，實(shí)現(xiàn)時(shí)采用的，實(shí)現(xiàn)時(shí)采用的方法也不同方法也不同。主要是方便理解和實(shí)現(xiàn)。主要是方便理解和實(shí)現(xiàn)。 劃分階段的依據(jù)是什么？每個(gè)階段所實(shí)現(xiàn)的劃分階段的依據(jù)是什么？每個(gè)階段所實(shí)現(xiàn)的功能相功能相對獨(dú)立對獨(dú)立。 邏輯上分五個(gè)階段：邏輯上分五個(gè)階段：詞法分析、語法分析、語義分詞法分析、語法分析、語義分析與中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成。析與中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成。 每個(gè)階段把源程序從一種表示變換成另一種表示。每個(gè)階段把源程序從一種表示變換成另一種表示。用一個(gè)例子說明各階段的功

10、能用一個(gè)例子說明各階段的功能第15頁/*一個(gè)一個(gè)PASCAL語言的源程序語言的源程序*/program test; /*this is an example,computing an area*/ var area, length, width: integer; begin length:=5;width:=5; area := 5length *widthlength *widthend. 第16頁第一階段：詞法分析第一階段：詞法分析 任務(wù)任務(wù)：從左到右掃描源程序，識別出每個(gè)單詞。從左到右掃描源程序，識別出每個(gè)單詞。o 附加任務(wù)：（附加任務(wù)：（1）濾掉空格（）濾掉空格（2）去掉注釋。）去掉

11、注釋。o 單詞符號是語言的基本組成成分。單詞符號是語言的基本組成成分。o 詞法分析的工作主要依據(jù)語言中單詞的構(gòu)成規(guī)則。詞法分析的工作主要依據(jù)語言中單詞的構(gòu)成規(guī)則。o 單詞的種類：單詞的種類： （1） 標(biāo)識符標(biāo)識符 （2） 關(guān)鍵字（關(guān)鍵字（char、int、if、else、while、for等）等） （3） 運(yùn)算符（即運(yùn)算符號運(yùn)算符（即運(yùn)算符號 +、*、/、&等）等） （4） 界符（常見的有界符（常見的有 ； ， ： （ ）等）等） （5） 常數(shù)常數(shù) 第17頁begin area:=5length*width length *widthend;單詞單詞類型類型內(nèi)部形式內(nèi)部形式begin關(guān)

12、鍵字關(guān)鍵字$beginarea標(biāo)識符標(biāo)識符id1:=界符界符:=5常數(shù)常數(shù)int1+算符算符+length標(biāo)識符標(biāo)識符id1*算符算符*width標(biāo)識符標(biāo)識符id2+算符算符+length標(biāo)識符標(biāo)識符id2*算符算符*width標(biāo)識符標(biāo)識符id3end關(guān)鍵字關(guān)鍵字$end;界符界符;例例:第18頁第二階段：語法分析第二階段：語法分析任務(wù)任務(wù): 在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，將單詞符號在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，將單詞符號串分解成各類語法短語（例：程序、語句、表達(dá)式）。串分解成各類語法短語（例：程序、語句、表達(dá)式）。o 確定整個(gè)輸入串是否構(gòu)成語法上正確的程序。確定整個(gè)輸入串

13、是否構(gòu)成語法上正確的程序。o 根據(jù)規(guī)則判定：根據(jù)規(guī)則判定：賦值語句：賦值語句：標(biāo)識符標(biāo)識符:表達(dá)式表達(dá)式 表達(dá)式：表達(dá)式：標(biāo)識符、常數(shù)是表達(dá)式標(biāo)識符、常數(shù)是表達(dá)式 表達(dá)式的運(yùn)算也是表達(dá)式表達(dá)式的運(yùn)算也是表達(dá)式例：識別符號串例：識別符號串id1:=int1 + id2 * id3 + id2 * id3是一個(gè)賦值語句（是一個(gè)賦值語句（ area:=5length*widthlength *width）而而int1 + id2 * id3 + id2 * id3是一個(gè)表達(dá)式是一個(gè)表達(dá)式 （ 5length*widthlength *width ）第19頁語法分析所依據(jù)的是語言的語法規(guī)則！語法分析所

14、依據(jù)的是語言的語法規(guī)則！id1:=int1 + id2 * id3 + id2 * id3第20頁第三階段：語義分析和中間代碼生成第三階段：語義分析和中間代碼生成任務(wù)任務(wù)：對語法分析所識別出的各類語法短語分析其含義，：對語法分析所識別出的各類語法短語分析其含義，進(jìn)行初步的翻譯進(jìn)行初步的翻譯(翻譯成中間代碼翻譯成中間代碼)。o 靜態(tài)語義審查靜態(tài)語義審查 變量定義變量定義 類型匹配類型匹配 類型轉(zhuǎn)換類型轉(zhuǎn)換 例：例：C:=A*B (檢查檢查C與、類型與、類型)o 中間代碼的翻譯中間代碼的翻譯 中間代碼有多種形式，如：中間代碼有多種形式，如： 四元式四元式: (運(yùn)算符，運(yùn)算對象運(yùn)算符，運(yùn)算對象1，運(yùn)

15、算對象，運(yùn)算對象2，結(jié)果，結(jié)果) 第21頁例：例：對賦值語句：對賦值語句： id1:=int1 + id2 * id3 + id2 * id3 1. 檢查檢查area、length、width是否定義、類型是否定義、類型 2. 生成中間代碼生成中間代碼(運(yùn)算符，運(yùn)算對象運(yùn)算符，運(yùn)算對象1，運(yùn)算對象，運(yùn)算對象2，結(jié)果，結(jié)果) (*, id2, id3, T1) (+, int1, T1, T2) (*, id2, id3, T3) (+, T2, T3, T4) (:=, T4, _, id1)id1:=int1 + id2 * id3 + id2 * id3第22頁第四階段：第四階段： 代碼優(yōu)

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

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

18、, 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第24頁 由左圖可以看由左圖可以看出，詞法分析出，詞法分析是實(shí)現(xiàn)編譯器是實(shí)現(xiàn)編譯器的基礎(chǔ)，語法的基礎(chǔ)，語法分析是實(shí)現(xiàn)編分析是實(shí)現(xiàn)編譯器的關(guān)鍵。譯器的關(guān)鍵。 因此按照這個(gè)因此按照這個(gè)順序來實(shí)現(xiàn)編順序來實(shí)現(xiàn)編譯器。譯器。第25頁編譯階段的組合 幾個(gè)概念幾個(gè)概念 遍：遍：對源程序或源程序的中間結(jié)果從頭到尾對源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成新

19、的掃描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。中間結(jié)果或目標(biāo)程序。 編譯前端編譯前端：主要指與源語言有關(guān)，與目標(biāo)語：主要指與源語言有關(guān)，與目標(biāo)語言無關(guān)的部分，通常包括詞法分析、語法分言無關(guān)的部分，通常包括詞法分析、語法分析、語義分析和中間代碼生成，與機(jī)器無關(guān)析、語義分析和中間代碼生成，與機(jī)器無關(guān)部分的代碼優(yōu)化。部分的代碼優(yōu)化。 編譯后端編譯后端：指與目標(biāo)機(jī)器有關(guān)的部分。如與：指與目標(biāo)機(jī)器有關(guān)的部分。如與機(jī)器有關(guān)的優(yōu)化、目標(biāo)代碼生成。機(jī)器有關(guān)的優(yōu)化、目標(biāo)代碼生成。第26頁編譯階段的組合第27頁為什么生成中間代碼第第28頁頁編譯程序中的主要數(shù)據(jù)結(jié)構(gòu) (續(xù))Token表表符號表符號表常

20、數(shù)表常數(shù)表錯(cuò)誤信息錯(cuò)誤信息語法樹語法樹中間代碼表中間代碼表臨時(shí)文件臨時(shí)文件目標(biāo)代碼表目標(biāo)代碼表第29頁 (1) Token表表 當(dāng)掃描程序?qū)⒆址占揭粋€(gè)記號中時(shí)，它通常是以當(dāng)掃描程序?qū)⒆址占揭粋€(gè)記號中時(shí)，它通常是以符號表示這個(gè)記號；這也就是說，作為一個(gè)枚舉數(shù)據(jù)類型符號表示這個(gè)記號；這也就是說，作為一個(gè)枚舉數(shù)據(jù)類型的值來表示源程序的記號集。的值來表示源程序的記號集。 (2) 語法樹語法樹（syntax tree） 如果分析程序確實(shí)生成了語法樹，它的構(gòu)造通常為基如果分析程序確實(shí)生成了語法樹，它的構(gòu)造通常為基于指針的標(biāo)準(zhǔn)結(jié)構(gòu)，在進(jìn)行分析時(shí)動態(tài)分配該結(jié)構(gòu)，則整于指針的標(biāo)準(zhǔn)結(jié)構(gòu)，在進(jìn)行分析時(shí)動態(tài)分

21、配該結(jié)構(gòu)，則整棵樹可作為一個(gè)指向根節(jié)點(diǎn)的單個(gè)變量保存。結(jié)構(gòu)中的每棵樹可作為一個(gè)指向根節(jié)點(diǎn)的單個(gè)變量保存。結(jié)構(gòu)中的每一個(gè)節(jié)點(diǎn)都是一個(gè)記錄，它的域表示由分析程序和之后的一個(gè)節(jié)點(diǎn)都是一個(gè)記錄，它的域表示由分析程序和之后的語義分析程序收集的信息。語義分析程序收集的信息。編譯程序中的主要數(shù)據(jù)結(jié)構(gòu)介紹第30頁 (3) 符號表（符號表（symbol table） 這個(gè)數(shù)據(jù)結(jié)構(gòu)中的信息與標(biāo)識符有關(guān)：函數(shù)、變量、這個(gè)數(shù)據(jù)結(jié)構(gòu)中的信息與標(biāo)識符有關(guān)：函數(shù)、變量、常量以及數(shù)據(jù)類型。常量以及數(shù)據(jù)類型。 符號表幾乎與編譯器的所有階段交互：掃描程序、符號表幾乎與編譯器的所有階段交互：掃描程序、分析程序或?qū)?biāo)識符輸入到表格中

22、的語義分析程序；語分析程序或?qū)?biāo)識符輸入到表格中的語義分析程序；語義分析程序?qū)⒃黾訑?shù)據(jù)類型和其他信息；優(yōu)化階段和代義分析程序?qū)⒃黾訑?shù)據(jù)類型和其他信息；優(yōu)化階段和代碼生成階段也將利用由符號表提供的信息選出恰當(dāng)?shù)拇a生成階段也將利用由符號表提供的信息選出恰當(dāng)?shù)拇a。碼。 因?yàn)閷Ψ柋淼脑L問如此頻繁，所以插入、刪除和因?yàn)閷Ψ柋淼脑L問如此頻繁，所以插入、刪除和訪問操作都必須比常規(guī)操作更有效。盡管可以使用各種訪問操作都必須比常規(guī)操作更有效。盡管可以使用各種樹的結(jié)構(gòu)，但雜湊表卻是達(dá)到這一要求的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)。樹的結(jié)構(gòu)，但雜湊表卻是達(dá)到這一要求的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)。第31頁 (4) 常數(shù)表（常數(shù)表（literal

23、 table） 常數(shù)表的功能是存放在程序中用到的常量和字符串，常數(shù)表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常數(shù)表中也十分重要。但是，在因此快速插入和查找在常數(shù)表中也十分重要。但是，在其中卻無需刪除，這是因?yàn)樗臄?shù)據(jù)全程應(yīng)用于程序而其中卻無需刪除，這是因?yàn)樗臄?shù)據(jù)全程應(yīng)用于程序而且常量或字符串在該表中只出現(xiàn)一次。且常量或字符串在該表中只出現(xiàn)一次。 (5) 中間代碼（中間代碼（intermediate code） 根據(jù)中間代碼的類型（例如四元式代碼）和優(yōu)化的根據(jù)中間代碼的類型（例如四元式代碼）和優(yōu)化的類型，該代碼可以是文本串的數(shù)組、臨時(shí)文本文件或是類型，該代碼可以是文本串的數(shù)

24、組、臨時(shí)文本文件或是結(jié)構(gòu)的連接列表。對于進(jìn)行復(fù)雜優(yōu)化的編譯器，應(yīng)特別結(jié)構(gòu)的連接列表。對于進(jìn)行復(fù)雜優(yōu)化的編譯器，應(yīng)特別注意選擇允許簡單重組的表示。注意選擇允許簡單重組的表示。第32頁 (6) 目標(biāo)目標(biāo)代碼（代碼（intermediate code） 存放最終生成的目標(biāo)代碼，該代碼最終是文本存放最終生成的目標(biāo)代碼，該代碼最終是文本形式的文件。形式的文件。 (7) 臨時(shí)文件（臨時(shí)文件（temporary file） 計(jì)算機(jī)過去一直未能在編譯時(shí)將整個(gè)程序保留計(jì)算機(jī)過去一直未能在編譯時(shí)將整個(gè)程序保留在存儲器中。這一問題已經(jīng)通過使用臨時(shí)文件來保在存儲器中。這一問題已經(jīng)通過使用臨時(shí)文件來保存翻譯時(shí)中間步驟的

25、結(jié)果或通過存翻譯時(shí)中間步驟的結(jié)果或通過“匆忙地匆忙地”編譯編譯（也就是只保留源程序早期部分的足夠信息用以處（也就是只保留源程序早期部分的足夠信息用以處理翻譯）解決了。理翻譯）解決了。第33頁1.3 編譯程序的設(shè)計(jì) 構(gòu)造編譯程序要掌握的內(nèi)容構(gòu)造編譯程序要掌握的內(nèi)容 源語言：理解其結(jié)構(gòu)和含義；源語言：理解其結(jié)構(gòu)和含義； 目標(biāo)語言：必須清楚硬件的系統(tǒng)結(jié)構(gòu)和指令的目標(biāo)語言：必須清楚硬件的系統(tǒng)結(jié)構(gòu)和指令的格式等；格式等； 編譯方法。編譯方法。第34頁1.3 編譯程序的構(gòu)造 一般實(shí)現(xiàn)編譯程序的方法一般實(shí)現(xiàn)編譯程序的方法1. 直接用機(jī)器語言編寫編譯程序直接用機(jī)器語言編寫編譯程序2. 用匯編語言編寫編譯程序用

26、匯編語言編寫編譯程序 注：編譯程序核心部分常用匯編語言編寫。注：編譯程序核心部分常用匯編語言編寫。3. 用高級語言編寫編譯程序用高級語言編寫編譯程序 注：這是普遍采用的方法。注：這是普遍采用的方法。4. 自編譯自編譯5. 用編譯工具自動生成用編譯工具自動生成:LEX(詞法分析詞法分析)與與YACC(用于自動產(chǎn)用于自動產(chǎn)生生LALR分析表分析表)6. 移植（同種語言的編譯程序在不同類型的機(jī)器之間移植）移植（同種語言的編譯程序在不同類型的機(jī)器之間移植）第35頁本書構(gòu)成及編譯程序框架 章節(jié)章節(jié) 第第3章章第第4章、第章、第5章章第第7章章 第第6章、第章、第8章章第36頁1.4 編譯技術(shù)的發(fā)展及應(yīng)用

27、1954年至年至1957年間，年間，F(xiàn)ORTRAN語言及其編譯器的開發(fā)。花了語言及其編譯器的開發(fā)?；?8個(gè)人年。個(gè)人年。幾乎與此同時(shí)，幾乎與此同時(shí)，Noam Chomsky開始研究語言開始研究語言文法文法(grammar，結(jié)構(gòu)規(guī)則，結(jié)構(gòu)規(guī)則)的難易程的難易程度以及識別它們所需的算法來為語言分類。度以及識別它們所需的算法來為語言分類。在在6 0年代和年代和7 0年代進(jìn)行的分析問題年代進(jìn)行的分析問題(parsing problem，用于限定上下文無關(guān)語言的，用于限定上下文無關(guān)語言的識別的有效算法識別的有效算法)的研究。的研究。有窮自動機(jī)有窮自動機(jī)(finite automata)和正規(guī)式和正規(guī)式

28、(regular expression) 的研究與喬姆斯基的研究的研究與喬姆斯基的研究幾乎同時(shí)開始，引出了表示程序設(shè)計(jì)語言的單詞的符號方式。幾乎同時(shí)開始，引出了表示程序設(shè)計(jì)語言的單詞的符號方式。接著又深化了生成有效的目標(biāo)代碼的方法，這就是最初的編譯器，實(shí)際上應(yīng)稱作接著又深化了生成有效的目標(biāo)代碼的方法，這就是最初的編譯器，實(shí)際上應(yīng)稱作代碼改進(jìn)技術(shù)代碼改進(jìn)技術(shù)(code improvement technique)。當(dāng)分析問題變得好懂起來時(shí)，人們就在開發(fā)程序上花費(fèi)了很大的功夫來研究這一當(dāng)分析問題變得好懂起來時(shí)，人們就在開發(fā)程序上花費(fèi)了很大的功夫來研究這一部分的編譯器的自動構(gòu)造。部分的編譯器的自動構(gòu)

29、造。Lex與與Yacc。在在70年代后期和年代后期和80年代早期，大量的項(xiàng)目都關(guān)注于編譯器其他部分的生成自動化，年代早期，大量的項(xiàng)目都關(guān)注于編譯器其他部分的生成自動化，這其中就包括了代碼生成。這些嘗試并未取得多少成功。這其中就包括了代碼生成。這些嘗試并未取得多少成功。 第37頁1.4.1 編譯技術(shù)最近的發(fā)展與復(fù)雜的程序設(shè)計(jì)語言的發(fā)展結(jié)合在一起。如用于函數(shù)語言編譯與復(fù)雜的程序設(shè)計(jì)語言的發(fā)展結(jié)合在一起。如用于函數(shù)語言編譯的的Hindley-Milner類型檢查的統(tǒng)一算法。類型檢查的統(tǒng)一算法。編譯器已成為基于窗口的交互開發(fā)環(huán)境編譯器已成為基于窗口的交互開發(fā)環(huán)境(IDE)的一部分，的一部分，IDE的的

30、標(biāo)準(zhǔn)并沒有多少，但已對標(biāo)準(zhǔn)的窗口環(huán)境進(jìn)行了開發(fā)。近年來對標(biāo)準(zhǔn)并沒有多少，但已對標(biāo)準(zhǔn)的窗口環(huán)境進(jìn)行了開發(fā)。近年來對此進(jìn)行了大量研究，但是基本的編譯器設(shè)計(jì)近此進(jìn)行了大量研究，但是基本的編譯器設(shè)計(jì)近20年來沒有多大的年來沒有多大的改變，現(xiàn)在正迅速地成為計(jì)算機(jī)科學(xué)課程中的中心一環(huán)。改變，現(xiàn)在正迅速地成為計(jì)算機(jī)科學(xué)課程中的中心一環(huán)。由多處理機(jī)的發(fā)展以及對并行處理的要求，最近的研究方向是并由多處理機(jī)的發(fā)展以及對并行處理的要求，最近的研究方向是并行編譯。行編譯。隨著嵌入式應(yīng)用的迅速增長，推動了交叉編譯技術(shù)的發(fā)展；對系隨著嵌入式應(yīng)用的迅速增長，推動了交叉編譯技術(shù)的發(fā)展；對系統(tǒng)芯片設(shè)計(jì)方法和關(guān)鍵統(tǒng)芯片設(shè)計(jì)方法和關(guān)鍵EDA技術(shù)的研究，也帶動了專用語言技術(shù)的研究，也帶動了專用語言VHDL等及其編譯技術(shù)的不斷深化。等及其編譯技術(shù)的不斷深化。 第38頁1.4.2 為什么要學(xué)習(xí)編譯原理及其構(gòu)造技術(shù) 有助于深刻理解和正確使用程序設(shè)計(jì)語言；有助于深刻理解和正確使用程序設(shè)計(jì)語言