1、編譯原理,程序設(shè)計語言,第一章 引論,1.1 什么叫編譯程序 1.2 編譯過程概述 1.3 編譯程序的結(jié)構(gòu) 1.4 編譯程序與程序設(shè)計環(huán)境（略） 1.5 編譯程序的生成,1. 什么是編譯程序？,1.1 什么叫編譯程序,翻譯程序：一種語言程序-另一種語言程序,源語言,目標(biāo)語言,編譯程序：高級語言程序-低級語言程序,匯編程序：匯編語言程序-機(jī)器語言程序,解釋程序：源語言程序-邊解釋邊執(zhí)行,（1）編譯方式：先編譯后執(zhí)行。,（2）解釋方式：以源程序作為輸入，但不產(chǎn)生目標(biāo)代碼，而 是邊解釋邊執(zhí)行源程序本身。,2.“高級語言程序”的執(zhí)行方式,1.1 什么叫編譯程序,編譯和解釋的主要區(qū)別：,是否產(chǎn)生目標(biāo)代碼

2、！,說明：很多語言處理系統(tǒng)組合了編譯和解釋兩個程序 源程序先被翻譯為一種中間表示形式的程序，再接受輸入數(shù)據(jù)并對源程序進(jìn)行解釋而生成輸出結(jié)果。 通常我們還是將其稱為一個語言編譯系統(tǒng)。 例如Java語言的處理系統(tǒng)就包括編譯和解釋兩部分。,2.“高級語言程序”的執(zhí)行方式,一個混合的語言處理系統(tǒng),3.,“編譯程序”在計算機(jī)系統(tǒng)中的位置較接近于“硬件”,1.1 什么叫編譯程序,4.發(fā)展,20世紀(jì)50年代 第一個編譯程序 FORTRAN編譯程序,目前：編譯原理與技術(shù)得到迅速發(fā)展，現(xiàn)已形成一套比較成熟的系統(tǒng)化的理論與方法，并開發(fā)出了一些好的編譯程序的實現(xiàn)語言、環(huán)境與工具。,當(dāng)時普遍認(rèn)為設(shè)計和實現(xiàn)編譯程序是一

3、件十分困難、令人生畏的事情,1.1 什么叫編譯程序,編譯技術(shù)是計算機(jī)科學(xué)中發(fā)展最迅速、最成熟的一個重要分支，集中體現(xiàn)了計算機(jī)科學(xué)發(fā)展的重要成果與精華。 通過本課程的學(xué)習(xí)，一方面要理解、掌握編譯系統(tǒng)的結(jié)構(gòu)、工作流程以及編譯程序各組成部分的設(shè)計原理和實現(xiàn)技術(shù)；另一面，通過學(xué)習(xí)編譯的理論和方法，提高對程序設(shè)計語言、操作系統(tǒng)、計算機(jī)原理和體系結(jié)構(gòu)等課程知識的綜合理解。,1.2 編譯過程概述,The elephant ate an banana.,什么是語言？,for K : = 1 to 100 do begin M : = I + 10 * K ; N : = J + 10 * K end,一.類比

4、自然語言翻譯和編譯過程,英漢 編譯的工作過程 1)識別單詞詞法分析 2)分析句子語法結(jié)構(gòu)語法分析 3)根據(jù)句子含義初步翻譯語義分析與中間代碼產(chǎn)生 4)修飾譯文優(yōu)化 5)寫出最后譯文目標(biāo)代碼生成,1.2 編譯過程概述,1.詞法分析,for K : = 1 to 100 do begin M : = I + 10 * K ; N : = J + 10 * K end,基本字 for 標(biāo)識符 K 賦值號 := 常數(shù) 1 基本字 to 常數(shù) 100 基本字 do 基本字 begin . .,1.2 編譯過程概述,詞法分析 ,規(guī)則： 規(guī)則描述工具： 任務(wù)：,依循詞法規(guī)則.,正規(guī)式和有限自動機(jī)（FA）.,

