編譯原理計(jì)算機(jī)科學(xué)技術(shù)系

1、編譯原理華東師大計(jì)算機(jī)科學(xué)技術(shù)系2008年P(guān)rinciples of Compiler7/21/20221課程目的、學(xué)習(xí)方法和基本要求性質(zhì) 專業(yè)基礎(chǔ)課程，是計(jì)算機(jī)科學(xué)技術(shù)的基礎(chǔ)前導(dǎo)課程 離散數(shù)學(xué)、程序設(shè)計(jì)語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)目的 編譯程序是計(jì)算機(jī)系統(tǒng)的基本系統(tǒng)軟件，本課程主要介紹設(shè)計(jì)、實(shí)現(xiàn)編譯程序時(shí)所涉及的基本原理、基本方法和基本技術(shù)。通過(guò)本課程的學(xué)習(xí)和上機(jī)實(shí)踐使學(xué)生掌握構(gòu)造高級(jí)程序設(shè)計(jì)語(yǔ)言編譯程序的基本原理、結(jié)構(gòu)、設(shè)計(jì)與實(shí)現(xiàn)技術(shù)，培養(yǎng)學(xué)生了解和掌握編譯原理的基本原理及典型技術(shù)并具備相當(dāng)?shù)膽?yīng)用能力。7/21/20222課程目的、學(xué)習(xí)方法和基本要求知識(shí) 形式語(yǔ)言與形式語(yǔ)言處理、自動(dòng)機(jī)理論、形

2、式描述方法、程序自動(dòng)生成方法、數(shù)據(jù)流和控制分析方法方法 系統(tǒng)性：前后的連接、融會(huì)貫通，避免孤立化 實(shí)踐性：可實(shí)現(xiàn)的系統(tǒng)軟件，理論與實(shí)踐相結(jié)合 多樣性：實(shí)現(xiàn)技術(shù)多樣、表示形式多樣 基本性：舉一反三，在掌握多種方法、算法和表 示形式的同時(shí)正確把握基本性7/21/20223課程目的、學(xué)習(xí)方法和基本要求本專業(yè)人員4種基本的專業(yè)能力計(jì)算思維能力算法的設(shè)計(jì)與分析能力程序設(shè)計(jì)和實(shí)現(xiàn)能力計(jì)算機(jī)軟硬件系統(tǒng)的認(rèn)知、分析、設(shè)計(jì)與應(yīng)用能力計(jì)算思維能力邏輯思維能力和抽象思維能力構(gòu)造模型對(duì)問(wèn)題進(jìn)行形式化描述理解和處理形式模型7/21/20224課程目的、學(xué)習(xí)方法和基本要求主要特點(diǎn) 抽象和形式化、理論證明和構(gòu)造性 前半部分

3、（詞法、語(yǔ)法分析）實(shí)現(xiàn)技術(shù)、形式化 后半部分（語(yǔ)義分析、代碼優(yōu)化、生成）希望“知其然，不知其所以然”“知其所以然”7/21/20225教材及主要參考書目教材 胡倫駿等 編譯原理電子工業(yè)出版社 2005年參考書目侯文永、張冬茉 編譯原理 電子工業(yè)出版社 2002年楊宗源編譯原理習(xí)題精選分析與解答清華大學(xué)出版社 2003徐國(guó)定 楊宗源 編譯程序構(gòu)造 華東師范大學(xué)出版社 1989.10Kenneth C. Loudon Compiler Construction: Principles and Practice Pws Publishing Company 1997Alfred V. Aho Rav

4、i Sethi Jeffrey D. Ullman Compilers Principles, Techniques, and Tools Addison-Wesley, Reading, Mass, 1986Charles N. Fischer Richard J. LeBlanc, Jr. Crafting A Compiler The Benjamin/Cummings Publishing Company 1988Dick Grune, Henri E Bal, Ceriel J H Jacobs,Koen G Langendoen, Modern Compiler Design Jo

5、hn Wiley & Sons, Ltd, 2000 7/21/20226第一章 編譯概述1.1 語(yǔ)言處理與編譯程序1.1.1 程序設(shè)計(jì)語(yǔ)言的引入是解決人機(jī)對(duì)話鴻溝的一個(gè)里程碑語(yǔ)言處理程序自然語(yǔ)言數(shù)學(xué)概念與符號(hào)程序設(shè)計(jì)語(yǔ)言機(jī)器指令人類的“計(jì)算”思維形式表示方法計(jì)算機(jī)的“計(jì)算”方式7/21/20227語(yǔ)言處理與編譯程序1.1.2 程序設(shè)計(jì)語(yǔ)言分類 程序設(shè)計(jì)語(yǔ)言是遵守一定規(guī)范的、描述“計(jì)算”（Computing）過(guò)程的形式語(yǔ)言。一般可以劃分 ：低級(jí)語(yǔ)言低級(jí)語(yǔ)言是面向機(jī)器的語(yǔ)言，它是為特定的計(jì)算機(jī)系統(tǒng)設(shè)計(jì)的語(yǔ)言。如：機(jī)器指令、匯編語(yǔ)言是低級(jí)語(yǔ)言。高級(jí)語(yǔ)言高級(jí)語(yǔ)言是與具體計(jì)算機(jī)無(wú)關(guān)的“通用”語(yǔ)言，它更

