編 譯 原 理課件

1、編 譯 原 理2022/9/21編譯原理引論2聯(lián)系方式E-mail: 手機公室：信息科學(xué)與技術(shù)學(xué)院辦公樓2012022/9/21編譯原理引論3課程簡介重要的計算機專業(yè)必修基礎(chǔ)課程，理論性強、算法多、難度大碩士研究生和博士研究生入學(xué)的考試科目課程性質(zhì)：必修課，4學(xué)分學(xué)時：52上課+12實驗=64學(xué)時參考教材：編譯原理(第2版)，清華大學(xué)出版社，張素琴等編著，2005年2月出版2022/9/21編譯原理引論4課程要求課前預(yù)習(xí)上課認(rèn)真聽講，不允許聊天、睡覺、玩游戲、看與本課程無關(guān)的書籍等無故不得曠課，有事要請假，三次以上無故曠課取消期末考試資格課后認(rèn)真復(fù)習(xí)，按時獨立地完成作

2、業(yè)實驗課之前要認(rèn)真準(zhǔn)備，認(rèn)真、獨立做實驗考試前認(rèn)真復(fù)習(xí)2022/9/21編譯原理引論6主要內(nèi)容什么是編譯程序編譯過程概述編譯程序的結(jié)構(gòu)編譯階段的組合解釋程序一些軟件工具程序設(shè)計語言范型2022/9/21編譯原理引論7編程語言的發(fā)展歷程第一代語言：機器語言特點：面向機器第二代語言：匯編語言特點：用針對指令的符號代替二進(jìn)制碼第三代語言：高級語言包括面向過程的語言和面向?qū)ο蟮恼Z言。例：Pascal，C，C+，C#，Java等第四代語言：面向問題的語言例：SQL編程語言的發(fā)展體現(xiàn)了編譯技術(shù)的發(fā)展2022/9/21編譯原理引論9高級語言程序的處理過程需預(yù)處理的源程序預(yù)處理程序源程序編譯程序匯編程序裝載/

3、連接編輯程序目標(biāo)匯編程序可再裝配的機器代碼絕對機器代碼可再裝配目標(biāo)文件2022/9/21編譯原理引論10編譯器和集成開發(fā)環(huán)境編譯器：即編譯程序，把高級語言經(jīng)分析翻譯為低級語言。集成開發(fā)環(huán)境：簡稱IDE（Integrated Develop Environment），是用于提供程序開發(fā)環(huán)境的應(yīng)用程序，一般包括代碼編輯器、編譯器、調(diào)試器和圖形用戶界面工具。背景：早期程序設(shè)計的各個階段都要用不同的軟件來進(jìn)行處理,如先用字處理軟件編輯源程序，再用編譯程序進(jìn)行編譯，然后用鏈接程序進(jìn)行函數(shù)、模塊連接, 開發(fā)者必須在幾種軟件間來回切換操作。 人們習(xí)慣上經(jīng)常把IDE稱為編譯器。2022/9/21編譯原理引論1

4、1常見語言及其IDE語言IDECTC2.0C+C+ Builder, VC+6.0, TC3.0C#VS.NETPascalTPOOPascalDelphiVBVB6.0 (解釋器)JavaEclipse, JBuilder2022/9/21編譯原理引論121.2 編譯過程概述從概念上來講，一個編譯程序的整個工作過程是劃分成階段進(jìn)行的，每個階段將源程序的一種表示形式轉(zhuǎn)換成另一種表示形式，各個階段進(jìn)行的操作在邏輯上是緊密連接在一起的。編譯程序分成詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成六個階段。另外兩個重要的工作：表格管理和出錯處理與上述六個階段都有聯(lián)系。2022/9/

5、21編譯原理引論13編譯過程比喻編譯過程翻譯文章詞法分析識別一個一個單詞語法分析分析文章每句話的語法語義分析分析文章每句話的含義中間代碼生成初步給出翻譯結(jié)果代碼優(yōu)化對初步的翻譯結(jié)果進(jìn)行修改目標(biāo)代碼生成最終翻譯結(jié)果2022/9/21編譯原理引論141.2.1 詞法分析詞法分析階段是編譯過程的第一個階段。這個階段的任務(wù)是從左到右一個字符一個字符地讀入源程序，對構(gòu)成源程序的字符流進(jìn)行掃描和分解，從而識別出一個個單詞。單詞：邏輯上緊密相連的一組字符，這些字符具有集體意義。2022/9/21編譯原理引論16詞法分析舉例(分析結(jié)果)1. 保留字 begin2. 保留字 var3. 標(biāo)識符 sum4. 逗號

