《編譯原理 I》教學(xué)大綱

1、編譯原理 I（Compiler Principles）課程代碼：3161040學(xué)分：3 學(xué)時(shí)：48 （其中：課程教學(xué)學(xué)時(shí)：40，實(shí)驗(yàn)學(xué)時(shí)：8）先修課程：程序設(shè)計(jì)基礎(chǔ)、離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)組成原理適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)教材：程序設(shè)計(jì)語言編譯原理，國防科技大學(xué)出版社，陳火旺等，2016年第3版開課學(xué)院：計(jì)算機(jī)與軟件學(xué)院一、課程性質(zhì)與課程目標(biāo)（一）課程性質(zhì)編譯原理是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門理論性與實(shí)踐性很強(qiáng)的專業(yè)課，以離散數(shù)學(xué)、高級語言程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)組成原理等作為先修課程。編譯原理課程蘊(yùn)涵著復(fù)雜問題的抽象能力、解決問題的分析思路和方法等分析問題能力的培養(yǎng)。通過本課程的學(xué)習(xí)，學(xué)

2、生應(yīng)該掌握程序設(shè)計(jì)語言翻譯過程的基本原理、方法、技術(shù)，為學(xué)生畢業(yè)后從事復(fù)雜軟件設(shè)計(jì)及計(jì)算機(jī)科學(xué)研究等相關(guān)工作培養(yǎng)理論學(xué)習(xí)基礎(chǔ)以及實(shí)踐技能的訓(xùn)練。學(xué)習(xí)課程有利于對程序設(shè)計(jì)語言的理解，可以便于掌握新的語言工具。同時(shí)，能夠利用形式化描述工具，表示復(fù)雜問題及求解過程。編譯系統(tǒng)是計(jì)算機(jī)系統(tǒng)中最重要的系統(tǒng)軟件之一，因此，對編譯系統(tǒng)的理論基礎(chǔ)、構(gòu)造方法、實(shí)現(xiàn)技術(shù)的學(xué)習(xí)是計(jì)算機(jī)與技術(shù)專業(yè)的學(xué)生重要專業(yè)內(nèi)容。課程從計(jì)算機(jī)科學(xué)中形式語言與自動(dòng)機(jī)的基本理論出發(fā)，全面系統(tǒng)地介紹編譯系統(tǒng)程序的主要功能、設(shè)計(jì)原理和構(gòu)造方法，重點(diǎn)解決高級程序設(shè)計(jì)語言翻譯器時(shí)遇到的普遍問題，而不偏向于某種源語言或目標(biāo)機(jī)器。本課程討論的概念和

3、技術(shù)也可應(yīng)用于一般的軟件設(shè)計(jì)之中。（二）課程目標(biāo)課程要求學(xué)生掌握編譯的基本理論、常用的編譯技術(shù)，了解編譯過程及編譯系統(tǒng)的構(gòu)造原理。目的是系統(tǒng)地向?qū)W生介紹編譯系統(tǒng)的結(jié)構(gòu)、工作流程及編譯程序各組成部分的設(shè)計(jì)原理和實(shí)現(xiàn)技術(shù)，使學(xué)生既掌握編譯理論和方法方面的基本知識，也具有設(shè)計(jì)、實(shí)現(xiàn)、分析和維護(hù)編譯程序的初步能力。課程目標(biāo)包括知識目標(biāo)和能力目標(biāo)，具體如下：課程目標(biāo)1：掌握程序設(shè)計(jì)語言編譯過程和編譯程序設(shè)計(jì)的結(jié)構(gòu)，以及構(gòu)造描述語言的文法。理解基于DAG的局部優(yōu)化和循環(huán)優(yōu)化等編譯器的優(yōu)化策略。培養(yǎng)學(xué)生解決計(jì)算機(jī)領(lǐng)域復(fù)雜工程問題的一般思路，并能夠判別計(jì)算機(jī)系統(tǒng)的復(fù)雜性，分析計(jì)算機(jī)系統(tǒng)優(yōu)化方法；課程目標(biāo)2：理

