《編譯原理實(shí)踐及應(yīng)用》第1章編譯原理概述

編譯原理實(shí)踐及應(yīng)用----清華大學(xué)出版社1教材及主要參考資料教材：編譯原理實(shí)踐及應(yīng)用，黃賢英，清華大學(xué)出版社主要參考資料：(1)編譯原理，陳火旺，國(guó)防工業(yè)出版社程序設(shè)計(jì)語(yǔ)言編譯方法，肖軍模，大連理工大學(xué)出版社編譯原理，張素琴，呂映芝，清華大學(xué)出版社編譯原理，alfred

V.Aho等著，李建中等譯，人民郵電出版社2C語(yǔ)言程序voidmain(){int

x,y,z;x=3;y=2;z=x+y;}內(nèi)存地址內(nèi)存內(nèi)容單元名字………………200H3x：局部變量201H2y：局部變量202H5z：局部變量…………匯編語(yǔ)言程序……movax,3mov

x,axmovax,2mov

y,axmov

ax,xmov

bx,yaddax,bxmovz,ax......300302304306308……序言3為什么要學(xué)習(xí)編譯原理？1、有助于深刻理解和正確使用程序設(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)越重要。4《編譯原理》課程在計(jì)算機(jī)科學(xué)中的重要地位

(1)學(xué)習(xí)編程最初是學(xué)習(xí)一門高級(jí)語(yǔ)言，C或Pascal，掌握編寫一些簡(jiǎn)單程序的方法；(2)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，建立“算法”的概念，對(duì)編程有更深入的理解。遇到問(wèn)題的時(shí)候，能夠?qū)ふ蚁鄳?yīng)的數(shù)據(jù)結(jié)構(gòu)模型，設(shè)計(jì)適當(dāng)?shù)乃惴▉?lái)解決問(wèn)題；(3)學(xué)習(xí)匯編語(yǔ)言，這門課程是我們真正深入了解計(jì)算機(jī)內(nèi)部工作的第一門課程。通過(guò)學(xué)習(xí)了解匯編語(yǔ)言如何變?yōu)闄C(jī)器語(yǔ)言，如何對(duì)應(yīng)于一條指令；(4)計(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ī)制。5《編譯原理》課程在計(jì)算機(jī)科學(xué)中的地位高級(jí)語(yǔ)言程序設(shè)計(jì)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)編譯原理操作系統(tǒng)系統(tǒng)軟件應(yīng)用軟件軟件工程信息系統(tǒng)電子商務(wù)匯編語(yǔ)言計(jì)算機(jī)組成原理6學(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é)作能力7本課程的特點(diǎn)(1)本課程理論性很強(qiáng)，學(xué)習(xí)時(shí)需要很強(qiáng)的邏輯思維能力(2)涉及的算法復(fù)雜，要深入地理解這些算法很困難(3)整個(gè)編譯程序的構(gòu)造方法非常精妙，就像一部走時(shí)精確的時(shí)鐘，很多齒輪、部件協(xié)調(diào)地運(yùn)轉(zhuǎn)，以驅(qū)動(dòng)指針準(zhǔn)確地旋轉(zhuǎn)；編譯程序也是如此，一邊掃描源程序，一邊經(jīng)過(guò)各個(gè)部件的運(yùn)算，準(zhǔn)確地輸出為目標(biāo)語(yǔ)言。(4)編譯原理課程各個(gè)部分之間的獨(dú)立性很強(qiáng)，包括詞法分析、語(yǔ)法分析、存儲(chǔ)的組織與分配、中間語(yǔ)言、語(yǔ)法制導(dǎo)翻譯、代碼生成與優(yōu)化這幾大部分。詞法分析和語(yǔ)法分析是其中的重點(diǎn)，語(yǔ)言分析也是難點(diǎn)，需要掌握比較復(fù)雜的算法邏輯；其他部分相對(duì)來(lái)說(shuō)知識(shí)性更強(qiáng)一些。各部分之間的方法也互相獨(dú)立，在學(xué)習(xí)時(shí)，便于逐個(gè)擊破。(5)考試考查的內(nèi)容相對(duì)來(lái)說(shuō)是很穩(wěn)定的，絕大多數(shù)題目的解法都非常機(jī)械。8學(xué)習(xí)方法(1)盡可能地掌握編譯原理的思想，要站得高一點(diǎn)，盡可能理解算法的思想，而不是背固定的算法。應(yīng)該盡力理解為什么要這樣做，逐漸在頭腦中建立起編譯器的整體概念，而不是零零散散的一些算法。(2)很多題目的解法比較固定，要熟練掌握相應(yīng)的具體方法。(3)多做習(xí)題,對(duì)于編譯這樣的學(xué)科，題目的規(guī)模很大，步驟繁多，而且前面的步驟一旦出錯(cuò)，后面都錯(cuò)。(4)要扎扎實(shí)實(shí)地牢記重要算法，配合大量的習(xí)題進(jìn)行練習(xí)，達(dá)到拿到題目就可以動(dòng)手做的地步。(5)一邊學(xué)習(xí)，一邊總結(jié)，關(guān)鍵是找差異：同一問(wèn)題可以用多種方法來(lái)求解，不同方法適用于不同的文法，對(duì)文法的限制和要求，相應(yīng)的表格的構(gòu)造、使用等，各個(gè)方面的差異都要關(guān)注。(6)親自動(dòng)手實(shí)現(xiàn)書(shū)上的一些算法,完成實(shí)驗(yàn)指導(dǎo)書(shū)上給出的一個(gè)簡(jiǎn)單的編譯程序，或者編譯程序的一部分，這樣能更靈活地掌握編譯程序構(gòu)造的精髓。

