1、編譯原理實踐及應(yīng)用,-清華大學(xué)出版社,2020年8月25日星期二,第2頁,教材及主要參考資料,教材：編譯原理實踐及應(yīng)用，黃賢英，清華大學(xué)出版社 主要參考資料： (1) 編譯原理，陳火旺，國防工業(yè)出版社 程序設(shè)計語言編譯方法，肖軍模，大連理工大學(xué)出版社 編譯原理，張素琴，呂映芝，清華大學(xué)出版社 編譯原理，alfred V.Aho等著，李建中等譯，人民郵電出版社,2020年8月25日星期二,第3頁,C語言程序,void main( ) int x,y,z; x=3; y=2; z=x+y; ,匯編語言程序,序言,2020年8月25日星期二,第4頁,為什么要學(xué)習(xí)編譯原理？,1、有助于深刻理解和正確使

2、用程序設(shè)計語言，加深對高級語言程序執(zhí)行過程的理解 2、有助于加深對整個計算機系統(tǒng)的理解。 3、設(shè)計開發(fā)編譯程序的軟件技術(shù)同樣可以用于其他軟件的設(shè)計開發(fā)。 4、隨著微處理器技術(shù)的飛速發(fā)展，處理器性能在很大程度上取決于編譯器的質(zhì)量、編譯技術(shù)成為計算機的核心技術(shù)，地位變得越來越重要。,2020年8月25日星期二,第5頁,編譯原理課程在計算機科學(xué)中的重要地位,(1) 學(xué)習(xí)編程最初是學(xué)習(xí)一門高級語言，C或Pascal，掌握編寫一些簡單程序的方法； (2) 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，建立“算法”的概念，對編程有更深入的理解。遇到問題的時候，能夠?qū)ふ蚁鄳?yīng)的數(shù)據(jù)結(jié)構(gòu)模型，設(shè)計適當(dāng)?shù)乃惴▉斫鉀Q問題； (3) 學(xué)習(xí)匯編語言，

3、這門課程是我們真正深入了解計算機內(nèi)部工作的第一門課程。通過學(xué)習(xí)了解匯編語言如何變?yōu)闄C器語言，如何對應(yīng)于一條指令； (4) 計算機組成原理課程的學(xué)習(xí)使我們了解到計算機的硬件組成，以及機器指令程序如何在計算機中運行的過程。 (5) 編譯原理課程幫助我們了解高級語言程序轉(zhuǎn)換成機器指令程序的過程?？梢詭椭覀兏羁痰乩斫飧呒壵Z言程序運行的內(nèi)部機制。,2020年8月25日星期二,第6頁,編譯原理課程在計算機科學(xué)中的地位,2020年8月25日星期二,第7頁,學(xué)習(xí)本課程的目的和任務(wù),加深對編程語言設(shè)計和實現(xiàn)的理解，對和編程語言有關(guān)的理論有所了解，對宏觀上把握編程語言來說，起一個奠基的作用，提升自身的編程能力

4、 掌握編譯程序的基本結(jié)構(gòu)，掌握常用的編譯技術(shù)和方法，將編譯原理的理論和方法應(yīng)用于一般的軟件設(shè)計中 培養(yǎng)團隊協(xié)作能力,2020年8月25日星期二,第8頁,本課程的特點,(1) 本課程理論性很強，學(xué)習(xí)時需要很強的邏輯思維能力 (2) 涉及的算法復(fù)雜，要深入地理解這些算法很困難 (3) 整個編譯程序的構(gòu)造方法非常精妙，就像一部走時精確的時鐘，很多齒輪、部件協(xié)調(diào)地運轉(zhuǎn)，以驅(qū)動指針準(zhǔn)確地旋轉(zhuǎn)；編譯程序也是如此，一邊掃描源程序，一邊經(jīng)過各個部件的運算，準(zhǔn)確地輸出為目標(biāo)語言。 (4) 編譯原理課程各個部分之間的獨立性很強，包括詞法分析、語法分析、存儲的組織與分配、中間語言、語法制導(dǎo)翻譯、代碼生成與優(yōu)化這幾大

5、部分。詞法分析和語法分析是其中的重點，語言分析也是難點，需要掌握比較復(fù)雜的算法邏輯；其他部分相對來說知識性更強一些。各部分之間的方法也互相獨立，在學(xué)習(xí)時，便于逐個擊破。 (5) 考試考查的內(nèi)容相對來說是很穩(wěn)定的，絕大多數(shù)題目的解法都非常機械。,2020年8月25日星期二,第9頁,學(xué)習(xí)方法,(1) 盡可能地掌握編譯原理的思想，要站得高一點，盡可能理解算法的思想，而不是背固定的算法。應(yīng)該盡力理解為什么要這樣做，逐漸在頭腦中建立起編譯器的整體概念，而不是零零散散的一些算法。 (2) 很多題目的解法比較固定，要熟練掌握相應(yīng)的具體方法。 (3) 多做習(xí)題, 對于編譯這樣的學(xué)科，題目的規(guī)模很大，步驟繁多，

