《編譯原理課程教案》第1章：編譯原理概述課件

1、編譯原理實(shí)踐及應(yīng)用編譯原理實(shí)踐及應(yīng)用編譯原理實(shí)踐及應(yīng)用 -中南大學(xué) 肖健宇編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第2頁(yè)教材及主要參考資料教材及主要參考資料 教材：編譯原理實(shí)踐及應(yīng)用，黃賢英，清華大學(xué)出版社 主要參考資料： (1) 編譯原理，陳火旺，國(guó)防工業(yè)出版社 (2)程序設(shè)計(jì)語(yǔ)言編譯方法，肖軍模，大連理工大學(xué)出版社 (3)編譯原理，張素琴，呂映芝，清華大學(xué)出版社 (4)編譯原理，alfred V.Aho等著，李建中等譯，人民郵電出版社編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第3頁(yè)序序 言言 編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第4頁(yè)C語(yǔ)言程序void main( ) int x,

2、y,z; x=3; y=2; z=x+y;什么是編譯？什么是編譯？從程序員可以理解的高級(jí)語(yǔ)言高級(jí)語(yǔ)言程序到機(jī)器可以理解的機(jī)器語(yǔ)言機(jī)器語(yǔ)言程序的自動(dòng)翻譯自動(dòng)翻譯過(guò)程。編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第5頁(yè)匯編語(yǔ)言程序mov ax,3mov x,axmov ax,2mov y,axmov ax,xmov bx,yadd ax,bxmov z,ax.300302304306308內(nèi)存地址 內(nèi)存內(nèi)容單元名字200H3x：局部變量201H2y：局部變量202H5z：局部變量機(jī)器碼編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第6頁(yè)為什么要學(xué)習(xí)編譯原理？為什么要學(xué)習(xí)編譯原理？ 1、有助于深刻理解和正

3、確使用程序設(shè)計(jì)語(yǔ)言，加深對(duì)高級(jí)語(yǔ)言程序執(zhí)行過(guò)程的理解 2、有助于加深對(duì)整個(gè)計(jì)算機(jī)系統(tǒng)的理解。 3、設(shè)計(jì)開(kāi)發(fā)編譯程序的軟件技術(shù)同樣可以用于其他軟件的設(shè)計(jì)開(kāi)發(fā)。 4、隨著微處理器技術(shù)的飛速發(fā)展，處理器性能在很大程度上取決于編譯器的質(zhì)量、編譯技術(shù)成為計(jì)算機(jī)的核心技術(shù)，地位變得越來(lái)越重要。 編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第7頁(yè)編譯原理編譯原理課程在計(jì)算機(jī)科學(xué)中課程在計(jì)算機(jī)科學(xué)中的重要地位的重要地位 (1) 學(xué)習(xí)編程最初是學(xué)習(xí)一門(mén)高級(jí)語(yǔ)言高級(jí)語(yǔ)言，C或Pascal，掌握編寫(xiě)一些簡(jiǎn)單程序的方法； (2) 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)，建立“算法”的概念，對(duì)編程有更深入的理解。遇到問(wèn)題的時(shí)候，能夠?qū)ふ蚁?/p>

4、應(yīng)的數(shù)據(jù)結(jié)構(gòu)模型，設(shè)計(jì)適當(dāng)?shù)乃惴▉?lái)解決問(wèn)題； (3) 學(xué)習(xí)匯編語(yǔ)言匯編語(yǔ)言，這門(mén)課程是我們真正深入了解計(jì)算機(jī)內(nèi)部工作的第一門(mén)課程。通過(guò)學(xué)習(xí)了解匯編語(yǔ)言如何變?yōu)闄C(jī)器語(yǔ)言，如何對(duì)應(yīng)于一條指令； (4) 計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理課程的學(xué)習(xí)使我們了解到計(jì)算機(jī)的硬件組成，以及機(jī)器指令程序如何在計(jì)算機(jī)中運(yùn)行的過(guò)程。 (5) 編譯原理編譯原理課程幫助我們了解高級(jí)語(yǔ)言程序轉(zhuǎn)換成機(jī)器指令程序的過(guò)程?？梢詭椭覀兏羁痰乩斫飧呒?jí)語(yǔ)言程序運(yùn)行的內(nèi)部機(jī)制。編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第8頁(yè)編譯原理編譯原理課程在計(jì)算機(jī)科學(xué)中課程在計(jì)算機(jī)科學(xué)中的地位的地位高級(jí)語(yǔ)言程序設(shè)計(jì)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)編譯原理操作系統(tǒng)