4、解形式化語言的表示語言的方法，理解簡單的圖靈機(jī)（有窮狀態(tài)自動(dòng)機(jī)與下推自動(dòng)機(jī)）的初步知識，了解自動(dòng)機(jī)技術(shù)在計(jì)算機(jī)科學(xué)領(lǐng)域中的重要作用。為深入學(xué)習(xí)計(jì)算機(jī)科學(xué)領(lǐng)域中的基本理論和基本方法奠定基礎(chǔ)。培養(yǎng)學(xué)生設(shè)計(jì)復(fù)雜軟件設(shè)計(jì)的基本方法，并能夠針對一個(gè)系統(tǒng)或者過程進(jìn)行抽象分析與識別，選擇或建立一種模型抽象表達(dá)，并進(jìn)行推理、求解和驗(yàn)證。（三）課程目標(biāo)與專業(yè)畢業(yè)要求指標(biāo)點(diǎn)的對應(yīng)關(guān)系本課程支撐專業(yè)培養(yǎng)計(jì)劃中的畢業(yè)要求指標(biāo)點(diǎn)1.2和2.1。畢業(yè)要求指標(biāo)點(diǎn)1.2：具備扎實(shí)的計(jì)算機(jī)工程基礎(chǔ)知識，了解通過計(jì)算機(jī)解決復(fù)雜工程問題的基本方法，并遵循復(fù)雜系統(tǒng)開發(fā)的工程化基本要求。畢業(yè)要求指標(biāo)點(diǎn)2.1：應(yīng)用數(shù)學(xué)、自然科學(xué)和工程科

5、學(xué)的基本原理，針對一個(gè)系統(tǒng)或者過程進(jìn)行抽象、分析與識別，并進(jìn)行問題推理、求解和驗(yàn)證。課程目標(biāo)畢業(yè)要求指標(biāo)點(diǎn)課程目標(biāo)1課程目標(biāo)2畢業(yè)指標(biāo)點(diǎn)1.2畢業(yè)指標(biāo)點(diǎn)2.1二、課程內(nèi)容及教學(xué)要求課程教學(xué)內(nèi)容包括：編譯過程和編譯程序的結(jié)構(gòu)，文法的構(gòu)造，非確定有限自動(dòng)機(jī)的確定化和最小化，正規(guī)表達(dá)式與有限自動(dòng)機(jī)的等價(jià)性，消除文法的左遞歸和回溯，遞歸下降子程序的構(gòu)造，預(yù)測分析表的構(gòu)造，算符優(yōu)先分析表和優(yōu)先函數(shù)的構(gòu)造，LR分析表的構(gòu)造，屬性的計(jì)算，翻譯模式的構(gòu)造，說明語句、賦值語句、布爾表達(dá)式和控制語句等的翻譯，名字的作用范圍和運(yùn)行時(shí)存儲空間的分配，基于DAG的局部優(yōu)化和循環(huán)優(yōu)化等。課程基本要求是：掌握編譯的基本理論

6、、常用的編譯技術(shù)，了解編譯過程及編譯系統(tǒng)的構(gòu)造原理。目的是系統(tǒng)地向?qū)W生介紹編譯系統(tǒng)的結(jié)構(gòu)、工作流程及編譯程序各組成部分的設(shè)計(jì)原理和實(shí)現(xiàn)技術(shù)，使學(xué)生既掌握編譯理論和方法方面的基本知識，也具有設(shè)計(jì)、實(shí)現(xiàn)、分析和維護(hù)編譯程序的初步能力。第1章引論（一）教學(xué)內(nèi)容編譯器的邏輯結(jié)構(gòu)(工作階段)編譯程序的結(jié)構(gòu)編譯程序的生成（二）教學(xué)要求了解編譯程序的起源程序設(shè)計(jì)語言的發(fā)展理解編譯程序和解釋程序的區(qū)別了解編譯程序的基本工作過程理解編譯程序的基本結(jié)構(gòu)掌握編譯程序各邏輯結(jié)構(gòu)的主要功能；（三）重點(diǎn)與難點(diǎn)1. 重點(diǎn)編譯程序的基本結(jié)構(gòu)和各個(gè)邏輯結(jié)構(gòu)的主要功能2. 難點(diǎn)編譯器的組織與設(shè)計(jì)第2章高級語言及語法描述（一）教學(xué)

