《羊四清編譯原理》

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

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

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

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

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

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

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

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

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

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

（美）AndrewW.Appel,MaiaGinsburg

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

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

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

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

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

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

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

前端主要由與源語言有關(guān)但與目標(biāo)機(jī)無關(guān)的那些部分組成。通常包括詞法分析、語法分析、語義分析與中間代碼產(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)境編譯程序無疑是實(shí)現(xiàn)高級語言的一個(gè)最重要的工具。但支持程序設(shè)計(jì)人員進(jìn)行程序設(shè)計(jì)開發(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ī)器語言或匯編語言作工具的。為了充分發(fā)揮各種不同硬件系統(tǒng)的效率，為了滿足各種不同的具體要求，現(xiàn)在許多人仍然使用這種工具來構(gòu)造編譯程序（或編譯程序的核心部分）但是越來越多的人已經(jīng)使用高級語言作工具來編譯程序。因?yàn)檫@樣可以大大節(jié)省程序設(shè)計(jì)的時(shí)間，熱切構(gòu)造出來的編譯程序易于閱讀、維護(hù)和移植。.T形圖為此我們用T形圖來表示源語言S、目標(biāo)語言T和編譯語言I（宿主語言）之間的關(guān)系。STI.用L1語言編寫編譯程序如果A機(jī)器上已有一個(gè)用A機(jī)器碼實(shí)現(xiàn)的某高級語言L1的編譯程序，則我們可以用L1語言編寫另一種高級語言L2的編譯程序，把寫好的L2編譯程序經(jīng)過L1編譯程序編譯后就可得到A機(jī)器代碼實(shí)現(xiàn)的L2編譯程序。A代碼A代碼L1語言A代碼L1語言L2語言A代碼A代碼

L2語言.

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