6、接近于人類的自然語(yǔ)言和數(shù)學(xué)表示。如：FORTRAN、Pascal、C、JAVA等等高級(jí)語(yǔ)言 。其他語(yǔ)言如：控制命令語(yǔ)言、查詢語(yǔ)言、腳本語(yǔ)言等。7/21/20228語(yǔ)言處理與編譯程序1.1.3 語(yǔ)言處理程序翻譯程序(Translator)翻譯程序是一種語(yǔ)言處理程序，它將輸入的用程序設(shè)計(jì)語(yǔ)言（源語(yǔ)言）書寫的程序（源程序）轉(zhuǎn)換為等價(jià)的用另一種語(yǔ)言書（目標(biāo)語(yǔ)言）寫的程序（目標(biāo)程序）。若源語(yǔ)言是匯編語(yǔ)言，目標(biāo)語(yǔ)言是機(jī)器語(yǔ)言，稱這種翻譯程序?yàn)閰R編程序。若源語(yǔ)言是高級(jí)語(yǔ)言，目標(biāo)語(yǔ)言是低級(jí)語(yǔ)言，稱這種翻譯程序?yàn)榫幾g程序 。 若源語(yǔ)言是高級(jí)語(yǔ)言，目標(biāo)語(yǔ)言是另一種高級(jí)語(yǔ)言，稱這種翻譯程序?yàn)檗D(zhuǎn)換程序 。7/21/2

7、0229語(yǔ)言處理與編譯程序解釋程序（Interpreter）解釋程序是一種語(yǔ)言處理程序，它對(duì)源程序逐個(gè)語(yǔ)句地進(jìn)行分析，并根據(jù)每個(gè)語(yǔ)句的含義執(zhí)行語(yǔ)句指定的功能。編譯程序（翻譯程序）與解釋程序主要的不同是：編譯程序?qū)⑾壬赡繕?biāo)程序，再執(zhí)行目標(biāo)程序，而解釋程序不生成目標(biāo)程序，邊翻譯、邊執(zhí)行。形象地說(shuō)，這類似于自然語(yǔ)言中的“筆譯”與“口譯”。 翻譯與解釋相結(jié)合的方法是一種不錯(cuò)的方法：即先將源程序翻譯為中間語(yǔ)言表示的代碼，然后再解釋執(zhí)行。例如，JAVA語(yǔ)言的源程序翻譯為一種稱為Bytecode的中間代碼，再通過(guò)JAVA虛擬機(jī)解釋執(zhí)行。 7/21/202210語(yǔ)言處理與編譯程序編譯程序的一個(gè)實(shí)例 FACO

8、M M-340的C語(yǔ)言編譯器程序名意義功能CV替換程序、$等字符的替換CPP預(yù)處理程序#include、#define等的處理CSA詞法、語(yǔ)法、語(yǔ)義分析程序生成中間代碼CCG代碼生成程序生成匯編指令A(yù)SM匯編程序生成二進(jìn)制機(jī)器指令LINK連接裝配程序生成可執(zhí)行程序7/21/202211語(yǔ)言處理與編譯程序相關(guān)說(shuō)明CV、CPP與語(yǔ)言、機(jī)器相關(guān)，ASM、LINK與機(jī)器相關(guān)，而CSA、CSG組成了編譯程序的主體。稱CSA為編譯器的前端獨(dú)立于目標(biāo)語(yǔ)言，稱CSG為編譯器的后端面向目標(biāo)語(yǔ)言。遍在編譯過(guò)程中，掃描一遍源程序（輸入文件），經(jīng)處理形成一個(gè)輸出文件，稱為一遍。合理地決定“遍數(shù)”，可提高效率（時(shí)/空）

