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

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

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

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

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

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

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

7、解釋程序不產(chǎn)生目標(biāo)代碼4.高級(jí)語言程序處理的兩種方法n18編譯程序 vs. 解釋程序編譯解釋n19二、編譯程序的功能n功能術(shù)語編譯程序的源語言(源程序S)編譯程序的目標(biāo)語言(目標(biāo)程序O、T)編譯程序的實(shí)現(xiàn)語言(I)S OI 高級(jí)語言書寫的程序 編譯程序低級(jí)語言程序S TIn20三、編譯程序在軟件中的地位軟件系統(tǒng)軟件語言處理系統(tǒng)操作系統(tǒng)編譯系統(tǒng)裸機(jī)1. 屬于系統(tǒng)軟件類n212. 計(jì)算機(jī)軟件相關(guān)概念n22預(yù)處理器編譯器匯編器裝配連接編輯骨架程序 源程序 目標(biāo)匯編程序 可重定位機(jī)器代碼 絕對機(jī)器碼可重定位目標(biāo)文件庫3. 語言處理過程n23四. 編譯工作重要貢獻(xiàn)者nGrace Hopper ，計(jì)算機(jī)軟

8、件的第一夫人n1906年12月9日出生在紐約市的一個(gè)海軍世家 ，1992年1月1日 去世；n1959年，成功地研制出第一個(gè)商用編程語言COBOL ；n世界上第三位程序員 ；nBug發(fā)現(xiàn)者和千年蟲制造者。n24John Cocke ，“IBM小子”n生于1925年，2002年去世n1987圖靈獎(jiǎng)n提出RISC概念n編譯器優(yōu)化奠基人n25A.J. Perlis n1966年，第一位圖靈獎(jiǎng)n獲獎(jiǎng)原因：在先進(jìn)編程技術(shù)和編譯架構(gòu)方面的貢獻(xiàn)。n1990年去世Michael O. Rabin、Dana S. Scottn1976年圖靈獎(jiǎng)n獲獎(jiǎng)原因：論文“有限自動(dòng)機(jī)與它們的決策問題”，被證明具有巨大的價(jià)值。n

9、.程序設(shè)計(jì)語言、編譯理論與方法約占1/3n261.2 編譯過程概述n27n所謂編譯過程是指將高級(jí)語言程序翻譯為等價(jià)的目標(biāo)程序的過程。n以翻譯外文資料為例，對比翻譯過程：n28n翻譯和編譯工作的比較翻譯外文編譯程序分析識(shí)別單詞分析句子根據(jù)語義進(jìn)行初步翻譯詞法分析語法分析語義分析生成中間代碼綜合修辭加工寫出譯文代碼優(yōu)化目標(biāo)代碼生成n29n 編譯邏輯過程:詞法分析語法分析語義分析中間代碼生成代碼優(yōu)化目標(biāo)代碼生成n 編譯輔助工作:表格管理出錯(cuò)處理n301. 詞法分析 掃描源程序的ASCII碼序列，拼出每一個(gè)單詞，并把每個(gè)單詞的ASCII碼序列替換為所謂的機(jī)內(nèi)表示TOKEN形式，這時(shí)還檢查詞法錯(cuò)誤。但詞

10、法分析階段不依靠語法關(guān)系。 簡單地說，就是從左至右讀字符流的源程序、識(shí)別(拼)單詞。 例： position = initial + rate * 60;n31詞法分析 position = initial + rate * 60;單詞類型單詞值 標(biāo)識(shí)符1(id1) position 算符(賦值) = 標(biāo)識(shí)符2(id2) initial 算符(加) + 標(biāo)識(shí)符3(id3) rate 算符(乘) * 整數(shù) 60 分號(hào) ；n32又如一個(gè)C源程序片斷： int a; a = a + 2;詞法分析后可能返回:單詞類型單詞值 保留字 int標(biāo)識(shí)符(變量名) a界符 ;標(biāo)識(shí)符(變量名) a算符(賦值) =

11、標(biāo)識(shí)符(變量名) a算符(加) +整數(shù) 2界符 ；n33有關(guān)術(shù)語n詞法分析(lexical analysis or scanning)The stream of characters making 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)識(shí)符-identifier(user-defined name)n34

12、2. 語法分析n功能：層次分析。依據(jù)源程序的語法規(guī)則把源程序的單詞序列組成語法短語(表示成語法樹). 掃描對象可能是源程序的ASCII碼序列，也可能是詞法分析后的TOKEN序列。主要任務(wù)是檢查源程序的形式語法錯(cuò)誤,每當(dāng)發(fā)現(xiàn)錯(cuò)誤時(shí)將輸出有關(guān)信息。position = initial + rate * 60 ;規(guī)則 :=“=” :=“+” :=“*” :=“(”“)” := := :=n35 賦值語句標(biāo)識(shí)符表達(dá)式表達(dá)式+表達(dá)式表達(dá)式標(biāo)識(shí)符整數(shù)標(biāo)識(shí)符=表達(dá)式*n36id1=id2+id3*N=+N 60*id1 Positionid2 initialid3 raten37有關(guān)術(shù)語n語法分析(synt

13、ax analysis or parsing)The purpose of syntax analysis is to determine the source programs phrase 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 structur

