中國石油大學(xué),編譯原理 第01章、編譯程序概論-3

1、1編譯原理主講： 馬 力單位： 計通學(xué)院 計算機科學(xué)系Email: 電話: 138542604872前 言n課程內(nèi)容n課程特點n課程性質(zhì)n學(xué)習(xí)章節(jié)n參考書n教學(xué)安排n考試安排課程內(nèi)容n基本內(nèi)容是介紹編譯程序構(gòu)造的基本原 理、方法和技術(shù)，包括詞法分析、語法分析、語義分析與中間代碼產(chǎn)生、代碼優(yōu)化及目標(biāo)代碼產(chǎn)生等。n簡言之，就是介紹如何將源程序翻譯成目標(biāo)代碼程序。3課程性質(zhì)n專業(yè)基礎(chǔ)課，原理性課程，限選。n上世紀(jì)50年代，F(xiàn)ORTRAN語言及編譯系統(tǒng)產(chǎn)生標(biāo)志著編譯技術(shù)開始形成。n60年代70年代是研究高峰期。n60年代中期開始在高校中開設(shè)課程。n80年代開始作為計算機科學(xué)與技術(shù)專業(yè)的必修基礎(chǔ)課程。4

2、課程特點n理論與實踐的結(jié)合 理論：編譯基礎(chǔ)理論 實踐：自己編寫編譯器n涉及的知識面廣泛 程序設(shè)計語言、計算機體系結(jié)構(gòu)、語言理論及算法、離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)等。n涉及的原理、方法和技術(shù)具有十分普遍的意義 編譯課程蘊含著計算學(xué)科中解決問題的思路、抽象和方法，這些與高等數(shù)學(xué)一樣，使你“享用一輩子”。56學(xué) 習(xí) 章 節(jié)第一章 編譯程序概論(一般了解)第二章 PL/0編譯程序的實現(xiàn)(自學(xué))第三章 文法和語言第四章 詞法分析第五章 自頂向下語法分析 - LL（1）文法第六章 自底向上語法分析 -優(yōu)先分析法第七章 自底向上語法分析 -LR分析法第八章 語法制導(dǎo)翻譯及代碼生成7參考書1編譯原理（第二版），張素琴

3、、呂映芝、蔣維杜、戴桂蘭編著，清華大學(xué)出版社，2013年版 (教材)2程序設(shè)計語言編譯原理（第三版），陳火旺、劉春林等編著，國防工業(yè)出版社，2000年3編譯原理與編譯程序構(gòu)造，高仲儀等編著，北京航空航天大學(xué)出版社，2001年4編譯原理，胡倫駿、徐蘭芳、劉建農(nóng)編，電子工業(yè)出版社，2002年85 龍書（Dragon book）英文名：Compilers: Principles,Techniques,and Tools作者：Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman中文名：編譯原理技術(shù)和工具6 虎書（Tiger book）英文名：Modern Compiler

4、Implementation in C作者：Andrew W.Appel,with Jens Palsberg中文名：現(xiàn)代編譯原理-C語言描述7 鯨書（Whale book）英文名：Advanced Compiler Design and Implementation作者：Steven S.Muchnick中文名：高級編譯器設(shè)計與實現(xiàn)9教學(xué)安排n教學(xué): 48課時 幻燈片+板書教學(xué)n課后作業(yè)：從第3章起一般每章交1次，大約5次n課終復(fù)習(xí)、串講一次n要求：課后復(fù)習(xí)、認(rèn)真作業(yè)10考試安排 考核范圍:重點考察編譯原理中的基本概念，編譯基礎(chǔ)理論以及編譯過程的各個階段的功能和實現(xiàn)方法?？己朔绞剑浩谀┛己伺c

5、平時成績相結(jié)合的方式。1）期末考核： 筆試、閉卷，答題時限120分鐘，占70%；2）平時成績： 視平時考勤、表現(xiàn)、課堂提問、作業(yè)完成情況等給分，占30%。 以上成績累計60分以上（包括60分）算考核通過。11第一章 編譯程序概論1.1 什么是編譯程序1.2 編譯過程概述1.3 編譯程序的結(jié)構(gòu)1.4 編譯階段的組合1.5 編譯技術(shù)的發(fā)展和應(yīng)用 121.1 什么是編譯程序(compiler)一、基本概念 1. 編譯程序 編譯程序是現(xiàn)代計算機系統(tǒng)的基本組成部分。 從功能上看，一個編譯程序就是一個語言翻譯程序，它把一種語言(稱作源語言)書寫的程序翻譯成另一種語言(稱作目標(biāo)語言)的等價的程序。 13程序