6、而且前面的步驟一旦出錯，后面都錯。 (4) 要扎扎實實地牢記重要算法，配合大量的習(xí)題進行練習(xí)，達到拿到題目就可以動手做的地步。 (5) 一邊學(xué)習(xí)，一邊總結(jié)，關(guān)鍵是找差異：同一問題可以用多種方法來求解，不同方法適用于不同的文法，對文法的限制和要求，相應(yīng)的表格的構(gòu)造、使用等，各個方面的差異都要關(guān)注。 (6) 親自動手實現(xiàn)書上的一些算法,完成實驗指導(dǎo)書上給出的一個簡單的編譯程序，或者編譯程序的一部分，這樣能更靈活地掌握編譯程序構(gòu)造的精髓。,2020年8月25日星期二,第10頁,編譯技術(shù)的發(fā)展,1954年至1957年間，F(xiàn)ORTRAN語言及其編譯器的開發(fā)。花了18個人年。 幾乎與此同時，Noam Ch

7、omsky開始研究語言文法(grammar，結(jié)構(gòu)規(guī)則)的難易程度以及識別它們所需的算法來為語言分類。 在6 0年代和7 0年代進行的分析問題(parsing problem，用于限定上下文無關(guān)語言的識別的有效算法)的研究。 有窮自動機(finite automata)和正規(guī)式(regular expression) 的研究與喬姆斯基的研究幾乎同時開始，引出了表示程序設(shè)計語言的單詞的符號方式。 接著又深化了生成有效的目標(biāo)代碼的方法，這就是最初的編譯器，實際上應(yīng)稱作代碼改進技術(shù)(code improvement technique)。 當(dāng)分析問題變得好懂起來時，人們就在開發(fā)程序上花費了很大的功夫來

8、研究這一部分的編譯器的自動構(gòu)造。Lex與Yacc。 在70年代后期和80年代早期，大量的項目都關(guān)注于編譯器其他部分的生成自動化，這其中就包括了代碼生成。這些嘗試并未取得多少成功。,2020年8月25日星期二,第11頁,編譯器設(shè)計最近的發(fā)展,與復(fù)雜的程序設(shè)計語言的發(fā)展結(jié)合在一起。如用于函數(shù)語言編譯的Hindley-Milner類型檢查的統(tǒng)一算法。 編譯器已成為基于窗口的交互開發(fā)環(huán)境(IDE)的一部分，IDE的標(biāo)準(zhǔn)并沒有多少，但已對標(biāo)準(zhǔn)的窗口環(huán)境進行了開發(fā)。近年來對此進行了大量研究，但是基本的編譯器設(shè)計近20年來沒有多大的改變，現(xiàn)在正迅速地成為計算機科學(xué)課程中的中心一環(huán)。 由多處理機的發(fā)展以及對并

9、行處理的要求，最近的研究方向是并行編譯。 隨著嵌入式應(yīng)用的迅速增長，推動了交叉編譯技術(shù)的發(fā)展；對系統(tǒng)芯片設(shè)計方法和關(guān)鍵EDA技術(shù)的研究，也帶動了專用語言VHDL等及其編譯技術(shù)的不斷深化。,2020年8月25日星期二,第12頁,編譯技術(shù)的應(yīng)用,語言的結(jié)構(gòu)化編輯器 :Turbo-Edit、editplus和Ultraedit等 語言程序的調(diào)試工具 語言程序的測試工具 高級語言之間的轉(zhuǎn)換工具 交叉編譯程序,引 論,第一章,2020年8月25日星期二,第14頁,本章要求,主要內(nèi)容：各種翻譯程序的概念，編譯過程和階段劃分，編譯程序的組成和結(jié)構(gòu)，編譯程序的構(gòu)造方法 重點掌握：編譯程序工作的基本過程及其各階

10、段的基本任務(wù)，編譯程序總框。,2020年8月25日星期二,第15頁,機器語言 (machine language) C7 06 0000 0002 匯編語言 (assembler language) MOV X , 2 高級語言 (high-level language) X = 2,為什么要使用編譯器？,2020年8月25日星期二,第16頁,計算機中的語言層次和轉(zhuǎn)換關(guān)系,2020年8月25日星期二,第17頁,操作系統(tǒng) 匯編語言,編譯程序所處的層次,計算機硬件,2020年8月25日星期二,第18頁,1.1 什么叫編譯程序,翻譯程序：能夠?qū)⒛撤N語言寫的程序轉(zhuǎn)換成另一種語言的程序，而且后者與前者在