9編譯技術(shù)的發(fā)展1954年至1957年間，F(xiàn)ORTRAN語(yǔ)言及其編譯器的開(kāi)發(fā)?；?8個(gè)人年。幾乎與此同時(shí)，NoamChomsky開(kāi)始研究語(yǔ)言文法(grammar，結(jié)構(gòu)規(guī)則)的難易程度以及識(shí)別它們所需的算法來(lái)為語(yǔ)言分類。在60年代和70年代進(jìn)行的分析問(wèn)題(parsingproblem，用于限定上下文無(wú)關(guān)語(yǔ)言的識(shí)別的有效算法)的研究。有窮自動(dòng)機(jī)(finiteautomata)和正規(guī)式(regularexpression)的研究與喬姆斯基的研究幾乎同時(shí)開(kāi)始，引出了表示程序設(shè)計(jì)語(yǔ)言的單詞的符號(hào)方式。接著又深化了生成有效的目標(biāo)代碼的方法，這就是最初的編譯器，實(shí)際上應(yīng)稱作代碼改進(jìn)技術(shù)(codeimprovementtechnique)。當(dāng)分析問(wèn)題變得好懂起來(lái)時(shí)，人們就在開(kāi)發(fā)程序上花費(fèi)了很大的功夫來(lái)研究這一部分的編譯器的自動(dòng)構(gòu)造。Lex與Yacc。在70年代后期和80年代早期，大量的項(xiàng)目都關(guān)注于編譯器其他部分的生成自動(dòng)化，這其中就包括了代碼生成。這些嘗試并未取得多少成功。

10編譯器設(shè)計(jì)最近的發(fā)展

與復(fù)雜的程序設(shè)計(jì)語(yǔ)言的發(fā)展結(jié)合在一起。如用于函數(shù)語(yǔ)言編譯的Hindley-Milner類型檢查的統(tǒng)一算法。編譯器已成為基于窗口的交互開(kāi)發(fā)環(huán)境(IDE)的一部分，IDE的標(biāo)準(zhǔn)并沒(méi)有多少，但已對(duì)標(biāo)準(zhǔn)的窗口環(huán)境進(jìn)行了開(kāi)發(fā)。近年來(lái)對(duì)此進(jìn)行了大量研究，但是基本的編譯器設(shè)計(jì)近20年來(lái)沒(méi)有多大的改變，現(xiàn)在正迅速地成為計(jì)算機(jī)科學(xué)課程中的中心一環(huán)。由多處理機(jī)的發(fā)展以及對(duì)并行處理的要求，最近的研究方向是并行編譯。隨著嵌入式應(yīng)用的迅速增長(zhǎng)，推動(dòng)了交叉編譯技術(shù)的發(fā)展；對(duì)系統(tǒng)芯片設(shè)計(jì)方法和關(guān)鍵EDA技術(shù)的研究，也帶動(dòng)了專用語(yǔ)言VHDL等及其編譯技術(shù)的不斷深化。11編譯技術(shù)的應(yīng)用語(yǔ)言的結(jié)構(gòu)化編輯器

