第一章 編譯原理引論

1、編譯原理編譯原理v計算機科學(xué)技術(shù)系計算機科學(xué)技術(shù)系v李薇李薇為什么要學(xué)習(xí)編譯原理v必修主干課程必修主干課程，操作系統(tǒng)和編譯系統(tǒng)構(gòu)成程序設(shè)計，操作系統(tǒng)和編譯系統(tǒng)構(gòu)成程序設(shè)計者與計算機之間的基本界面。者與計算機之間的基本界面。v通過學(xué)習(xí)該課程，掌握編譯的基本理論、常用的編通過學(xué)習(xí)該課程，掌握編譯的基本理論、常用的編譯技術(shù)，了解編譯過程及編譯系統(tǒng)結(jié)構(gòu)和機理。能譯技術(shù)，了解編譯過程及編譯系統(tǒng)結(jié)構(gòu)和機理。能運用所學(xué)技術(shù)解決實際問題，能運用所學(xué)技術(shù)解決實際問題，能獨立編寫一個小型獨立編寫一個小型編譯系統(tǒng)編譯系統(tǒng)。v此外，通過學(xué)習(xí)編譯原理可以更好地理解程序語言此外，通過學(xué)習(xí)編譯原理可以更好地理解程序語言的內(nèi)

2、部機制的內(nèi)部機制, ,從而更好地理解和運用程序設(shè)計語言。從而更好地理解和運用程序設(shè)計語言。能運用編譯程序構(gòu)造的原理和技術(shù)完成能運用編譯程序構(gòu)造的原理和技術(shù)完成相關(guān)軟件工相關(guān)軟件工具的設(shè)計和開發(fā)具的設(shè)計和開發(fā)工作。工作。課程內(nèi)容課程內(nèi)容介紹編譯器構(gòu)造的一般原理和基本實現(xiàn)方法介紹的理論知識：形式語言和自動機理論、語法制導(dǎo)的定義和屬性文法、類型論等強調(diào)形式描述技術(shù)和自動生成技術(shù)課課 程程 簡簡 介介先行課程先行課程 高等數(shù)學(xué)、離散數(shù)學(xué)、匯編語言、數(shù)據(jù)結(jié)構(gòu)教材和參考書教材和參考書v李建中譯，李建中譯，編譯原理編譯原理（龍書）（龍書），機械工業(yè)出版社，機械工業(yè)出版社v陳火旺陳火旺 劉春林等，劉春林等，程

3、序設(shè)計語言編譯原理程序設(shè)計語言編譯原理，國防工，國防工業(yè)出版社業(yè)出版社v呂映芝，張素琴等，呂映芝，張素琴等，編譯原理編譯原理，清華大學(xué)出版社，清華大學(xué)出版社v李冬梅，施?；?，李冬梅，施海虎，編譯原理編譯原理，人民郵電出版社，人民郵電出版社課程特點：理論性強，算法復(fù)雜課程特點：理論性強，算法復(fù)雜v平時（平時（20%）無故曠課：無故曠課：5一本教材，一本教材，認真聽課認真聽課：以講義為主，做適當(dāng)?shù)墓P：以講義為主，做適當(dāng)?shù)墓P記記認真完成課堂和課后認真完成課堂和課后作業(yè)作業(yè)完成要求的完成要求的課外實驗課外實驗內(nèi)容內(nèi)容v期末（期末（80%）:閉卷筆試閉卷筆試第一章第一章 編譯概述編譯概述 掌握編譯程序中

4、所涉及的有關(guān)名詞術(shù)語掌握編譯程序中所涉及的有關(guān)名詞術(shù)語2.2.理解編譯程序總的框架，明確編譯程序工理解編譯程序總的框架，明確編譯程序工作的基本過程及各階段的基本任務(wù)作的基本過程及各階段的基本任務(wù)教學(xué)目標(biāo)教學(xué)目標(biāo)1.1. .程序的翻譯程序的翻譯1.2. 編譯的過程編譯的過程1.3. 編譯程序的邏輯結(jié)構(gòu)編譯程序的邏輯結(jié)構(gòu)1.4. 編譯程序的生成編譯程序的生成 1.5. 編譯技術(shù)的應(yīng)用及發(fā)展編譯技術(shù)的應(yīng)用及發(fā)展教學(xué)內(nèi)容1.1 程序的翻譯程序的翻譯v語言和翻譯語言和翻譯：語言是人類交流思想和信息的工具。如自然語言，世界上存在著許多種語言，各國之間要交流信息,就要有各種語言之間的翻譯。計算機語言同樣是豐

