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

1、編譯原理Compiler Principles一、課程基本情況課程類別：專業(yè)主干課課程學(xué)分：3 學(xué)分課程總學(xué)時：48學(xué)時，其中講課：40學(xué)時，實(shí)驗(yàn)（含上機(jī)）： 8學(xué)時課程性質(zhì)：必修 開課學(xué)期：第6學(xué)期先修課程： 離散數(shù)學(xué)、高級語言程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)適用專業(yè)： 計算機(jī)科學(xué)與技術(shù)教 材：程序設(shè)計語言編譯原理（第三版），國防科技大學(xué)出版社，陳火旺等，2003年開課單位： 計算機(jī)與軟件學(xué)院 軟件工程系二、課程性質(zhì)、教學(xué)目標(biāo)和任務(wù) 編譯系統(tǒng)是計算機(jī)系統(tǒng)中最重要的系統(tǒng)軟件之一，對編譯系統(tǒng)的理論基礎(chǔ)、構(gòu)造方法、實(shí)現(xiàn)技術(shù)的研究是計算機(jī)科學(xué)研究的基本內(nèi)容。本課程的主要內(nèi)容是從計算機(jī)科學(xué)中形式語言與自動機(jī)的基本理

2、論出發(fā)，全面系統(tǒng)地介紹編譯系統(tǒng)程序的主要功能、設(shè)計原理和構(gòu)造方法，重點(diǎn)解決高級程序設(shè)計語言翻譯器時遇到的普遍問題，而不偏向于某種源語言或目標(biāo)機(jī)器。本課程討論的概念和技術(shù)也可應(yīng)用于一般的軟件設(shè)計之中。課程要求學(xué)生掌握編譯的基本理論、常用的編譯技術(shù)，了解編譯過程及編譯系統(tǒng)的構(gòu)造（機(jī)理和結(jié)構(gòu)）。設(shè)置該課目的是系統(tǒng)地向?qū)W生介紹編譯系統(tǒng)的結(jié)構(gòu)、工作流程及編譯程序各組成部分的設(shè)計原理和實(shí)現(xiàn)技術(shù)，使學(xué)生既掌握編譯理論和方法方面的基本知識，也具有設(shè)計、實(shí)現(xiàn)、分析和維護(hù)編譯程序的初步能力。三、教學(xué)內(nèi)容和要求第1章 引論(2學(xué)時)1.1編譯程序的概念（0.5學(xué)時）（1）了解編譯程序的起源（2）程序設(shè)計語言的發(fā)展（

3、3）理解編譯程序和解釋程序的區(qū)別重點(diǎn)：編譯程序的概念，理解編譯程序和解釋程序1.2編譯程序的結(jié)構(gòu)（1學(xué)時）（1）了解編譯程序的基本工作過程（2）理解編譯程序的基本結(jié)構(gòu)（3）掌握編譯程序各邏輯結(jié)構(gòu)的主要功能；重點(diǎn)：編譯程序的基本結(jié)構(gòu)和各個邏輯結(jié)構(gòu)的主要功能1.3編譯程序的生成（0.5學(xué)時）（1）了解編譯程序與程序設(shè)計環(huán)境（2）了解編譯技術(shù)的應(yīng)用（3）理解編譯程序的生成過程重點(diǎn)：編譯程序的生成過程第2章 高級語言及語法描述(4學(xué)時)2.1 程序語言的定義 （1學(xué)時）（1）理解形式語言中語法的概念（2）了解語義的概念重點(diǎn)：形式語言中文法的定義2.2 高級語言的一般特性 （1學(xué)時）（1）了解高級語言的

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

5、）掌握確定有限自動機(jī)（DFA） （3）掌握非確定有限自動機(jī)（NFA） （4）掌握正規(guī)文法與有限自動機(jī)的等價性 （5）掌握正規(guī)式與有限自動機(jī)的等價性 （6）掌握確定有限自動機(jī)的化簡 重點(diǎn)：DFA的概念和工作原理難點(diǎn)：正則文法、有窮狀態(tài)自動機(jī)和正則式間的相互轉(zhuǎn)化第4章 語法分析自上而下分析 （6學(xué)時）4.1 語法分析器的功能 （0.5學(xué)時）了解語法分析程序的功能4.2 自上而下分析面臨的問題 （0.5學(xué)時）掌握自上而下分析面臨的問題重點(diǎn)：自上而下分析面臨的問題4.3 LL（1）分析法 （2學(xué)時）（1）掌握左遞歸的消除方法 （2）掌握避免回溯、提左因子的方法（3）理解LL（1）分析條件 重點(diǎn)：左遞歸