:Turbo-Edit、editplus和Ultraedit等語(yǔ)言程序的調(diào)試工具語(yǔ)言程序的測(cè)試工具高級(jí)語(yǔ)言之間的轉(zhuǎn)換工具

交叉編譯程序

12引論第一章13本章要求主要內(nèi)容：各種翻譯程序的概念，編譯過(guò)程和階段劃分，編譯程序的組成和結(jié)構(gòu)，編譯程序的構(gòu)造方法重點(diǎn)掌握：編譯程序工作的基本過(guò)程及其各階段的基本任務(wù)，編譯程序總框。14機(jī)器語(yǔ)言(machinelanguage)C70600000002匯編語(yǔ)言(assemblerlanguage)

MOVX,2高級(jí)語(yǔ)言(high-levellanguage)

X=2為什么要使用編譯器？15計(jì)算機(jī)中的語(yǔ)言層次和轉(zhuǎn)換關(guān)系16高級(jí)語(yǔ)言語(yǔ)言處理程序操作系統(tǒng)匯編語(yǔ)言編譯程序所處的層次計(jì)算機(jī)硬件C編譯程序C語(yǔ)言Basic解釋程序Basic語(yǔ)言Fortran編譯程序Fortran語(yǔ)言............171.1什么叫編譯程序翻譯程序：能夠?qū)⒛撤N語(yǔ)言寫的程序轉(zhuǎn)換成另一種語(yǔ)言的程序，而且后者與前者在邏輯上是等價(jià)的。編譯程序：是一種將高級(jí)語(yǔ)言程序(源程序)翻譯成低級(jí)語(yǔ)言(目標(biāo)程序)的程序解釋程序：接受某高級(jí)語(yǔ)言的一個(gè)語(yǔ)句輸入，進(jìn)行解釋并控制計(jì)算機(jī)執(zhí)行，馬上得到這句的執(zhí)行結(jié)果，然后再接受下一句。181.1什么叫編譯程序編譯程序（Compiler）——將高級(jí)程序設(shè)計(jì)語(yǔ)言程序翻譯成邏輯上等價(jià)的低級(jí)語(yǔ)言(匯編語(yǔ)言,機(jī)器語(yǔ)言)程序的翻譯程序。功能編譯程序源程序目標(biāo)程序計(jì)算機(jī)運(yùn)行輸入數(shù)據(jù)結(jié)果19解釋程序解釋程序（Interpreter）——將高級(jí)程序設(shè)計(jì)語(yǔ)言寫的源程序作為輸入，邊解釋邊執(zhí)行源程序本身，而不產(chǎn)生目標(biāo)程序的翻譯程序。功能解釋程序源程序輸入數(shù)據(jù)結(jié)果20對(duì)編譯程序的一些說(shuō)明編譯程序?qū)嵸|(zhì)上是一個(gè)翻譯程序，要注意等價(jià)變換本課程的任務(wù)就是講解在這個(gè)轉(zhuǎn)換過(guò)程中所涉及到的一些理論和方法，最后，使用這些理論和方法，自己編寫一個(gè)小的編譯器轉(zhuǎn)換是一個(gè)總體的功能，要抓住總體結(jié)構(gòu)，逐層細(xì)分，寫編譯器時(shí)要體現(xiàn)軟件工程中軟件設(shè)計(jì)的原則，自頂向下，逐層分解。編譯器要完成的轉(zhuǎn)換任務(wù)相當(dāng)復(fù)雜，實(shí)現(xiàn)編譯器時(shí)必須分步驟分階段實(shí)現(xiàn)。分階段實(shí)現(xiàn)的好處是能夠簡(jiǎn)化程序的設(shè)計(jì)，當(dāng)然也可以不分階段實(shí)現(xiàn)。21編譯程序的分類診斷編譯程序優(yōu)化編譯程序可變目標(biāo)編譯程序交叉編譯程序22與編譯程序相關(guān)的程序解釋程序(Interpreter)匯編程序(assembler)連接程序(linker)連接系統(tǒng)函數(shù)與系統(tǒng)資源裝入程序(loader)重定位(relocation)預(yù)處理器(Preprocessor)編輯器(editor)Debugger,Profiler,ProjectManager23編譯原理是討論編譯程序設(shè)計(jì)的基本理論、基本概念、基本方法什么是編譯原理241.2編譯過(guò)程概述1、邏輯上分五個(gè)階段：詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成

