編譯原理課程教學(xué)大綱-東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院

1、編譯原理課程教學(xué)大綱(課程編號(hào)711302 學(xué)分-學(xué)時(shí)-上機(jī)4.0-64-16 )東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院一、課程的性質(zhì)與目的本課程是軟件工程專業(yè)必修的專業(yè)核心課。本課程的教學(xué)目的， 是使學(xué)生在學(xué)習(xí)程序設(shè)計(jì)基礎(chǔ)及語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，進(jìn)一步理解程序及程序設(shè)計(jì)語(yǔ)言的本質(zhì)，掌握程序詞法分析和句法分析的基本原理和方法。學(xué)會(huì)構(gòu)造一個(gè)編譯程序， 用以將一種語(yǔ)言所編寫(xiě)的程序(如，用C語(yǔ)言編寫(xiě)的程序)等價(jià)變換為另一種語(yǔ)言所編寫(xiě)的程序(如，用匯編語(yǔ)言編寫(xiě)的程序)，并能對(duì)變換過(guò)程中所生成的中間代碼程序及變換所得的程序進(jìn)行優(yōu)化，以培養(yǎng)良好的程序設(shè)計(jì)優(yōu)化思維，提高學(xué)生的編程能力，為學(xué)習(xí)有關(guān)專業(yè)課程和進(jìn)行大型軟

2、件實(shí)踐打 下必要的基礎(chǔ)。二、課程內(nèi)容的教學(xué)要求1 .編譯原理及編譯程序構(gòu)造引論(1)開(kāi)設(shè)編譯原理課程的主要作用：讓學(xué)生理解開(kāi)設(shè)編譯原理課程的意義和作用，編譯原理課程在計(jì)算機(jī)專業(yè)課程體系中的地位，學(xué)習(xí)編譯原理課程應(yīng)采用的方法，編譯原理課程知識(shí)體系結(jié)構(gòu)，讓學(xué)生初步認(rèn)識(shí)學(xué)習(xí)編譯原理課程的重要性和潛在的使用價(jià)值。(2)編譯程序及其構(gòu)造過(guò)程概述：介紹編譯程序的基本含義、作用和結(jié)構(gòu)，簡(jiǎn)述編譯程序構(gòu)造的基本過(guò)程，以讓學(xué)生形成編譯程序構(gòu)造的總體印象。2 .(程序設(shè)計(jì))語(yǔ)言和語(yǔ)法描述(1)語(yǔ)言描述體系結(jié)構(gòu)： 了解語(yǔ)言的語(yǔ)法、語(yǔ)義和語(yǔ)用的基本含義及相互作用，掌握 描述語(yǔ)言語(yǔ)法的基本方法和過(guò)程， 使學(xué)生清楚語(yǔ)言語(yǔ)法

3、描述應(yīng)包括由字符構(gòu)造單詞的詞法描 述，及由單詞構(gòu)造句子的句法描述。(2)語(yǔ)言和文法的基本概念： 掌握語(yǔ)言與文法的相關(guān)基本概念，如，串、句子、句型、 文法、產(chǎn)生式、推導(dǎo)與歸約等，語(yǔ)言文法對(duì)語(yǔ)言語(yǔ)法描述的作用，文法的形式化描述方法和過(guò)程，Chomsky形式語(yǔ)言文法體系及其在語(yǔ)言語(yǔ)法描述中的應(yīng)用、特別是正規(guī)文法及上下 文無(wú)關(guān)文法在語(yǔ)言語(yǔ)法描述中的應(yīng)用。(3)從語(yǔ)言構(gòu)造文法：了解常見(jiàn)語(yǔ)言句子構(gòu)造模式，掌握從典型語(yǔ)言句子模式構(gòu)造對(duì)應(yīng)無(wú)產(chǎn)生式文法的方法，使學(xué)生能夠理解由語(yǔ)言構(gòu)造文法的重要性。(4)語(yǔ)法樹(shù)、分析樹(shù)與二義文法：掌握語(yǔ)法樹(shù)、分析樹(shù)及二義文法的基本概念，如，語(yǔ)法樹(shù)、分析樹(shù)、短語(yǔ)、句柄、二義文法，語(yǔ)