5、富多彩的。程序語言的分類v低級語言（低級語言（Low level Language)字位碼、機器語言、匯編語言字位碼、機器語言、匯編語言特點：與特定的機器有關(guān)，功效高，但使用復(fù)特點：與特定的機器有關(guān)，功效高，但使用復(fù)雜、繁雜、繁瑣、費時、易出錯瑣、費時、易出錯v高級語言高級語言 v - Fortran、Pascal、C 語言等語言等特點：不依賴具體機器，移植性好、對用戶要特點：不依賴具體機器，移植性好、對用戶要求低、易使用、易維護等。求低、易使用、易維護等。v計算機硬件只懂自己的指令系統(tǒng)，那么它是如何識別除機器語言以外的另一種語言呢？v解決這一問題的方法：翻譯程序！翻譯程序v翻譯程序：能夠把某

6、一種語言程序（稱為源語言源語言程序）轉(zhuǎn)換成另一種語言程序（稱為目標(biāo)語言目標(biāo)語言程序）的一個程序，而后者與前者在邏輯上是等價的。v程序翻譯的方式通常有兩種，一種是編譯方式，另一種是解釋方式。源程序翻譯程序目標(biāo)程序編譯方式編譯程序v編譯程序編譯程序：如果一個翻譯程序的源語言源語言是某種高級語言，其目標(biāo)語言目標(biāo)語言是相對于某一計算機的匯編語言或機器語言，則稱這種翻譯程序為編譯程序（或稱為編譯器）。v若編譯生成的目標(biāo)程序不是機器代碼，而是匯編語言程序，則還要增加一個會變程序?qū)⑵鋾優(yōu)闄C器代碼。源程序（高級語言編寫）編譯程序目標(biāo)程序（機器語言或匯編語言編寫）匯編程序v如果一個翻譯程序的源語言是某種匯編語

7、言，其目標(biāo)語言是某一計算機的機器語言，則稱這種翻譯程序為匯編程序。源程序（匯編語言編寫）匯編程序目標(biāo)程序（機器語言編寫）解釋方式解釋程序v解釋程序解釋程序: 是一種語言處理程序，它以源程序作為輸入，但不產(chǎn)生目標(biāo)代碼，它將源程序中的語句按動態(tài)順序，逐句翻譯成課執(zhí)行代碼，一旦具備執(zhí)行條件，則立即執(zhí)行這一階段代碼得到部分結(jié)果。源程序（高級語言編寫）解釋程序計算結(jié)果v編譯和解釋程序編譯和解釋程序v編譯程序的工作相當(dāng)于載翻譯一本原著，計算機運行編譯后的目標(biāo)程序，相當(dāng)于閱讀一本譯著；而解釋程序的工作相當(dāng)于在進行同聲翻譯，計算機運行解釋程序，相當(dāng)于我們直接通過翻譯聽外賓講話。v程序的編譯執(zhí)行：程序的編譯執(zhí)行

8、：輸入數(shù)據(jù)輸入數(shù)據(jù)源程序源程序編譯程序編譯程序運行系統(tǒng)運行系統(tǒng)目標(biāo)程序目標(biāo)程序v程序的解釋執(zhí)行：如：BASIC、Prolog，問題：效率低下解釋程序解釋程序源程序源程序輸入數(shù)據(jù)輸入數(shù)據(jù)計算結(jié)果計算結(jié)果為什么解釋運行的工作效率低于編譯方式？為什么解釋運行的工作效率低于編譯方式？編譯程序與解釋程序的差別v根本區(qū)別：是否生成目標(biāo)代碼！功能功能工作結(jié)果工作結(jié)果實現(xiàn)技術(shù)上實現(xiàn)技術(shù)上解釋解釋程序程序源程序的一個執(zhí)行執(zhí)行系統(tǒng)源程序的執(zhí)行結(jié)果執(zhí)行結(jié)果執(zhí)行中間代碼編譯編譯程序程序源程序的一個轉(zhuǎn)換轉(zhuǎn)換系統(tǒng)源程序的目標(biāo)代碼目標(biāo)代碼把中間代碼轉(zhuǎn)換成目標(biāo)程序“編譯+解釋執(zhí)行”系統(tǒng)源程序源程序編譯程序編譯程序源程序的中間