5、系統(tǒng)軟件應(yīng)用軟件軟件工程信息系統(tǒng)電子商務(wù)匯編語(yǔ)言計(jì)算機(jī)組成原理編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第9頁(yè)學(xué)習(xí)本課程的目的和任務(wù)學(xué)習(xí)本課程的目的和任務(wù) 加深對(duì)編程語(yǔ)言設(shè)計(jì)和實(shí)現(xiàn)的理解，對(duì)和編程語(yǔ)言有關(guān)的理論有所了解，對(duì)宏觀上把握編程語(yǔ)言來(lái)說(shuō)，起一個(gè)奠基的作用，提升自身的編程能力 掌握編譯程序的基本結(jié)構(gòu)，掌握常用的編譯技術(shù)和方法，將編譯原理的理論和方法應(yīng)用于一般的軟件設(shè)計(jì)中 培養(yǎng)團(tuán)隊(duì)協(xié)作能力編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第10頁(yè)本課程的特點(diǎn)本課程的特點(diǎn) (1) 本課程理論性很強(qiáng)，學(xué)習(xí)時(shí)需要很強(qiáng)的邏輯思維能力 (2) 涉及的算法復(fù)雜，要深入地理解這些算法很困難 (3) 編譯原理課程

6、各個(gè)部分之間的獨(dú)立性很強(qiáng)，包括詞法分析、語(yǔ)法分析、存儲(chǔ)的組織與分配、中間語(yǔ)言、語(yǔ)法制導(dǎo)翻譯、代碼生成與優(yōu)化這幾大部分。詞法分析、及語(yǔ)義分析是重點(diǎn)；其他部分相對(duì)來(lái)說(shuō)知識(shí)性更強(qiáng)一些。編譯原理實(shí)踐及應(yīng)用引引 論論第一章第一章 編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第12頁(yè)本章要求本章要求 主要內(nèi)容主要內(nèi)容：各種翻譯程序的概念，編譯各種翻譯程序的概念，編譯過(guò)程和階段劃分，編譯程序的組成和結(jié)過(guò)程和階段劃分，編譯程序的組成和結(jié)構(gòu)，編譯程序的構(gòu)造方法構(gòu)，編譯程序的構(gòu)造方法 重點(diǎn)掌握：重點(diǎn)掌握：編譯程序工作的基本過(guò)程及編譯程序工作的基本過(guò)程及其各階段的基本任務(wù)，編譯程序總框。其各階段的基本任務(wù)，編譯程序總

7、框。編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第13頁(yè) 問(wèn)題：?jiǎn)栴}： 1. 什么是編譯程序？ 2. 編譯程序的工作過(guò)程是什么樣的？ 3. 編譯程序的總體結(jié)構(gòu)是什么樣的？ 4. 什么叫編譯前端、編譯后端？ 5. 什么叫“遍”（pass）？ 6. 編譯程序有哪些生成方法？編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第14頁(yè)v編譯程序（編譯程序（Compiler）v功能功能編譯程序編譯程序源程序源程序目標(biāo)程序目標(biāo)程序計(jì)算機(jī)運(yùn)行計(jì)算機(jī)運(yùn)行輸入數(shù)據(jù)輸入數(shù)據(jù)結(jié)果結(jié)果1.1 編譯程序是什么編譯程序是什么編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第15頁(yè)計(jì)算機(jī)中的語(yǔ)言層次和轉(zhuǎn)換關(guān)系計(jì)算機(jī)中的語(yǔ)言層次和轉(zhuǎn)換關(guān)系編

