編譯原理第1章

1、編譯原理(第3版）2 編譯原理這門課程主要介紹編譯原理這門課程主要介紹設(shè)計設(shè)計和構(gòu)造和構(gòu)造編譯程序編譯程序的基本原理和常用的的基本原理和常用的技術(shù)和方法技術(shù)和方法。本章重點介紹編譯程序的本章重點介紹編譯程序的基本概念基本概念。3 翻譯程序是指這樣一個程序翻譯程序是指這樣一個程序, ,它把它把一種語言一種語言( (稱作源語言稱作源語言) )所寫的程序所寫的程序( (源源程序程序) )翻譯成等價的另一種語言翻譯成等價的另一種語言( (稱作稱作目標(biāo)語言目標(biāo)語言) )的程序的程序( (目標(biāo)程序目標(biāo)程序) )。 高級語言程序機(jī)器語言程序翻譯程序#include int main(void) printf

2、(hello, worldn); return 0; 00 00 10 10.4 編譯程序編譯程序是一種是一種翻譯程序翻譯程序，它將，它將高級語言高級語言所寫的所寫的源程序源程序翻譯成翻譯成等價的等價的機(jī)器語言機(jī)器語言或或匯編語言匯編語言的的目標(biāo)程序目標(biāo)程序。 源程序源程序高級語言程序高級語言程序編譯程序編譯程序目標(biāo)程序目標(biāo)程序匯編語言或者匯編語言或者機(jī)器語言程序機(jī)器語言程序5 采用編譯方式在計算機(jī)上執(zhí)行用高級采用編譯方式在計算機(jī)上執(zhí)行用高級語言編寫的程序，需分階段進(jìn)行。語言編寫的程序，需分階段進(jìn)行。第一種情況：第一種情況：源程序源程序編編譯譯程程序序機(jī)器語言機(jī)器語言目標(biāo)程序目標(biāo)程序初始數(shù)據(jù)初

3、始數(shù)據(jù)運(yùn)行系統(tǒng)運(yùn)行系統(tǒng)結(jié)果結(jié)果編編 譯譯 階階 段段運(yùn)運(yùn) 行行 階階 段段高級語言高級語言 程序程序6第二種情況：第二種情況：源程序源程序編編譯譯程程序序機(jī)器機(jī)器語言語言目標(biāo)目標(biāo)程序程序初始數(shù)據(jù)初始數(shù)據(jù)運(yùn)行系統(tǒng)運(yùn)行系統(tǒng)結(jié)果結(jié)果編編 譯譯 階階 段段運(yùn)行階段運(yùn)行階段匯匯編編程程序序匯編匯編語言語言目標(biāo)目標(biāo)程序程序匯匯 編編 階階 段段高級語言高級語言 程序程序7 將英文句子將英文句子 “I wish you success ”翻譯成中文句子的大致過程是：翻譯成中文句子的大致過程是：q 詞法分析詞法分析q 語法分析語法分析q 語義分析語義分析q 修飾工作修飾工作q 翻譯成文翻譯成文 8 編譯程序是

4、將一種語言形式翻譯成編譯程序是將一種語言形式翻譯成另一種語言形式，因此，其工作過程一另一種語言形式，因此，其工作過程一般可劃分為如下五個階段：般可劃分為如下五個階段： q 詞法分析詞法分析 q 語法分析語法分析 q 語義分析和中間代碼生成語義分析和中間代碼生成 q 代碼優(yōu)化代碼優(yōu)化 q 目標(biāo)代碼生成目標(biāo)代碼生成9 float r，h，s； s = 2* *3.1416 * * r * *(rh);例如例如 計算圓柱體表面積的程序計算圓柱體表面積的程序 片斷如下：片斷如下：10 詞法分析階段的任務(wù)是對構(gòu)成詞法分析階段的任務(wù)是對構(gòu)成源程序的源程序的字符串字符串從左到右進(jìn)行掃描從左到右進(jìn)行掃描和分解

5、，根據(jù)語言的和分解，根據(jù)語言的詞法規(guī)則詞法規(guī)則，識，識別出一個一個具有獨(dú)立意義的別出一個一個具有獨(dú)立意義的單詞單詞( 也稱也稱單詞符號單詞符號, 簡稱簡稱符號符號 )。1. 11 詞法規(guī)則詞法規(guī)則是單詞符號的形成規(guī)則是單詞符號的形成規(guī)則, ,它規(guī)定了哪樣的字符串構(gòu)成一個單詞它規(guī)定了哪樣的字符串構(gòu)成一個單詞符號。符號。 float r float r，h h，s s； s = 2s = 2* *3.14163.1416* *r r* *(h(hr)r)；例如例如12 上述源程序通過詞法分析識別出上述源程序通過詞法分析識別出如下單詞符號：如下單詞符號： 基本字基本字 float 標(biāo)識符標(biāo)識符 r、

6、h、s 常數(shù)常數(shù) 3.1416、2 算符算符 * * 、 界符界符 （、（、 ）、）、 ；、；、 ，、，、= 13 語法分析的任務(wù)是在詞法分析的基語法分析的任務(wù)是在詞法分析的基 礎(chǔ)上礎(chǔ)上, 根據(jù)語言的根據(jù)語言的語法規(guī)則語法規(guī)則從從單詞符單詞符 號串號串中識別出各種中識別出各種語法單位語法單位 ( 如表如表 達(dá)式、說明、語句等達(dá)式、說明、語句等 ) , ,并進(jìn)行并進(jìn)行語法語法 檢查檢查, ,即檢查各種語法單位在語法結(jié)即檢查各種語法單位在語法結(jié) 構(gòu)上的正確性。構(gòu)上的正確性。 14 語言的語言的語法規(guī)則語法規(guī)則規(guī)定了如何從單規(guī)定了如何從單詞符號形成語法單位，詞符號形成語法單位，語法規(guī)則語法規(guī)則是語是

7、語法單位的形成規(guī)則。法單位的形成規(guī)則。 float r float r，h h，s s； s = 2s = 2* *3.14163.1416* *r r* *(h(hr)r)；例如例如15 單詞符號串單詞符號串 s=2* *3.1416 * * r * *(hr)中，中，“s” 是是，單詞符號串，單詞符號串 “2 * * 3.1416 * * r * *(hr)”組合成組合成這樣的語法單位這樣的語法單位 , 由由=構(gòu)成構(gòu)成這這樣的語法單位。樣的語法單位。16 語義分析語義分析的任務(wù)是首先對每種語的任務(wù)是首先對每種語法單位進(jìn)行靜態(tài)的語義審查，然后分法單位進(jìn)行靜態(tài)的語義審查，然后分析其含義析其含義

8、，并用另一種語言形式并用另一種語言形式 (比比源語言更接近于目標(biāo)語言的一種中間源語言更接近于目標(biāo)語言的一種中間代碼或直接用目標(biāo)語言代碼或直接用目標(biāo)語言 ) 來描述這種來描述這種語義。語義。17 將將s = 2* *3.1416 * * r * *(hr)翻譯成如下翻譯成如下形式的四元式中間代碼：形式的四元式中間代碼：(1) ( * *, 2, 3.1416, T1 ) (2) ( * *, T1, r, T2 )(3) ( +, h, r, T3 )(4) ( * *, T2, T3, T4 )(5) ( =, T4, _, s )18 代碼優(yōu)化的任務(wù)是對前階段產(chǎn)生的代碼優(yōu)化的任務(wù)是對前階段產(chǎn)

9、生的中間代碼進(jìn)行中間代碼進(jìn)行等價變換或改造等價變換或改造，以期獲得，以期獲得更為更為高效即省時間和空間的目標(biāo)代碼高效即省時間和空間的目標(biāo)代碼。優(yōu)。優(yōu)化主要包括局部優(yōu)化和循環(huán)優(yōu)化等，例如化主要包括局部優(yōu)化和循環(huán)優(yōu)化等，例如上述四元式經(jīng)局部優(yōu)化后得：上述四元式經(jīng)局部優(yōu)化后得： (1) ( * *, 6.28, r, T2 )(2) ( +, h, r, T3 )(3) ( * *, T2, T3, T4 )(4) ( =, T4, _, s )19 目標(biāo)代碼生成的任務(wù)是將中間目標(biāo)代碼生成的任務(wù)是將中間代碼變換成特定機(jī)器上的絕對指令代碼變換成特定機(jī)器上的絕對指令代碼或可重定位的指令代碼或匯編代碼或可

10、重定位的指令代碼或匯編指令代碼。指令代碼。 20表格管理和錯誤處理表格管理和錯誤處理 編譯程序在工作過程中需要建立一編譯程序在工作過程中需要建立一些表格，以登記源程序中所提供的或在些表格，以登記源程序中所提供的或在編譯過程中所產(chǎn)生的一些信息，編譯各編譯過程中所產(chǎn)生的一些信息，編譯各個階段的工作都涉及到個階段的工作都涉及到構(gòu)造、查找、修構(gòu)造、查找、修改或存取有關(guān)表格中的信息改或存取有關(guān)表格中的信息，因此，在，因此，在編譯程序中必須有一組管理各種表格的編譯程序中必須有一組管理各種表格的程序。程序。 在編譯程序的各個階段中，都要涉及在編譯程序的各個階段中，都要涉及表格管理和錯誤處理表格管理和錯誤處理

11、。21表格管理和錯誤處理表格管理和錯誤處理 一個好的編譯程序在編譯過程中，一個好的編譯程序在編譯過程中，應(yīng)具有應(yīng)具有廣泛的程序查錯能力廣泛的程序查錯能力，并能準(zhǔn)確，并能準(zhǔn)確地報告錯誤的種類及出錯位置，以便用地報告錯誤的種類及出錯位置，以便用戶查找和糾正，因此，在編譯程序中還戶查找和糾正，因此，在編譯程序中還必須有一個出錯處理程序。必須有一個出錯處理程序。 22編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu) 源程序源程序語義分析和中間代碼生成程序語義分析和中間代碼生成程序語法分析程序語法分析程序詞法分析程序詞法分析程序代碼優(yōu)化程序代碼優(yōu)化程序目標(biāo)代碼生成程序目標(biāo)代碼生成程序 目標(biāo)程序目標(biāo)程序表表格格管管理理程程序