7、內(nèi)容程序語言的定義高級語言的一般特性程序語言的語法描述（二）教學(xué)要求理解形式語言中語法的概念了解語義的概念了解高級語言的分類了解高級語言的結(jié)構(gòu)理解上下文無關(guān)文法理解語法分析樹與二義性理解形式語言的分類（三）重點(diǎn)與難點(diǎn)1. 重點(diǎn)（1）形式語言中文法的定義（2）形式語言中語言的定義（3）形式語言中文法的分類2. 難點(diǎn)文法、推導(dǎo)及語言的形式化定義，上下文無關(guān)文法、正則文法和對應(yīng)語言的相互轉(zhuǎn)換第3章詞法分析教學(xué)內(nèi)容詞法分析器的功能詞法分析器的設(shè)計(jì)正規(guī)表達(dá)式與有限自動(dòng)機(jī)（二）教學(xué)要求了解詞法分析器的功能和輸出形式理解詞法分析器作為一個(gè)獨(dú)立子程序掌握狀態(tài)轉(zhuǎn)換圖及實(shí)現(xiàn)理解單詞符號的識別：超前搜索掌握正規(guī)式與

8、正規(guī)集掌握確定有限自動(dòng)機(jī)（DFA）掌握非確定有限自動(dòng)機(jī)（NFA）掌握正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性掌握正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性掌握確定有限自動(dòng)機(jī)的化簡了解Lex工具的使用方法（三）重點(diǎn)與難點(diǎn)1. 重點(diǎn)DFA的概念和工作原理；詞法分析器的功能及詞法分析器的實(shí)現(xiàn)；lex工具的使用2. 難點(diǎn)狀態(tài)轉(zhuǎn)換圖及實(shí)現(xiàn)；正則文法、有窮狀態(tài)自動(dòng)機(jī)和正則式間的相互轉(zhuǎn)化；正則表達(dá)式轉(zhuǎn)化為最小化的DFA的過程第4章語法分析自上而下分析教學(xué)內(nèi)容語法分析器的功能自上而下分析面臨的問題LL（1）分析法遞歸下降分析程序構(gòu)造預(yù)測分析程序（二）教學(xué)要求了解語法分析程序的功能掌握自上而下分析面臨的問題掌握左遞歸的消除方法掌握避免回溯

9、、提左因子的方法理解LL（1）文法的定義理解遞歸下降分析程序的構(gòu)造方法理解預(yù)測分析程序工作過程掌握預(yù)測分析表的構(gòu)造了解LL（1）分析中的錯(cuò)誤處理理解詞法分析器作為一個(gè)獨(dú)立子程序（三）重點(diǎn)與難點(diǎn)1. 重點(diǎn)自上而下分析面臨的問題；預(yù)測分析表的構(gòu)造；左遞歸的消除方法和避免回溯的方法；遞歸下降分析程序的構(gòu)造2. 難點(diǎn) First集合與Follow集合的含義與計(jì)算方法第5章語法分析自上而下分析教學(xué)內(nèi)容自下而上分析基本問題算符優(yōu)先分析LR分析法語法分析器的自動(dòng)產(chǎn)生工具Yacc（二）教學(xué)要求掌握歸約的方法理解符號棧的使用與語法樹的表示掌握算符優(yōu)先分析算法了解優(yōu)先函數(shù)了解算符優(yōu)先分析中的出錯(cuò)處理理解LR分析器

