【正文】 《 編譯原理 》 課程信息 ? 教學(xué)目的與要求： 編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分之一。本課程重點(diǎn)講述編譯程序的設(shè)計(jì)原理和常用實(shí)現(xiàn)技術(shù)。通過(guò)課程的學(xué)習(xí)和實(shí)驗(yàn)的完成， 應(yīng)該 清楚的理解一個(gè)編譯程序是如何工作的；如果在以后遇到了任何一個(gè)程序設(shè)計(jì)語(yǔ)言， 應(yīng)該 知道如何實(shí)現(xiàn)這個(gè)語(yǔ)言的多數(shù)機(jī)制； 應(yīng) 具有一定的使用編譯構(gòu)造工具開(kāi)發(fā)編譯程序的經(jīng)驗(yàn)； 會(huì) 將所學(xué)的常用技術(shù)和算法應(yīng)用于類似的軟件的設(shè)計(jì)和實(shí)現(xiàn)中。 課程架構(gòu)： 1 理論和實(shí)踐并重的課程 2 理論部分的題目出現(xiàn)于書面練習(xí)，課堂小測(cè)和期末考試 3 實(shí)踐題目（ Project） – Project1: 用高級(jí)語(yǔ)言（ C或 Pascal）實(shí)現(xiàn)擴(kuò)充的 PL/0編譯程序 – Project2: 使用編譯構(gòu)造工具實(shí)現(xiàn)面向?qū)ο笳Z(yǔ)言 Tool的編譯程序 – Project3: 使用編譯構(gòu)造工具實(shí)現(xiàn)擴(kuò)充的 PL0編譯程序 – Project4: 用 GCC裁制一個(gè)編譯器（任選） 4 各部分權(quán)重 – 書面練習(xí)抽查 – 課堂小測(cè)（兩次） 10% – 實(shí)踐 20%或 35% （必做 : Project1占 10%； 選做 : Project2占25%， Project3占 10% ；任選： Project4待定） – 期末考試 70%或 55% 教材及主要參考書 ? 教材： 《 編譯原理 》 （第 2版），張素琴、呂映芝、蔣維杜、戴桂蘭，清華大學(xué)出版社 2022 ? 參考書： 《 Compilers: Principles, Technigues, and Tools》 Alfred , Ravi Sethi, Jeffrey , AddisonWesley,1986. 影印版：人民郵電出版社，2022 ? 參考書 :《 程序設(shè)計(jì)語(yǔ)言 編譯原理 》 （第 3版），陳火旺、劉春林等，國(guó)防工業(yè)出版社 2022 教學(xué)內(nèi)容 1 編譯程序概述 編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分之一 .編譯程序一般由詞法分析程序，語(yǔ)法分析程序，語(yǔ)義分析程序，中間代碼生成程序，目標(biāo)代碼生成程序，代碼優(yōu)化程序，符號(hào)表管理程序和錯(cuò)誤處理程序等成分構(gòu)成。本章概要介紹編譯成分的主要功能以及編譯階段的邏輯關(guān)系。 2 PL/0 編譯程序剖析 給出一個(gè)簡(jiǎn)單的類 Pascal語(yǔ)言，其編譯程序用高級(jí)語(yǔ)言（ C和 Pascal）實(shí)現(xiàn)。通過(guò)剖析該高級(jí)語(yǔ)言程序以理解各編譯成分的功能及手工實(shí)現(xiàn)方法。 教學(xué)內(nèi)容 3 高級(jí)語(yǔ)言的認(rèn)識(shí) 要學(xué)習(xí)和構(gòu)造編譯程序，理解和定義程序設(shè)計(jì)語(yǔ)言是必不可少的。每個(gè)程序設(shè)計(jì)語(yǔ)言都有一定的規(guī)則用以規(guī)定合適程序的語(yǔ)法結(jié)構(gòu)，也需要有對(duì)一個(gè)程序的含義的描述。上下文無(wú)關(guān)文法給出程序設(shè)計(jì)語(yǔ)言的精確的 ,易于理解的語(yǔ)法說(shuō)明。尚沒(méi)有公認(rèn)的形式系統(tǒng)描述程序含義，但也有流行的描述語(yǔ)義規(guī)則的方法 —屬性文法。 4 詞法分析程序的自動(dòng)構(gòu)造 詞法分析程序是編譯程序的一個(gè)構(gòu)成部分，它的主要任務(wù)是掃描源程序，按構(gòu)詞規(guī)則識(shí)別單詞，并報(bào)告發(fā)現(xiàn)的詞法錯(cuò)誤。正則表達(dá)式和有窮狀態(tài)自動(dòng)機(jī)分別作為單詞的描述工具和識(shí)別機(jī)制，成為詞法分析程序的自動(dòng)構(gòu)造原理，學(xué)習(xí) Lex（ Flex）工具的使用方法。 教學(xué)內(nèi)容 5 語(yǔ)法分析程序的構(gòu)造 ?自頂向下的語(yǔ)法分析?？梢钥醋魇菫橐粋€(gè)輸入串尋找一個(gè)最左推導(dǎo)的過(guò)程 ,也等價(jià)于從根開(kāi)始 ,按前序生成結(jié)點(diǎn)，為輸入串構(gòu)造分析樹(shù)的過(guò)程。討論一種有效的無(wú)回溯的自頂向下分析程序 ,這種分析程序稱為預(yù)測(cè)分析程序。介紹對(duì)于一個(gè)文法類： LL（ 1）文法 , 如何自動(dòng)的構(gòu)造預(yù)測(cè)分析程序。 ?自底向上（自下而上）語(yǔ)法分析方法，也稱移進(jìn) 歸約分析法。它的實(shí)現(xiàn)思想是對(duì)輸入符號(hào)串自左向右進(jìn)行掃描，并將輸入符逐個(gè)移入一個(gè)后進(jìn)先出棧中，邊移進(jìn)邊分析，一旦棧頂符號(hào)串形成可歸約串，就用相應(yīng)非終結(jié)符代替可歸約串，這稱為一步歸約，重復(fù)這一過(guò)程，直到歸約到棧中只剩文法的開(kāi)始符號(hào)時(shí)，則為分析成功，并確認(rèn)輸入串是文法的句子。本章介紹LR分析法，分析過(guò)程中歸約的是當(dāng)前句型的句柄，稱為規(guī)范歸約。重點(diǎn)講解 LR類（ LR（ 0）、 SLR（ 1）、 LALR（ 1）、 LR（ 1））文法的分析表的構(gòu)造原理。 教學(xué)內(nèi)容 6 語(yǔ)義分析和中間代碼生成 在詞法分析和語(yǔ)法分析之后，編譯程序下一個(gè)邏輯階段的任務(wù)是語(yǔ)義分析和生成中間代碼。引入屬性文法和語(yǔ)法制導(dǎo)的翻譯的概念，介紹中間代碼的形式，針對(duì)一些語(yǔ)法成分討論相應(yīng)語(yǔ)義處理工作的描述。 7 符號(hào)表 介紹符號(hào)表的一般組織和使用方法，討論分程序結(jié)構(gòu)語(yǔ)言的名字作用域分析及符號(hào)表設(shè)計(jì)方案。 教學(xué)內(nèi)容 8 運(yùn)行時(shí)的存儲(chǔ)組織和管理 編譯的最終目標(biāo)是生成目標(biāo)程序。在目標(biāo)代碼生成前，編譯程序必須對(duì)目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間進(jìn)行組織和安排 . 介紹目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間的存儲(chǔ)分配策略，說(shuō)明程序設(shè)計(jì)語(yǔ)言本身關(guān)于名稱的作用域和生存期的規(guī)則與存儲(chǔ)分配策略的關(guān)系，重點(diǎn)討論棧式動(dòng)態(tài)存儲(chǔ)方案 . 教學(xué)內(nèi)容 9 代碼優(yōu)化和目標(biāo)代碼生成 代碼優(yōu)化是對(duì)代碼作一些等價(jià)變換，以使得最后生成的目標(biāo)代碼更為高效。介紹優(yōu)化技術(shù)，優(yōu)化分類以及優(yōu)化工作的基礎(chǔ)－控制流和數(shù)據(jù)流分析問(wèn)題。 編譯的最后一個(gè)邏輯階段是目標(biāo)代碼生成。目標(biāo)代碼生成程序的設(shè)計(jì)細(xì)節(jié)要考慮目標(biāo)語(yǔ)言和操作系統(tǒng)的特點(diǎn)。討論目標(biāo)代碼生成程序設(shè)計(jì)的一般問(wèn)題，包括指令選擇，寄存器分配和計(jì)算順序選擇。 教師聯(lián)系信息 張素琴 電話 62785601 辦公室 東主樓 10207 董淵 電話 62794240 辦公室 東主樓 10209 王生原 電話 62794240 辦公室 東主樓 10209 課程相關(guān)資料 相關(guān)資料放在 密碼都是 piler05。 第 1章 概述 什么是編譯程序 程序設(shè)計(jì)語(yǔ)言的實(shí)現(xiàn) 處理源程序的軟件工具 編譯技術(shù)的發(fā)展 (piler) 編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分 . 從功能上看，一個(gè)編譯程序就是一個(gè)語(yǔ)言翻譯程序，它把一種語(yǔ)言 (稱作源語(yǔ)言 )書寫的程序翻譯成另一種語(yǔ)言 (稱作目標(biāo)語(yǔ)言 )的等價(jià)的程序 . 什么是編譯程序 功能 術(shù)語(yǔ) 編譯程序的源語(yǔ)言 (源程序 ) 編譯程序的目標(biāo)語(yǔ)言(目標(biāo)程序 ) 編譯程序的實(shí)現(xiàn)語(yǔ)言 S O I 高級(jí)語(yǔ)言 書寫的程序 編譯程序 低級(jí)語(yǔ)言程序 S T I 什么是編譯程序 ? 分類 –軟件 –系統(tǒng)軟件 –語(yǔ)言處理系統(tǒng) 操作系統(tǒng) 編譯系統(tǒng) 裸機(jī) 分類 ? 軟件：計(jì)算機(jī)系統(tǒng)中的程序及其文檔 ? 系統(tǒng)軟件：居于計(jì)算機(jī)系統(tǒng)中最靠近硬件的一層，其他軟件一般都通過(guò)系統(tǒng)軟件發(fā)揮作用。他和具體的應(yīng)用領(lǐng)域無(wú)關(guān)，如編譯系統(tǒng)和操作系統(tǒng)等。 ? 語(yǔ)言處理系統(tǒng)：把軟件語(yǔ)言書寫的各種程序處理成可在計(jì)算機(jī)上執(zhí)行的程序。 ? 軟件語(yǔ)言：用于書寫軟件的語(yǔ)言。它主要包括需求定義語(yǔ)言，功能性語(yǔ)言，設(shè)計(jì)性語(yǔ)言，程序設(shè)計(jì)語(yǔ)言以及文檔語(yǔ)言。 什么是編譯程序 ? 語(yǔ)言轉(zhuǎn) (變）換系統(tǒng) C++編譯器 C++ C Java Bytecode Java編譯器 術(shù)語(yǔ) ? 編譯程序 (piler) ? 編譯程序的源語(yǔ)言 (源程序 ) (source language)(source program) ? 編譯程序的目標(biāo)語(yǔ)言 (目標(biāo)程序 ) (object or target language)(object or target program) ? 編譯程序的實(shí)現(xiàn)語(yǔ)言 (implementation language) ? 語(yǔ)言處理程序 (language processor) ? 語(yǔ)言轉(zhuǎn)（變）換 (language transformation) 編譯邏輯過(guò)程 ? 詞法分析 ? 語(yǔ)法分析 ? 語(yǔ)義分析 ? 中間代碼生成 ? 代碼優(yōu)化 ? 目標(biāo)代碼生成 詞法分析 — 第一步識(shí)別單詞 英文句子由單詞構(gòu)成 This line is a longer sentence. （字母組成的有集體含義的最小成分） ? 句子開(kāi)頭的單詞第一個(gè)字母要大寫 ? 空格是單詞分隔符 ? 句點(diǎn)是句子結(jié)尾 ist his linealo gerse nte nce. 詞法分析 從左至右掃描字符流的源程序、分解構(gòu)成源程序的字符串，識(shí)別出 (拼 )一個(gè)個(gè)的單詞（符號(hào)） 單詞符號(hào)是語(yǔ)言中具有獨(dú)立意義的最基本結(jié)構(gòu)。多數(shù)程序語(yǔ)言中，單詞符號(hào)一般包括 — 各類型的常數(shù)、保留字、標(biāo)識(shí)符、運(yùn)算符、界符等等。 例如 double f = sqrt(1)。 詞法分析 double f = sqrt(1)。 TDOUBLE (“double”) TIDENT (“f”) TOP (“=“) TIDENT (“sqrt”) TLPAREN (“(“) TOP (“”) TINTCONSTANT (“1”) TRPAREN (“)”) TSEP (“?！? 詞法分析 ? 詞法分析 (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. ? 單詞 token ? 保留字 reserved word ? 標(biāo)識(shí)符 identifier(userdefined name) 例 ? 程序文本 If x = y then z := 1 else z := 2。 經(jīng)詞法分析，變成一個(gè)個(gè)單詞 ? if, x, =, y, then, z, ? :=, 1, else, z, :=, 2, 。 ? 語(yǔ)言的單詞符號(hào)是由詞法規(guī)則所確定的。詞法規(guī)則規(guī)定了字母表中哪樣的字符串是一個(gè)單詞符號(hào)。 詞法分析 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) ； 語(yǔ) 法分析 Syntax Analysis 功能 :層次分析 .依據(jù) 源程序的 語(yǔ)法規(guī)則 把源程序的單詞序列組成語(yǔ)法短語(yǔ) (表示成語(yǔ)法樹(shù) ). ? 也 稱為 ―parsing‖ ? 使用 contextfree grammars ? 結(jié)構(gòu) 上的合法性 Structural validation （可生成語(yǔ)法樹(shù)或推導(dǎo) Creates parse tree or derivation） This line is a longer sentence p r o n o u n n o u n v e r b a r t i c l e a d j e c t i v es u b j e c tn o u no b j e c ts e n t e n c eT h i s l i n e i sa l o n g e rs e n t e n c e分析程序成分 Gt h e n s t m ta s s i g n a d j e c t i v ep r e d i c a t e e l s e s t m tI f t h e n e l s ex =y Z 1 2Z double f = sqrt(1)。 ―sqrt(1)‖的 推導(dǎo) Expression ? FuncCall ? TIDENT TLPAREN Expression TRPAREN ? TIDENT TLPAREN UnaryExpression TRPAREN ? TIDENT TLPAREN TOP Expression TRPAREN ? TIDENT TLPAREN TOP TINTCONSTANT TRPAREN 規(guī)則 Expression UnaryExpr