9、形式輸出數(shù)據(jù)輸出數(shù)據(jù)解釋程序解釋程序輸入數(shù)據(jù)輸入數(shù)據(jù)例如例如Java語言語言.java java源程序文件.class 二進制字節(jié)碼文件Java虛擬機（JVM)本地計算機系統(tǒng)編譯編譯程序在計算機系統(tǒng)中的位置v編譯程序是一種軟件，是系統(tǒng)軟件。通常認為系統(tǒng)軟件是居于計算機系統(tǒng)中最靠近硬件的一層，其他軟件一般都通過系統(tǒng)軟件發(fā)揮作用。幾個概念幾個概念v宿主機：運行編譯程序的計算機v目標(biāo)機：運行編譯程序所產(chǎn)生的目標(biāo)代碼的計算機v交叉編譯程序：一個編譯程序產(chǎn)生不同于其宿主機的機器代碼v可變目標(biāo)編譯程序：不需要重寫編譯程序中與機器無關(guān)的部分就能改變目標(biāo)機1.2 編譯的過程編譯的過程v1.編譯程序的工作過程編

10、譯程序的工作過程v2.2.編譯器各階段的工作編譯器各階段的工作1.1.編譯程序的工作過程編譯程序的工作過程v編譯過程本身是一種語言的翻譯過程，類似于外文的翻譯。v將英文句子“I wish you success翻譯成中文。v翻譯外文資料：1、能識別出句子中的一個單詞；2、分析句子的語法結(jié)構(gòu)；3、根據(jù)句子的含義進行初步翻譯；4、對譯文進行修飾；5、寫出最后的譯文。翻譯外文資料與編譯源程序進行類比翻譯外文翻譯外文編譯程序編譯程序分析分析識別單詞識別單詞分析句子分析句子根據(jù)語義進行根據(jù)語義進行初步翻譯初步翻譯詞法分析詞法分析語法分析語法分析語義分析、生成中間代碼語義分析、生成中間代碼綜合綜合修辭加工

11、修辭加工寫出譯文寫出譯文代碼優(yōu)化代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成將編譯過程劃分為將編譯過程劃分為5個基本階段個基本階段詞法分析詞法分析語法分析語法分析語義分析及中間代碼生成語義分析及中間代碼生成代碼優(yōu)化代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成v從概念上來講，一個編譯程序的整個工作過程是劃分成階段進行的，每個階段將源程序的一種表示形式轉(zhuǎn)換成另一種表示形式，各個階段進行的操作在邏輯上是緊密連接在一起的。v事實上，某些階段可能組合在一起，這些階段間的源程序的中間表示形式就沒必要構(gòu)造出來了。1.2 編譯的過程編譯的過程v1.編譯程序的工作過程編譯程序的工作過程v2.2.編譯器各階段的工作編譯器各階段的工作2.

12、2.編譯器各階段的工作編譯器各階段的工作(1)(1)詞法分析詞法分析v詞法分析階段是編譯過程的第一個階段。這個階段的任務(wù)是從左到右一個字符一個字符地讀入源程序，對構(gòu)成源程序的字符流進行掃描和分解，根據(jù)語言的詞法規(guī)則識別出一個個具有獨立意義的最小語法單位，即單詞。v一個C源程序片斷：int a;a = a + 2;詞法分析后可能返回:單詞類型單詞類型 單詞值單詞值保留字 int標(biāo)識符 a界符 ;標(biāo)識符 a 算符(賦值) =標(biāo)識符 a算符(加) +整數(shù) 2界符 ；v詞法分析的功能如下：v識別出源程序中意義獨立的最小詞法單位單詞。v刪除無用的空格、回車和其他與輸入介質(zhì)有關(guān)的符號v刪除程序員為了提高程

