編譯原理預(yù)備課——第一章引論

1、第一章 引論 授課人授課人: : 衛(wèi)志華衛(wèi)志華 ZZ 內(nèi)容線索 n什么叫編譯程序什么叫編譯程序 n編譯過程概述編譯過程概述 n編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu) n編譯程序的生成編譯程序的生成 n總結(jié)總結(jié) 程序語言技術(shù)的發(fā)展 匯編語言匯編語言 機(jī)器語言機(jī)器語言 高級(jí)語言高級(jí)語言 MOV X, 2 C7 06 0000 0002 X=2 表示機(jī)器實(shí)際操作表示機(jī)器實(shí)際操作 的數(shù)字代碼的數(shù)字代碼 以符號(hào)形式給出指以符號(hào)形式給出指 令和存儲(chǔ)地址的令和存儲(chǔ)地址的 類似于數(shù)學(xué)定義或類似于數(shù)學(xué)定義或 自然語言的簡潔形自然語言的簡潔形 式編寫程序的操作式編寫程序的操作 表示在表示在IBM PC 上上 使用的使用的I

2、ntel 8x86 處理器將數(shù)字處理器將數(shù)字2移移 至地址至地址0 0 0 0 （16進(jìn)制）的指令進(jìn)制）的指令 ？ 程序的執(zhí)行方式 n高級(jí)語言程序通常采用高級(jí)語言程序通常采用解釋方式解釋方式和和翻譯方式翻譯方式兩種方式執(zhí)行兩種方式執(zhí)行 解釋方式解釋方式 逐個(gè)語句地分析和執(zhí)行逐個(gè)語句地分析和執(zhí)行 如如Basic，Prolog 優(yōu)點(diǎn)優(yōu)點(diǎn)：易于查錯(cuò)：易于查錯(cuò) 缺點(diǎn)缺點(diǎn)：效率低，運(yùn)行速度慢：效率低，運(yùn)行速度慢 翻譯方式翻譯方式 對(duì)整個(gè)程序進(jìn)行分析，翻譯成等價(jià)對(duì)整個(gè)程序進(jìn)行分析，翻譯成等價(jià) 機(jī)器語言程序后執(zhí)行機(jī)器語言程序后執(zhí)行 如如Pascal，F(xiàn)ortran，C 優(yōu)點(diǎn)優(yōu)點(diǎn)：只需分析和翻譯一次，：只需分

3、析和翻譯一次， 缺點(diǎn)缺點(diǎn)：在運(yùn)行中發(fā)現(xiàn)的錯(cuò)誤必：在運(yùn)行中發(fā)現(xiàn)的錯(cuò)誤必 須查找整個(gè)程序確定須查找整個(gè)程序確定 解釋程序和編譯程序 解釋程序解釋程序：邊解：邊解 釋邊執(zhí)行源語釋邊執(zhí)行源語 言程序，不產(chǎn)言程序，不產(chǎn) 生目標(biāo)語言程生目標(biāo)語言程 序。序。 編譯程序編譯程序：能夠把某：能夠把某 種語言的程序轉(zhuǎn)種語言的程序轉(zhuǎn) 換成另一種語言換成另一種語言 的程序，而后者的程序，而后者 與前者在邏輯上與前者在邏輯上 是等價(jià)的。是等價(jià)的。 功能功能工作結(jié)果工作結(jié)果實(shí)現(xiàn)技術(shù)上實(shí)現(xiàn)技術(shù)上 編譯編譯 程序程序 源程序的一源程序的一 個(gè)個(gè)轉(zhuǎn)換轉(zhuǎn)換系統(tǒng)系統(tǒng) 源程序的源程序的 目標(biāo)代碼目標(biāo)代碼 把中間代碼轉(zhuǎn)把中間代碼轉(zhuǎn) 換

