《編譯原理》課程教學大綱

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

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

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

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

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

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

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

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

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