4、法樹(shù)在語(yǔ)言語(yǔ)法分析過(guò)程中的作用，語(yǔ)法樹(shù)構(gòu) 造方法和過(guò)程，二義文法對(duì)語(yǔ)言文法的簡(jiǎn)化描述的作用。3 .詞法分析(1)詞法分析程序的作用和基本構(gòu)造過(guò)程：讓學(xué)生掌握詞法分析程序的作用和基本構(gòu)造過(guò)程，了解詞法分析程序構(gòu)造的關(guān)鍵問(wèn)題，如，詞法描述方法、由詞法描述構(gòu)造相應(yīng)詞法分析程序的思想方法。(2)正規(guī)表達(dá)式、正規(guī)語(yǔ)言與正規(guī)文法：掌握正規(guī)表達(dá)式對(duì)單詞模式表達(dá)的作用，由基本字符構(gòu)造正規(guī)表達(dá)式的方法和過(guò)程，識(shí)別一個(gè)正規(guī)表達(dá)式的方法， 以及正規(guī)語(yǔ)言的基本概念，理解正規(guī)表達(dá)式、正規(guī)語(yǔ)言、正規(guī)文法三者之間的等價(jià)關(guān)系和轉(zhuǎn)換方法。(3)有限自動(dòng)機(jī)：讓學(xué)生了解有限自動(dòng)機(jī)對(duì)正規(guī)表達(dá)式識(shí)別(也就是單詞識(shí)別)的作用，掌握有限自

5、動(dòng)機(jī)的基本概念， 熟悉由正規(guī)表達(dá)式構(gòu)造非確定有限自動(dòng)機(jī)的方法與過(guò)程，掌握 將非確定有限自動(dòng)機(jī)確定化的理由、 方法與過(guò)程， 熟悉確定有限自動(dòng)機(jī)最小化的理由、 方法和過(guò)程，了解正規(guī)文法（正規(guī)表達(dá)式、正規(guī)語(yǔ)言）與有限自動(dòng)機(jī)之間的相互轉(zhuǎn)換方法、以及由確定有限自動(dòng)機(jī)構(gòu)造相應(yīng)詞法分析程序的方法和過(guò)程。（ 4）詞法分析程序生成工具Lex ： 了解 Lex 的基本思想和使用方法。4. 語(yǔ)法（句法）分析（ 1）語(yǔ)法分析基本過(guò)程和方法概述： 進(jìn)一步理解上下文無(wú)關(guān)文法與語(yǔ)言語(yǔ)法描述的關(guān)聯(lián)， 了解利用下推自動(dòng)機(jī)進(jìn)行語(yǔ)法分析的基本過(guò)程， 熟悉典型語(yǔ)法分析方法的基本思想， 深 刻理解“推導(dǎo) 匹配” 、 “移進(jìn) 歸約”的語(yǔ)

6、法分析的思想。（ 2）自頂向下語(yǔ)法分析： 理解自頂向下語(yǔ)法分析方法的基本思想和基本過(guò)程，了解基于遞歸下降分析法構(gòu)造語(yǔ)法分析程序的基本思想和基本過(guò)程，掌握預(yù)測(cè)分析法LL（1） 的基本思想和基本技巧、特別是左遞歸消除、首符集First 和隨符集 Follow 構(gòu)造的技巧，能夠由上下文無(wú)關(guān)文法構(gòu)造 LL（1）分析表，了解基于 LL（1）分析表進(jìn)行具體句子的分析過(guò)程。（ 3）自底向上語(yǔ)法分析： 理解自底向上語(yǔ)法分析方法的基本思想和基本過(guò)程，重點(diǎn)掌握 LR 分析法的基本思想和基本過(guò)程， 能夠由上下文無(wú)關(guān)文法構(gòu)造簡(jiǎn)單的 LR 分析表 （SLR（1）分析表 ）和規(guī)范的 LR 分析表 （LR（1） 分析表 ）

7、， 了解由 LR（1） 構(gòu)造 LALR（1） 分析表的基本思想和基本過(guò)程。（ 4）二義文法的語(yǔ)法分析： 掌握語(yǔ)法分析過(guò)程解決文法二義性的基本思想，能夠通過(guò)二義文法的附加條件構(gòu)造相應(yīng)的SLR（1）或LR（1）分析表。（ 5）語(yǔ)法分析程序生成工具YACC ： 了解 YACC 的基本思想和應(yīng)用過(guò)程。5. 語(yǔ)義分析（ 1）屬性文法： 了解引入符號(hào)屬性對(duì)語(yǔ)言語(yǔ)義描述的作用，理解將上下文無(wú)關(guān)文法轉(zhuǎn)換為屬性文法的意義、 過(guò)程和關(guān)鍵， 掌握屬性文法中語(yǔ)義規(guī)則的使用方法， 理解邊進(jìn)行語(yǔ)法分析、邊進(jìn)行語(yǔ)義分析的語(yǔ)義屬性值計(jì)算的基本思想。（ 2）屬性文法中的綜合屬性值計(jì)算方法： 能夠由只具有綜合屬性的屬性文法構(gòu)造一