4、成目標(biāo)程序換成目標(biāo)程序 解釋解釋 程序程序 源程序的一源程序的一 個(gè)個(gè)執(zhí)行執(zhí)行系統(tǒng)系統(tǒng) 源程序的源程序的 執(zhí)行結(jié)果執(zhí)行結(jié)果 執(zhí)行中間代碼執(zhí)行中間代碼 n簡單的說，編譯就是全文翻譯，全部翻譯完才執(zhí)行。簡單的說，編譯就是全文翻譯，全部翻譯完才執(zhí)行。 解釋就相當(dāng)于同聲翻譯，邊翻譯邊執(zhí)行。解釋就相當(dāng)于同聲翻譯，邊翻譯邊執(zhí)行。 解釋程序和編譯程序的區(qū)別 編譯程序的分類 n依據(jù)編譯程序的不同用途和側(cè)重，可分類為依據(jù)編譯程序的不同用途和側(cè)重，可分類為: 診斷型編譯程序診斷型編譯程序(Diagnostic Compiler ) 優(yōu)化型編譯程序優(yōu)化型編譯程序(Optimizing Compiler) 交叉型編譯

5、程序交叉型編譯程序(Cross Compiler) 可變目標(biāo)型編譯程序可變目標(biāo)型編譯程序(Retargetable Compiler) 編譯技術(shù)的發(fā)展 n在在1954年至年至1957年期間，年期間，IBM的的John Backus帶領(lǐng)的一個(gè)研究小組帶領(lǐng)的一個(gè)研究小組 對(duì)對(duì)FORTRAN語言及其編譯器的開發(fā)語言及其編譯器的開發(fā) 將算術(shù)公式翻譯成機(jī)器代碼。將算術(shù)公式翻譯成機(jī)器代碼。 nNoam Chomsky 開始了自然語言結(jié)構(gòu)的研究。他的發(fā)現(xiàn)最終使得編開始了自然語言結(jié)構(gòu)的研究。他的發(fā)現(xiàn)最終使得編 譯器結(jié)構(gòu)異常簡單譯器結(jié)構(gòu)異常簡單 n 70年代，有窮自動(dòng)機(jī)和形式語言的研究，促進(jìn)了編譯器的發(fā)展年代，

6、有窮自動(dòng)機(jī)和形式語言的研究，促進(jìn)了編譯器的發(fā)展 Steve Johnson為為Unix系統(tǒng)編寫了系統(tǒng)編寫了Yacc （yet another compiler- compiler）。）。 Mike Lesk為為Unix系統(tǒng)開發(fā)的系統(tǒng)開發(fā)的 Lex n至今已形成一套比較成熟、系統(tǒng)的理論與方法及開發(fā)環(huán)境，但并行編至今已形成一套比較成熟、系統(tǒng)的理論與方法及開發(fā)環(huán)境，但并行編 譯、嵌入式應(yīng)用的交叉編譯等仍在研究和發(fā)展中。譯、嵌入式應(yīng)用的交叉編譯等仍在研究和發(fā)展中。 內(nèi)容線索 什么叫編譯程序什么叫編譯程序 n編譯過程概述編譯過程概述 n編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu) n編譯程序的生成編譯程序的生成 n總結(jié)

7、總結(jié) 編譯過程概述 n掌握編譯過程的五個(gè)基本階段，是我們學(xué)習(xí)編譯原理課程掌握編譯過程的五個(gè)基本階段，是我們學(xué)習(xí)編譯原理課程 的基本內(nèi)容，把編譯的五個(gè)基本階段與英譯中的五個(gè)步驟的基本內(nèi)容，把編譯的五個(gè)基本階段與英譯中的五個(gè)步驟 相比較，有利于對(duì)編譯過程的理解：相比較，有利于對(duì)編譯過程的理解： 1. 識(shí)別出句子中的一個(gè)個(gè)單詞識(shí)別出句子中的一個(gè)個(gè)單詞 2. 分析句子的語法結(jié)構(gòu)分析句子的語法結(jié)構(gòu) 3. 初步翻譯句子的含意初步翻譯句子的含意 4. 譯文修飾譯文修飾 5. 寫出最后譯文寫出最后譯文 1. 詞法分析詞法分析 2. 語法分析語法分析 3. 語義分析中間代碼生成語義分析中間代碼生成 4. 優(yōu)化優(yōu)

