《羊四清編譯原理》

編譯原理主講：羊四清授課對(duì)象：計(jì)算機(jī)系

計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)2004級(jí)2007年上學(xué)期

.學(xué)習(xí)編譯原理的目的和意義從簡(jiǎn)單實(shí)用主義看，學(xué)習(xí)編譯原理是沒(méi)有任何作用的，因?yàn)橐话銇?lái)說(shuō)99%的程序員，不需要寫(xiě)自己的編譯器，也不需要去讀懂任何編譯器代碼。

但是我認(rèn)為編譯原理還是很值得一學(xué)的：

第一、學(xué)習(xí)編譯原理可以幫助自己更加深層次的理解程序語(yǔ)言和內(nèi)部機(jī)制。

第二、學(xué)習(xí)編譯原理可以用來(lái)做簡(jiǎn)單的命令解釋器，這個(gè)經(jīng)常都很需要。比如游戲的腳本引擎。

第三、學(xué)習(xí)正則表達(dá)式，有很大的用處。

第四、它的理論基礎(chǔ)堅(jiān)實(shí)，其形式化系統(tǒng)不僅應(yīng)用于編譯技術(shù)，還大量應(yīng)用于人工智能、多媒體技術(shù)及數(shù)據(jù)庫(kù)等領(lǐng)域。.本課程的地位計(jì)算機(jī)專業(yè)的專業(yè)基礎(chǔ)課是軟件技術(shù)基礎(chǔ)是計(jì)算機(jī)專業(yè)的學(xué)生必修的一門主干課是本學(xué)科研究生入學(xué)考試的課程之一.學(xué)習(xí)任務(wù)

掌握編譯的理論基礎(chǔ)和形式化系統(tǒng)了解編譯的全過(guò)程及其具體實(shí)現(xiàn)方法.學(xué)習(xí)方法1、認(rèn)真聽(tīng)課，認(rèn)真理解書(shū)中的基本概念、基本原理與基本算法2、弄懂書(shū)中的例題與習(xí)題3、在看書(shū)時(shí)或理解例題時(shí)，一定要?jiǎng)澇鱿鄳?yīng)的細(xì)節(jié)變化過(guò)程，通過(guò)畫(huà)圖來(lái)加深理解4、在理解的基礎(chǔ)上記憶5、理論結(jié)合實(shí)踐.學(xué)習(xí)要求

成績(jī)考核方法平時(shí)成績(jī)占30%期末考試成績(jī)占70%。平時(shí)成績(jī)?yōu)椋赫n堂點(diǎn)名10%作業(yè)10%上機(jī)實(shí)驗(yàn)10%.參考書(shū)教材---陳火旺劉春林等程序設(shè)計(jì)語(yǔ)言編譯原理國(guó)防工業(yè)出版社2000TomasPittmn,TheartofCompilerDesigntheoryandPractice,Prentice-Hall1992ALFREDV.AHO,RAVISETHI,JEFFREYD.ULLMAN,CompilersPrinciples,TechniquesandToolsADDISSON-WESLEY1986---龍書(shū)之稱DavidAWatt&DeryckFBrownProgramminglanguageprocessorsinjava(inc,inc++)compilersandinterpreters,Prentice-Hall2000ModernCompilerImplementationinC

（美）AndrewW.Appel,MaiaGinsburg

CambridgeUniversityPress–虎書(shū)之稱.參考書(shū)TerrenceW.Pratt,MarvinV.ZelkowitzProgrammingLanguagesDesignandImplementation,Prentice-Hall1996Bennett,J.P.,IntroductiontoCompilingtechniques:afirstcourseusingANSIC,LEXandYACC.-2nded-,TheMcGRAW-HILLPublishingCompany1996–ModernCompilerImplementationinJava,SecondEdition2002年虎書(shū)第2版