12、序出出錯錯處處理理程程序序( 字符串字符串)231.3 編譯程序的生成方法編譯程序的生成方法q 對源語言和目標(biāo)語言認(rèn)真分析對源語言和目標(biāo)語言認(rèn)真分析q 設(shè)計編譯算法設(shè)計編譯算法q 選擇語言編制程序選擇語言編制程序q 調(diào)試編譯程序調(diào)試編譯程序q 提交相關(guān)文檔資料提交相關(guān)文檔資料 編譯程序是一個復(fù)雜的系統(tǒng)程序，要編譯程序是一個復(fù)雜的系統(tǒng)程序，要生成一個編譯程序一般要考慮以下幾方面：生成一個編譯程序一般要考慮以下幾方面：24編譯程序的自動生成編譯程序的自動生成 如目前已廣為使用詞法分析程序的自如目前已廣為使用詞法分析程序的自動生成系統(tǒng)動生成系統(tǒng)LEX和語法分析程序自動生成和語法分析程序自動生成系統(tǒng)系

13、統(tǒng)YACC等，此外等，此外, 還有可用來自動產(chǎn)還有可用來自動產(chǎn)生整個編譯程序的軟件工具：編譯程序產(chǎn)生整個編譯程序的軟件工具：編譯程序產(chǎn)生器生器, 它的功能是將任一語言的詞法規(guī)則、它的功能是將任一語言的詞法規(guī)則、語法規(guī)則和語義解釋的描述作為輸入，自語法規(guī)則和語義解釋的描述作為輸入，自動生成該語言的編譯程序。動生成該語言的編譯程序。 隨著編譯技術(shù)和自動機(jī)理論的發(fā)展隨著編譯技術(shù)和自動機(jī)理論的發(fā)展, 近近年來已研制出了一些編譯程序的年來已研制出了一些編譯程序的自動生成自動生成系統(tǒng)系統(tǒng)。25編譯程序的自動生成編譯程序的自動生成 生成編譯程序的方法還常采用生成編譯程序的方法還常采用自編譯自編譯方式方式和移