13、序可讀性所加的注釋v如果發(fā)現(xiàn)錯誤則報告出錯v(2)(2)語法分析語法分析v根據(jù)根據(jù)語法規(guī)則語法規(guī)則（即語言的文法），分析并識別（即語言的文法），分析并識別出各種出各種語法成分語法成分（如表達式、語句、函數(shù)等），（如表達式、語句、函數(shù)等），并進行并進行語法正確性檢查語法正確性檢查。v通常將語法分析的結(jié)果表示為語法樹。通常將語法分析的結(jié)果表示為語法樹。例：y = x + r * 6賦值語句賦值語句標(biāo)識符標(biāo)識符表達式表達式表達式表達式表達式表達式表達式表達式標(biāo)識符標(biāo)識符整數(shù)整數(shù)標(biāo)識符標(biāo)識符表達式表達式y(tǒng)=x+r*6v語法分析的功能是進行層次分析，把源程序的單詞序列組成語法短語(表示成語法樹)。依據(jù)的

14、是語法規(guī)則。C語言的賦值語句的規(guī)則為：vv單詞序列y = x + r * 6之所以能表示成上圖的語法樹，依據(jù)的是賦值語句和表達式的語法規(guī)則。:=“=”:=“+” | “*”:=“(”“)” | | | v(3)語義分析及中間代碼生成語義分析及中間代碼生成v語義分析階段的任務(wù)是審查源程序有無語義錯誤。源程序中有些語法成分，按照語法規(guī)則去判斷，它是正確的，但它不符合語義規(guī)則。比如使用了沒有聲明的變量；或者給一個過程名賦值；或者調(diào)用函數(shù)時參數(shù)類型不合適或者參加運算的兩個變量類型不匹配等等。v比如下邊的程序片段：int arr2,c;c = arr1 * 10 ;v其中的賦值語句是符合語法規(guī)則的，但是