10、的工作方法掌握LR（0）項(xiàng)目集族和LR（0）分析表的構(gòu)造掌握SLR分析表的構(gòu)造了解Yacc工具的使用（三）重點(diǎn)與難點(diǎn)1. 重點(diǎn)規(guī)約的方法；算符優(yōu)先分析表的構(gòu)造；LR分析法的工作方法2. 難點(diǎn)項(xiàng)目集規(guī)范組的構(gòu)造與LR（0）分析表的構(gòu)造第6章屬性文法和語法制導(dǎo)翻譯及中間代碼生成教學(xué)內(nèi)容屬性文法翻譯模式語義處理語法制導(dǎo)翻譯中間代碼簡單賦值語句的翻譯數(shù)組的翻譯布爾表達(dá)式和控制結(jié)構(gòu)的翻譯（二）教學(xué)要求了解基于屬性文法的處理方法理解屬性的依賴圖和屬性計(jì)算方法了解S-屬性文法的自下而上計(jì)算了解L-屬性文法和自頂向下翻譯理解自頂向下翻譯及常見語言的翻譯及中間代碼表示了解遞歸下降翻譯器的設(shè)計(jì)理解符號棧的使用與語

11、法樹的表示理解后綴式、圖表示法、三地址代碼的中間代碼表示方法掌握四元式的表示方法理解說明語句的翻譯方法理解賦值語句的翻譯理解簡單算術(shù)表達(dá)式及賦值語句理解數(shù)組元素的引用掌握控制結(jié)構(gòu)中的布爾式翻譯理解簡單控制語句的翻譯（三）重點(diǎn)與難點(diǎn)1. 重點(diǎn)屬性的分類及屬性的依賴圖；常見語言的翻譯及中間代碼表示；四元式表示形式；賦值語句的翻譯；數(shù)組的翻譯；布爾表達(dá)式和if控制結(jié)構(gòu)的翻譯2. 難點(diǎn)屬性的計(jì)算方法；數(shù)組的翻譯；理解控制結(jié)構(gòu)的目標(biāo)結(jié)構(gòu)*第7章符號表的管理與組織教學(xué)內(nèi)容理解符號表的構(gòu)成教學(xué)要求掌握符號表的構(gòu)造與組織（三）重點(diǎn)與難點(diǎn)1. 重點(diǎn)符號表的結(jié)構(gòu)與組織2. 難點(diǎn)符號表的存儲第八章運(yùn)行時(shí)存儲空間組織

12、教學(xué)內(nèi)容目標(biāo)程序運(yùn)行時(shí)的活動(dòng)存儲分配策略教學(xué)要求了解過程（函數(shù)）的活動(dòng)理解參數(shù)傳遞基本過程了解運(yùn)行時(shí)存儲器的劃分理解活動(dòng)記錄了解靜態(tài)存儲分配理解簡單的棧式存儲分配理解C的活動(dòng)記錄及函數(shù)調(diào)用、函數(shù)進(jìn)入、數(shù)組空間分配和過程返回了解嵌套過程語言的棧式實(shí)現(xiàn)了解堆式動(dòng)態(tài)存儲分配（三）重點(diǎn)與難點(diǎn)1. 重點(diǎn)理解參數(shù)傳遞方法和C語言活動(dòng)記錄的結(jié)構(gòu)2. 難點(diǎn)C語言的函數(shù)調(diào)用的活動(dòng)記錄組織與管理第9章優(yōu)化教學(xué)內(nèi)容什么是優(yōu)化局部優(yōu)化循環(huán)優(yōu)化教學(xué)要求理解局部優(yōu)化的基本方案掌握基本塊的DAG表示及其應(yīng)用了解循環(huán)優(yōu)化、代碼外提、強(qiáng)度削弱、刪除歸納變量等常用局部優(yōu)化方法（三）重點(diǎn)與難點(diǎn)1. 重點(diǎn)基本塊的DAG表示及其應(yīng)用2