6、設(shè)計語言低級語言高級語言匯編語言機器語言翻譯程序翻譯程序2.程序設(shè)計語言及其翻譯源程序 目標(biāo)程序翻譯程序14翻譯程序Translator匯編程序Assembler編譯程序Compiler 解釋程序Interpreter高級語言3.翻譯程序154. 高級語言程序處理的兩種方法(1) 編譯途徑 方法一：源程序運行程序目標(biāo)程序編譯程序結(jié)果初始數(shù)據(jù)編譯階段運行階段164.高級語言程序處理的兩種方法(1) 編譯途徑 方法二：源程序運行程序目標(biāo) 代碼編譯程序結(jié)果初始數(shù)據(jù)編譯階段運行階段匯編語言匯編程序匯編階段17(2) 解釋途徑源程序結(jié)果解釋程序初始數(shù)據(jù)直接解釋執(zhí)行、中間代碼與編譯的主要區(qū)別：解釋程序不產(chǎn)

7、生目標(biāo)代碼4.高級語言程序處理的兩種方法18編譯程序 vs. 解釋程序編譯解釋19二、編譯程序的功能n功能術(shù)語編譯程序的源語言(源程序S)編譯程序的目標(biāo)語言(目標(biāo)程序O、T)編譯程序的實現(xiàn)語言(I)S OI 高級語言書寫的程序 編譯程序低級語言程序S TI20三、編譯程序在軟件中的地位 軟件 系統(tǒng)軟件 語言處理系統(tǒng)操作系統(tǒng)編譯系統(tǒng)裸機1. 屬于系統(tǒng)軟件類212. 計算機軟件相關(guān)概念 計算機系統(tǒng)中的程序及其文檔軟件 居于計算機系統(tǒng)中最靠近硬件的一層，其他軟件一般都通過系統(tǒng)軟件發(fā)揮作用。它和具體的應(yīng)用領(lǐng)域無關(guān)，如編譯系統(tǒng)和操作系統(tǒng)等系統(tǒng)軟件 把軟件語言書寫的各種程序處理成可在計算機上執(zhí)行的程序語言

8、處理系統(tǒng) 用于書寫軟件的語言。它主要包括需求定義語言、功能性語言、設(shè)計性語言、程序設(shè)計語言以及文檔語言軟件語言22預(yù)處理器編譯器匯編器裝配連接編輯骨架程序 源程序 目標(biāo)匯編程序 可重定位機器代碼 絕對機器碼可重定位目標(biāo)文件庫3. 語言處理過程23四. 編譯工作重要貢獻(xiàn)者nGrace Hopper ，計算機軟件的第一夫人n1906年12月9日出生在紐約市的一個海軍世家 ，1992年1月1日 去世；n1959年，成功地研制出第一個商用編程語言COBOL ；n世界上第三位程序員 ；nBug發(fā)現(xiàn)者和千年蟲制造者。24John Cocke ，“IBM小子”n生于1925年，2002年去世n1987圖靈獎

9、n提出RISC概念n編譯器優(yōu)化奠基人25A.J. Perlis n1966年，第一位圖靈獎n獲獎原因：在先進(jìn)編程技術(shù)和編譯架構(gòu)方面的貢獻(xiàn)。n1990年去世Michael O. Rabin、Dana S. Scottn1976年圖靈獎n獲獎原因：論文“有限自動機與它們的決策問題”，被證明具有巨大的價值。n.程序設(shè)計語言、編譯理論與方法約占1/3261.2 編譯過程概述n所謂編譯過程是指將高級語言程序翻譯為等價的目標(biāo)程序的過程。n以翻譯外文資料為例，對比翻譯過程：1. 能識別出句子中的一個單詞2. 分析句子的語法結(jié)構(gòu)3. 根據(jù)句子的含義進(jìn)行初步翻譯4. 對譯文進(jìn)行修飾5. 寫出最后的譯文27n翻譯