15、因為沒有聲明變量arr1，而存在語義錯。v中間代碼生成中間代碼生成( (可選）可選）v所謂“中間代碼”是一種結(jié)構(gòu)簡單、含義明確的記號系統(tǒng)，這種記號系統(tǒng)可以設(shè)計為多種多樣的形式，重要的設(shè)計原則為兩點：一是容易生成；二是容易將它翻譯成目標(biāo)代碼。v中間代碼的形式：中間代碼的形式： 四元式、三元式、逆波蘭表示四元式、三元式、逆波蘭表示四元式四元式其中t1、t2、t3為編譯程序引入的臨時工作單元例：y = x + r * 6運算符左運算對象 右運算對象 結(jié)果(1)inttoreal 6-t1(2)*rt1t2(3)+xt2t3(4)=t3y四元式(運算符，運算對象1，運算對象2，結(jié)果)v(4) 中間代碼

16、優(yōu)化代碼優(yōu)化( (可選）可選）v代碼優(yōu)化階段的任務(wù)是對前階段產(chǎn)生的中間代碼進行變換或進行改造，目的是使生成的目標(biāo)代碼更為高效，即省時間和省空間。(1) (itr, 6, , t1)(2) (*, r, t1, t2)(3) (+, t2, x, t3)(4) (=, t3, , y)中間代碼優(yōu)化中間代碼優(yōu)化(1) (*, r, 6.0, t1)(2) (+, t1, x, y)v這只是優(yōu)化工作的兩個方面，此外諸如公共子表達式的刪除、強度削弱、循環(huán)優(yōu)化等優(yōu)化工作將在后面的章節(jié)詳細介紹。v代碼優(yōu)化工作會降低編譯程序的編譯速度，因此編譯優(yōu)化階段常常作為可選擇階段，編譯程序具有控制機制以允許用戶在編譯

17、速度和目標(biāo)代碼的質(zhì)量間進行權(quán)衡。v思考：代碼優(yōu)化能提高編譯程序的運行效率嗎？v(5) (5) 目標(biāo)代碼生成目標(biāo)代碼生成v目標(biāo)代碼生成階段的任務(wù)是把中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。這是編譯的最后階段，它的工作與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)，這個階段的工作很復(fù)雜，涉及到硬件系統(tǒng)功能部件的運用、機器指令的選擇、各種數(shù)據(jù)類型變量的存儲空間分配以及寄存器和后緩寄存器的調(diào)度等。movr, R1mul#6.0, R1movx, R2addR1, R2movR2, y運算符左運算對象右運算對象結(jié)果(1)*r6.0t1(2)+t1xy任務(wù)：任務(wù)：把中間代碼變換成特定機器上

18、的低級語言代碼低級語言代碼目標(biāo)代碼可采用如下三種形式之一：(1)具有絕對地址的機器指令代碼。(2)匯編語言形式的目標(biāo)程序。需要經(jīng)過匯編程序匯編，以產(chǎn)生機器代碼。(3)可重定位的指令代碼。多數(shù)編譯程序所產(chǎn)生的目標(biāo)代碼都是這種類型。目標(biāo)代碼生成程序代碼優(yōu)化程序語義分析生成中間代碼語法分析程序詞法分析程序編譯過程小結(jié)編譯過程小結(jié)S.PO.Pv上述編譯過程的階段劃分是一種典型的處理模上述編譯過程的階段劃分是一種典型的處理模式，事實上并非所有的編譯程序都包括這樣幾式，事實上并非所有的編譯程序都包括這樣幾個階段。有些編譯程序并不要中間代碼，即不個階段。有些編譯程序并不要中間代碼，即不存在中間代碼生成階段；

19、有些編譯程序不進行存在中間代碼生成階段；有些編譯程序不進行優(yōu)化，優(yōu)化階段即可省去優(yōu)化，優(yōu)化階段即可省去; ;有些最簡單的編譯有些最簡單的編譯程序只有詞法分析，語法分析；語義分析和目程序只有詞法分析，語法分析；語義分析和目標(biāo)代碼生成，標(biāo)代碼生成，1.3 編譯程序的邏輯結(jié)構(gòu)編譯程序的邏輯結(jié)構(gòu) 按邏輯功能不同，可將編譯過程劃分為五個基本階 段，與此相對應(yīng)，我們將實現(xiàn)整個編譯過程的編譯程序劃 分為五個邏輯階段（即五個邏輯子過程）。每個階段中都要有：符號表管理符號表管理和錯誤處理錯誤處理診察錯誤，并能報告用戶錯誤性質(zhì)和位置出錯處理能力的優(yōu)劣是衡量編譯程序質(zhì)量好壞的一個重要指標(biāo)。填表：把源程序中的信息和編

20、譯過程中所產(chǎn)生的信息登記在表格中查表：在隨后的編譯過程中同時又要不斷的查找這些表格中的信息符號表管理符號表管理錯誤處理錯誤處理編譯程序的邏輯結(jié)構(gòu)編譯程序的邏輯結(jié)構(gòu)典型的編譯程序具有典型的編譯程序具有7個邏輯部分個邏輯部分S.PO.P語義分析及語義分析及生成中間代碼生成中間代碼程序程序代碼生成程序代碼生成程序代碼優(yōu)化代碼優(yōu)化程序程序語法分析程序語法分析程序詞法分析程序詞法分析程序錯錯誤誤處處理理符符號號表表管管理理 詞法分析：識別單詞，至少分以下幾大類：關(guān)鍵字（保留字）、標(biāo)識符、字面量、特殊符號； 語法分析：得到語言結(jié)構(gòu)并以樹的形式表示 語義分析：考察結(jié)構(gòu)正確的句子是否語義合法，可修改樹結(jié)構(gòu)；

21、中間代碼生成（可選）：生成一種既接近目標(biāo)語言，又與具體機器無關(guān)的表示，便于優(yōu)化與代碼生成；（到目前為止，編譯器與解釋器可以一致） 中間代碼優(yōu)化（可選）：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化等；優(yōu)化實際上是一個等價變換，變換前后的指令序列完成同樣的功能，但是，在占用的空間上和程序執(zhí)行的時間上都更省、更有效。 目標(biāo)代碼生成：不同形式的目標(biāo)代碼匯編、可重定位、絕對機器指令; 符號表管理：合理組織符號，便于各階段查找、填寫等； 出錯處理：錯誤的種類詞法錯、語法錯、靜態(tài)語義錯、動態(tài)語義錯。編譯器掃描的遍數(shù)v遍（趟）遍（趟）：是對源程序或源程序的中間結(jié)果從頭到尾掃描一遍，并作有關(guān)加工處理，生成新的中間結(jié)果或目標(biāo)程

22、序。v例如：詞法分析器對輸入源程序進行第一遍掃描，語法分析進行第二遍掃描v但一個階段對應(yīng)一遍掃描的工作方式是邏輯上的，由于多次掃描的方式需要大量的存儲空間存放中間表示，并且會增加一些不必要的輸入輸出操作，因此編譯器往往把若干個階段的工作結(jié)合起來，對應(yīng)一遍掃描，從而減少對程序的掃描遍數(shù)。v一個編譯程序應(yīng)分成幾遍，如何劃分，是與源程序、設(shè)計要求、硬件設(shè)備等諸因素有關(guān)的，因地難于統(tǒng)一劃定。v在主存可能的前提下，一般遍數(shù)盡可能少一點為好。但并不是每種語言都可以用單遍編譯程序?qū)崿F(xiàn)。編譯階段的組合v在前面所討論的編譯過程中階段的劃分是編譯程序的邏輯組織。有時，常常把編譯的過程分為前端前端(front en

23、d)和后端后端(back end)，前端的工作主要依賴于源語言而與目標(biāo)機無關(guān), 后端工作依賴于目標(biāo)機而一般不依賴源語言。根據(jù)編譯程序各部分功能，將編譯程序分成根據(jù)編譯程序各部分功能，將編譯程序分成前端前端和和后端后端 前端前端：通常將與：通常將與源程序源程序有關(guān)的編譯部分稱為前端。有關(guān)的編譯部分稱為前端。 詞法分析、語法分析、語義分析、中間代碼生成詞法分析、語法分析、語義分析、中間代碼生成 -分析部分分析部分 特點：與特點：與源語言源語言有關(guān)有關(guān) 后端后端：與：與目標(biāo)機目標(biāo)機有關(guān)的部分稱為后端。有關(guān)的部分稱為后端。 代碼優(yōu)化、代碼生成代碼優(yōu)化、代碼生成-綜合部分綜合部分 特點：與特點：與目標(biāo)機

24、目標(biāo)機有關(guān)有關(guān)編譯程序的前端和后端編譯程序的前端和后端.java java源程序文件.class 二進制字節(jié)碼文件Java虛擬機（JVM)本地計算機系統(tǒng)編譯同一前端同一前端+ +不同后端不同后端 不同機器構(gòu)成同一語言的編譯程序不同機器構(gòu)成同一語言的編譯程序例如例如JavaJava語言語言 不同前端不同前端+ +同一后端同一后端 同一機器生成幾個語言的編譯程序同一機器生成幾個語言的編譯程序例如例如GCCGCC 編譯程序集合編譯程序集合1.4 編譯程序的生成編譯程序的生成v早期人們用匯編語言編寫編譯程序，但其效率低，實現(xiàn)困難，比如FORTRAN語言編譯器18年才完成。v專門的編譯編譯工具，可以支持

25、編譯程序某些部分的自動生成。比如：LEX和YACC等。v說到一個編譯程序， 一定要知道它的源語言是什麼，目標(biāo)語言是什麼，還有它的實現(xiàn)語言是什麼。常使用T型圖來表示一個編譯程序所涉及的三個語言。S：源語言 O：目標(biāo)語言 T：編譯程序?qū)崿F(xiàn)語言S OTv開發(fā)編譯程序的途徑開發(fā)編譯程序的途徑:v自展法自展法v工具法工具法v自動生成法自動生成法v移植法移植法自展法自展法v利用A機器上已有的用A代碼編寫的L1語言的編譯程序，把用L1語言編寫的L2語言的編譯程序進行編譯，得到A機器代碼實現(xiàn)的L2語言的編譯程序。表示為：L 2 語言A代碼L1語言L 1 語言A代碼A代碼L 2 語言A代碼A代碼v或者表示為：L 2 語言A代碼L1語言L 1 語言A代碼A代碼L 2 語言A代碼A代碼v編譯程序移植：編譯程序移植：用A機器上的L語言編寫能在機器B上運行的L語言的編譯程序v先用L語言編寫出在A機