13、. 難點(diǎn)構(gòu)造基本塊對應(yīng)的DAG圖；循環(huán)優(yōu)化三、本課程開設(shè)的實(shí)驗(yàn)項(xiàng)目編號實(shí)驗(yàn)項(xiàng)目名稱學(xué)時(shí)類型要求支撐的課程目標(biāo)1詞法分析程序的實(shí)現(xiàn)4設(shè)計(jì)性必做課程目標(biāo)1，22遞歸下降語法分析程序的實(shí)現(xiàn)4綜合性必做課程目標(biāo)1，23簡單編譯器(解釋器)的實(shí)現(xiàn)選做課程目標(biāo)1，2實(shí)驗(yàn)1：詞法分析程序的實(shí)現(xiàn)1. 實(shí)驗(yàn)?zāi)康募耙罄斫鈶?yīng)用DFA表示高級語言源程序的單詞構(gòu)成；深刻領(lǐng)會狀態(tài)轉(zhuǎn)換圖的含義，逐步理解有限自動(dòng)機(jī)；掌握手工生成詞法分析器的方法，了解詞法分析器的內(nèi)部工作原理。2. 實(shí)驗(yàn)主要內(nèi)容按規(guī)則拼單詞，并轉(zhuǎn)換成二元式形式刪除注釋行刪除多余的空格、回車符、制表符列表打印源程序，按照源程序的行打印，在每行的前面加上行號，并

14、且打印出每行包含的記號的二元形式填寫并生成符號表發(fā)現(xiàn)并定位錯(cuò)誤3. 重難點(diǎn)分析浮點(diǎn)數(shù)的合法性與指出單詞的錯(cuò)誤類型，符號表的建立與管理實(shí)驗(yàn)2. 遞歸下降語法分析程序的實(shí)現(xiàn)1. 實(shí)驗(yàn)?zāi)康募耙罄斫飧呒壵Z言語法的表示工具上下文無關(guān)文法；深刻領(lǐng)會規(guī)則的含義，并能夠利用遞歸程序模擬推導(dǎo)的過程；掌握手工生成語法分析器的方法，了解語法分析器的內(nèi)部工作原理。2. 實(shí)驗(yàn)主要內(nèi)容1）設(shè)計(jì)合適的文法的規(guī)則存儲結(jié)構(gòu)；2）利用遞歸程序模擬文法的推導(dǎo)句子的基本過程。3. 重難點(diǎn)1）構(gòu)造合適的存儲結(jié)構(gòu)存儲文法中的規(guī)則；2）設(shè)計(jì)遞歸程序完成推導(dǎo)過程。實(shí)驗(yàn)3. （選做）簡單編譯器(解釋器)的實(shí)現(xiàn)1. 實(shí)驗(yàn)?zāi)康募耙罄斫飧呒壵Z言

15、語法的表示方法，使用Lex和Yacc工具實(shí)現(xiàn)定義語言的詞法語法及語義分析；深刻領(lǐng)會規(guī)則的含義，并能夠利用利用屬性文法設(shè)計(jì)設(shè)計(jì)實(shí)現(xiàn)中間代碼生成任務(wù)；掌握編譯器的基本設(shè)計(jì)原理和設(shè)計(jì)方法及工作原理；以小組答辯形式解題，并給出實(shí)習(xí)分?jǐn)?shù)。2. 實(shí)驗(yàn)主要內(nèi)容1）自定義語言的規(guī)則；2）實(shí)現(xiàn)所定義語言的簡單翻譯過程。3. 重難點(diǎn)1）構(gòu)造合適的存儲結(jié)構(gòu)存儲文法中的規(guī)則；2）使用語法工具實(shí)現(xiàn)簡單編譯器的前端任務(wù)；3）設(shè)計(jì)合適的屬性文法實(shí)現(xiàn)語義以及中間代碼生成任務(wù)，最好能給出局部優(yōu)化的方法。注：本課程為專業(yè)課，授課對象為三年級的學(xué)生，實(shí)驗(yàn)類型主要包括驗(yàn)證性和綜合性實(shí)驗(yàn)，均需要提交實(shí)驗(yàn)報(bào)告，實(shí)驗(yàn)報(bào)告主要包括實(shí)驗(yàn)?zāi)康摹?/p>