DavidA.Watt,ProgrammingLanguageSyntaxandSemantics,PrenticeHall1991.編譯原理，清華大學(xué)出版社，呂映芝等編著，1998。編譯原理技術(shù)與工具（英文版）編譯原理與實(shí)踐（英文影印版）高級(jí)編譯器設(shè)計(jì)與實(shí)現(xiàn)現(xiàn)代編譯原理--C語(yǔ)言描述（英文影印版）現(xiàn)代編譯原理-C語(yǔ)言描述參考書(shū).主要內(nèi)容及課時(shí)安排第1章引論2第2章高級(jí)語(yǔ)言及其語(yǔ)法描述4第3章詞法分析8第4章語(yǔ)法分析—自上而下分析6第5章語(yǔ)法分析—自下而上分析8第6章屬性方法和語(yǔ)法制導(dǎo)翻譯6第7章語(yǔ)義分析和中間代碼生成10.第8章符號(hào)表4第9章運(yùn)行時(shí)存儲(chǔ)空間組織6第10章優(yōu)化3第11章目標(biāo)代碼生成3第12章并行編譯基礎(chǔ)4理論：64節(jié)（16*4）上機(jī)及課程設(shè)計(jì)：26節(jié).第一章引論1.1什么叫編譯程序編譯程序:是指這樣的程序，它能夠把某種語(yǔ)言的程序轉(zhuǎn)換成另一種語(yǔ)言的程序，而后者與前者在邏輯上是等價(jià)的。如果源語(yǔ)言是諸如FORTRAN、Pascal、C、Ada、Smalltalk或Java這樣的“高級(jí)語(yǔ)言”，而目標(biāo)語(yǔ)言如匯編語(yǔ)言之類的“低級(jí)語(yǔ)言”這樣的翻譯程序則稱之為編譯程序。.編譯程序又簡(jiǎn)稱為“編譯器”第一個(gè)編譯器是20世界50年代的后期出現(xiàn)的FORTRAN語(yǔ)言編譯器。同樣，解釋程序又簡(jiǎn)稱為“解釋器”，但是在概念上與編譯器有明顯區(qū)別：編譯程序是源轉(zhuǎn)換系統(tǒng)，而解釋程序是源程序的一個(gè)執(zhí)行系統(tǒng)。編譯程序的結(jié)果是得到等價(jià)源程序的某種目標(biāo)機(jī)程序，而解釋程序的結(jié)果是得到源程序的執(zhí)行結(jié)果，即它相當(dāng)于執(zhí)行源程序的抽象機(jī)。.編譯程序與解釋程序的區(qū)別一個(gè)語(yǔ)言的解釋程序是著樣的程序：它以該語(yǔ)言寫(xiě)的源程序作為輸入，但不產(chǎn)生目標(biāo)程序，而是邊解釋邊執(zhí)行源程序本身。術(shù)語(yǔ)“編譯”的內(nèi)涵是實(shí)現(xiàn)從源語(yǔ)言表示的算法向目標(biāo)語(yǔ)言表示的算法的等價(jià)變換。.編譯程序的分類診斷編譯程序：用于幫助程序開(kāi)發(fā)和調(diào)試優(yōu)化編譯程序：提高目標(biāo)代碼的效率宿主機(jī)：運(yùn)行編譯程序的計(jì)算機(jī)目標(biāo)機(jī)：運(yùn)行編譯程序所產(chǎn)生的目標(biāo)代碼的計(jì)算機(jī)交叉編譯程序：編譯程序產(chǎn)生不同于宿主機(jī)的機(jī)器代碼可變目標(biāo)程序代碼：不需重編譯程序中與機(jī)器無(wú)關(guān)的部分就能改變目標(biāo)機(jī)。

.交叉編譯程序編譯程序在一個(gè)機(jī)器（宿主機(jī)）上運(yùn)行，產(chǎn)生另一個(gè)機(jī)器（目標(biāo)機(jī)）的匯編語(yǔ)言。嵌入式系統(tǒng)中的應(yīng)用程序正是借助這樣的編譯程序生成。