8、化 5. 目標(biāo)代碼生成目標(biāo)代碼生成 英譯英譯編譯編譯 詞法分析 n詞法分析程序又稱掃描程序。詞法分析程序又稱掃描程序。 任務(wù)：讀源程序的字符流、識(shí)別單詞（也稱單詞符號(hào)，或簡稱符任務(wù)：讀源程序的字符流、識(shí)別單詞（也稱單詞符號(hào)，或簡稱符 號(hào)），如標(biāo)識(shí)符、整數(shù)、界限符等，并轉(zhuǎn)換成內(nèi)部形式。號(hào)），如標(biāo)識(shí)符、整數(shù)、界限符等，并轉(zhuǎn)換成內(nèi)部形式。 輸入：源程序中的字符流輸入：源程序中的字符流 輸出：等長的內(nèi)部形式，即屬性字。輸出：等長的內(nèi)部形式，即屬性字。 n在詞法分析階段工作所依循的是語言的詞法規(guī)則。在詞法分析階段工作所依循的是語言的詞法規(guī)則。 n描述詞法規(guī)則的有效工具是正規(guī)式和有限自動(dòng)機(jī)。描述詞法規(guī)則的

9、有效工具是正規(guī)式和有限自動(dòng)機(jī)。 n方法：狀態(tài)圖；方法：狀態(tài)圖；DFA；NFA 例：一個(gè)例：一個(gè)C C源程序片段：源程序片段： int a; a=a+2; 詞法分析后返回詞法分析后返回( (如右圖如右圖) )： 單詞類型單詞類型 單詞值單詞值 保留字保留字 int 標(biāo)識(shí)符標(biāo)識(shí)符 a 界符界符 ; 標(biāo)識(shí)符標(biāo)識(shí)符 a 算符算符(賦值賦值) = 標(biāo)識(shí)符標(biāo)識(shí)符 a 算符算符(加加) + 整數(shù)整數(shù) 2 界符界符 ； 詞法分析示例 語法分析 n語法分析程序又稱識(shí)別程序。語法分析程序又稱識(shí)別程序。 任務(wù)：讀入由詞法分析程序識(shí)別出的符號(hào)，根據(jù)給定語法規(guī)則，任務(wù)：讀入由詞法分析程序識(shí)別出的符號(hào)，根據(jù)給定語法規(guī)則，

10、 識(shí)別出各個(gè)語法單位（如：短語、子句、語句、程序段、程序）識(shí)別出各個(gè)語法單位（如：短語、子句、語句、程序段、程序）, 并生成另一種內(nèi)部表示。并生成另一種內(nèi)部表示。 輸入：由詞法分析程序識(shí)別出并轉(zhuǎn)換的符號(hào)輸入：由詞法分析程序識(shí)別出并轉(zhuǎn)換的符號(hào) 輸出：另一種內(nèi)部表示，如語法分析樹或其它中間表示。輸出：另一種內(nèi)部表示，如語法分析樹或其它中間表示。 n語法規(guī)則通常用上下文無關(guān)文法描述。語法規(guī)則通常用上下文無關(guān)文法描述。 n方法：遞歸子程序法、方法：遞歸子程序法、LR分析法、優(yōu)先分析法。分析法、優(yōu)先分析法。 n規(guī)則規(guī)則 :=“:=” :=“+” :=“*” :=“(”“)” := := := 例：例：i