6、 ,5. 標(biāo)識符 first6. 逗號 ,7. 標(biāo)識符 count8. 冒號:9. 保留字 real10. 分號 ;11. 標(biāo)識符 sum12. 賦值號 :=13. 標(biāo)識符 first14. 加號 +15. 標(biāo)識符 count16. 乘號 *17. 整數(shù) 1018. 保留字 end19. 界符 .beginvar sum, first, count: real;sum := first + count * 10end.2022/9/21編譯原理引論171.2.2 語法分析語法分析是編譯過程的第二個階段。任務(wù)：在詞法分析的基礎(chǔ)上將單詞序列分解成各類語法短語，如“程序”，“語句”，“表達(dá)式”等。語

7、法短語可表示成語法樹。依據(jù)：語言的語法規(guī)則，即描述程序結(jié)構(gòu)的規(guī)則。通過語法分析確定整個輸入串是否構(gòu)成一個語法上正確的程序。語法規(guī)則通常是由遞歸規(guī)則定義的。2022/9/21編譯原理引論19語法樹舉例二 (id1:=id2+id3*10):=id1 +id2 *id3 102022/9/21編譯原理引論20語法規(guī)則舉例一(表達(dá)式)任何標(biāo)識符是表達(dá)式任何常數(shù)（整常數(shù)、實常數(shù)）是表達(dá)式若表達(dá)式1和表達(dá)式2都是表達(dá)式，那么：表達(dá)式1+表達(dá)式2表達(dá)式1*表達(dá)式2（表達(dá)式）都是表達(dá)式2022/9/21編譯原理引論21語法規(guī)則舉例二(語句)標(biāo)識符:=表達(dá)式 是語句While (表達(dá)式) do 語句 和If

8、(表達(dá)式) then 語句 else 語句都是語句。2022/9/21編譯原理引論221.2.3 語義分析任務(wù)：審查源程序有無語義錯誤，為代碼生成階段收集類型信息。例如：語法分析的一個工作是進(jìn)行類型檢查，審查每個算符是否具有語言規(guī)范允許的運算對象，當(dāng)不符合語言規(guī)范時，便以程序應(yīng)報告錯誤。假如在語句sum:=first + count * 10中，*的兩個運算對象：count是實型，10是整型，則語義分析階段進(jìn)行語義審查之后，在語法分析得到的分析樹上增加一個語義處理結(jié)點，表示整型變成實型的一目運算符inttoreal。2022/9/21編譯原理引論23語義分析舉例id1 +:=id2 *id3

9、inttoreal102022/9/21編譯原理引論241.2.4 中間代碼生成在進(jìn)行語法分析和語義分析階段的工作之后，有的編譯程序?qū)⒃闯绦蚓幊桃环N內(nèi)部表示形式，這種內(nèi)部表示形式叫做中間語言或中間代碼。中間代碼設(shè)計的原則：容易生成容易將它翻譯成目標(biāo)代碼常用的中間代碼形式四元式的語法： （運算符，運算對象1，運算對象2，結(jié)果）2022/9/21編譯原理引論261.2.5 代碼優(yōu)化任務(wù)：對前階段產(chǎn)生的中間代碼進(jìn)行變換或進(jìn)行改造，目的是使生成的目標(biāo)代碼更為高效，即省時間和省空間。例：上節(jié)生成的中間代碼優(yōu)化為：(*id310.0t1)(+id2t1id1)2022/9/21編譯原理引論271.2.6

10、目標(biāo)代碼生成任務(wù)：把中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。例：使用兩個寄存器，上節(jié)的中間代碼可能生成如下匯編代碼：MOVid3R2MUL#10.0R2MOVid2R1ADDR1R2MOVR1id12022/9/21編譯原理引論291.4 編譯階段的組合編譯的過程可以分為前端和后端兩個部分前端由那些主要依賴于源語言而與目標(biāo)機無關(guān)的階段組成，通常包括詞法分析、語法分析、語義分析和中間代碼生成。后端指那些依賴于目標(biāo)機而一般不依賴源語言，只與中間代碼有關(guān)的那些階段，即目標(biāo)代碼生成，以及相關(guān)出錯處理和符號表操作前端和后端可以任意組合實現(xiàn)編譯程序2022/9/21編譯原