8、譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第16頁(yè)解釋程序解釋程序v解釋程序（解釋程序（Interpreter）v功能功能解釋程序解釋程序源程序源程序輸入數(shù)據(jù)輸入數(shù)據(jù)結(jié)果結(jié)果編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第17頁(yè)編譯程序的分類(lèi)編譯程序的分類(lèi)診斷編譯程序診斷編譯程序優(yōu)化編譯程序優(yōu)化編譯程序可變目標(biāo)編譯程序可變目標(biāo)編譯程序交叉編譯程序交叉編譯程序編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第18頁(yè)與編譯程序相關(guān)的程序與編譯程序相關(guān)的程序解釋程序解釋程序(Interpreter)(Interpreter)匯編程序匯編程序(assembler)(assembler)連接程序連接程序(linke

9、r)(linker) 連接系統(tǒng)函數(shù)與系統(tǒng)資源連接系統(tǒng)函數(shù)與系統(tǒng)資源裝入程序裝入程序(loader)(loader) 重定位重定位(relocation)(relocation)預(yù)處理器預(yù)處理器(Preprocessor)(Preprocessor)編輯器編輯器(editor)(editor)Debugger,Pro ManagerDebugger,Pro Manager編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第19頁(yè)編譯原理是討論編譯程序設(shè)計(jì)的基本理論、基本概念、基本方法 什么是編譯原理什么是編譯原理編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第20頁(yè)1.2 編譯過(guò)程概述編譯過(guò)程概述 邏輯上分

10、五個(gè)階段：詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成。 每個(gè)階段把源程序從一種表示變換成另一種表示。源 程 序編 譯 器目 標(biāo) 程 序詞法分析語(yǔ)法分析語(yǔ)義分析與中間代碼生成代碼優(yōu)化目標(biāo)代碼生成編譯原理實(shí)踐及應(yīng)用編譯過(guò)程和英文翻譯過(guò)程對(duì)比編譯過(guò)程和英文翻譯過(guò)程對(duì)比 把英文翻譯為中文把英文翻譯為中文 識(shí)別出句子中的一個(gè)個(gè)單詞；識(shí)別出句子中的一個(gè)個(gè)單詞； 分析句子的語(yǔ)法結(jié)構(gòu)；分析句子的語(yǔ)法結(jié)構(gòu)； 根據(jù)句子的含義進(jìn)行初步翻譯；根據(jù)句子的含義進(jìn)行初步翻譯； 對(duì)譯文進(jìn)行修飾；對(duì)譯文進(jìn)行修飾； 寫(xiě)出最后的譯文。寫(xiě)出最后的譯文。 詞法分析詞法分析語(yǔ)法分析語(yǔ)法分析中間代碼中間代碼產(chǎn)生產(chǎn)生

11、優(yōu)化優(yōu)化目標(biāo)代碼目標(biāo)代碼產(chǎn)生產(chǎn)生編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第22頁(yè)第一階段：詞法分析第一階段：詞法分析任務(wù)任務(wù):從左到右掃描源程序，識(shí)別出每個(gè)單詞o附加任務(wù)：a、濾掉空格 b、識(shí)別單詞 o 單詞符號(hào)是語(yǔ)言的基本組成成分o詞法分析的工作主要依據(jù)語(yǔ)言的詞法規(guī)詞法規(guī)則則，描述詞法規(guī)則的有效工具是正規(guī)式正規(guī)式和有限自動(dòng)機(jī)和有限自動(dòng)機(jī)。編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第23頁(yè)begin result:=5B * CB * Cend;單詞類(lèi)型內(nèi)部形式begin關(guān)鍵字$beginresult標(biāo)識(shí)符id1:=界符:=5常數(shù)int1+算符+B標(biāo)識(shí)符id1*算符*C標(biāo)識(shí)符id2+算符+B