每個(gè)階段把源程序從一種表示變換成另一種表示詞法分析語(yǔ)法分析語(yǔ)義分析與中間代碼生成代碼優(yōu)化目標(biāo)代碼生成25按照詞法分析、語(yǔ)法分析、語(yǔ)義分析等這種方式來(lái)劃分階段的原因是：每個(gè)階段的復(fù)雜程度不同，所依據(jù)的理論基礎(chǔ)不同，實(shí)現(xiàn)時(shí)采用的方法也不同。主要是方便理解和實(shí)現(xiàn)。劃分階段的依據(jù)是什么？每個(gè)階段所實(shí)現(xiàn)的功能相對(duì)獨(dú)立。26第一階段：詞法分析任務(wù):從左到右掃描源程序，識(shí)別出每個(gè)單詞附加任務(wù)：a、濾掉空格b、識(shí)別單詞

單詞符號(hào)是語(yǔ)言的基本組成成分詞法分析的工作主要依據(jù)語(yǔ)言的詞法規(guī)則，描述詞法規(guī)則的有效工具是正規(guī)式和有限自動(dòng)機(jī)。單詞的種類：（1）標(biāo)識(shí)符（2）關(guān)鍵字（char、int、if、else、switch、while、for等）（3）運(yùn)算符（即運(yùn)算符號(hào)+、－、*、/、&等）（4）界符（常見(jiàn)的有；，：（）等）（5）常數(shù)

27beginresult:=5＋B*C＋B*Cend;單詞類型內(nèi)部形式begin關(guān)鍵字$beginresult標(biāo)識(shí)符id1:=界符:=5常數(shù)int1+算符+B標(biāo)識(shí)符id1*算符*C標(biāo)識(shí)符id2+算符+B標(biāo)識(shí)符id2*算符*C標(biāo)識(shí)符id3end關(guān)鍵字$end;界符;例:28第二階段：語(yǔ)法分析任務(wù):在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，將單詞符號(hào)串分解成各類語(yǔ)法短語(yǔ)(例：程序、語(yǔ)句、表達(dá)式)。確定整個(gè)輸入串是否構(gòu)成語(yǔ)法上正確的程序。根據(jù)規(guī)則判定：賦值語(yǔ)句：標(biāo)識(shí)符：＝表達(dá)式表達(dá)式：標(biāo)識(shí)符、常數(shù)是表達(dá)式；表達(dá)式的運(yùn)算也是表達(dá)式

例：識(shí)別符號(hào)串id1:=int1+id2*id3+id2*id3（即result:=5＋B*C＋B*C）是一個(gè)賦值語(yǔ)句，而int1+id2*id3+id2*id3

（5＋B*C＋B*C）是一個(gè)表達(dá)式29語(yǔ)法分析所依據(jù)的是語(yǔ)言的語(yǔ)法規(guī)則，表示語(yǔ)法規(guī)則的工具是上下文無(wú)關(guān)文法,用下推自動(dòng)機(jī)實(shí)現(xiàn)。id1:=int1+id2*id3+id2*id330第三階段：語(yǔ)義分析和中間代碼生成任務(wù)：對(duì)語(yǔ)法分析所識(shí)別出的各類語(yǔ)法范疇分析其含義，進(jìn)行初步的翻譯(翻譯成中間代碼)。靜態(tài)語(yǔ)義審查變量定義類型匹配類型轉(zhuǎn)換例：C:=A*B(檢查C與Ａ、Ｂ類型)中間代碼的翻譯