11、d1:=id2+id3id1:=id2+id3* *1010 例：id1:=id2+id3*10 的語法樹 語義分析 n對(duì)語法分析樹或其他內(nèi)部中間表示進(jìn)行對(duì)語法分析樹或其他內(nèi)部中間表示進(jìn)行靜態(tài)語義靜態(tài)語義 檢查檢查，如果正確則進(jìn)行中間代碼的翻譯。，如果正確則進(jìn)行中間代碼的翻譯。 按照語法樹的層次關(guān)系和先后次序，逐個(gè)語句地進(jìn)行按照語法樹的層次關(guān)系和先后次序，逐個(gè)語句地進(jìn)行 語義處理。語義處理。 主要任務(wù)：主要任務(wù)： 進(jìn)行類型審查，審查每個(gè)算符是否符合語進(jìn)行類型審查，審查每個(gè)算符是否符合語 言規(guī)范，不符合時(shí)應(yīng)報(bào)告錯(cuò)誤。言規(guī)范，不符合時(shí)應(yīng)報(bào)告錯(cuò)誤。 n變量是否定義變量是否定義 n類型是否正確類型是否

12、正確 例例:Program p(); Var rate:real; procedure initial; position := initial + rate * 60 /* error */ /* error */ /* warning */; 語義分析示例 插入語義處理結(jié)點(diǎn)的語法樹 60 := + * Id1 position Id2 initial Id3 rate inttoreal 中間代碼 n中間代碼是一種獨(dú)立于具體硬件的記號(hào)系統(tǒng)，或者與現(xiàn)代中間代碼是一種獨(dú)立于具體硬件的記號(hào)系統(tǒng)，或者與現(xiàn)代 計(jì)算機(jī)的指令形式有某種程度的接近，或者能比較容易地計(jì)算機(jī)的指令形式有某種程度的接近，或者能

13、比較容易地 變換成機(jī)器指令。變換成機(jī)器指令。 任務(wù)：將各類語法單位，如任務(wù)：將各類語法單位，如“表達(dá)式表達(dá)式”、 “語句語句”、“程序程序”等等 翻譯為中間代碼序列。翻譯為中間代碼序列。 輸入：句子輸入：句子 輸出：中間代碼序列輸出：中間代碼序列 n中間代碼的形式：常見的有四元式、三元式和逆波蘭式等中間代碼的形式：常見的有四元式、三元式和逆波蘭式等 n方法：語義子程序；方法：語義子程序；DAG圖，語法制導(dǎo)翻譯圖，語法制導(dǎo)翻譯 n對(duì)于源程序?qū)τ谠闯绦騭um:= first + count * 10可以生成如下所示可以生成如下所示 的四元式：的四元式： （1） (inttoreal , 10 ,

14、, t1 ) （2） ( * , id3 , t1 , t2 ) （3） ( + , id2 , t2 , t3 ) （4） ( := , t3 , , id1 ) n 其中：其中：id1、id2、id3分別表示分別表示sum、first、count的機(jī)的機(jī) 器內(nèi)部表示，器內(nèi)部表示，t1、t2、t3是臨時(shí)生成的名字，表示中間運(yùn)是臨時(shí)生成的名字，表示中間運(yùn) 算結(jié)果。算結(jié)果。 t1，t2，t3是是 臨時(shí)變量臨時(shí)變量 id1id2id3 n四元式的形式為：四元式的形式為： （算符，運(yùn)算對(duì)象（算符，運(yùn)算對(duì)象1 1，運(yùn)算對(duì)象，運(yùn)算對(duì)象2 2，結(jié)果）；，結(jié)果）； 例例2：C語言的源程序語言的源程序a =

15、b*c + b*d 的三地址序列（賦值的三地址序列（賦值 語句形式的四元式）：語句形式的四元式）： (1) t1 := b*c (2) t2 := b*d (3) t3 := t1 + t2 (4) a := t3 例例3:源程序：源程序： if (a 四元式：四元式： 100（j=,a,b,102) 101 (j, _, _, 104) 102 (-, a, c, t1) 103 (=, t1, _, a) 104 (*, b, c, t2) 105 (=, t2, _, c) 優(yōu)化 n優(yōu)化的任務(wù)在于對(duì)前段產(chǎn)生的中間代碼進(jìn)行加工，優(yōu)化的任務(wù)在于對(duì)前段產(chǎn)生的中間代碼進(jìn)行加工， 把它變換成功能相