5、輸入源程序，對構(gòu)成源程序的字符串進(jìn)行掃描和分解，識別出一個個的單詞符號，如基本字、標(biāo)識符、常數(shù)、算符、界符等。,1.2 編譯過程概述,2. 語法分析,for K : = 1 to 100 do begin M : = I + 10 * K ; N : = J + 10 * K end,規(guī)則： 規(guī)則描述工具： 任務(wù)：,依循語法規(guī)則.,上下文無關(guān)文法.,在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，對單詞符號串進(jìn)行語法分析，識別出各類語法單位，最終判斷輸入串是否構(gòu)成語法上正確的“程序”。,1.2 編譯過程概述,2 語法分析,3.語義分析和中間代碼產(chǎn)生,規(guī)則： 規(guī)則描述工具： 任務(wù)：,語義規(guī)則,屬性文法,

6、兩部分工作： 1.對每種語法范疇進(jìn)行靜態(tài)語義檢查; 2.若語義正確，則進(jìn)行中間代碼翻譯.,對語法分析器識別出的各類語法單位，分析其含義并進(jìn)行初步翻譯（產(chǎn)生中間代碼）。,中間代碼：一種獨立于具體硬件的記號系統(tǒng)，更接近于機(jī)器代碼,1.2 編譯過程概述,for K : = 1 to 100 do begin M : = I + 10 * K ; N : = J + 10 * K end；,K:=1 L1:if 100K goto L2 T1:=10*K M:=I+T1 T2:=10*K N:=J+T2 K:=K+1 goto L1 L2:,語義分析后產(chǎn)生的中間代碼：,三地址代碼,具體實現(xiàn)：三元式，四

7、元式，間接三元式,1.2 編譯過程概述,K:=1 L1:if 100K goto L2 T1:=10*K M:=I+T1 T2:=10*K N:=J+T2 K:=K+1 goto L1 L2:,四元式序列：,1.2 編譯過程概述,任務(wù)：對中間代碼進(jìn)行加工變換，以期在最后階段 能產(chǎn)生出更為高效（省時間和空間）的目標(biāo) 代碼。,4.優(yōu)化,包括：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無用代碼等,1.2 編譯過程概述,優(yōu)化前,優(yōu)化后,1.2 編譯過程概述,任務(wù)：把中間代碼變換成特定機(jī)器上的低級語言代碼， 實現(xiàn)最后的翻譯。,5.目標(biāo)代碼生成,絕對指令代碼/可重定位的指令代碼/匯編指令代碼,有賴于硬件系統(tǒng)結(jié)構(gòu)和

8、機(jī)器指令含義,1.2 編譯過程概述,1.3 編譯程序的結(jié)構(gòu),一.編譯程序總框圖,1.表格管理 編譯各階段都要涉及到構(gòu)造、查找或 更新有關(guān)表格 。,表格的作用： 登記源程序的各類信息和編譯各階段的進(jìn)展?fàn)顩r。 種類：符號名表、常數(shù)表、標(biāo)號表、入口名表、過程引用表 符號表： 用來登記源程序中出現(xiàn)的每個名字以及名字的各種屬性。,1.3 編譯程序的結(jié)構(gòu),2.出錯處理 每一階段都可能檢測出錯誤，絕大多 數(shù)錯誤可在前三階段檢測出來 .,任務(wù)：設(shè)法發(fā)現(xiàn)錯誤，并把有關(guān)錯誤信息報告給用戶.,語法錯誤：源程序中不符合語法/詞法規(guī)則的錯誤。詞法/語法分析時檢測 語義錯誤：源程序中不符合語義規(guī)則的錯誤。 語義分析/運(yùn)行

9、時檢測出來 舉例：語法錯誤 單詞拼寫錯誤、括號不匹配 語義錯誤 說明錯誤、作用域錯誤、類型不匹配,1.3 編譯程序的結(jié)構(gòu),二.遍,1.編譯過程的劃分： 上述劃分的五個階段僅僅是邏輯功能上的一種劃分,2.遍（Pass） 對源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。,具體實現(xiàn)時，受各方面（如源語言、設(shè)計要求等）限制，往往組織成若干遍,1.3 編譯程序的結(jié)構(gòu),3.注意： 既可以將幾個不同階段合為一遍，也可以把一個階段的工作分為若干遍 例如： 詞法分析+語法分析一遍 語法分析+語義分析與中間代碼產(chǎn)生一遍 優(yōu)化 若干遍,根據(jù)系統(tǒng)資源的狀況、運(yùn)行目標(biāo)的要求等