中間代碼有多種形式，如：

四元式:(運(yùn)算符，運(yùn)算對(duì)象1，運(yùn)算對(duì)象2，結(jié)果)31例：對(duì)賦值語(yǔ)句：id1:=int1+id2*id3+id2*id3

1.檢查result、Ｂ、C是否定義、類型

2.生成中間代碼(運(yùn)算符，運(yùn)算對(duì)象1，運(yùn)算對(duì)象2，結(jié)果)

(*,id2,id3,T1)(+,int1,T1,T2)(*,id2,id3,T3)(+,T2,T3,T4)(:=,T4,_,id1)id1:=int1+id2*id3+id2*id332第四階段：代碼優(yōu)化任務(wù)：對(duì)已產(chǎn)生的中間代碼進(jìn)行加工變換，使生成的目標(biāo)代碼更為高效(時(shí)間和空間)。優(yōu)化方法包括：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無(wú)用代碼等。代碼的優(yōu)化依據(jù)的是程序的等價(jià)變換規(guī)則。序號(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)33第五階段：目標(biāo)代碼的生成任務(wù)：把中間代碼(或經(jīng)優(yōu)化的中間代碼)變換成特定機(jī)器上的低級(jí)語(yǔ)言代碼。依賴于機(jī)器的硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令的含義目標(biāo)代碼可以是：絕對(duì)指令代碼、可重定位的指令代碼、匯編指令代碼序號(hào)

四元式1(*,id2,id3,T1)2

(+,int1,T1,T2)3(+,T2,T1,id1)（1）movAX,id2（2）mulAX,id3（3）movBX,AX（4）addAX,int1（5）addAX,BX（6）movid1,AX341.3編譯程序的結(jié)構(gòu)

由左圖可以看出，詞法分析是實(shí)現(xiàn)編譯器的基礎(chǔ)，語(yǔ)法分析是實(shí)現(xiàn)編譯器的關(guān)鍵。因此按照這個(gè)順序來(lái)實(shí)現(xiàn)編譯器每一步的實(shí)現(xiàn)都依賴于一定的理論基礎(chǔ)。數(shù)學(xué)，尤其是離散數(shù)學(xué)是程序設(shè)計(jì)方法學(xué)的理論基礎(chǔ)351.3編譯程序的結(jié)構(gòu)(續(xù))幾個(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)代碼生成36編譯階段的組合37為什么生成中間代碼381.3編譯程序的結(jié)構(gòu)(續(xù))

(1)記號(hào)(token)

當(dāng)掃描程序?qū)⒆址占揭粋€(gè)記號(hào)中時(shí)，它通常是以符號(hào)表示這個(gè)記號(hào)；這也就是說(shuō)，作為一個(gè)枚舉數(shù)據(jù)類型的值來(lái)表示源程序的記號(hào)集。編譯程序中的主要數(shù)據(jù)結(jié)構(gòu):39編譯程序中的主要數(shù)據(jù)結(jié)構(gòu)(2)語(yǔ)法樹(shù)（syntaxtree）如果分析程序確實(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ǔ)義分析程序收集的信息。40(3)符號(hào)表（symboltable）這個(gè)數(shù)據(jù)結(jié)構(gòu)中的信息與標(biāo)識(shí)符有關(guān)：函數(shù)、變量、常量以及數(shù)據(jù)類型。符號(hào)表幾乎與編譯器的所有階段交互：掃描程序、分析程序或?qū)?biāo)識(shí)符輸入到表格中的語(yǔ)義分析程序；語(yǔ)義分析程序?qū)⒃黾訑?shù)據(jù)類型和其他信息；優(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ù)據(jù)結(jié)構(gòu):41(4)常數(shù)表（literaltable）常數(shù)表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常數(shù)表中也十分重要。但是，在其中卻無(wú)需刪除，這是因?yàn)樗臄?shù)據(jù)全程應(yīng)