16、要求和內(nèi)容，設(shè)計(jì)說明文檔，測試用例、運(yùn)行結(jié)果、源代碼以及總結(jié)。四、學(xué)時(shí)分配及教學(xué)方法章教學(xué)形式及學(xué)時(shí)分配主要教學(xué)方法支撐的課程目標(biāo)課堂教學(xué)實(shí)驗(yàn)上機(jī)課程實(shí)踐小計(jì)第一章引論22講授課程目標(biāo)1第二章高級語言及語法描述44講授、習(xí)題課程目標(biāo)1，2第三章詞法分析6410講授、習(xí)題、實(shí)驗(yàn)課程目標(biāo)1，2第四章語法分析自上而下分析6410講授、演示、實(shí)驗(yàn)課程目標(biāo)1，2第五章語法分析自上而下分析66講授、演示、習(xí)題課程目標(biāo)1，2第六章屬性文法和語法制導(dǎo)翻譯及中間代碼生成88講授、演示、習(xí)題課程目標(biāo)1，2*第七章符號表的管理與組織00自學(xué)課程目標(biāo)1，2第八章運(yùn)行時(shí)存儲空間組織44講授、演示、習(xí)題課程目標(biāo)1，2第九

17、章優(yōu)化44講授、演示、習(xí)題課程目標(biāo)1，2合計(jì)40848注：1.課程實(shí)踐學(xué)時(shí)按相關(guān)專業(yè)培養(yǎng)計(jì)劃列入表格； 2.主要教學(xué)方法包括講授法、討論法、演示法、研究型教學(xué)方法（基于問題、項(xiàng)目、案例等教學(xué)方法）等。五、課程考核課程考核方式包括期末考試、平時(shí)作業(yè)及實(shí)習(xí)情況考核（其中包括筆記、大作業(yè)等）和實(shí)驗(yàn)情況考核。考核形式考核要求考核權(quán)重備注平時(shí)作業(yè)課后完成2030個(gè)習(xí)題，主要考核學(xué)生對每節(jié)課知識點(diǎn)的復(fù)習(xí)、理解和掌握度，按10%計(jì)入總成績；可讓學(xué)生查閱資料，了解本課程相關(guān)技術(shù)發(fā)展情況，自主學(xué)習(xí)并完成10%平時(shí)作業(yè)情況期中測試筆試，閉卷。題型與期末試卷類似10%25%無期中考試為0實(shí)驗(yàn)完成2個(gè)實(shí)驗(yàn)（或者選做任

18、務(wù)，以答辯形式考核），主要訓(xùn)練學(xué)生應(yīng)用所學(xué)知識構(gòu)建實(shí)驗(yàn)系統(tǒng)，并進(jìn)行實(shí)驗(yàn)的能力，最后按10%計(jì)入課程總成績10%15%實(shí)驗(yàn)報(bào)告5%；程序檢查通過5%，優(yōu)秀實(shí)習(xí)增加5%期末考試試卷題型包括簡答題、分析題2大類，以卷面成績的60-70%計(jì)入課程總成績60%70%期末考試采用閉卷筆試。六、參考書目及學(xué)習(xí)資料美 Alfred V.Aho等著，趙建華，鄭滔等譯，編譯原理（第2版），機(jī)械工業(yè)出版社，2009。張幸兒，計(jì)算機(jī)編譯原理，科學(xué)出版社，2008勞頓著，馮博琴等譯，編譯原理及實(shí)踐，機(jī)械工業(yè)出版社，2004七、大綱說明1. 主要采用多媒體教學(xué)手段，主要知識點(diǎn)板書與多媒體相結(jié)合，多種教學(xué)手段綜合運(yùn)用。2. 課后共需完成近2030個(gè)習(xí)題作業(yè)，以評價(jià)學(xué)生對所學(xué)內(nèi)容的理解和應(yīng)用情況。附錄1：實(shí)驗(yàn)考核方式及評分細(xì)則本實(shí)驗(yàn)以考查為主，考核的內(nèi)容包括實(shí)驗(yàn)過程的表現(xiàn)（其中包含分析與解決問題的能力）、實(shí)驗(yàn)報(bào)告的質(zhì)量等。分析與解決問題的能力采用提問和現(xiàn)場操作的方式進(jìn)行。實(shí)驗(yàn)成績中出勤、預(yù)習(xí)占10%，實(shí)驗(yàn)過程表現(xiàn)占60、實(shí)驗(yàn)報(bào)告及思考題占30。成績組成考核/