10、和編譯工作的比較翻譯外文編譯程序分析識別單詞分析句子根據(jù)語義進(jìn)行初步翻譯詞法分析語法分析語義分析生成中間代碼綜合修辭加工寫出譯文代碼優(yōu)化目標(biāo)代碼生成2829n 編譯邏輯過程:詞法分析語法分析語義分析中間代碼生成代碼優(yōu)化目標(biāo)代碼生成n 編譯輔助工作:表格管理出錯處理301. 詞法分析 掃描源程序的ASCII碼序列，拼出每一個單詞，并把每個單詞的ASCII碼序列替換為所謂的機內(nèi)表示TOKEN形式，這時還檢查詞法錯誤。但詞法分析階段不依靠語法關(guān)系。 簡單地說，就是從左至右讀字符流的源程序、識別(拼)單詞。 例： position = initial + rate * 60;31詞法分析 positi

11、on = initial + rate * 60;單詞類型單詞值 標(biāo)識符1(id1) position 算符(賦值) = 標(biāo)識符2(id2) initial 算符(加) + 標(biāo)識符3(id3) rate 算符(乘) * 整數(shù) 60 分號 ；32又如一個C源程序片斷： int a; a = a + 2;詞法分析后可能返回:單詞類型單詞值 保留字 int標(biāo)識符(變量名) a界符 ;標(biāo)識符(變量名) a算符(賦值) =標(biāo)識符(變量名) a算符(加) +整數(shù) 2界符 ；有關(guān)術(shù)語n詞法分析(lexical analysis or scanning) The stream of characters ma

12、king up a source program is read from left to right and grouped into tokens, which are sequences of characters that have a collective meaning.n單詞-tokenn保留字-reserved wordn標(biāo)識符-identifier(user-defined name)33342. 語法分析n功能：層次分析。依據(jù)源程序的語法規(guī)則把源程序的單詞序列組成語法短語(表示成語法樹). 掃描對象可能是源程序的ASCII碼序列，也可能是詞法分析后的TOKEN序列。主要任務(wù)

13、是檢查源程序的形式語法錯誤,每當(dāng)發(fā)現(xiàn)錯誤時將輸出有關(guān)信息。position = initial + rate * 60 ;規(guī)則 :=“=” :=“+” :=“*” :=“(”“)” := := :=35 賦值語句標(biāo)識符表達(dá)式表達(dá)式+表達(dá)式表達(dá)式標(biāo)識符整數(shù)標(biāo)識符=表達(dá)式*36id1=id2+id3*N=+N 60*id1 Positionid2 initialid3 rate有關(guān)術(shù)語n語法分析(syntax analysis or parsing) The purpose of syntax analysis is to determine the source programs phrase

14、structure. This process is also called parsing. The source program is parsed to check whether it conforms to the source languages syntax, and to construct a suitable representation of its phrase structure.37383. 語義分析n分析語法成份的含義，進(jìn)行語義上的正確性檢查，為代碼生成階段收集類型信息。n語義檢查包括： 變量是否定義過； 類型是否正確； 是否用了0作除數(shù)等。39例:main p(

15、);float rate;void initial;position = initial + rate * 60; /* error */ /* error */ /* warning */;40又如: n int arr 2,abc;n abc = arr * 10;nmain p();n float rate;n float initial;n float position ;n n position = initial + rate * 60;41語義分析例：60=+*Id1 positionId2 initialId3 rateinttoreal有關(guān)術(shù)語n語義分析(semantic a

16、nalysis) The parsed program is further analyzed to determine whether it conforms to the source languages contextual constraints: scope rules, type rules e.g. To relate each applied occurrence of an identifier in the source program to the corresponding declaration. 42434.中間代碼生成n根據(jù)相應(yīng)語義，進(jìn)行初步翻譯，生成中間代碼（即

17、一種結(jié)構(gòu)簡單，含義明確的記號系統(tǒng)）。n掃描對象通常是語法分析后的結(jié)果，這部分把源程序的TOKEN序列轉(zhuǎn)換成更接近目標(biāo)代碼的中間代碼的序列。n生成中間代碼有利于代碼優(yōu)化和目標(biāo)代碼的移植。 源程序的內(nèi)部(中間)表示： 后綴式、三元式、四元式、樹、波蘭式、逆波蘭式等例如：后綴式：ab+c* 表示(a+b)*c三元式： ( *，id3，t1)四元式： ( *，id3，t1，t2) 4445中間代碼生成例：將 id1= id2 + id3 * 60 表示為四元式：(1)(inttoreal,60-t1)(2)(*,id3t1t2)(3)(+,id2t2t3)(4)(=,t3-id1)有關(guān)術(shù)語n中間代碼生

18、成(intermediate code generation) This is where the intermediate representation of the source program is created. We want this representation to be easy to generate, and easy to translate into the target program. The representation can have a variety of forms, but a common one is called three-address