12、標(biāo)識(shí)符id2*算符*C標(biāo)識(shí)符id3end關(guān)鍵字$end;界符;例:編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第24頁(yè)第二階段：語(yǔ)法分析第二階段：語(yǔ)法分析任務(wù)任務(wù): o 在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，將單詞符號(hào)串分解成各類(lèi)語(yǔ)法短語(yǔ)(例：程序、語(yǔ)句、表達(dá)式)。o 確定整個(gè)輸入串是否構(gòu)成語(yǔ)法上正確的程序。o 語(yǔ)法分析所依據(jù)的是語(yǔ)言的語(yǔ)法規(guī)則，表示語(yǔ)法規(guī)則的工具是上下文無(wú)關(guān)文法，用下推自動(dòng)機(jī)實(shí)現(xiàn)。編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第25頁(yè)id1:=int1 + id2 * id3 + id2 * id3 例：識(shí)別符號(hào)串id1:=int1 + id2 * id3 + id2 * id3

13、（即 result:= 5B * CB * C）是一個(gè)賦值語(yǔ)句。編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第26頁(yè)第三階段：語(yǔ)義分析和中間代碼生成第三階段：語(yǔ)義分析和中間代碼生成任務(wù)任務(wù)：對(duì)語(yǔ)法分析所識(shí)別出的各類(lèi)語(yǔ)法范疇分析其含義，進(jìn)行初步的翻譯(翻譯成中間代碼)。o 靜態(tài)語(yǔ)義審查 變量定義 類(lèi)型匹配 類(lèi)型轉(zhuǎn)換 例：C:=A*B (檢查C與、類(lèi)型)o 中間代碼的翻譯 中間代碼有多種形式，如： 四元式: (運(yùn)算符，運(yùn)算對(duì)象1，運(yùn)算對(duì)象2，結(jié)果) 編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第27頁(yè)例：對(duì)賦值語(yǔ)句： id1:=int1 + id2 * id3 + id2 * id3 1. 檢查res

14、ult、C是否定義類(lèi)型 2. 生成中間代碼(運(yùn)算符，運(yùn)算對(duì)象運(yùn)算符，運(yùn)算對(duì)象1，運(yùn)算對(duì)象，運(yùn)算對(duì)象2，結(jié)果，結(jié)果) (*, id2, id3, T1) (+, int1, T1, T2) (*, id2, id3, T3) (+, T2, T3, T4) (:=, T4, _, id1)id1:=int1 + id2 * id3 + id2 * id3編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第28頁(yè)第四階段：第四階段： 代碼優(yōu)化代碼優(yōu)化任務(wù)任務(wù)：對(duì)已產(chǎn)生的中間代碼進(jìn)行加工變換，使生成的目標(biāo)代碼更為高效(時(shí)間和空間)。o 優(yōu)化方法包括：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無(wú)用代碼等。o 代碼的優(yōu)

15、化依據(jù)的是程序的等價(jià)變換規(guī)則。編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第29頁(yè)序號(hào) 四元式1(*, id2, id3, T1)2(+, int1, T1, T2)3(*, id2, id3, T3)4(+, T2, T3, T4)5(:=, T4, _, id1)序號(hào) 四元式1(*, id2, id3, T1)2 (+, int1, T1, T2)3(+, T2, T1, id1)例：編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第五階段：目標(biāo)代碼的生成第五階段：目標(biāo)代碼的生成任務(wù)任務(wù)：把中間代碼(或經(jīng)優(yōu)化的中間代碼)變換成特定機(jī)器上的低級(jí)語(yǔ)言代碼。o 依賴(lài)于機(jī)器的硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令的含義o

16、 目標(biāo)代碼可以是：絕對(duì)指令代碼、可重定位的指令代碼、匯編指令代碼編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第31頁(yè)第31頁(yè)序號(hà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, AX例：編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第32頁(yè)1.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu) 編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第33頁(yè)編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第34頁(yè)