8、個(gè)句子的加以屬性標(biāo)注的分析樹(shù)。（ 3）類型檢查： 了解類型作為一種特殊的屬性時(shí)的屬性計(jì)算過(guò)程和方法，即，類型檢查的基本思想和方法。6. 中間代碼生成（ 1） 常見(jiàn)中間代碼形式： 了解常見(jiàn)中間代碼形式， 掌握三地址碼和四元式的基本思想。（ 2） 型語(yǔ)句生成三地址碼的方法： 掌握表達(dá)式、基本賦值語(yǔ)句、含有數(shù)組元素的語(yǔ)句、 If 語(yǔ)句、 While 語(yǔ)句翻譯成三地址碼的方法，能夠?qū)⒁欢魏猩鲜稣Z(yǔ)句的程序翻譯成三地址碼語(yǔ)句序列。（ 3） 典型語(yǔ)句生成四元式的方法： 掌握表達(dá)式、 基本賦值語(yǔ)句、 含有數(shù)組元素的語(yǔ)句、If 語(yǔ)句、 While 語(yǔ)句翻譯成四元式的方法，能夠?qū)⒁欢魏猩鲜稣Z(yǔ)句的程序翻譯成四元

9、式序列，熟悉翻譯過(guò)程中拉鏈回填的基本技巧。7. 運(yùn)行時(shí)環(huán)境（ 1）程序執(zhí)行過(guò)程與激活樹(shù)： 了解程序在計(jì)算機(jī)系統(tǒng)中執(zhí)行過(guò)程，掌握激活樹(shù)概念。（ 2）程序運(yùn)行時(shí)數(shù)據(jù)存儲(chǔ)空間分配策略： 了解程序運(yùn)行時(shí)數(shù)據(jù)存儲(chǔ)空間分配策略，重點(diǎn)理解棧式存儲(chǔ)分配策略。（ 3）棧式存儲(chǔ)分配策略： 掌握活動(dòng)記錄的基本概念，理解C 語(yǔ)言程序運(yùn)行過(guò)程中基于活動(dòng)記錄的數(shù)據(jù)存儲(chǔ)分配策略，能夠構(gòu)造一個(gè)C 語(yǔ)言程序?qū)?yīng)的數(shù)據(jù)存儲(chǔ)棧圖。8. 程序優(yōu)化（ 1） 程序分塊與程序流圖： 了解程序優(yōu)化的一般方法和過(guò)程， 掌握程序基本塊的概念，能夠?qū)⒁欢纬绦騽澐譃榛緣K、并構(gòu)造以基本塊為結(jié)點(diǎn)的程序流圖。（ 2）塊內(nèi)優(yōu)化： 能夠構(gòu)造表示一個(gè)基本塊所

10、涉及數(shù)據(jù)量及其關(guān)聯(lián)的有向無(wú)環(huán)圖，掌握基于有向無(wú)環(huán)圖的塊內(nèi)優(yōu)化方法，能夠?qū)σ粋€(gè)基本塊進(jìn)行塊內(nèi)優(yōu)化并寫(xiě)出優(yōu)化后的代碼序列。（ 3)循環(huán)優(yōu)化：掌握必經(jīng)結(jié)點(diǎn)集和回邊的基本概念，能夠找出程序流圖中的循環(huán)，了 解循環(huán)優(yōu)化的基本方法。（ 4)基于數(shù)據(jù)流分析的優(yōu)化：了解數(shù)據(jù)流分析的作用，理解變量引用定值鏈、定值到達(dá)數(shù)據(jù)流方程、活躍變量數(shù)據(jù)流方程的含義和作用。三、上機(jī)實(shí)習(xí)要求了解程序設(shè)計(jì)語(yǔ)言的詞法和語(yǔ)法(句法)的表示形式，理解詞法和語(yǔ)法分析程序的構(gòu)造方 法和過(guò)程，了解簡(jiǎn)單的塊內(nèi)優(yōu)化方法。四、能力培養(yǎng)的要求1 .分析能力的培養(yǎng)： 主要是對(duì)程序結(jié)構(gòu)、編譯程序構(gòu)造方法和過(guò)程、程序優(yōu)化方法進(jìn) 行分析的能力的培養(yǎng)，同時(shí)也

