1、編 譯 原 理,夏 斌 ,關(guān)于編譯原理課程,內(nèi)容 編譯原理是介紹如何將高級(jí)程序設(shè)計(jì)語言變換成計(jì)算機(jī)硬件所能識(shí)別的機(jī)器語言，以便計(jì)算機(jī)進(jìn)行處理。 介紹編譯系統(tǒng)的工作原理 介紹編譯系統(tǒng)的構(gòu)造方法,先行課程：高等數(shù)學(xué)、 (PASCAL)、離散數(shù)學(xué)、 匯編語言、數(shù)據(jù)結(jié)構(gòu),編譯原理課程應(yīng)用領(lǐng)域 編譯器的設(shè)計(jì) 一般的軟件設(shè)計(jì),例如： 文本編輯器、信息檢索系統(tǒng)、模式識(shí)別器 打字程序、繪圖系統(tǒng) 優(yōu)化程序,本課程的地位,是計(jì)算機(jī)專業(yè)的學(xué)生必修的一門主干課 是本學(xué)科研究生入學(xué)考試的課程之一 是軟件技術(shù)基礎(chǔ),學(xué)習(xí)方法,1、認(rèn)真聽課，認(rèn)真理解書中的基本概念、基 本原理與基本算法 2、認(rèn)真做作業(yè) 3、在看書時(shí)或理解例題

2、時(shí)，一定要畫出相應(yīng) 的細(xì)節(jié)變化過程，通過畫圖來加深理解 4、在理解的基礎(chǔ)上記憶 5、理論結(jié)合實(shí)踐,編譯原理 呂映芝 清華大學(xué)出版社,編譯原理 技術(shù)與工具 人民郵電出版社,Compiler Construction Principle and Pratice 編譯原理及實(shí)踐 Kenneth C.Louden 機(jī)械工業(yè)出版社,參 考 書 籍 參 考 書 籍,Compilers Principles,Techniques,and Tools 龍書,第一章 引論,本章內(nèi)容： 什么是編譯程序 編譯程序各階段的主要功能,在計(jì)算機(jī)上如何執(zhí)行一個(gè)高級(jí)語言程序？ 把高級(jí)語言程序翻譯成機(jī)器語言程序 運(yùn)行所得的機(jī)器

3、語言程序求得計(jì)算結(jié)果 翻譯器：能夠?qū)⒁环N語言轉(zhuǎn)換成另一種語言的軟件，而且后者與前者在邏輯上是等價(jià)的。 源語言 目標(biāo)語言,編譯 專指由高級(jí)語言轉(zhuǎn)換為低級(jí)語言 解釋 接受某高級(jí)語言的一個(gè)語句輸入，進(jìn)行解釋并控制計(jì)算機(jī)執(zhí)行，馬上得到這句的執(zhí)行結(jié)果，然后再接受下一句。,編譯和解釋的區(qū)別：,特點(diǎn)： 1編譯器：工作效率高，即時(shí)間快、空間?。唤换バ耘c動(dòng)態(tài)特性差、可移植性差。大多數(shù)PL采用此種方法翻譯 2解釋器：工作效率低，即時(shí)間慢、空間費(fèi)；交互性與動(dòng)態(tài)特性好、可移植性好。早期的Basic和現(xiàn)在的Java等。 基本功能：二者相同 所采用的技術(shù)：從翻譯的角度來講，兩種方式所涉及的原理、方法、技術(shù)相似。,英譯漢與

4、編譯的比較,1.識(shí)別出句子中的一個(gè)個(gè)單詞 2.分析句子的語法結(jié)構(gòu) 3.分析句子的語義 4.初步翻譯 5.譯文修飾 6.寫出最后譯文,1.詞法分析 2.語法分析 3.語義分析 4.中間代碼生成 5.優(yōu)化 6.目標(biāo)代碼生成,1.1 詞法分析,任務(wù) 輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)的單詞。 單詞 是高級(jí)語言中有實(shí)在意義的最小語法單位，它由字符構(gòu)成。,識(shí)別右邊程序中的單詞 基本字：Void , int , float 標(biāo)識(shí)符: a, b, c, d, x, y, jisuan 常數(shù) : 50 算符 : +,*,= 界限符: ; , ( ),Void jisuan() int