16、同，但功效更高的優(yōu)化了的中把它變換成功能相同，但功效更高的優(yōu)化了的中 間表示代碼，以期在最后階段產(chǎn)生更為高效（省間表示代碼，以期在最后階段產(chǎn)生更為高效（省 時(shí)間和空間）的代碼時(shí)間和空間）的代碼 n優(yōu)化所依循的原則是程序的等價(jià)變換規(guī)則優(yōu)化所依循的原則是程序的等價(jià)變換規(guī)則 n其方法有：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪其方法有：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪 除無用代碼等。除無用代碼等。 舉例： id1:= id2 + id3 * 60 (1)(inttoreal60-t1) (2)( * id3t1t2) (3)( +id2t2t3) (4)( :=t3-id1) 變換成變換成 （1） ( *i

17、d360.0t1) ( 2）（）（ + id2 t1id1) 目標(biāo)代碼生成 n這一階段的任務(wù)：把中這一階段的任務(wù)：把中 間代碼（或經(jīng)優(yōu)化處理間代碼（或經(jīng)優(yōu)化處理 后）變換成特定機(jī)器上后）變換成特定機(jī)器上 的低級(jí)語言代碼。它有的低級(jí)語言代碼。它有 賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī) 器指令含義。器指令含義。 與機(jī)器相關(guān)與機(jī)器相關(guān) (*,id360.0t1) (+,id2t1id1) movfid3 R2 mulf#60.0 R2 movfid2 R1 addfR2 R1 movfR1 id1 內(nèi)容線索 什么叫編譯程序什么叫編譯程序 編譯過程概述編譯過程概述 n編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)

18、n編譯程序的生成編譯程序的生成 n總結(jié)總結(jié) 表表 格格 管管 理理 詞法分析器詞法分析器 語法分析器語法分析器 語義分析與中間代碼產(chǎn)生語義分析與中間代碼產(chǎn)生 優(yōu)化器優(yōu)化器 目標(biāo)代碼生成器目標(biāo)代碼生成器 源程序源程序 單詞符號(hào)單詞符號(hào) 語法單位語法單位 中間代碼中間代碼 中間代碼中間代碼 目標(biāo)代碼目標(biāo)代碼 出出 錯(cuò)錯(cuò) 處處 理理 編譯程序的結(jié)構(gòu) 符號(hào)名表符號(hào)名表 常量名、變量名、數(shù)組 名、過程名、 性質(zhì)、 引用、定義 常數(shù)表常數(shù)表 標(biāo)號(hào)表標(biāo)號(hào)表 入口名表入口名表 過程引用表過程引用表 各種類型常數(shù)的值 標(biāo)號(hào)的定義和引用情況 過程的入口名和入口位置 外部過程的名字、引用位置 循環(huán)表循環(huán)表 等價(jià)名表

19、等價(jià)名表 公用鏈表公用鏈表 格式表格式表 中間代碼表中間代碼表 表格與表格管理 n編譯程序涉及的表格有編譯程序涉及的表格有 名名 字字 種種 類類類類 型型層層 次次偏移量偏移量 mm過過 程程 0 0 a a變變 量量 real real1 1d d b b變變 量量 real real1 1d+4d+4 c c變變 量量 real real1 1d+8d+8 n在編譯程序使用的表格中最重要的是符號(hào)表。在編譯程序使用的表格中最重要的是符號(hào)表。 記錄源程序中使用的名字記錄源程序中使用的名字(標(biāo)識(shí)符標(biāo)識(shí)符) 收集每個(gè)名字的各種屬性信息收集每個(gè)名字的各種屬性信息 n類型、作用域、分配存儲(chǔ)信息類型、