11、要注意培養(yǎng)針對(duì)具體程序設(shè)計(jì)語(yǔ)言構(gòu)造編譯程序的能力的培 養(yǎng)。2 .算法分析和實(shí)現(xiàn)能力的培養(yǎng)：要求學(xué)生通過(guò)本課程的學(xué)習(xí)，具備對(duì)各種相關(guān)算法進(jìn)行實(shí)現(xiàn)的能力。3 .外文文獻(xiàn)閱讀能力的培養(yǎng)：該課程采用英文教材、英文課件和英文試卷，要求學(xué)生通過(guò)本課程的學(xué)習(xí)，能夠具備直接閱讀專業(yè)外文文獻(xiàn)的能力。4 .自學(xué)能力的培養(yǎng)： 通過(guò)本課程的教學(xué)，要培養(yǎng)和提高學(xué)生對(duì)所學(xué)知識(shí)進(jìn)行整理、概 括、消化吸收的能力，以及圍繞課堂教學(xué)內(nèi)容，閱讀參考書(shū)籍和資料，自我擴(kuò)充知識(shí)領(lǐng)域的 能力。5 .表達(dá)能力的培養(yǎng)：主要是通過(guò)作業(yè)，清晰、整潔地表達(dá)自己解決問(wèn)題的思路和步驟的能 力。6 .創(chuàng)新能力的培養(yǎng)： 培養(yǎng)學(xué)生獨(dú)立思考、深入鉆研問(wèn)題的習(xí)慣

12、，和對(duì)問(wèn)題提出多種解 決方案、選擇不同方法，以及對(duì)方法進(jìn)行簡(jiǎn)化和舉一反三的能力。五、建議學(xué)時(shí)分配課程內(nèi)容講課習(xí)題課或課堂討論實(shí)驗(yàn)上機(jī)編譯原理及編譯程序構(gòu)造引論3開(kāi)設(shè)編譯原理課程的主要作用1編譯程序及其構(gòu)造過(guò)程概述2程序設(shè)計(jì)語(yǔ)言和語(yǔ)法描述92語(yǔ)言描述體系結(jié)構(gòu)2語(yǔ)言和文法的基本概念2從語(yǔ)言構(gòu)造文法32語(yǔ)法樹(shù)、分析樹(shù)與二義文法2詞法分析1024詞法分析程序的作用和基本構(gòu)造 過(guò)程1正規(guī)表達(dá)式、正規(guī)語(yǔ)言與正規(guī)文法2有限自動(dòng)機(jī)724詞法分析程序生成工具Lex1語(yǔ)法分析15412語(yǔ)法分析基本過(guò)程和方法概述1自頂向下語(yǔ)法分析424自底向上語(yǔ)法分析728二義文法的語(yǔ)法分析2語(yǔ)法分析程序生成工具 YACC1語(yǔ)義分析52屬性文法2屬性文法中的綜合屬性值計(jì)算方 法22類型檢查1中間代碼生成62常見(jiàn)中間代碼形式1典型語(yǔ)句生成三地址碼的方法1典型語(yǔ)句生成四元式的方法42運(yùn)行時(shí)環(huán)境52程序執(zhí)行過(guò)程與激活樹(shù)1程序運(yùn)行時(shí)數(shù)據(jù)存儲(chǔ)空間分配策 略1棧式存儲(chǔ)分配策略32程序優(yōu)化92程序分塊與程序流圖2塊內(nèi)優(yōu)化32循環(huán)優(yōu)化2基于數(shù)據(jù)流分析的優(yōu)化2復(fù)習(xí)2六、考核方式總評(píng)成績(jī)=平時(shí)成績(jī)（包括作業(yè)和考勤）+上機(jī)實(shí)驗(yàn)+期末考試成績(jī)平時(shí)成績(jī)占10%上機(jī)試驗(yàn)占20%期末考試成績(jī)占70%七、教材及參考書(shū)1