5、 y,c,d; float x,a,b; x=a+b*50; y=（c+d）*(x+b）; ,詞法分析依照詞法規(guī)則，識(shí)別出正確的單詞，轉(zhuǎn)換成統(tǒng)一規(guī)格，備用。 轉(zhuǎn)換 對(duì)基本字、運(yùn)算符、界限符的轉(zhuǎn)換 標(biāo)識(shí)符的轉(zhuǎn)換 常數(shù)的轉(zhuǎn)換 轉(zhuǎn)換完成后的格式：（單詞種別，單詞符號(hào)的 屬性值） 二元式表示 （單詞種別，單詞符號(hào)的屬性值） 描述詞法規(guī)則的有效工具是正規(guī)式和有限自動(dòng)機(jī)。,1.2 語法分析,任務(wù)：根據(jù)語言的語法規(guī)則，把單詞流組成各類語法單位，如：短語、句子、過程、程序 語法規(guī)則：語言的規(guī)則，又稱為文法；規(guī)定單詞如何構(gòu)成短語、語句、過程和程序。 語法規(guī)則通常用上下文無關(guān)文法描述。,表達(dá)式的語法特征 任何一個(gè)

6、標(biāo)識(shí)符都是表達(dá)式； 任何一個(gè)數(shù)都是表達(dá)式； 如果e1和e2都是表達(dá)式，那么 e1 + e2 e1 * e2 (e1) 也都是表達(dá)式,position := initial + rate * 60;,語法分析有兩種方法： 推導(dǎo)(Derive)和規(guī)約(Reduce) 語法分析過程也可以用一棵倒著的樹來表示，這棵樹叫做分析樹,賦值語句,標(biāo)識(shí)符 （position）,整數(shù) (60),1.3 語義分析,任務(wù)：檢查程序的語義正確性，以保證程序各部分能有意義的結(jié)合在一起，為以后的代碼生成階段收集類型信息 語義分析階段的重要工作：類型檢查,position := initial + rate * 60;,1.

7、4 中間代碼生成,任務(wù)：根據(jù)語義規(guī)則產(chǎn)生一種介于源語言與目標(biāo)代碼之間的一種中間代碼。 中間代碼是不依賴于機(jī)器但是又便于生成依賴于機(jī)器的目標(biāo)代碼的一種結(jié)構(gòu)簡單、含義明確的記號(hào)系統(tǒng) 中間代碼形式 逆波蘭式、 四元式、三元式,position := initial + rate * 60;,1.5 代碼優(yōu)化,任務(wù)：對(duì)前面產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生更為高效的目標(biāo)代碼。 原則：等價(jià)變換 主要方面：公共子表達(dá)式的提取、合并已知量、刪除無用語句、循環(huán)優(yōu)化等。,例.,For (k=1;k=100;k+) m=i+10*k; n=j+10*k; ,1.6 目標(biāo)代碼生成,任務(wù)：把經(jīng)過優(yōu)化的中

8、間代碼轉(zhuǎn)化成特定 機(jī)器上的低級(jí)語言代碼 目標(biāo)代碼的形式 絕對(duì)指令代碼:可立即執(zhí)行的目標(biāo)代碼。 匯編指令代碼：匯編語言程序，需要通過匯編程序匯編后才能運(yùn)行。 可重定位指令代碼：先將各目標(biāo)模塊連接起來，確定變量、常數(shù)在主存中的位置，裝入主存后才能成為可以運(yùn)行的絕對(duì)指令代碼。,temp1 := id3 * 60.0 id1 := id2 * temp1,1.7 符號(hào)表管理,表格作用：用來記錄源程序的各種信息以及編譯過程中的各種狀況。 與編譯前四階段有關(guān)的表格有： 符號(hào)表、常數(shù)表、標(biāo)號(hào)表、分程序入口表、中間代碼表等。 符號(hào)表：用來登記源程序中的常量名、變量名、數(shù)組名、過程名等，記錄它們的性質(zhì)、定義和引用情況。,1.8 錯(cuò)誤診斷和報(bào)告,任務(wù)：如果源程序有錯(cuò)誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯(cuò)誤，并報(bào)告給用戶。 完成：由專門的出錯(cuò)處理程序來完成 錯(cuò)誤類型: 語法錯(cuò)誤:在詞法分析和語法分析階段檢測(cè)出來。 語義錯(cuò)誤：一般在語義分析階段檢測(cè)。,1.9 階段的分組,編譯前端：主要指與源語言有關(guān)，與目標(biāo)語言無關(guān)的部分，通常包括詞法分析、語法分析、語義分析和中間代碼生成，與機(jī)器無關(guān)部分的代碼優(yōu)化 編譯后端：指與目標(biāo)機(jī)器有關(guān)的部分。如與機(jī)器有關(guān)的優(yōu)化、目標(biāo)代碼生成,遍：對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。,