20、作用域、分配存儲(chǔ)信息 符號(hào)表 出錯(cuò)處理 n程序中的錯(cuò)誤可分為語法錯(cuò)誤和語義錯(cuò)誤兩類。程序中的錯(cuò)誤可分為語法錯(cuò)誤和語義錯(cuò)誤兩類。 n語法錯(cuò)誤可在詞法分析和語法分析階段查出來。語法錯(cuò)誤可在詞法分析和語法分析階段查出來。 n例如，下列錯(cuò)誤都屬于語法錯(cuò)誤：例如，下列錯(cuò)誤都屬于語法錯(cuò)誤： （1）缺少分隔符號(hào)：）缺少分隔符號(hào)：DIMENSION A(10) B(10) （2）保留字拼寫錯(cuò)誤：）保留字拼寫錯(cuò)誤：DEMENSION A(10) （3）括號(hào)不配對(duì)：）括號(hào)不配對(duì)： WRITE（6,10)（A（1，J），），J1，10），），I1，10） 此外還有多余分隔符號(hào)，無循環(huán)終結(jié)語句等等。此外還有多余分隔符

21、號(hào)，無循環(huán)終結(jié)語句等等。 語義錯(cuò)誤 n語義錯(cuò)誤有些可在語義錯(cuò)誤有些可在編譯時(shí)編譯時(shí)查出來，有些則需在查出來，有些則需在運(yùn)行時(shí)運(yùn)行時(shí)才能才能 查出來。查出來。 n典型的語義錯(cuò)誤：典型的語義錯(cuò)誤： 標(biāo)識(shí)符沒有說明就使用；標(biāo)識(shí)符沒有說明就使用； 標(biāo)號(hào)有引用而無定義；標(biāo)號(hào)有引用而無定義； 形式參數(shù)和實(shí)在參數(shù)結(jié)合時(shí)在類型、個(gè)數(shù)、位置等方面不一致等形式參數(shù)和實(shí)在參數(shù)結(jié)合時(shí)在類型、個(gè)數(shù)、位置等方面不一致等 等，等， n這些錯(cuò)誤可在編譯時(shí)查出來，而另一些錯(cuò)誤如下標(biāo)越界、這些錯(cuò)誤可在編譯時(shí)查出來，而另一些錯(cuò)誤如下標(biāo)越界、 運(yùn)算溢出、調(diào)用某些標(biāo)準(zhǔn)函數(shù)時(shí)自變量的值不符合要求等，運(yùn)算溢出、調(diào)用某些標(biāo)準(zhǔn)函數(shù)時(shí)自變量的值

22、不符合要求等， 則需要到程序運(yùn)行時(shí)才能查出來。則需要到程序運(yùn)行時(shí)才能查出來。 一個(gè)好的編譯程序應(yīng)該：一個(gè)好的編譯程序應(yīng)該： 全全 最大限度發(fā)現(xiàn)錯(cuò)誤最大限度發(fā)現(xiàn)錯(cuò)誤 準(zhǔn)準(zhǔn) 準(zhǔn)確指出錯(cuò)誤的性質(zhì)和發(fā)生地點(diǎn)準(zhǔn)確指出錯(cuò)誤的性質(zhì)和發(fā)生地點(diǎn) 局部化局部化 將錯(cuò)誤的影響限制在盡可能小的范圍內(nèi)將錯(cuò)誤的影響限制在盡可能小的范圍內(nèi) 若能若能自動(dòng)校正錯(cuò)誤自動(dòng)校正錯(cuò)誤則更好，但其則更好，但其代價(jià)非常高代價(jià)非常高 編譯階段的組合 n編譯程序可以從邏輯上分成幾個(gè)階段，對(duì)于各個(gè)階段的劃分僅僅是指編譯程序可以從邏輯上分成幾個(gè)階段，對(duì)于各個(gè)階段的劃分僅僅是指 其邏輯結(jié)構(gòu)，而在具體實(shí)現(xiàn)時(shí)，經(jīng)常是將幾個(gè)階段組合在一起。例如，其邏輯結(jié)