10、，可以將一個編譯程序設(shè)計形成多遍掃描的形式，在每一遍掃描中完成不同的任務(wù)。,1.3 編譯程序的結(jié)構(gòu),當(dāng)一遍中包含若干階段時，各階段的工作是穿插進(jìn)行的 。,例如：,識別出一個語法單位時,1.3 編譯程序的結(jié)構(gòu),三.編譯前端與后端,1、前端： 由與源語言有關(guān)但與目標(biāo)機(jī)無關(guān)的那些部分組成 包括詞法分析、語法分析、語義分析與中間代碼 產(chǎn)生、部分代碼優(yōu)化工作,2、后端： 包括編譯程序中與目標(biāo)機(jī)有關(guān)的那些部分，如與 目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。,不依賴于源語言而僅僅依賴于中間語言,1.3 編譯程序的結(jié)構(gòu),1.5 編譯程序的生成,一. 設(shè)計目標(biāo),目標(biāo)程序小，執(zhí)行速度快 編譯程序小，執(zhí)行速度快 診斷

11、能力強(qiáng)，可靠性強(qiáng) 可移植性，可擴(kuò)充性,如何實現(xiàn)編譯器？,直接用可運(yùn)行 的代碼編制,太費(fèi)力！,1.5 編譯程序的生成,以匯編語言或機(jī)器語言為工具 優(yōu)點: 可以針對具體的機(jī)器，充分發(fā)揮計算機(jī)的系統(tǒng)功能。生成的程序效率高。 缺點: 程序難讀、難寫、易出錯、難維護(hù)、生產(chǎn)的效率低。,五.編譯程序生成,高級語言書寫,優(yōu)點: 程序易讀、易理解、容易維護(hù)、生產(chǎn)的效率高。 缺點: 難以充分發(fā)揮計算機(jī)的系統(tǒng)功能，生成的程序效率低。,1.5 編譯程序的生成,2、問題,（1）歷史上第一個高級語言的編譯程序是怎樣構(gòu)造的？ -自編譯技術(shù)（自展技術(shù)） （2）已有A機(jī)器上的L1語言（如：C語言）的編譯程序，如何構(gòu)造A機(jī)器上的

12、L2語言（如：PASCAL語言）的編譯程序？ （3）已有A機(jī)器上的L語言的編譯程序，如何構(gòu)造B機(jī)器上的L語言的編譯程序？ -交叉編譯 /移植,源語言,編譯程序?qū)崿F(xiàn)語言,目標(biāo)語言,一般采用基于T形圖的方式：,表現(xiàn)語言翻譯的T形圖,1.5 編譯程序的生成,高級語言書寫 利用已有的某種語言的編譯程序?qū)崿F(xiàn)另一語言的編譯程序。,同一臺機(jī)器 不同的語言,1.5 編譯程序的生成,移植方法 把一種機(jī)器上的編譯程序移植到另一種機(jī)器上。,同一種語言不同的機(jī)器,1.5 編譯程序的生成,L1+L2+.+Ln,L1+L2,自展技術(shù),L1,1.5 編譯程序的生成,編譯程序自動產(chǎn)生 編譯程序-編譯程序，編譯程序書寫系統(tǒng),編譯程序 自動產(chǎn)生器,1.5 編譯程序的生成,編譯程序-編譯程序，編譯程序書寫系統(tǒng),LEX 詞法分析程序產(chǎn)生器 YACC 語法分析程序產(chǎn)生器 ANTLR LL(K)文法的語法分析器生成器 BISON 語法分析程序產(chǎn)生器,1.5 編譯程序的生成,1.5 編譯程序的生成,三.如何學(xué)習(xí)構(gòu)造編譯程序,要在某一臺機(jī)器上為某種語言構(gòu)造一個編譯程序，必須掌握以下內(nèi)容：,源語言：對被編譯的源語言，要深刻理解其結(jié)構(gòu)（語法）和 含義（語義）。