19、code or 4- tuple code.46475.代碼優(yōu)化p對中間代碼進(jìn)行加工變換，以得到高質(zhì)量的目標(biāo)代碼。p 按代碼級別，可分成源代碼優(yōu)化、中間代碼優(yōu)化和目標(biāo)代碼優(yōu)化三種。p 其中：中間代碼優(yōu)化掃描對象是中間代碼,任務(wù)是把優(yōu)化前的中間代碼轉(zhuǎn)換成可產(chǎn)生高質(zhì)量目標(biāo)代碼的中間代碼。p 優(yōu)化工作包括表達(dá)式優(yōu)化、公共子表達(dá)式優(yōu)化、不變表達(dá)式外提和削減運算強度等。48代碼優(yōu)化例：t1 = b* c t1 = b* c t2 = t1+ 0 優(yōu)化后： a= t1 + t1t3 = b* ct4 = t2 + t3a = t4代碼優(yōu)化舉例 運算符左運算對象右運算對象結(jié)果(1)IntToReal6-t1

20、(2)*rt1t2(3)+xt2t3(4)=-t3y 運算符左運算對象右運算對象結(jié)果(1)*r6.0t1(2)+xt1y49有關(guān)術(shù)語n代碼優(yōu)化(Intermediate code optimization) The optimizer accepts input in the intermediate representation and output a version still in the intermediate representation .In this phase, the compiler attempts to produce the smallest, fastest

21、and most efficient running result by applying various techniques.50516.目標(biāo)代碼生成n把中間代碼變換成特定機器上的低級語言代碼。n掃描對象是中間代碼，任務(wù)是從中間代碼產(chǎn)生目標(biāo)代碼，這一部分的工作與目標(biāo)機緊密相關(guān)，其它部分的工作幾乎與目標(biāo)機無關(guān)。目標(biāo)代碼生成舉例 運算符左運算對象右運算對象結(jié)果(1)*r6.0t1(2)+xt1yMOV r, R1MUL#6.0, R1MOV x, R2ADDR1, R2MOV R2, y52531.3 編譯程序的結(jié)構(gòu) (components)n詞法分析程序n語法分析程序n語義分析程序n中間代碼

22、生成程序n代碼優(yōu)化程序n目標(biāo)代碼生成程序n符號表管理程序n出錯處理程序54一.表格管理n編譯過程中，需經(jīng)常收集、記錄或查詢程序中所出現(xiàn)的各種量的有關(guān)屬性（信息）。為此，編譯程序需要建立一批不同用途的表格（常數(shù)表、變量表、關(guān)鍵字表等符號表）。n除此之外，根據(jù)不同的分析方法，編譯程序還保持一些專用的表格（LL分析表、LR分析表、狀態(tài)矩陣等）。n合理地設(shè)計和使用表格是編譯過程中一個重要的問題55二.出錯處理n出錯處理包括詞法錯誤、語法錯誤、靜態(tài)語義錯誤、動態(tài)語義錯誤等；n詞法錯誤：不符合構(gòu)詞規(guī)則的錯誤，如非法字符；n語法錯誤：不符合語法規(guī)則的錯誤，如括號不匹配，缺少分號；n語義錯誤：不符合語義規(guī)則的

23、錯誤，如類型不一致，作用域錯誤，變量未定義；n出錯處理模塊的作用是：檢查錯誤、報告出錯信息、排錯、恢復(fù)編譯工作。n加上表格管理和出錯處理部分后，一個典型的編譯程序結(jié)構(gòu)如下圖所示。典型的編譯程序結(jié)構(gòu)56n編譯前端：與源語言有關(guān)，如詞法分析，語法分析，語義分析與中間代碼產(chǎn)生，與機器無關(guān)的優(yōu)化n編譯后端：與目標(biāo)機有關(guān)，與目標(biāo)機有關(guān)的優(yōu)化，目標(biāo)代碼產(chǎn)生1.4 編譯階段的組合源語言中間語言目標(biāo)語言前端后端一. 前端與后端同一前端+不同后端 不同機器構(gòu)成同一語言的編譯程序nJava編譯58不同前端+同一后端 同一機器生成幾個語言的編譯程序nGCC59n遍：對源程序（包括源程序中間形式）從頭到尾掃描一次，并做有關(guān)的加工處理，生成新的源程序中間形式或目標(biāo)程序，通常稱之為一遍（也稱一趟）。n上一遍的結(jié)果是下一遍的