23、構(gòu)，而在具體實(shí)現(xiàn)時(shí)，經(jīng)常是將幾個(gè)階段組合在一起。例如， 可以將各部分組合成前端和后端。可以將各部分組合成前端和后端。 編譯過程 前端：詞法分析、語法分析、語義分析、 中間代碼生成、優(yōu)化工作。 后端：目標(biāo)代碼生成、出錯(cuò)處理、符號(hào)表 操作。 主要與源語 言有關(guān) 主要與目標(biāo) 代碼有關(guān) 遍（遍（Pass） n對(duì)源程序或源程序的中間結(jié)對(duì)源程序或源程序的中間結(jié) 果從頭到尾掃描一次，并做果從頭到尾掃描一次，并做 相關(guān)處理，生成新的中間結(jié)相關(guān)處理，生成新的中間結(jié) 果或目標(biāo)程序的過程。果或目標(biāo)程序的過程。 n“遍遍”是處理數(shù)據(jù)的一個(gè)完是處理數(shù)據(jù)的一個(gè)完 整周期，每遍工作從外存上整周期，每遍工作從外存上 獲得前一

24、遍的中間結(jié)果（源獲得前一遍的中間結(jié)果（源 程序），完成它所含的有關(guān)程序），完成它所含的有關(guān) 工作之后，再把結(jié)果記錄于工作之后，再把結(jié)果記錄于 外存。外存。 詞法分析詞法分析 語法分析語法分析 中間代碼生成中間代碼生成 代碼優(yōu)化代碼優(yōu)化 目標(biāo)代碼生成目標(biāo)代碼生成 一遍一遍 語法分析器語法分析器 處于核心地位處于核心地位 一遍一遍 局部優(yōu)化局部優(yōu)化 一遍一遍 一遍一遍 全局優(yōu)化全局優(yōu)化 遍的次數(shù)和效果 n一個(gè)編譯程序可由一遍、兩遍或多遍完成。每一一個(gè)編譯程序可由一遍、兩遍或多遍完成。每一 遍可完成不同的階段或多個(gè)階段的工作。遍可完成不同的階段或多個(gè)階段的工作。 從時(shí)間從時(shí)間 和空間和空間 角度看角

25、度看 多遍編譯多遍編譯 少占內(nèi)存，多耗時(shí)間少占內(nèi)存，多耗時(shí)間 一遍編譯一遍編譯 多占內(nèi)存，少耗時(shí)間多占內(nèi)存，少耗時(shí)間 內(nèi)容線索 什么叫編譯程序什么叫編譯程序 編譯過程概述編譯過程概述 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu) n編譯程序的生成編譯程序的生成 n總結(jié)總結(jié) 編譯程序?qū)崿F(xiàn)語言 n機(jī)器語言機(jī)器語言 n匯編語言匯編語言 充分發(fā)揮各種不同硬件系統(tǒng)的效率充分發(fā)揮各種不同硬件系統(tǒng)的效率 滿足各種不同的具體要求滿足各種不同的具體要求 n高級(jí)語言高級(jí)語言 大大節(jié)省程序設(shè)計(jì)的時(shí)間大大節(jié)省程序設(shè)計(jì)的時(shí)間 構(gòu)造出來的編譯程序易于閱讀、維護(hù)和移植構(gòu)造出來的編譯程序易于閱讀、維護(hù)和移植 T形圖 n其中：其中： S:源語

26、言源語言(程序程序)，Source language(program) T:目標(biāo)語言目標(biāo)語言(程序程序), target/objectlanguage(program) I:實(shí)現(xiàn)語言實(shí)現(xiàn)語言, implementation language ST I 示例 L2A L1 L2A AL1 A A A A機(jī)器上已有一個(gè)用機(jī)器上已有一個(gè)用A A 機(jī)器碼機(jī)器碼實(shí)現(xiàn)的某高級(jí)實(shí)現(xiàn)的某高級(jí) 語言語言L1L1的編譯程序的編譯程序 用用L L1 1語言語言編寫另編寫另 一種高級(jí)語言一種高級(jí)語言L L2 2 的編譯程序的編譯程序 A A機(jī)器代碼機(jī)器代碼實(shí)現(xiàn)實(shí)現(xiàn) 的的L L2 2編譯程序編譯程序 編譯程序的生成技術(shù)

