編譯原理教學大綱

一、說明

（一）課程性質

《編譯原理》課程是計算機科學與技術專業、軟件工程專業學生必須掌握的重要專業必修課，

也是一門理論性、實踐性和技術性很強的課程。編譯系統是現代計算機系統的基本組成之一，編譯

程序構造的基本原理和技術不僅應用于編譯程序的設計，也廣泛應用于一般軟件的設計和實現。

（二）教學目的

本課程的學習目的在于使學生掌握編譯程序的基本概念、基本原理、設計方法和實現技術，具

有初步分析實際編譯系統的能力，并能編制和調試簡單編譯程序，為今后從事編譯及其他有關軟件

的研究和開發工作打下較為堅實的基礎。

（三）教學內容

本課程系統講述程序設計語言的編譯程序的概念、構造、以及實現的主要算法和技術。通過對

本課程的學習，使學生較為透徹地理解編譯程序的概念、原理，了解語言翻譯的全過程（詞法分析、

語法分析、語義分析與中間代碼生成、代碼優化和目標代碼生成），掌握編譯程序中常用的主要算法

和技巧；并通過上機實習初步掌握編譯器構造的基本方法。

（四）教學時數

教學總學時數90,其中：

理論課54

實驗課36

（五）教學方式

理論講授與實驗結合

二、本文

理論部分

第1章緒論

教學要點：

1.高級語言程序的執行方式

2.編譯程序的基本結構及其各階段的基本任務

教學時數：

3學時

教學內容：

M引言

了解：高級程序設計語言與編譯技術之間的聯系

1.2程序設“語言與程序（1學時）

了解：程序設計語言的定義涉及到的四個方面

掌握：BNF范式

高級語言程序的兩種執行方式

1.2編譯程序構造及有關概念（2學時）

理解：編譯程序的功能

掌握：編譯程序基本結構以及每一階段的任務

第2章文法與語言

教學要點：

1、符號串和符號串集合及其運算。

2、文法和語言的形式定義。

3、文法和語言的分類

4、文法等價變換

5、語法樹，句型分析。

教學時數：

9學時

教學內容：

2.1符號串與符號串集合（1學時）

了解：符號串與符號串集合的定義，以及相關運算

2.2文法與語言的形式定義（2學時）

理解：規則和文法的定義

推導和歸約

熟練掌握：

句子與句型，短語與簡單短語，句柄

語言的定義，由文法產生句型（句子），由句型（句子）確定文法

難點：短語、簡單短語、句柄的求法

由文法產生句型（句子），由句型（句子）確定文法

2.3語言的分類（1學時）

了解：形式語言與自動機

掌握：Chomsky文法的定義

文法和語言的分類

2.4文法等價于等價變換（4學時）

掌握：文法等價的概念

熟練掌握：

壓縮文法等價變換

消去左遞歸的文法等價變換

難點：壓縮文法等價變換

消去左遞歸的文法等價變換

2.5語法分析樹與句型分析（1學時）

了解：句型分析存在的基本問題

理解：語法分析樹

規范推導和規范歸約

掌握：文法二義性的判斷

句型分析技術

難點：文法二義性的判斷

第3章詞法分析

教學要點：

1、狀態轉換圖的構造和運行

2、DFA和NFA以及他們之間的轉換

3、詞法分析程序的實現

教學時數：

7學時

教學內容：

3.1引言

了解：詞法分析與詞法分析程序

詞法分析程序的實現方式

3.2正則表達式與有窮狀態自動機（4）

了解：正則式的性質

掌握：正則式

正則式和有窮自動機之間的相互轉換

正則文法構造正則式

熟練掌握：

構造狀態轉換圖，運行狀態轉換圖

確定的有窮自動機（DFA）,不確定的有窮自動機（NFA）

NFA—DFA的轉換，DFA的化簡

難點：NFA—DFA的轉換，DFA的化簡

正則式和有窮自動機之間的相互轉換

3.3詞法分析程序的實現（1學時）

了解：手工編寫詞法分析程序的基本思路

理解：單詞的描述工具

3.4詞法分析程序的自動生成（1學時）

理解：詞法分析程序自動生成的思想和實質

第4章語法分析一自頂向下分析技術

教學要點：

1、自頂向下分析技術解決的問題

2、遞歸下降分析技術及實現

3、預測分析技術及實現

教學時數：

8學時

教學內容：

4.1引言

理解；自頂向下分析技術的實質和要解決的問題

4.2帶回溯的自頂向下分析技術(2學時)

理解：帶回溯的自頂向下分析技術的基本思想，存在的問題及解決方法

4.3無回溯的自頂向下分析技術(6學時)

理解：遞歸下降分析技術的實現思想

遞歸下降程序的構造方法

應用遞歸下降分析技術識別句子

掌握：實施無回溯的自頂向下分析技術的先決條件

預測分析技術的基本實現思想

應用預測分析技術進行句型分析時語法分析樹的構造

熟練掌握：

預測分析表的構造

應用預測分析技術進行句型識別

第5章語法分析一自底向上分析技術

教學要點：

1.算符優先分析技術

2.LR(k)分析技術

教學時數：

12學時

教學內容：

5.1引言(1學時)

理解：自底向上分析技術的實質和要解決的基本問題

掌握：移入?歸約法

5.2算符優先分析技術(5學時)

了解：優先函數的引入

算符優先矩陣和優先函數的不足