11、邏輯上是等價的。 編譯程序：是一種將高級語言程序(源程序)翻譯成低級語言(目標(biāo)程序)的程序 解釋程序：接受某高級語言的一個語句輸入，進行解釋并控制計算機執(zhí)行，馬上得到這句的執(zhí)行結(jié)果，然后再接受下一句。,2020年8月25日星期二,第19頁,1.1 什么叫編譯程序,編譯程序（Compiler）將高級程序設(shè)計語言程序翻譯成邏輯上等價的低級語言(匯編語言,機器語言)程序的翻譯程序。 功能,編譯程序,源程序,目標(biāo)程序,計算機運行,輸入數(shù)據(jù),結(jié)果,2020年8月25日星期二,第20頁,解釋程序,解釋程序（Interpreter）將高級程序設(shè)計語言寫的源程序作為輸入，邊解釋邊執(zhí)行源程序本身，而不產(chǎn)生目標(biāo)程

12、序的翻譯程序。 功能,解釋程序,源程序,輸入數(shù)據(jù),結(jié)果,2020年8月25日星期二,第21頁,對編譯程序的一些說明,編譯程序?qū)嵸|(zhì)上是一個翻譯程序，要注意等價變換 本課程的任務(wù)就是講解在這個轉(zhuǎn)換過程中所涉及到的一些理論和方法，最后，使用這些理論和方法，自己編寫一個小的編譯器 轉(zhuǎn)換是一個總體的功能，要抓住總體結(jié)構(gòu)，逐層細(xì)分，寫編譯器時要體現(xiàn)軟件工程中軟件設(shè)計的原則，自頂向下，逐層分解。 編譯器要完成的轉(zhuǎn)換任務(wù)相當(dāng)復(fù)雜，實現(xiàn)編譯器時必須分步驟分階段實現(xiàn)。分階段實現(xiàn)的好處是能夠簡化程序的設(shè)計，當(dāng)然也可以不分階段實現(xiàn)。,2020年8月25日星期二,第22頁,編譯程序的分類,診斷編譯程序 優(yōu)化編譯程序 可

13、變目標(biāo)編譯程序 交叉編譯程序,2020年8月25日星期二,第23頁,與編譯程序相關(guān)的程序,解釋程序(Interpreter) 匯編程序(assembler) 連接程序(linker) 連接系統(tǒng)函數(shù)與系統(tǒng)資源 裝入程序(loader) 重定位(relocation) 預(yù)處理器(Preprocessor) 編輯器(editor) Debugger,Profiler,Project Manager,2020年8月25日星期二,第24頁,編譯原理是討論編譯程序設(shè)計的基本理論、基本概念、基本方法,什么是編譯原理,2020年8月25日星期二,第25頁,1.2 編譯過程概述,1、邏輯上分五個階段：詞法分析、

14、語法分析、語義分析與中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成 每個階段把源程序從一種表示變換成另一種表示,2020年8月25日星期二,第26頁,按照詞法分析、語法分析、語義分析等這種方式來劃分階段的原因是：每個階段的復(fù)雜程度不同，所依據(jù)的理論基礎(chǔ)不同，實現(xiàn)時采用的方法也不同。主要是方便理解和實現(xiàn)。 劃分階段的依據(jù)是什么？每個階段所實現(xiàn)的功能相對獨立。,2020年8月25日星期二,第27頁,第一階段：詞法分析,任務(wù):從左到右掃描源程序，識別出每個單詞 附加任務(wù)：a、濾掉空格 b、識別單詞 單詞符號是語言的基本組成成分 詞法分析的工作主要依據(jù)語言的詞法規(guī)則，描述詞法規(guī)則的有效工具是正規(guī)式和有限自動機。

15、 單詞的種類： （1） 標(biāo)識符 （2） 關(guān)鍵字（char、int、if、else、switch、while、for等） （3） 運算符（即運算符號 +、*、/、,例:,2020年8月25日星期二,第29頁,第二階段：語法分析,任務(wù): 在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，將單詞符號串分解成各類語法短語(例：程序、語句、表達式)。 確定整個輸入串是否構(gòu)成語法上正確的程序。 根據(jù)規(guī)則判定：賦值語句：標(biāo)識符：表達式 表達式：標(biāo)識符、常數(shù)是表達式； 表達式的運算也是表達式 例：識別符號串id1:=int1 + id2 * id3 + id2 * id3（即 result:= 5B * CB * C）