11、理引論30前端和后端的組合某一編譯程序的前端加上相應(yīng)不同的后端可以為不同的機器構(gòu)成同一個源語言的編譯程序不同語言編譯的前端生成某一種中間語言，在使用一個共同的后端，可以為同一機器生成幾個語言的編譯程序2022/9/21編譯原理引論31編譯過程的掃描遍數(shù)一個編譯過程可以由一遍，兩遍或者多遍完成。所謂“遍”，也稱作“趟”，是對源程序或其等價的中間語言程序從頭到尾掃視并完成規(guī)定任務(wù)的過程。在實際的編譯系統(tǒng)的設(shè)計中，編譯的幾個階段的工作應(yīng)該怎樣組合，即編譯程序究竟分成幾遍，參考的因素主要是源語言和機器（目標(biāo)機）的特征2022/9/21編譯原理引論321.5 解釋程序編譯程序和解釋程序：編譯程序的編譯和

12、運行是兩個獨立分開的階段，它先把一個高級語言程序翻譯成某個機器的匯編或二進(jìn)制代碼程序，然后這個二進(jìn)制代碼程序在機器上運行以生成結(jié)果解釋程序接受某個語言的程序并立即運行這個源程序，它的工作模式是一個個的獲取、分析并執(zhí)行源程序語句，一旦第一個語句分析結(jié)束，源程序便開始運行并且生成結(jié)果。解釋程序的輸入包括源程序和源程序的輸入數(shù)據(jù)，它不生成目標(biāo)代碼，直接輸出結(jié)果。2022/9/21編譯原理引論33解釋程序的功能源程序初始數(shù)據(jù)解釋程序計算結(jié)果2022/9/21編譯原理引論34編譯程序和解釋程序編譯程序和解釋程序在存儲組織方面的不同：編譯程序處理時，在源程序被編譯階段，存儲區(qū)中要為源程序和目標(biāo)代碼開辟空間

13、，要存放編譯用的各種各樣表格，如符號表。在目標(biāo)代碼運行階段，存儲區(qū)中主要是目標(biāo)代碼和數(shù)據(jù)，編譯所用的任何信息都不再需要。解釋程序一般是把源程序一個語句一個語句的進(jìn)行語法分析，轉(zhuǎn)換為一種內(nèi)部表示形式，存放在源代碼區(qū)。在解釋程序工作的整個過程中，源程序、符號表等內(nèi)容始終存放在存儲區(qū)中，并且存放格式要設(shè)計得易于使用和修改2022/9/21編譯原理引論35編譯程序的運行區(qū)內(nèi)容源程序緩沖區(qū)名字表目標(biāo)代碼緩沖區(qū)編譯程序用中間表示及各種表格目標(biāo)代碼區(qū)數(shù)據(jù)區(qū)編譯時運行時2022/9/21編譯原理引論36解釋程序的存儲區(qū)內(nèi)容解釋系統(tǒng)源程序工作單元及名字表標(biāo)號表緩沖區(qū)（輸入輸出）棧區(qū)2022/9/21編譯原理引論

14、37Java語言環(huán)境編譯環(huán)境運行環(huán)境(Java平臺)Java源程序(*.java)Java編譯程序JavaBYTECODES(*.class)類轉(zhuǎn)載器BYTECODES驗證器Java類庫Java虛擬機解釋程序即時編譯程序硬件JavaBYTECODES(來自本地的或經(jīng)由網(wǎng)絡(luò)的)2022/9/21編譯原理引論381.6 處理源程序的軟件工具語言的結(jié)構(gòu)化編輯器語言程序的調(diào)試工具程序格式化工具語言程序測試工具靜態(tài)分析器動態(tài)測試器程序理解工具高級語言之間的轉(zhuǎn)換工具2022/9/21編譯原理引論391.7 程序設(shè)計語言范型強制（命令）式語言(imperative language)也稱過程式語言。代表語言

15、：C, FORTRAN, Pascal這種語言是面向動作的，即一個計算過程看作是一系列動作。其動作是命令驅(qū)動，以語句形式表示。一個強制式語言程序由一系列的語句組成，每個語句的執(zhí)行引起若干存儲單元中的值的改變。強制式語言執(zhí)行的解釋與萬諾曼機的體系結(jié)構(gòu)對應(yīng)：順序執(zhí)行指令，通過機器狀態(tài)（內(nèi)存，各種寄存器和外存的內(nèi)容）的改變理解指令執(zhí)行的含義。2022/9/21編譯原理引論40程序設(shè)計語言范型函數(shù)式語言(functional language)也成為應(yīng)用式語言。代表語言：ML, LISP函數(shù)式語言更注重程序所表示的功能，而不是一個語句接一個語句地執(zhí)行。程序的開發(fā)過程是從前面已有的函數(shù)出發(fā)構(gòu)造出更復(fù)雜的函數(shù)，對初始數(shù)據(jù)集進(jìn)行操作，直至最后形成的函數(shù)可以用于從初始數(shù)據(jù)計算出最終的結(jié)果。程序的執(zhí)