理解：算符優先分析技術

算符文法和其性質

熟練掌握：

算法優先矩陣，算符優先關系的構造

應用算符優先分析技術識別句型

優先函數的構造

5.3LR(k)分析技術(6學時)

了解：LR(k)的定義和性質

LALR(1)分析表的構造

理解：LR識別程序和識別算法

四種LR分析技術之間的關系

掌握：可歸前綴和子前綴，識別活前綴的有限自動機

活前綴及其可歸前綴的一般計算方法；

LR(0)分析技術的相關概念，LR(0)文法

SLR(1)分析技術的相關概念，SLR(1)文法

LR(1)項集規范族的構造，LR(1)分析表的肉造

熟練掌握：

LR(0)項集規范族的構造，LR(0)分析表的構造

SLR（1）分析表的構造

第6章語義分析與目標代碼生成

教學要點：

1.中間代碼的形式

2.幾種常見語句和結構的翻譯

教學時數：

9學時

教學內容：

6.1概況（1學時）

了解：屬性文法；語法制導翻譯概論

6.2中間代碼生成（2學時）

了解：產生中間代碼的必要性

掌握：幾類中間代碼的格式

6.3控制語句的翻譯（6學時）

了解：數組元素引用的翔譯

過程語句的翻譯

說明語句的翻譯

熟練掌握：

簡單算術表達式和賦值語句的翻譯

布爾表達式的翻譯

控制語句的翻譯

第7章運行環境

教學要點：

幾種存儲分配策略

教學時數：

1學時

教學內容：

7.1存儲分配策略（1學時）

了解：靜態存儲分配，校式存儲分配，堆式存儲分配

第8章代碼優化

教學要點：

1.優化的定義、分類

2.局部優化

3.循環優化

教學時數：

4學時

教學內容：

8.1引言

理解：優碼優化的概念和分類

8.2基本塊的優化（2學時）

了解：dag圖

掌握：幾種基本塊的優化技術

8.3循環優化（2學時）

了解：循環優化的實現

掌握：循環優化的幾種技術

8.4窺孔優化

了解：窺孔優化的概念和技術

第9章程序錯誤的檢查和校正

教學要點：

1.程序錯誤的必然性和類別

2.詞法錯誤的復原和校正

3.語法錯誤的復原和校正

教學時數：

I學時

教學內容：

9.1概況

了解：程序錯誤的必然性和類別

9.2詞法錯誤的復原和校正

了解：詞法錯誤種類和校正方法

9.3語法錯誤的復原和校正

了解：語法錯誤種類和校正方法

實驗部分

（一）基本要求

《編譯原理》是計算機科學與技術專業的一門重要專業課，是一門理論性和實踐性都比較強的

課程。進行上機實驗的目的是使學生通過完成上機實驗題目加深對課堂教學內容的理解，同時培養

學生實際動手能力。

教學目的：

1.通過實驗要學會用BNF范式定義?個簡單的程序設計語言。

2.學會用高級程序設計語言設計一詞法分析器、語法分析器、中間代碼產生器，用這個簡單

的程序設計語言書寫一段程序，并調試運行出來。

3.進行科學研究的基本訓練，培養學生嚴謹認真的科學態度，提高分析問題和解決問題的能

力。

基本要求：

1.試驗前做好預習，明確試驗目的，基本原理及操作要點，

2.在試驗的整個過程中要注意觀察試驗結果，必要時重復試驗；

3.刈試驗結果進行分析，做好試驗報告；

（二）實驗項目總表

序號實驗項口名稱學時數項目類別項目類型

1文法的表示與壓縮6基礎必做

從正則文法構造FA并

26設計必做

運行

預測分析表的生成，及

3應用預測分析技術識8綜合必做

別句子

SLR（1）分析表的生成

4及應用SLR（l）分析技8綜合必做

術識別句子

賦值語句的語義分析

58綜合必做

實現

（三）實驗項目內容及要求

實驗一文法的表示與壓縮

1、實驗目的及要求：

1.掌握文法在計算機內的存儲表示；

2.了解Chomsky文法的四元組表示；

3.掌握文法壓縮的方法

2、實驗內容及學時分配：（6學時）

1.輸入任意上下文無關文法，輸出四元組形式；

2.輸入任意的上下文無關文法，輸出壓縮后的文法

實驗二從正則文法構造FA并運行

1、實驗目的及要求：

1.掌握有窮狀態自動機的概念

2.掌握FA的存儲表示及其與正則文法的關系；

3.運行有窮狀態自動機；

3、實驗內容及學時分配：(6學時)

1.輸入任意的正則文法：五元組形式輸出相應的有窮狀態自動機。

2.識別有窮狀態自動機是確定的還是非確定的。

3.輸入該文法的句子，運行FA

實驗三預測分析表的生成，及應用預測分析技術識別句子

1、實驗目的及要求：

1.掌握firse集合和follow集合的構造算法

2.掌握應用預測分析表的構造

3.利用預測分析技術進行句型分析；

2、實驗內容及學時分配：(8學時)

1.輸入任意的LL(1)文法及其待識別的符號串。

2.輸出first集合和follow集合以及預測分析表

3.判斷輸入符號串是否問文法的句子

實驗四SLR(1)分析表的生成及應用SLR(l)分析技術識別句子

1、實驗目的及要求：

1.掌握LR(1)分析表生成的基本思想