9、LINK程序linker：連接程序：多個(gè)不同的目標(biāo)文件 一個(gè) 可執(zhí)行文件loader：裝配程序：相對(duì)地址 絕對(duì)地址7/21/202212語(yǔ)言處理與編譯程序編譯器所在的集成環(huán)境編輯器（Editor)調(diào)試器（Debugger)描述器（Profiler)項(xiàng)目管理器（Project Manager)等7/21/202213編譯程序概貌1.2 編譯過(guò)程和編譯程序的基本結(jié)構(gòu)抽象地看：源程序（S）編譯程序（C）目標(biāo)程序（T）出錯(cuò)信息（E）7/21/202214 這是一個(gè)邏輯模型 獨(dú)立于具體的語(yǔ)言和機(jī)器7/21/202215以賦值語(yǔ)句 pos:=init+rate*60 為例來(lái)了解編譯的全過(guò)程詞法分析 (Le

10、xical Analysis)功能：a) 掃描源程序的字符串，識(shí)別出意義獨(dú)立的最小的詞法單位單詞（Token）。b) 刪除注解、空格、回車及與輸入介質(zhì)有關(guān)的符號(hào)。c) 報(bào)告詞法錯(cuò)誤。如上述賦值語(yǔ)句經(jīng)過(guò)詞法分析后輸出為如下單詞：(ID,pos) (OP,:=) (ID,init) (OP,+) (ID,rate) (OP,*) (CONST,60) 7/21/202216語(yǔ)法分析 (Syntax Analysis) 功能：對(duì)輸入的單詞串，按程序設(shè)計(jì)語(yǔ)言的語(yǔ)法規(guī)則，檢查源程序句法正確性。例如某語(yǔ)言關(guān)于賦值語(yǔ)句的語(yǔ)法規(guī)則是：賦值語(yǔ)句是：ID:=EXPID、CONST是EXP若EXP1和EXP2是EX

11、P，則EXP1+EXP2、 EXP1*EXP2、 (EXP1)是EXP。可以通過(guò)自頂向下或自底向上的句法分析方法，建立分析樹(shù)（又稱 句法樹(shù)、推導(dǎo)樹(shù)）進(jìn)行句法分析。 7/21/202217對(duì)此例，分析樹(shù)為：7/21/202218語(yǔ)義分析 (Semantic Analysis) 功能：檢查語(yǔ)義的正確性，完成語(yǔ)義解釋及必要的轉(zhuǎn)換。例如：此例中各變量的數(shù)據(jù)類型是float，由于rate與60的類型不同就應(yīng)該進(jìn)行轉(zhuǎn)換，即將60轉(zhuǎn)換為60.0。中間代碼生成 （Intermediate Code Generation） 功能：將單詞串轉(zhuǎn)換為等價(jià)的中間代碼串。 常見(jiàn)的中間代碼有：四元組、三元組、 逆波蘭（后綴

12、）表示等。上例中的賦值語(yǔ)句可翻譯為（四元組形式）：(float， ，60，t1) (*，ID.rate，t1，t2) (+，ID.init，t2，t3) (:=,t3, ,ID.pos)其中t1，t2，t3是臨時(shí)變量、ID.x是x在符號(hào)表中的位置。 7/21/202219代碼優(yōu)化 (Code Optimization)功能：以提高目標(biāo)代碼運(yùn)行的時(shí)/空間效率為目的 的對(duì)中間代碼進(jìn)行等價(jià)變換。常見(jiàn)的方法有：刪除無(wú)用賦值和多余運(yùn)算、常量合并、運(yùn)算強(qiáng)度削弱、代碼外提、復(fù)寫傳播等等。此例中的中間代碼通過(guò)優(yōu)化可為：(*，ID.rate，60.0，t1) (+，ID.init，t1，t2) (:=，t2，

13、，ID.pos)代碼生成 （Code Generation）功能：將中間代碼串轉(zhuǎn)換為匯編代碼或機(jī)器指令。7/21/202220代碼生成此例中優(yōu)化后的中間代碼可生成如下的匯編代碼：LOAD R0, drate(R3)LOAD R1, d60.0(R3)MULT R0, R1LOAD R0, dinit(R3)ADD R0, R1STORE R1, dpos(R3)其中R3是基地址寄存器，dx是x的位移（相對(duì)于R3的內(nèi)容）。 7/21/202221出錯(cuò)處理 (Error Handle) 功能：顯示出錯(cuò)的位置、性質(zhì)，限制出錯(cuò)的影響，為盡可能多地發(fā)現(xiàn)錯(cuò)誤做些恢復(fù)工作。符號(hào)表管理 (Symbol-Table Management) 功能：管理源程序中各種數(shù)據(jù)對(duì)象及其各種屬性，提供包括生成、查詢、更新等各種功能。 7/21/202222編譯程序的生成方法1.3 編譯程序的生成方法1.3.1 手工生成完全由人采用低級(jí)語(yǔ)言開(kāi)發(fā)編譯程序，工作量很大。1.3.2 自動(dòng)生成利用自動(dòng)生成工具開(kāi)發(fā)編譯程序。如