6、的消除方法和避免回溯的方法4.4 遞歸下降分析程序構(gòu)造（0.5學(xué)時）理解遞歸下降分析程序的構(gòu)造方法重點(diǎn)：遞歸下降分析程序的構(gòu)造4.5 預(yù)測分析程序 （1.5學(xué)時）（1）理解預(yù)測分析程序工作過程 （2）掌握預(yù)測分析表的構(gòu)造 （3）了解LL（1）分析中的錯誤處理 重點(diǎn)：預(yù)測分析表的構(gòu)造第5章 語法分析自下而上分析 （6學(xué)時）5.1 自下而上分析基本問題（0.5學(xué)時） （1）了解規(guī)范歸約 （2）掌握歸約的方法 （3）理解符號棧的使用與語法樹的表示重點(diǎn)：規(guī)約的方法 5.2 算符優(yōu)先分析 （2學(xué)時）（1）掌握算符優(yōu)先分析算法 （2）了解優(yōu)先函數(shù) （3）了解算符優(yōu)先分析中的出錯處理 重點(diǎn)：算符優(yōu)先分析表的

7、構(gòu)造5.3 LR分析法 （3學(xué)時）（1）理解LR分析器的工作方法（2）掌握LR（0）項(xiàng)目集族和LR（0）分析表的構(gòu)造 （3）掌握SLR分析表的構(gòu)造 重點(diǎn)：LR分析法的工作方法難點(diǎn)：LR（0）分析表的構(gòu)造 5.4 語法分析器的自動產(chǎn)生工具Yacc（0.5學(xué)時） 了解Yacc工具的使用第6章 屬性文法和語法制導(dǎo)翻譯 （4學(xué)時）6.1 屬性文法 （2學(xué)時）（1）了解基于屬性文法的處理方法 （2）理解屬性的依賴圖和屬性計算方法 （3）了解S一屬性文法的自下而上計算（4）了解L一屬性文法和自頂向下翻譯 重點(diǎn)：屬性的分類難點(diǎn)：屬性的計算方法6.2翻譯模式 （2學(xué)時）（1）理解自頂向下翻譯 （2）了解遞歸下

8、降翻譯器的設(shè)計第7章 語義分析和中間代碼產(chǎn)生 （4學(xué)時）7.1 中間語言（0.5學(xué)時）（1）理解后綴式、圖表示法、三地址代碼的中間代碼表示方法（2）掌握四元式的表示方法重點(diǎn)：四元式表示形式 7.2 簡單語句的翻譯（1.5學(xué)時）（1）理解說明語句的翻譯方法（2）理解賦值語句的翻譯 （3）理解簡單算術(shù)表達(dá)式及賦值語句 （4）理解數(shù)組元素的引用 （5）了解記錄中域的引用 重點(diǎn)：賦值語句的翻譯和數(shù)組的翻譯難點(diǎn)：數(shù)組的翻譯7.3 布爾表達(dá)式和控制結(jié)構(gòu)的翻譯 （2學(xué)時）（1）了解數(shù)值表示法 （2）掌握控制結(jié)構(gòu)中的布爾式翻譯 （3）理解簡單控制語句的翻譯 重點(diǎn)：布爾表達(dá)式和if控制結(jié)構(gòu)的翻譯難點(diǎn)：理解控制結(jié)

9、構(gòu)的目標(biāo)結(jié)構(gòu)第8章 運(yùn)行時存儲空間組織 （4學(xué)時）8.1 目標(biāo)程序運(yùn)行時的活動 （2學(xué)時）（1）了解過程（函數(shù)）的活動 （2）理解參數(shù)傳遞 （3）了解運(yùn)行時存儲器的劃分 （2）理解活動記錄 8.2存儲分配策略 （2學(xué)時）（1）了解靜態(tài)存儲分配 （2）理解簡單的棧式存儲分配 （3）理解C的活動記錄及函數(shù)調(diào)用、函數(shù)進(jìn)入、數(shù)組空間分配和過程返回 （4）了解嵌套過程語言的棧式實(shí)現(xiàn) （5）了解堆式動態(tài)存儲分配重點(diǎn)：理解參數(shù)傳遞方法和C語言活動記錄的結(jié)構(gòu)第9章 優(yōu)化 （4學(xué)時）（1）理解局部優(yōu)化的基本方案 （2）掌握基本塊的DAG表示及其應(yīng)用 （3）了解循環(huán)優(yōu)化、代碼外提、強(qiáng)度削弱、刪除歸納變量等常用局部優(yōu)化方法重點(diǎn)： 基本塊的DAG表示及其應(yīng)用 四、課程考核（1）作業(yè)等：作業(yè)：10次，課程論文： 篇；（2）考核方式：閉卷考試（3）總評成績計算方式：（平時成績、實(shí)驗(yàn)成績、期中考試成績和期末考試成績等綜合計算）平時成績*20%+實(shí)驗(yàn)成績*10%+期中考試成績*（15%20%）+期末考試成績*（50%55%）五、參考書目1.Alfred V