.1.2編譯過(guò)程概述掌握編譯過(guò)程的五個(gè)基本階段，是我們學(xué)習(xí)編譯原理課程的基本內(nèi)容，把編譯的五個(gè)基本階段與英譯中的五個(gè)步驟相比較，有利于對(duì)編譯過(guò)程的理解：.英譯與編譯的比較1.識(shí)別出句子中的一個(gè)個(gè)單字2.分析句子的語(yǔ)法結(jié)構(gòu)3.初步翻譯句子的含意4.譯文修飾5.寫(xiě)出最后譯文1.詞法分析2.語(yǔ)法分析3.語(yǔ)義分析中間代碼生成4.優(yōu)化5.目標(biāo)代碼生成.第一階段:詞法分析詞法分析的任務(wù):

輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)單詞（也稱單詞符號(hào)，或簡(jiǎn)稱符號(hào)）

工具:在詞法分析階段工作所依循的是語(yǔ)言的詞法規(guī)則。描述詞法規(guī)則的有效工具是正規(guī)式和有限自動(dòng)機(jī)。.第二階段:語(yǔ)法分析語(yǔ)法分析的任務(wù)：

在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把單詞符號(hào)分解成各類語(yǔ)法單位（語(yǔ)法范疇），如“短語(yǔ)”、“句子”、“子句”、“程序段”等。工具:語(yǔ)法規(guī)則通常用上下文無(wú)關(guān)文法描述。.第三階段:語(yǔ)義分析與中間代碼的產(chǎn)生任務(wù):這一階段通常包括兩方面的工作首先對(duì)各種語(yǔ)法范疇進(jìn)行靜態(tài)語(yǔ)義檢查，如果正確則進(jìn)行另一方面的工作，即進(jìn)行中間代碼的翻譯。工具:通常使用屬性文法描述語(yǔ)義規(guī)則所謂“中間代碼”是一種含義明確，便于處理的記號(hào)系統(tǒng)。中間代碼除四元式外，還有三元式、間接三元式、逆波蘭記號(hào)、樹(shù)形表示等。.第四階段:優(yōu)化任務(wù):優(yōu)化的任務(wù)在于對(duì)前段產(chǎn)生的中間代碼進(jìn)行加工，以期在最后階段產(chǎn)生更為高效（省時(shí)間和空間）的代碼工具:優(yōu)化所依循的原則是程序的等價(jià)變換規(guī)則.其方法有：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無(wú)用代碼等。.第五階段:目標(biāo)代碼生成任務(wù)：把中間代碼（或經(jīng)優(yōu)化處理后）變換成特定機(jī)器上的低級(jí)語(yǔ)言代碼。它有賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義。目標(biāo)代碼的形式可以是絕對(duì)指令代碼或可重定位的指令代碼可匯編指令代碼..1.3編譯程序的結(jié)構(gòu)表格管理詞法分析器語(yǔ)法分析器語(yǔ)義分析與中間代碼產(chǎn)生優(yōu)化器目標(biāo)代碼生成器源程序單詞符號(hào)語(yǔ)法單位中間代碼中間代碼目標(biāo)代碼出錯(cuò)處理.1.3.2表格與表格管理從上圖中我們可以看到除編譯的五個(gè)基本階段外，一個(gè)完整的編譯程序還應(yīng)包括“表格管理”和“出錯(cuò)處理”兩部分在編譯程序使用的表格中最重要的是符號(hào)表它用來(lái)登記源程序中出現(xiàn)的每一個(gè)名字以及名子的各種屬性。如一個(gè)名字是常量名、變量名，還是過(guò)程名等；如果是變量名它的類型又是什么、所站內(nèi)存是多大、地址是什么等。.1.3.3出錯(cuò)處理一個(gè)編譯程序不僅能對(duì)書(shū)寫(xiě)正確的程序進(jìn)行編譯，而且應(yīng)能對(duì)處現(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。如果源程序有錯(cuò)，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯(cuò)誤，把有關(guān)錯(cuò)誤報(bào)告給用戶。這部分的工作是由專門的一組程序（叫做處錯(cuò)處理程序）完程的。.1.3.4遍遍:就是對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一次,并作胡關(guān)的加工處理,生成新的中間結(jié)果或目標(biāo)程序.遍的劃分:可以將多個(gè)階段劃分為遍,也可以將1個(gè)階段劃分為多遍..1.3.5編譯前端與后端

前端主要由與源語(yǔ)言有關(guān)但與目標(biāo)機(jī)無(wú)關(guān)的那些部分組成。通常包括詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼產(chǎn)生，有的代碼優(yōu)化工作，也可以包括在前端。

后端包括編譯程序中與目標(biāo)代碼有關(guān)的部分，如與目標(biāo)機(jī)有關(guān)的有關(guān)的優(yōu)化，和目標(biāo)代碼的生成等。.1.4編譯程序與程序設(shè)計(jì)環(huán)境編譯程序無(wú)疑是實(shí)現(xiàn)高級(jí)語(yǔ)言的一個(gè)最重要的工具。但支持程序設(shè)計(jì)人員進(jìn)行程序設(shè)計(jì)開(kāi)發(fā)通常還需要其它一些工具：如編輯程序、連接程序、調(diào)試程序等。編譯程序與這些程序設(shè)計(jì)工具一起構(gòu)成所謂的程序設(shè)計(jì)環(huán)境。在一個(gè)程序設(shè)計(jì)環(huán)境中，編譯程序起著中心的作用。連接程序、調(diào)試程序、程序分析等工具直接依賴于編譯程序所產(chǎn)生的結(jié)果，而其它工具的構(gòu)造也常常要用到編譯的原理、方法和技術(shù)。.Ada程序設(shè)計(jì)環(huán)境--APSE宿主機(jī)KPSEAPSEMAPSE……編譯程序調(diào)試程序連接程序命令解釋程序配置管理程序編輯程序.1.5編譯程序的生成以前構(gòu)造編譯程序大多是用機(jī)器語(yǔ)言或匯編語(yǔ)言作工具的。為了充分發(fā)揮各種不同硬件系統(tǒng)的效率，為了滿足各種不同的具體要求，現(xiàn)在許多人仍然使用這種工具來(lái)構(gòu)造編譯程序（或編譯程序的核心部分）但是越來(lái)越多的人已經(jīng)使用高級(jí)語(yǔ)言作工具來(lái)編譯程序。因?yàn)檫@樣可以大大節(jié)省程序設(shè)計(jì)的時(shí)間，熱切構(gòu)造出來(lái)的編譯程序易于閱讀、維護(hù)和移植。.T形圖為此我們用T形圖來(lái)表示源語(yǔ)言S、目標(biāo)語(yǔ)言T和編譯語(yǔ)言I（宿主語(yǔ)言）之間的關(guān)系。STI.用L1語(yǔ)言編寫(xiě)編譯程序如果A機(jī)器上已有一個(gè)用A機(jī)器碼實(shí)現(xiàn)的某高級(jí)語(yǔ)言L1的編譯程序，則我們可以用L1語(yǔ)言編寫(xiě)另一種高級(jí)語(yǔ)言L2的編譯程序，把寫(xiě)好的L2編譯程序經(jīng)過(guò)L1編譯程序編譯后就可得到A機(jī)器代碼實(shí)現(xiàn)的L2編譯程序。A代碼A代碼L1語(yǔ)言A代碼L1語(yǔ)言L2語(yǔ)言A代碼A代碼

L2語(yǔ)言.

我們還可以采用“自編譯方式”產(chǎn)生編譯程序。方法是，先對(duì)語(yǔ)言的核心部分構(gòu)造一個(gè)小小的編譯程序（可用低級(jí)語(yǔ)言實(shí)現(xiàn)），再以他為工具構(gòu)造一個(gè)能夠編譯更多語(yǔ)言成分的較大編譯程序。如此擴(kuò)展下去，就像滾雪球一樣，越滾越大，最后形成人們所期望的整個(gè)編譯程序。這種通過(guò)一系列的自展途徑而形成編譯程序的過(guò)程叫做自編譯過(guò)程。..現(xiàn)在將編譯器移植到一個(gè)新的主機(jī)，只要求重寫(xiě)源代碼的后端來(lái)生成新機(jī)器的代碼。接著用舊的編譯器