14、植方式和移植方式。 隨著并行技術(shù)和并行語言的發(fā)展，處隨著并行技術(shù)和并行語言的發(fā)展，處理并行語言的并行編譯技術(shù)和將串行程序理并行語言的并行編譯技術(shù)和將串行程序轉(zhuǎn)換成并行程序的轉(zhuǎn)換成并行程序的自動并行編譯技術(shù)自動并行編譯技術(shù)正在正在深入研究之中。深入研究之中。261.4 編譯技術(shù)在軟件開發(fā)中的應(yīng)用編譯技術(shù)在軟件開發(fā)中的應(yīng)用 雖然我們只有少數(shù)人從事構(gòu)造或雖然我們只有少數(shù)人從事構(gòu)造或維護(hù)程序語言編譯程序的工作維護(hù)程序語言編譯程序的工作, ,但是，但是，大部分系統(tǒng)軟件和應(yīng)用軟件的開發(fā)，大部分系統(tǒng)軟件和應(yīng)用軟件的開發(fā)，通常要用到編譯的原理和技術(shù)。通常要用到編譯的原理和技術(shù)。271.4 編譯技術(shù)在軟件開發(fā)中

15、的應(yīng)用編譯技術(shù)在軟件開發(fā)中的應(yīng)用 例如例如, ,設(shè)計詞法分析器的串匹配設(shè)計詞法分析器的串匹配技術(shù)已用于技術(shù)已用于正文編輯器、信息檢索正文編輯器、信息檢索系統(tǒng)和模式識別程序；系統(tǒng)和模式識別程序；上下文無關(guān)上下文無關(guān)文法和語法制導(dǎo)定義已用于創(chuàng)建諸文法和語法制導(dǎo)定義已用于創(chuàng)建諸如如排版、繪圖系統(tǒng)排版、繪圖系統(tǒng)和語言結(jié)構(gòu)化編和語言結(jié)構(gòu)化編輯器中，代碼優(yōu)化技術(shù)已用于輯器中，代碼優(yōu)化技術(shù)已用于程序程序驗證器驗證器和和從非結(jié)構(gòu)化的程序產(chǎn)生結(jié)從非結(jié)構(gòu)化的程序產(chǎn)生結(jié)構(gòu)化程序構(gòu)化程序的編程之中。的編程之中。 28q 編譯過程的五個階段編譯過程的五個階段q 編譯程序的結(jié)構(gòu)框圖編譯程序的結(jié)構(gòu)框圖編譯程序編譯程序是一種翻譯程序，它將高是一種翻譯程序，它將高級語言所寫的源程序級語言所寫的源程