27、 n自編譯自編譯 n交叉編譯交叉編譯 n自展自展 n移植移植 自編譯 n用某種高級(jí)語言書寫自己的編譯程序稱為自編譯。用某種高級(jí)語言書寫自己的編譯程序稱為自編譯。 n例如例如,假定假定A機(jī)器上已有一個(gè)機(jī)器上已有一個(gè)PASCAL語言編譯程序語言編譯程序, 則可則可 用用PASCAL語言編寫一個(gè)功能更強(qiáng)的語言編寫一個(gè)功能更強(qiáng)的PASCAL語言編譯語言編譯 程序，然后借助于原有的編譯程序?qū)π戮帉懙某绦颍缓蠼柚谠械木幾g程序?qū)π戮帉懙腜ASCAL編編 譯程序進(jìn)行編譯譯程序進(jìn)行編譯, 從而得到一個(gè)能在從而得到一個(gè)能在A機(jī)器上運(yùn)行的功能機(jī)器上運(yùn)行的功能 更強(qiáng)的更強(qiáng)的PASCAL編譯程序。編譯程序。 交叉

28、編譯 n用用x機(jī)器上的編譯程序產(chǎn)生可在機(jī)器上的編譯程序產(chǎn)生可在 y 機(jī)器上運(yùn)行的目標(biāo)代碼機(jī)器上運(yùn)行的目標(biāo)代碼 稱為交叉編譯。稱為交叉編譯。 n 例如例如, 若若x機(jī)器上已有機(jī)器上已有C語言編譯程序語言編譯程序,則可用則可用x機(jī)器中的機(jī)器中的 C語言書寫一個(gè)編譯程序語言書寫一個(gè)編譯程序, 該編譯程序的源程序是該編譯程序的源程序是C語言程語言程 序序,而產(chǎn)生的目標(biāo)程序則是基于而產(chǎn)生的目標(biāo)程序則是基于y機(jī)器的機(jī)器的, 即產(chǎn)生在即產(chǎn)生在y機(jī)器上機(jī)器上 執(zhí)行的低級(jí)語言程序。執(zhí)行的低級(jí)語言程序。 n 上述兩種方法假定已有一個(gè)編譯程序上述兩種方法假定已有一個(gè)編譯程序, 若沒有若沒有, 則可采用則可采用 自展

29、或移植法。自展或移植法。 自展 n首先確定一個(gè)非常簡單的核心語言首先確定一個(gè)非常簡單的核心語言L0，然后用機(jī)器語言或，然后用機(jī)器語言或 匯編語言書寫出其編譯程序匯編語言書寫出其編譯程序T0； n到到L1，L0 L1，并用，并用L0編寫編寫L1的編譯程序的編譯程序T1(自編譯自編譯)； n然后再把語言然后再把語言L1擴(kuò)充為擴(kuò)充為L2，L1 L2，并用，并用L1編寫編寫L2的編的編 譯程序譯程序T2； 這樣不斷擴(kuò)展，直到完成所要求的編譯程序?yàn)橹?。這樣不斷擴(kuò)展，直到完成所要求的編譯程序?yàn)橹埂?移植 n移植是指移植是指A機(jī)器上的某種高級(jí)語言的編譯程序稍機(jī)器上的某種高級(jí)語言的編譯程序稍 加改動(dòng)后能在加改動(dòng)后能在B機(jī)器上運(yùn)行。機(jī)器上運(yùn)行。 n一個(gè)程序若能較易地從一個(gè)程序若能較易地從A機(jī)移到機(jī)移到B機(jī)上運(yùn)行機(jī)上運(yùn)行, 則稱則稱 該程序可移植。該程序可移植。 自動(dòng)編譯 n自動(dòng)生成編譯程序的軟件工具自動(dòng)生成編譯程序的軟件工具, 只要把源程序的定義及機(jī)只要把源程序的定義及機(jī) 器語言的描述輸入到該軟件中器語言的描述輸入到該軟