14、e.n383. 語義分析n分析語法成份的含義，進(jìn)行語義上的正確性檢查，為代碼生成階段收集類型信息。n語義檢查包括：變量是否定義過；類型是否正確；是否用了0作除數(shù)等。n39例:main p();float rate;void initial;position = initial + rate * 60; /* error */ /* error */ /* warning */;n40又如: n int arr 2,abc;n abc = arr * 10;nmain p();n float rate;n float initial;n float position ;n n position

15、= initial + rate * 60;n41語義分析例：60=+*Id1 positionId2 initialId3 rateinttorealn42有關(guān)術(shù)語n語義分析(semantic analysis)The parsed program is further analyzed to determine whether it conforms to the source languages contextual constraints: scope rules, type rulese.g. To relate each applied occurrence of an ident

16、ifier in the source program to the corresponding declaration. n434.中間代碼生成n根據(jù)相應(yīng)語義，進(jìn)行初步翻譯，生成中間代碼（即一種結(jié)構(gòu)簡單，含義明確的記號(hào)系統(tǒng)）。n掃描對象通常是語法分析后的結(jié)果，這部分把源程序的TOKEN序列轉(zhuǎn)換成更接近目標(biāo)代碼的中間代碼的序列。n生成中間代碼有利于代碼優(yōu)化和目標(biāo)代碼的移植。 n44源程序的內(nèi)部(中間)表示： 后綴式、三元式、四元式、樹、波蘭式、逆波蘭式等例如：后綴式：ab+c* 表示(a+b)*c三元式： ( *，id3，t1)四元式： ( *，id3，t1，t2) n45中間代碼生成例：將

17、id1= id2 + id3 * 60 表示為四元式：(1)(inttoreal,60-t1)(2)(*,id3t1t2)(3)(+,id2t2t3)(4)(=,t3-id1)n46有關(guān)術(shù)語n中間代碼生成(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 targe

18、t program. The representation can have a variety of forms, but a common one is called three-address code or 4- tuple code.n475.代碼優(yōu)化p對中間代碼進(jìn)行加工變換，以得到高質(zhì)量的目標(biāo)代碼。p 按代碼級(jí)別，可分成源代碼優(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á)式外提和削減運(yùn)算強(qiáng)度等。n48代碼優(yōu)化例：t1 = b* c t

19、1 = b* c t2 = t1+ 0 優(yōu)化后： a= t1 + t1t3 = b* ct4 = t2 + t3a = t4n49代碼優(yōu)化舉例 運(yùn)算符左運(yùn)算對象右運(yùn)算對象結(jié)果(1)IntToReal6-t1(2)*rt1t2(3)+xt2t3(4)=-t3y 運(yùn)算符左運(yùn)算對象右運(yùn)算對象結(jié)果(1)*r6.0t1(2)+xt1yn50有關(guān)術(shù)語n代碼優(yōu)化(Intermediate code optimization)The optimizer accepts input in the intermediate representation and output a version still in

20、the intermediate representation .In this phase, the compiler attempts to produce the smallest, fastest and most efficient running result by applying various techniques.n516.目標(biāo)代碼生成把中間代碼變換成特定機(jī)器上的低級(jí)語言代碼。掃描對象是中間代碼，任務(wù)是從中間代碼產(chǎn)生目標(biāo)代碼，這一部分的工作與目標(biāo)機(jī)緊密相關(guān)，其它部分的工作幾乎與目標(biāo)機(jī)無關(guān)。n52目標(biāo)代碼生成舉例 運(yùn)算符左運(yùn)算對象右運(yùn)算對象結(jié)果(1)*r6.0t1(2)+xt

21、1yMOV r, R1MUL#6.0, R1MOV x, R2ADDR1, R2MOV R2, yn531.3 編譯程序的結(jié)構(gòu) (components)n詞法分析程序n語法分析程序n語義分析程序n中間代碼生成程序n代碼優(yōu)化程序n目標(biāo)代碼生成程序n符號(hào)表管理程序n出錯(cuò)處理程序n54一.表格管理編譯過程中，需經(jīng)常收集、記錄或查詢程序中所出現(xiàn)的各種量的有關(guān)屬性（信息）。為此，編譯程序需要建立一批不同用途的表格（常數(shù)表、變量表、關(guān)鍵字表等符號(hào)表）。除此之外，根據(jù)不同的分析方法，編譯程序還保持一些專用的表格（LL分析表、LR分析表、狀態(tài)矩陣等）。合理地設(shè)計(jì)和使用表格是編譯過程中一個(gè)重要的問題n55二.出

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