16、是一個賦值語句， 而int1 + id2 * id3 + id2 * id3 （5B * CB * C） 是一個表達式,2020年8月25日星期二,第30頁,語法分析所依據(jù)的是語言的語法規(guī)則， 表示語法規(guī)則的工具是上下文無關(guān)文法,用下推自動機實現(xiàn)。,id1:=int1 + id2 * id3 + id2 * id3,2020年8月25日星期二,第31頁,第三階段：語義分析和中間代碼生成,任務(wù)：對語法分析所識別出的各類語法范疇分析其含義，進行初步的翻譯(翻譯成中間代碼)。 靜態(tài)語義審查 變量定義 類型匹配 類型轉(zhuǎn)換 例：C:=A*B (檢查C與、類型) 中間代碼的翻譯 中間代碼有多種形式，如：

17、四元式: (運算符，運算對象1，運算對象2，結(jié)果),2020年8月25日星期二,第32頁,例：對賦值語句： id1:=int1 + id2 * id3 + id2 * id3 1. 檢查result、C是否定義、類型 2. 生成中間代碼,(運算符，運算對象1，運算對象2，結(jié)果) (*, id2, id3, T1) (+, int1, T1, T2) (*, id2, id3, T3) (+, T2, T3, T4) (:=, T4, _, id1),id1:=int1 + id2 * id3 + id2 * id3,2020年8月25日星期二,第33頁,第四階段： 代碼優(yōu)化,任務(wù)：對已產(chǎn)生的中

18、間代碼進行加工變換，使生成的目標(biāo)代碼更為高效(時間和空間)。 優(yōu)化方法包括：公共子表達式的提取、循環(huán)優(yōu)化、刪除無用代碼等。 代碼的優(yōu)化依據(jù)的是程序的等價變換規(guī)則。,2020年8月25日星期二,第34頁,第五階段：目標(biāo)代碼的生成,任務(wù)：把中間代碼(或經(jīng)優(yōu)化的中間代碼)變換成特定機器上的低級語言代碼。 依賴于機器的硬件系統(tǒng)結(jié)構(gòu)和機器指令的含義 目標(biāo)代碼可以是：絕對指令代碼、可重定位的指令代碼、匯編指令代碼,2020年8月25日星期二,第35頁,1.3編譯程序的結(jié)構(gòu),由左圖可以看出，詞法分析是實現(xiàn)編譯器的基礎(chǔ)，語法分析是實現(xiàn)編譯器的關(guān)鍵。 因此按照這個順序來實現(xiàn)編譯器 每一步的實現(xiàn)都依賴于一定的理論

19、基礎(chǔ)。 數(shù)學(xué)，尤其是離散數(shù)學(xué)是程序設(shè)計方法學(xué)的理論基礎(chǔ),2020年8月25日星期二,第36頁,1.3 編譯程序的結(jié)構(gòu)(續(xù)),幾個概念 符號表：登記源程序中出現(xiàn)的名字以及名字的各種屬性 遍：對源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。 編譯前端：主要指與源語言有關(guān)，與目標(biāo)語言無關(guān)的部分，通常包括詞法分析、語法分析、語義分析和中間代碼生成，與機器無關(guān)部分的代碼優(yōu)化 編譯后端：指與目標(biāo)機器有關(guān)的部分。如與機器有關(guān)的優(yōu)化、目標(biāo)代碼生成,2020年8月25日星期二,第37頁,編譯階段的組合,2020年8月25日星期二,第38頁,為什么生成中間代碼,2020

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

21、1頁,(3) 符號表（symbol table） 這個數(shù)據(jù)結(jié)構(gòu)中的信息與標(biāo)識符有關(guān)：函數(shù)、變量、常量以及數(shù)據(jù)類型。符號表幾乎與編譯器的所有階段交互：掃描程序、分析程序或?qū)?biāo)識符輸入到表格中的語義分析程序；語義分析程序?qū)⒃黾訑?shù)據(jù)類型和其他信息；優(yōu)化階段和代碼生成階段也將利用由符號表提供的信息選出恰當(dāng)?shù)拇a。因為對符號表的訪問如此頻繁，所以插入、刪除和訪問操作都必須比常規(guī)操作更有效。盡管可以使用各種樹的結(jié)構(gòu)，但雜湊表卻是達到這一要求的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)。有時在一個列表或棧中可使用若干個表格。,編譯程序中的主要數(shù)據(jù)結(jié)構(gòu):,2020年8月25日星期二,第42頁,(4) 常數(shù)表（literal table） 常數(shù)表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常數(shù)表中也十分重要。但是，在其中卻無需刪除，這是因為它的數(shù)據(jù)全程應(yīng)用于程序而且常量或字符串在該表中只出現(xiàn)一次。,編譯程序中的主要數(shù)據(jù)結(jié)構(gòu):,2020年8月25日星期二,第43頁,(5) 中間代碼（intermediate code） 根據(jù)中間代碼的類型（例如三元式代碼）和優(yōu)化的類型，該代碼可以是文本串的數(shù)組、臨時文本文件或是結(jié)構(gòu)的連接列