17、 幾個(gè)概念 符號(hào)表：登記源程序中出現(xiàn)的名字以及名字的各種屬性。 遍：對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。 編譯前端：主要指與源語(yǔ)言有關(guān)，與目標(biāo)語(yǔ)言無(wú)關(guān)的部分，通常包括詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼生成，與機(jī)器無(wú)關(guān)部分的代碼優(yōu)化。 編譯后端：指與目標(biāo)機(jī)器有關(guān)的部分。如與機(jī)器有關(guān)的優(yōu)化、目標(biāo)代碼生成。編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第35頁(yè)編譯階段的組合編譯階段的組合編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第36頁(yè)為什么要生成中間代碼為什么要生成中間代碼編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第37頁(yè)(1) 記號(hào)記號(hào)(

18、(token) ) 當(dāng)掃描程序?qū)⒆址占揭粋€(gè)記號(hào)中時(shí)，它通常是以符號(hào)表示這個(gè)記號(hào)；這也就是說(shuō)，作為一個(gè)枚舉數(shù)據(jù)類(lèi)型的值來(lái)表示源程序的記號(hào)集。編譯程序中的主要數(shù)據(jù)結(jié)構(gòu)編譯程序中的主要數(shù)據(jù)結(jié)構(gòu): :編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第38頁(yè)(2) 語(yǔ)法樹(shù)（語(yǔ)法樹(shù)（syntax tree） 如果分析程序確實(shí)生成了語(yǔ)法樹(shù)，它的構(gòu)造通常為基于指針的標(biāo)準(zhǔn)結(jié)構(gòu)，在進(jìn)行分析時(shí)動(dòng)態(tài)分配該結(jié)構(gòu)，則整棵樹(shù)可作為一個(gè)指向根節(jié)點(diǎn)的單個(gè)變量保存。結(jié)構(gòu)中的每一個(gè)節(jié)點(diǎn)都是一個(gè)記錄，它的域表示由分析程序和之后的語(yǔ)義分析程序收集的信息。編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第39頁(yè)(3) 符號(hào)表（符號(hào)表（symbo

19、l table） 這個(gè)數(shù)據(jù)結(jié)構(gòu)中的信息與標(biāo)識(shí)符有關(guān)：函數(shù)、變量、常量以及數(shù)據(jù)類(lèi)型。符號(hào)表幾乎與編譯器的所有階段交互：掃描程序、分析程序或?qū)?biāo)識(shí)符輸入到表格中的語(yǔ)義分析程序；語(yǔ)義分析程序?qū)⒃黾訑?shù)據(jù)類(lèi)型和其他信息；優(yōu)化階段和代碼生成階段也將利用由符號(hào)表提供的信息選出恰當(dāng)?shù)拇a。因?yàn)閷?duì)符號(hào)表的訪問(wèn)如此頻繁，所以插入、刪除和訪問(wèn)操作都必須比常規(guī)操作更有效。盡管可以使用各種樹(shù)的結(jié)構(gòu)，但雜湊表卻是達(dá)到這一要求的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)。有時(shí)在一個(gè)列表或棧中可使用若干個(gè)表格。編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第40頁(yè)(4) 常數(shù)表（常數(shù)表（literal table） 常數(shù)表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常數(shù)表中也十分重要。但是，在其中卻無(wú)需刪除，這是因?yàn)樗臄?shù)據(jù)全程應(yīng)用于程序而且常量或字符串在該表中只出現(xiàn)一次。編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第41頁(yè)(5) 中間代碼（中間代碼（intermediate code） 根據(jù)中間代碼的類(lèi)型（例如三元式代碼）和優(yōu)化的類(lèi)型，該代碼可以是文本串的數(shù)組、臨時(shí)文本文件或是結(jié)構(gòu)的連接列表。對(duì)于進(jìn)行復(fù)雜優(yōu)化的編譯器，應(yīng)特別注意選擇允許簡(jiǎn)單重組的表示。編譯原理實(shí)踐及應(yīng)用2022年2月2日星期三第42頁(yè)(6) 臨時(shí)文件（臨時(shí)文件（t e m p o r a ry file） 計(jì)算機(jī)過(guò)去一直未能在編