教案

2006-2007學(xué)年第1學(xué)期

課程名稱：編譯原理

課程編號:________________

學(xué)院、專業(yè)、年級:計算機科學(xué)與技術(shù)學(xué)院

任課教師：________________

教師所在單位：計算機科學(xué)與技術(shù)學(xué)院

泰山學(xué)院

《編譯原理》教案

課程簡介

編譯原理是計算機科學(xué)與技術(shù)專業(yè)的一門重要專業(yè)課程。該課程的目的是讓學(xué)生掌握程序設(shè)計語言編譯

程序構(gòu)造的一般原理、基本設(shè)計方法、主要實現(xiàn)技術(shù)和一些自動構(gòu)造工具，從而讓學(xué)生了解將高級程序設(shè)計

語言源程序翻譯成計算機能處理的目標(biāo)代碼語言的整個過程。該課程是理論性很強的課程，對于計算機專業(yè)

學(xué)生的進一步深造有較大的促進作用。同時，該課程還可以提高學(xué)生計算機的專業(yè)素質(zhì)，培養(yǎng)他們的軟件開

發(fā)能力和抽象思維能力，為進一步深造打下基礎(chǔ)。課程主要內(nèi)容有：詞法分析、自頂向下語法分析、自底向

上語法分析、屬性文法和語法制導(dǎo)翻譯、存儲器管理、符號表的組織與管理、中間代碼優(yōu)化、代碼生成等內(nèi)

容。課程要求：了解編譯程序的構(gòu)造技術(shù)：理解編譯原理的理論基礎(chǔ)即文法與形式語言概念；掌握各種詞法

分析、語法分析、語法制導(dǎo)翻譯、代碼優(yōu)化、存儲管理的方法和技巧；具備一定的設(shè)計相關(guān)語法分析器的能

力。

該課程是計算機專業(yè)中較難得一門專業(yè)課，有如下四個重點，也是難點：（1）自動機理論（2）語法分

析（3）語法制導(dǎo)的翻譯（4）代碼優(yōu)化。

《編譯原理》教案

教學(xué)大綱

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

課程名稱：編譯原理

英文名稱：ThePrincipleofCompilerDesign

課程編號：

課程類別：專業(yè)課

學(xué)時數(shù)：80學(xué)時

學(xué)分?jǐn)?shù)：4

先修課程：高級程序設(shè)計語言、數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)等

適用年級：四年級

適用專業(yè)：計算機科學(xué)與技術(shù)

一、內(nèi)容簡介

該課程的研究對象是編譯程序構(gòu)造的一般原理、基本設(shè)計方法、主要實現(xiàn)技術(shù)和一些自動構(gòu)造工具，從

而讓學(xué)生掌握將高級程序設(shè)計語言翻譯成計算機能處理的目標(biāo)代碼語言的整個過程。該課程的主要內(nèi)容為：

詞法分析、自頂向下語法分析、自底向上語法分析、屬性文法和語法制導(dǎo)翻譯、存儲器管理、符號表的組織

與管理、中間代碼優(yōu)化、代碼生成等內(nèi)容。

二、本課程的性質(zhì)、目的和任務(wù)

編譯原理是計算機科學(xué)與技術(shù)專業(yè)的一門重要專業(yè)課程，其研究對象是編譯程序構(gòu)造的一般原理、基本

設(shè)計方法、主要實現(xiàn)技術(shù)和一些自動構(gòu)造工具，從而讓學(xué)生掌握將高級程序設(shè)計語言翻譯成計算機能處理的

目標(biāo)代碼語言的整個過程。

通過該課程的學(xué)習(xí)，使學(xué)生掌握編譯原理的基本理論和編譯程序的構(gòu)造技術(shù)，為進一步學(xué)習(xí)和深造打下

基礎(chǔ)。該課程的主要內(nèi)容有：詞法分析、自頂向下語法分析、自底向上語法分析、屬性文法和語法制導(dǎo)翻譯、

存儲器管理、符號表的組織與管理、中間代碼優(yōu)化、代碼生成等內(nèi)容。

通過各個教學(xué)環(huán)節(jié)，逐步培養(yǎng)學(xué)生的抽象思維能力、程序設(shè)計能力和自學(xué)能力，培養(yǎng)學(xué)生運用所學(xué)知識、

獨立解決較復(fù)雜問題的能力。

三、本課程與其它課程的關(guān)系

本課程是計算機科學(xué)與技術(shù)專業(yè)的重要專業(yè)課。其先行課有高級程序設(shè)計語言、數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)、

計算機系統(tǒng)結(jié)構(gòu)、操作系統(tǒng)等。

課程基礎(chǔ)性、理論性強，與相關(guān)課程的學(xué)習(xí)聯(lián)系密切，是計算機科學(xué)與技術(shù)專業(yè)學(xué)生進一步提高的基本

課程。

四、本課程的基本要求

了解編譯程序的構(gòu)造技術(shù)；理解編譯原理的理論基礎(chǔ)即文法與形式語言概念；掌握各種詞法分析、語法

分析、語法制導(dǎo)翻譯、代碼優(yōu)化、存儲管理的方法和技巧；具備一定的設(shè)計相關(guān)語法分析器的能力。

五、課程內(nèi)容與學(xué)時分配

（一）編譯原理概論2學(xué)時

1、教學(xué)內(nèi)容：

什么是編譯原理

編譯過程概述

編譯程序的結(jié)構(gòu)

編譯階段的組合

編譯技術(shù)和軟件工具

2、教學(xué)要求：

了解：編譯技術(shù)和軟件工具。

掌握：什么是編譯原理，編譯程序的結(jié)構(gòu)，編譯過程和六個階段的任務(wù)和組合。

（二）PL/O編譯程序的實現(xiàn)4學(xué)時

1、教學(xué)內(nèi)容：

PL/O語言描述：PL/O語言的語法描述圖；PL/O語言文法的EBNF表示

PL/O編譯程序的結(jié)構(gòu)

PL/O編譯程序的詞法分析

PL/O編譯程序的語法分析

PL/O編譯程序的目標(biāo)代碼結(jié)構(gòu)和代碼生成

PL/O編譯程序的語法錯誤處理

PL/O編譯程序的目標(biāo)代碼解釋執(zhí)行時的存儲分配

2、教學(xué)要求：

了解：PL/O編譯程序的詞法分析、語法分析、目標(biāo)代碼結(jié)構(gòu)和代碼生成、語法錯誤處理及目標(biāo)代碼解釋

執(zhí)行時的存儲分配。

掌握：PL/O語言的語法描述圖及文法的EBNF表示，PL/O編譯程序的結(jié)構(gòu)。

（三）文法和語言4學(xué)時

1、教學(xué)內(nèi)容：

文法的直觀概念

符號和符號串

文法和語言的形式定義

文法的類型

上下文無關(guān)文法及其語法樹

句型的分析：自上而下的分析方法；自下而上的分析方法；句型分析的有關(guān)問題

有關(guān)文法實用中的一些說明：有關(guān)文法的實用限制；上下文無關(guān)文法中的e規(guī)則

2、教學(xué)要求：

了解：文法的直觀概念，符號和符號串，上下文無關(guān)文法中的€規(guī)則。

掌握：文法和語言的形式定義。

熟練掌握：文法的類型，上下文無關(guān)文法及其語法樹，句型的分析。

（四）詞法分析8學(xué)時

1、教學(xué)內(nèi)容：

詞法分析程序的設(shè)計：詞法分析程序與語法分析程序的接口方式；詞法分析程序的輸出；將詞法分析工

作分離的考慮

單詞的描述工具：正規(guī)文法；正規(guī)式；正規(guī)文法到正規(guī)式

有窮自動機：確定的有窮自動機(DFA)；不確定的有窮自動機(NFA)；DFA-NFA的轉(zhuǎn)換；確定有

窮自動機的化簡

正規(guī)式和有窮自動機的等價性

正規(guī)式和有窮自動機間的轉(zhuǎn)換

詞法分析程序的自動構(gòu)造工具：LEX語言(選講內(nèi)容)

2、教學(xué)要求：

了解：詞法分析程序與語法分析程序的接口方式和輸出；詞法分析工作分離的考慮，LEX語言。

掌握：正規(guī)文法；正規(guī)式；正規(guī)文法到正規(guī)式。

熟練掌握：確定的有窮自動機(DFA)；不確定的有窮自動機(NFA)；DFA-NFA的轉(zhuǎn)換；確定有窮

自動機的化簡，正規(guī)式和有窮自動機的等價性，正規(guī)式和有窮自動機間的轉(zhuǎn)換。

(五)自頂向下語法分析方法6學(xué)時

1、教學(xué)內(nèi)容：

確定的自頂向下分析思想

LL(1)文法的判別

某些非LL(1)文法到LL(1)文法的等價變換

不確定的自頂向下分析思想

確定的自頂向下分析方法：遞歸子程序法；預(yù)測分析法

2、教學(xué)要求：

了解：不確定的自頂向下分析思想。

掌握：確定的自頂向下分析思想，LL(1)文法的判別，遞歸子程序法，預(yù)測分析法。

熟練掌握：某些非LL(1)文法到LL(1)文法的等價變換。

(六)自底向上優(yōu)先分析法6學(xué)時

1、教學(xué)內(nèi)容：

自底向上優(yōu)先分析法概述

簡單優(yōu)先分析法：優(yōu)先關(guān)系；簡單優(yōu)先文法的定義；簡單優(yōu)先分析法

算符優(yōu)先分析法：直觀算符優(yōu)先分析法；算符優(yōu)先分析法的定義；算符優(yōu)先關(guān)系表的構(gòu)造；算符優(yōu)先分

析法；優(yōu)先函數(shù)；算符優(yōu)先分析法的局限性

2、教學(xué)要求：

掌握：簡單優(yōu)先分析法。

熟練掌握：算符優(yōu)先分析法。

(七)LR分析法10學(xué)時

1、教學(xué)內(nèi)容：

LR分析概述

LR(0)分析：可歸前綴和子前綴；識別活前綴的有限自動機；活前綴及其可歸前綴的一般計算方法；LR(0)

項目集規(guī)范族的構(gòu)造

SLR⑴分析

LR(1)分析：LR(1)項目集族的構(gòu)造；LR(1)分析表的構(gòu)造

LALR(l)分析

二義性文法在LR分析中的應(yīng)用

2、教學(xué)要求：

掌握：SLR⑴分析，LALR⑴分析。

熟練掌握：LR（O）分析，LR（1）分析。

（八）語法制導(dǎo)翻譯和中間代碼生成10學(xué)時

1、教學(xué)內(nèi)容：

屬性文法

語法制導(dǎo)翻譯概論

中間代碼的形式：逆波蘭記號；三元式和樹形表示；四元式

簡單賦值語句的翻譯

布爾表達式的翻譯：布爾表達式的翻譯方法；控制語句中布爾表達式的翻譯

控制結(jié)構(gòu)的翻譯：條件轉(zhuǎn)移；開關(guān)語句；for循環(huán)語句；出口語句；goto語句；過程調(diào)用語句的四元式

產(chǎn)生。

說明語句的翻譯：簡單說明句的翻譯；過程中的說明

數(shù)組和結(jié)構(gòu)的翻譯：數(shù)組說明和數(shù)組元素的引用；結(jié)構(gòu)（記錄）說明和引用的翻譯

2、教學(xué)要求：

掌握：中間代碼的形式逆波蘭記號、三元式和樹形表示、四元式。

熟練掌握：簡單賦值語句、布爾表達式、控制結(jié)構(gòu)、說明語句、數(shù)組和結(jié)構(gòu)的翻譯。

（九）符號表4學(xué)時

1、教學(xué)內(nèi)容：

符號表的作用和地位

符號的主要屬性機作用

符號表的組織：符號表的總體組織：符號表項的排列；關(guān)鍵字域的組織；其它域的組織；下推鏈域的組

織

符號表的管理：符號表的初始化；符號的登錄；符號的查找；符號表中分程序結(jié)構(gòu)層次的管理

2、教學(xué)要求：

掌握：符號的主要屬性機作用。

熟練掌握：符號表的組織。

（十）目標(biāo)程序運行時的存儲組織6學(xué)時

1、教學(xué)內(nèi)容：

數(shù)據(jù)空間的三種不同使用方法和管理方法：靜態(tài)存儲分配；動態(tài)存儲分配；棧式動態(tài)存儲分配；堆式動

態(tài)存儲分配

棧式存儲分配的實現(xiàn)：簡單的棧式存儲分配的實現(xiàn)；嵌套過程語言的棧式實現(xiàn)；分程序結(jié)構(gòu)的存儲管理

參數(shù)傳遞：傳值；傳地址；過程參數(shù)

2、教學(xué)要求：

了解：堆式動態(tài)存儲分配、過程調(diào)用、過程進入和過程返回

掌握：靜態(tài)存儲分配，參數(shù)的傳值、傳地址和過程參數(shù)

熟練掌握：簡單的棧式存儲分配的實現(xiàn)；嵌套過程語言的棧式實現(xiàn)；分程序結(jié)構(gòu)的存儲管理

（+-）代碼優(yōu)化8學(xué)時

1、教學(xué)內(nèi)容：

優(yōu)化技術(shù)簡介

局部優(yōu)化：基本塊的劃分；基本塊的變換；基本塊的DAG表示；DAG的應(yīng)用；DAG構(gòu)造算法討論

控制流分析和循環(huán)優(yōu)化：出現(xiàn)域循環(huán)；循環(huán)；循環(huán)的查找；可規(guī)約流圖；循環(huán)優(yōu)化

數(shù)據(jù)流的分析與全局優(yōu)化：一些主要的概念；數(shù)據(jù)流方程的一般形式；到達一定值數(shù)據(jù)流方程；可用表

達式及其數(shù)據(jù)流方程；活躍變量數(shù)據(jù)流方法；復(fù)寫傳播

2、教學(xué)要求：

了解：數(shù)據(jù)流的分析與全局優(yōu)化。

掌握：局部優(yōu)化、控制流分析和循環(huán)優(yōu)化。

十二、代碼生成6學(xué)時

1、教學(xué)內(nèi)容：

代碼生成概述

一個計算機模型

一個簡單的代碼生成器：寄存器分配的原則；待用信息鏈表法；代碼生成算法

代碼生成研究現(xiàn)狀：中間語言的選擇；代碼生成的自動化研究

2、教學(xué)要求：

了解：代碼生成研究現(xiàn)狀。

掌握：寄存器分配的原則；待用信息鏈表法；代碼生成算法。

五、主要參考書目

考試教材：《編譯原理》，呂映芝、張素琴等編著清華大學(xué)出版社。

主要參考書目有；

《Compilers:Principles,Techniques,andTools/編譯原理技術(shù)與工具（英文版）》ALFREDV.AHO,

RAVISETHI,JEFFREYD.ULLMAN.

《程序設(shè)計語言編譯原理》陳火旺，國防工業(yè)出版社，2000

《編譯原理及編譯程序構(gòu)造》高仲儀、金茂忠，北京航空學(xué)院出版社，1990.12

《編譯原理》胡倫駿、徐蘭芳、劉建農(nóng)編，電子工業(yè)出版社.2002年

《編譯程序原理與技術(shù)》李贛生、王華民編著，清華大學(xué)出版社

《編譯原理技術(shù)》陳意云，中國科技大學(xué)出版社

《編譯原理習(xí)題精選》陳意云、張昱著，中國科技大學(xué)出版社

《編譯原理》教案

授課時間第一周第1次課

課程的性質(zhì)與任務(wù)

第1章引論

1.1什么是編譯程序

任課教師

授課章節(jié)1.2編譯過程、編譯程序的結(jié)構(gòu)馮玲講師

及職稱

1.3編譯程序和軟件工具

1.4程序設(shè)計語言范型

教學(xué)方法

多媒體課堂教學(xué)課時安排節(jié)課

與手段2

《編譯原理》（第2版）張素琴，呂映芝等著，清華大學(xué)出版社

《Compilers:Principles,Techniques,andTools/編譯原理技術(shù)與工具（英文版）》

ALFREDV.AHO.RAVISETHI,JEFFREYD.ULLMAN.

《程序設(shè)計語言編譯原理》陳火旺，國防工業(yè)出版社，2000

使用教材和

《編譯原理及編譯程序構(gòu)造》高仲儀、金茂忠，北京航空學(xué)院出版社，1990.12

主要參考書

《編譯原理》胡倫駿、徐蘭芳、劉建農(nóng)編，電子工業(yè)出版社.2002年

《編譯程序原理與技術(shù)》李贛生、王華民編著，清華大學(xué)出版社

《編譯原理技術(shù)》陳意云，中國科技大學(xué)出版社

《編譯原理習(xí)題精選》陳意云、張昱著，中國科技大學(xué)出版社

教學(xué)目的與要求：

本章重點對編譯程序的功能和結(jié)構(gòu)做了綜合概述，要求學(xué)生了解編譯程序各個成分在編譯階段的邏輯關(guān)系以

及它們怎樣作為一個整體完成編譯任務(wù)的。

1了解課程的性質(zhì)與任務(wù)

2理解什么是編譯程序

3了解編譯過程和編譯程序的結(jié)構(gòu)

4為什么要學(xué)習(xí)編譯程序

教學(xué)重點，難點：

1.理解理解什么是編譯程序

2.了解編譯過程和編譯程序的結(jié)構(gòu)

教學(xué)內(nèi)容:

課程的性質(zhì)與任務(wù)

?本課程地位屬于計算機科學(xué)與技術(shù)專業(yè)的一門重要的專業(yè)必修課。

?本課程的學(xué)習(xí)有助于對語言的執(zhí)行系統(tǒng)、程序語言的理解。

?通過本課程的學(xué)習(xí)，要掌握編譯程序的一般構(gòu)造原理，包括語言基礎(chǔ)知識、詞法分析程序設(shè)計原理和構(gòu)造

方法。各種語法分析技術(shù)和中間代碼生成符號表的構(gòu)造、代碼優(yōu)化、并行編譯技術(shù)常識及運行時存儲空間的

組織等基本方法和主要實現(xiàn)技術(shù)。

語言的發(fā)展

?機器語言

?匯編語言

?高級語言

?查詢語言、標(biāo)注語言

第1章編譯程序概論

1.1什么是編譯程序

1.1.1語言處理程序

語言處理程序：把較高級語言編寫的程序語義等價地變換成較低級語言程序的程序。

/匯編程序

語言處理程序《解釋程序

、編譯程序

(0)語言的執(zhí)行方式

解釋方式(Basic)口譯

編譯方式(C,pascal)筆譯

(1)匯編程序

匯編程序：把用匯編語言編寫的程序翻譯成機器語言的程序。

匯編語言是為特定的計算機或計算機系統(tǒng)設(shè)計的面向機器的語言。如8086/8088PC、Z-80、VAX匯編語言。

匯編的過程就是對匯編指令逐行進行處理，最終得到機器代碼的過程。

—A|匯編程序]―定藐))

⑵解釋程序

解釋程序：對用高級語言編寫的程序進行逐句分析并立即得到結(jié)果。

解釋程序按源程序中語句的動態(tài)順序逐句進行分析翻譯，并立即予以執(zhí)行，它不產(chǎn)生目標(biāo)代碼。

BASICAPLLISPJava等語言就是采用解釋方法實現(xiàn)的。

高級語言解釋系統(tǒng)(interpreter)

功能：讓計算機執(zhí)行高級語言(basic,lisp,prolog)

與編譯程序的不同：1)不生成目標(biāo)代碼2)能支持交互環(huán)境(同增量式編譯系統(tǒng))

源程序|解釋程序

計算結(jié)果

初始數(shù)據(jù)

解釋系統(tǒng)

直接對源程序中的語句進行分析，執(zhí)行其隱含的操作。

《編譯原理》教案

如：....

b:=2;

lnt2

a：=b+2;i-------y編譯程刃-----〉

Stb

writea;

Ldb

add2

Sta

解釋程序直接將4的值輸出(顯示)

⑶編譯程序

編譯程序：把用高級語言編寫的源程序翻譯成等價的低級語言(稱作目標(biāo)語言)程序。

編譯系統(tǒng)是編譯程序和運行系統(tǒng)的合稱。

一個編譯程序把一個高級語言源程序翻譯成目標(biāo)程序的工作可分為前后銜接的六個階段：詞法分析、語

法分析、語義分析、中間代碼生成、代碼優(yōu)化及目標(biāo)代碼生成。大多數(shù)高級語言是采用編譯的方法實現(xiàn)的。

如：PASCAL>FORTRAN.ADA、C、C++、PL/1、ALGOL60、ALGOL68,等等。

1.1.2什么是編譯程序(compiler)

編譯程序是現(xiàn)代計算機系統(tǒng)的基本組成部分.

從功能上看，一個編譯程序就是一個語言翻譯程序，它把一種語言(稱作源語言)書寫的程序翻譯成另--種語言

(稱作目標(biāo)語言)的等價的程序.

編譯程序的功能

術(shù)語：編譯程序的源語言(源程序)；

編譯程序的目標(biāo)語言(目標(biāo)程序)；

編譯程序的實現(xiàn)語言；

軟件：計算機系統(tǒng)中的程序及其文檔；

系統(tǒng)軟件：居于計算機系統(tǒng)中最靠近硬件的一層，其他軟件一般都通過系統(tǒng)軟件發(fā)揮作用。他和具體

的應(yīng)用領(lǐng)域無關(guān)，如編譯系統(tǒng)和操作系統(tǒng)等。

處理系統(tǒng)：把軟件語言書寫的各種程序處理成可在計算機上執(zhí)行的程序。

軟件語言：用于書寫軟件的語言。它主要包括需求定義語言，功能性語言，設(shè)計性語言，程序設(shè)計語

言以及文檔語言

編譯程序(compiler);

編譯程序的源語言(源程序)(sourcelanguage)(sourceprogram);

編譯程序的目標(biāo)語言(目標(biāo)程序)(objectortargetlanguage)(objectortargetprogram);

編譯程序的實現(xiàn)語言(implementationlanguage);

語言處理程序(languageprocessor);

語言轉(zhuǎn)(變)換(languagetransformation)

—源程序一

?

I預(yù)處理器I

《編譯原理》教案

1.2編譯過程和結(jié)構(gòu)

1.2.1編譯邏輯過程

（1）詞法分析這個階段的任務(wù)是從左至右、從上到下一個字符一個字符地讀入源程序，對構(gòu)成源程序的字符

流進行掃描和分解，從而識別出一個個單詞。

詞法分析后可能返回：

單詞類型單詞值

保留字int

標(biāo)識符（變量名）a

界符；

標(biāo)識符（變量名）a

算符（賦值）=

標(biāo)識符（變量名）a

算符（加）+

整數(shù)2

界符；

有關(guān)術(shù)語

詞法分析--從左到右讀字符流的源程序、識別（拼）單詞。

單詞--具有獨立意義的基本語法單位。

保留字-一具有特殊規(guī)定的意義，不允許用戶將它們作為別用，是用戶定義標(biāo)識符的禁區(qū)。

標(biāo)識符--用來表示程序、過程、函數(shù)、類型、常量和變量等名稱的符號。

（2）語法分析

在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則（文法規(guī)則）,把單詞符號串分解成各類語法單位，如“短語”、

“句子”、“程序段”和“程序”。通過語法分解，確定整個輸入串是否構(gòu)成一個語法上正確的程序.

例：符號串X+0.168*Y,經(jīng)語法分析就可識別出這個字符串屬于算術(shù)表達式。

Y:=X+0.168*Y;

語法分析所依循的是語言的語法規(guī)則，用產(chǎn)生式描述。語法分析器讀入單詞，將它們組合成按產(chǎn)生式規(guī)

定的各類語法單位。

sum:=first+count*10

規(guī)則

〈賦值語句＞：:=＜標(biāo)識符＞"：=”〈表達式》

〈表達式》:=〈表達式＞“+”（表達式〉

〈表達式》:=＜表達式＞“*”〈表達式》

〈表達式》:=“（”〈表達式》“）”

（表達式》:=〈標(biāo)識符＞

〈表達式》:=〈整數(shù)》

〈表達式》:=＜實數(shù)＞

《編譯原理》教案

賦值語句

表達式

標(biāo)識符

術(shù)語

語法：定義語言各語法成分的形式或結(jié)構(gòu)。

語法分析：依據(jù)源程序的語法規(guī)則把源程序的單詞序列組成語法短語(表示成語法樹)。

語法樹(推導(dǎo)樹)：表示句型推導(dǎo)(或歸約)的樹型結(jié)構(gòu)。語法樹有助于理解一個句子語法結(jié)構(gòu)的層次0

(3)語義分析

語義審查(靜態(tài)語義)

類型匹配

類型轉(zhuǎn)換

例:Programp();

Varrate:real;

procedureinitial;

position:=initial+rate*60

/*error*//*error*//*warning*/;

語義分析的一個重要內(nèi)容是類型檢查，對表達式及語句中的各語法成分作類型檢查和分析.

如：

Varcount:real;

Varfirst:real;

Varsum:real;

sum:=first+count*10

術(shù)語

語法：用來定義語言中各語法成份的形式或結(jié)構(gòu)。

語義：用來規(guī)格各語法成份的含義和功能，即規(guī)定它們的屬性或在執(zhí)行時應(yīng)進行的運算或操作。

語義分析：檢查源程序是否包含語義錯誤，并搜集類型，供后面的代碼生成階段使用，只有語法和語義正確

的源程序才可被翻譯成目標(biāo)代碼。語義分析程序需要進行頻繁的造表和查表工作。

(4)中間代碼生成

語義分析之后生成一種介于源語言和目標(biāo)語言之間的中間語言代碼。中間代碼有多種形式：三元式、四

元式、逆波蘭表示、樹型結(jié)構(gòu)

《編譯原理》教案

例：a:=b*c

三元式：逆波蘭表示式：abc*:=

(1)(*,b,c)樹：,:=

(2)(:=,a,⑴)a*

四元式：bc

(*,b,c,a)

idl:=id2+id3*10

因運算需要，需設(shè)置臨時變量tl,t2,t3來存放中間運算結(jié)果。

四元式(算符第一運算量第二運算量運算結(jié)果)

(1)(inttoreal,10,tl)

(2)(*,id3,tl,t2)

(3)(+,id2,t2,t3)

(4)(:=,t3,idl)

中間代碼的幾種形式

逆波蘭表示：運算符在其運算量之后的表達式。

三元式：(OP,ARG1,ARG2)

四元式：(OP,ARG1,ARG2,RESULT)

樹：根結(jié)點0P,左子樹ARG1,右子樹ARG2

(5)代碼優(yōu)化

對前階段產(chǎn)生的中間代碼進行加工變換，以期在最后階段能產(chǎn)生出更為高效(省時間和省空間)的目標(biāo)代碼

tl=b*ctl=b*c

t2=tl+0t2=tl+tl

t3=b*ca-t2

t4=t2+t3

a=t4

在本例中，b、c的值沒有改變，故tl=t3,由第二個表達式知道t2=tl。

(6)目標(biāo)代碼生成

將前階段產(chǎn)生的中間代碼翻譯為機器語言或匯編語言形式的目標(biāo)程序。目標(biāo)程序總是按某一具體計算機的機

器語言或匯編語言來產(chǎn)生的。

目標(biāo)代碼生成

(*,id310.0tl)

(+,id2tlidl)

1

I

movfid3,R2

mulf#10.0,R2

movfid2,R1

addfR2,R1

movfRI,idl

《編譯原理》教案

(7)符號表管理

符號表管理：記錄源程序中使用的名字，收集每個名字的各種屬性信息:類型、作用域、分配存儲信息

在編譯過程中，源程序中的標(biāo)識符及其各種屬性都要記錄在符號表中，這些屬性可以提供標(biāo)識符的存儲分配

信息、類型信息、作用域信息等等。對于過程標(biāo)識符，還要有參數(shù)信息，包括參數(shù)的個數(shù)和類型、實參和形

參的結(jié)合方式等等。

符號表結(jié)構(gòu)

符號表是一種含記錄的數(shù)據(jù)結(jié)構(gòu)，通常一個標(biāo)識符在符號表中占一個記錄，記錄中除了標(biāo)識符的名字域

之外，還有記錄該標(biāo)識符屬性的域。

(8)出錯處理

編譯的每一個階段都會發(fā)現(xiàn)源程序的錯誤，在發(fā)現(xiàn)錯誤之后，一?般要對其有一定的處理措施，因而編譯

還可繼續(xù)執(zhí)行，不會一有錯誤就停止編譯工作。

出錯處理(errorhandling)(errorreportinganderrorrecovery)

在詞法分析中，能發(fā)現(xiàn)單詞拼寫錯誤。

在語法分析中，檢查單詞串是否符合語法的結(jié)構(gòu)規(guī)則。

在語義分析中，編譯程序進一步查出語法上雖正確但含有無意義的操作部分，如兩個標(biāo)識符相加，一個是數(shù)

組名，一個是過程名，雖然語法上允許，但語義上不允許，各種錯誤，都應(yīng)在相應(yīng)的階段進

行處理。

檢查錯誤

報告出錯信息(錯誤種類及位置)

校錯及排錯

恢復(fù)編譯工作

1.2.2編譯程序的結(jié)構(gòu)(components)

A詞法分析程序k

出

錯

處

理

】目標(biāo)代碼生成程序r

1.2.3編譯階段的組合

分析，綜合(synthesis)

源程序的分析

線性分析

層次分析

語義分析

目標(biāo)程序的綜合

編譯的前端(frontend):這些階段以來于源語言、與目標(biāo)機無關(guān)。

編譯的后端(backend)：依賴于目標(biāo)機器的階段。

遍(趟)從頭到尾掃描源程序(各種形式)一遍(pass)

編譯階段和運行階段存儲結(jié)構(gòu)

《編譯原理》教案

1.3編譯技術(shù)和軟件工具

編譯程序?qū)崿F(xiàn)方式:手工,機器語言,匯編,系統(tǒng)程序設(shè)計語言，自動構(gòu)造工具lexyaccgcc

1.3.1編譯程序的發(fā)展

riented--------'編譯?,,Computer-

oriented

1,...---

計算模式，語言馮諾曼機體系

范式結(jié)構(gòu)并行體系

結(jié)構(gòu)嵌入系統(tǒng)

編譯程序的發(fā)展

(1)語言范型(支持的計算模式)

命令式(imperativelanguage)

應(yīng)用式(applicative),也成函數(shù)式

基于規(guī)則的(rule-based)

面向?qū)ο蟮?object-oriented)

(2)編譯程序執(zhí)行環(huán)境

批處理

交互環(huán)境

嵌入系統(tǒng)環(huán)境

1.3.2編譯技術(shù)和軟件工具

結(jié)構(gòu)化編輯器

程序調(diào)試工具

程序測試工具：1靜態(tài)分析2動態(tài)分析3度量工具(結(jié)構(gòu)度量)

4分析工具(sourceinsight)

高級語言轉(zhuǎn)換工具

廣泛的語言領(lǐng)域

1.3.3研究領(lǐng)域

(1)并行化編譯技術(shù)

目的：提高并行計算機體系結(jié)構(gòu)的性能

(2)交叉編譯器

由于目標(biāo)機指令系統(tǒng)與宿主機的指令系統(tǒng)不同，編譯時將應(yīng)用程序的源程序在宿主機上生成目標(biāo)機代碼，稱

為交叉編譯。簡單地說，就是在一個平臺上生成另一個平臺上的可執(zhí)行代碼。

嵌入式

(3)自展編譯技術(shù)用被編譯的語言來書寫該語言自身的編譯程序。

小結(jié)

《編譯原理》教案

復(fù)習(xí)思考題、作業(yè)題：

1.什么是編譯程序？

2.簡要介紹編譯過程的六個階段，并給出編譯程序的結(jié)構(gòu)。

下次課預(yù)習(xí)要點

預(yù)習(xí)第二章PL/O編譯程序的結(jié)構(gòu)與詞法分析等內(nèi)容

實施情況及教學(xué)效果分析

授課時間分配合理；

編譯過程、編譯基本概念重點突出，

學(xué)生能夠掌握基本內(nèi)容；

教學(xué)效果良好。

學(xué)院審核意見

同意實施

學(xué)院負責(zé)人簽字

年月日

《編譯原理》教案

授課時間第一周__________第2次課

第2章PL/O編譯程序的實現(xiàn)

2.1PL/O語言描述

任課教師

授課章節(jié)2.2PL/O編譯程序的結(jié)構(gòu)馮玲講師

及職稱

2.3PL/O編譯程序的詞法分析

教學(xué)方法

多媒體課堂教學(xué)課時安排2節(jié)課

與手段

《編譯原理》（第2版）張素琴，呂映芝等著，清華大學(xué)出版社

《Compilers:Principles,Techniques,andTools/編譯原理技術(shù)與工具（英文版）》

ALFREDV.AHO,RAVISETHI,JEFFREYD.ULLMAN.

《程序設(shè)計語言編譯原理》陳火旺，國防工業(yè)出版社，2000

使用教材和

《編譯原理及編譯程序構(gòu)造》高仲儀、金茂忠，北京航空學(xué)院出版社，1990.12

主要參考書

《編譯原理》胡倫駿、徐蘭芳、劉建農(nóng)編，電子工業(yè)出版社.2002年

《編譯程序原理與技術(shù)》李贛生、王華民編著，清華大學(xué)出版社

《編譯原理技術(shù)》陳意云，中國科技大學(xué)出版社

《編譯原理習(xí)題精選》陳意云、張昱著，中國科技大學(xué)出版社

教學(xué)目的與要求:

以PL/O為實例，學(xué)習(xí)編譯程序?qū)崿F(xiàn)的基本步驟和相關(guān)技術(shù)。

教學(xué)重點，難點:

PL/O編譯程序的結(jié)構(gòu)與詞法分析

教學(xué)內(nèi)容:第2章PL/O編譯程序的實現(xiàn)

PL/O編譯系統(tǒng)的結(jié)構(gòu)框架

PL/O源程序

PL/O編譯程庠

類pcode代碼

類pcode解釋程序/

輸入▲輸出

2.1PL/0語言

⑴PL/0程序示例

CONSTA=10;(*常量說明部分*)

VARB,C;(*變量說明部分*)

PROCEDUREP;(*過程說明部分*)

VARD;

PROCEDUREQ;

VARX;

BEGIN

READ(X);

D:二X;

WHILEX#()

DOCALLP;

END;

BEGIN

WRITE(D);

CALLQ;

END;

BEGIN

CALLP;

END.

(2)PL/0的語法描述圖

程序一?分序口

口內(nèi)的文字表示非終結(jié)符v

O或O內(nèi)的文字或符號表示終結(jié)符

條件語法描述圖

表達式和項的語法描述圖

因子的語法圖

⑶PL/0語言文法的EBNF表示

EBNF引入的符號（元符號）：

＜＞用左右尖括號括起來的語法成分為非終結(jié)符

::=（一）'定義為‘：：=（一）的左部由右部定義

I喊，

｛）表示花括號內(nèi)的語法成分可重復(fù)任意次或限定次數(shù)

[]表示方括號內(nèi)的語法成分為任選項

（）表示圓括號內(nèi)的成分優(yōu)先

例：用EBNF描述〈整數(shù)〉的定義：

〈整數(shù)＞：：=[+■＜數(shù)字＞｛＜數(shù)字＞｝

〈數(shù)字＞：：=0|1|2|3|4|5|6|7|8|9

或更好的寫法

〈整數(shù)＞：：=[+卜]＜非零數(shù)字〉｛〈數(shù)字〉｝10

〈非零數(shù)字＞：：=1|2|3|4|5|6|7|8|9

〈數(shù)字＞：：=0|〈非零數(shù)字〉

PL/0余言的文法表示見P15.

（4）PL/0語言是PASCAL語言的子集

同PASCAL作用域規(guī)則（內(nèi)層可引用包圍它的外層定義的標(biāo)識符），上下文約束，過程可嵌套定義，可遞歸調(diào)

用

子集

數(shù)據(jù)類型，只有整型

數(shù)據(jù)結(jié)構(gòu)，只有簡變和常數(shù)

數(shù)字最多為14位

標(biāo)識符的有效長度是10

語句種類

過程最多可嵌套三層

⑸目標(biāo)代碼類pcode

目標(biāo)代碼類pcode是一種假想棧式計算機的匯編語言。指令格式：

目標(biāo)程序

《編譯原理》教案

(2)PL/O編譯程序的總體設(shè)計

其編譯過程采用一趟掃描方式，以語法、語義分析程序為核心

詞法分析程序和代碼生成程序都作為一個過程，當(dāng)語法分析需要讀單詞時就調(diào)用詞法分析程序，而當(dāng)語

法、語義分析正確，需要生成相應(yīng)的目標(biāo)代碼時，則調(diào)用代碼生成程序。

表格管理程序?qū)崿F(xiàn)變量，常量和過程標(biāo)識符的信息的登錄與查找。

出錯處理程序，對詞法和語法、語義分析遇到的錯誤給出在源程序中出錯的位置和與錯誤性質(zhì)有關(guān)的編

號，并進行錯誤恢復(fù)。

(3)編譯程序總體流程圖

(4)PL/O編譯程序過程一覽表(P17)

2.3PL/O編譯程序的詞法分析

(1)PI/O詞法分析程序Getsym

識別的單詞：(類別，值)

保留字：如：BEGIN,END、IF、THEN等

運算符：如：+、-、*、/、：=、#、>=、<=等

標(biāo)識符：用戶定義的變量名、常數(shù)名、過程名

常數(shù)：如：10、25、100等整數(shù)

界符：如—」、‘；‘、'('、)等

Getsym用到三個單元：

SYM:存放單詞類別

ID:存放標(biāo)識符的值

NUM:存放整數(shù)的值

(2)詞法分析過程GETSYM

流程圖(P19)

所要完成的任務(wù)：

濾空格

識別保留字

識別標(biāo)識符

拼數(shù)

識別單字符單詞(<,>等)

拼雙字符單詞(<=,<>等)

輸出源程序

讀字符子程序(getch)(p20)

(3)進一步的說明

z如何識別標(biāo)識符

y先查保留字表，建立保留字表

保留字內(nèi)部表示

beginbeginsym

callcallsym

writewritesym

查到時找到相應(yīng)的內(nèi)部表示

若不是保留字，則是用戶定義的標(biāo)識符，應(yīng)建立標(biāo)識符表。

類似地可以建立運算符、常數(shù)、界符表

詞法分析程序的實現(xiàn)見附錄

《編譯原理》教案

復(fù)習(xí)思考題、作業(yè)題：P30,練習(xí)2

2.2若pl/O編譯程序運行時的存儲分配策略采用棧式動態(tài)分配，并用動態(tài)鏈和靜態(tài)鏈的方式分別解決遞歸調(diào)用和非局部變量的

引用問題，試寫出下列程序執(zhí)行到賦值語句b:=10時運行棧的布局示意圖。Varx,y;

Procedurep;

Vara;

Procedureq;

Varb;

Begin(q)

B:=10;

End(q);

Procedures;

Varc,d;

Procedurer;

Vare,f;

Begin(r)

Callq;

End(r);

Begin(s)

Callr;

End⑸；

Begin(p);

Calls;

End(p);

Begin(main)

Callp;

End(main).

下次課預(yù)習(xí)要點

復(fù)習(xí)PL/O編譯程序的結(jié)構(gòu)與詞法分析，預(yù)習(xí)2.4—2.7小節(jié)

實施情況及教學(xué)效果分析

授課時間分配合理；

PL/O語言、編譯各階段的功能為教學(xué)重點，也是難點;

學(xué)生能夠掌握基本內(nèi)容；

教學(xué)效果良好。

學(xué)院審核意見

同意實施

學(xué)院負責(zé)人簽字

年月日

《編譯原理》教案

授課時間第二周第2次課

第2章PL/O編譯程序的實現(xiàn)

2.4PL/O編譯程序的語法語義分析

2.5PL/O編譯程序的目標(biāo)代碼結(jié)構(gòu)和代碼生成

任課教師

授課章節(jié)2.6PL/O編譯程序的語法錯誤處理馮玲講師

及職稱

2.7PL/O編譯程序的目標(biāo)代碼解釋執(zhí)行時的存

儲分配

教學(xué)方法

多媒體課堂教學(xué)課時安排2節(jié)課

與手段

《編譯原理》（第2版）張素琴，呂映芝等著，清華大學(xué)出版社

《Compilers:Principles,Techniques,andTools/編譯原理技術(shù)與工具（英文版）》

ALFREDV.AHO,RAVISETHI,JEFFREYD.ULLMAN.

《程序設(shè)計語言編譯原理》陳火旺，國防工業(yè)出版社，2000

使用教材和

《編譯原理及編譯程序構(gòu)造》高仲儀、金茂忠，北京航空學(xué)院出版社，1990.12

主要參考書

《編譯原理》胡倫駿、徐蘭芳、劉建農(nóng)編，電子工業(yè)出版社.2002年

《編譯程序原理與技術(shù)》李贛生、王華民編著，清華大學(xué)出版社

《編譯原理技術(shù)》陳意云，中國科技大學(xué)出版社

《編譯原理習(xí)題精選》陳意云、張昱著，中國科技大學(xué)出版社

教學(xué)目的與要求：

以PL/O為實例，學(xué)習(xí)編譯程序?qū)崿F(xiàn)的基本步驟和相關(guān)技術(shù)。

教學(xué)重點，難點：

1掌握PL/O編譯程序的語法語義分析與目標(biāo)代碼結(jié)構(gòu)和代碼生成

2了解PL/O編譯程序的語法錯誤處理

3理解PL/O編譯程序的目標(biāo)代碼解釋執(zhí)行時的存儲分配

《編譯原理》教案

教學(xué)內(nèi)容：

2.4PL/O編譯程序語法語義分析

2.4.1PL/O編譯程序語法分析的設(shè)計與實現(xiàn)

自頂向下的語法分析

遞歸子程序法：對于每個非終結(jié)符，編寫一個子程序，由該子程序負責(zé)識別該語法單位是否正確。

先回憶PL/O的語法規(guī)定。

遞歸子程序法：對應(yīng)每個非終結(jié)符語法單元，編一個獨立的處理過程（或子程序），識別該終結(jié)符對應(yīng)的

句子。

語法分析從讀入第一個單詞開始，由非終結(jié)符（程序>（即開始符）出發(fā)，沿語法描述圖箭頭所指出的方

向進行分析。當(dāng)遇到非終結(jié)符時，則調(diào)用相應(yīng)的處理過程，從語法描述圖看，也就進入了一個語法單元,

再沿當(dāng)前所進入的語法單元所指箭頭方向繼續(xù)進行分析。當(dāng)遇到描述圖中是終結(jié)符時，則判斷當(dāng)前讀入

的單詞是否與圖中的終結(jié)符相匹配，若匹配，再讀取下一個單詞繼續(xù)分析。遇到分支點時，將當(dāng)前的單

詞與分支點上多個終結(jié)符逐個相比較，若都不匹配時可能是進入下一個非終結(jié)符語法單位或是出錯。

表達式的EBNF

〈表達式〉：：=[+■〈項〉｛（+I-）〈項〉｝

〈項〉：：=〈因子〉｛（*|/）〈因子〉）

〈因子〉：：=〈標(biāo)識符〉|〈無符號整數(shù)〉「（，〈表達式〉9'

〈表達式〉的遞歸子程序?qū)崿F(xiàn)

procedureexpr;

begin

ifsymin[plus,minus]then

begin

getsym;term;

end

elseterm;

whilesymin[plus,minus]do

begin

getsym;term;

end

end;

〈項〉的遞歸子程序?qū)崿F(xiàn)

〈項〉：：=〈因子〉｛（*|/）〈因子〉）

procedureterm;

begin

factor;

whilesymin[times,slash]do

begin

getsym;factor;

end

end;

〈因子〉的遞歸子程序?qū)崿F(xiàn)

procedurefactor;

begin

ifsym<>identthen

《編譯原理》教案

ifsym＜＞numberthen

ifsym='（'then

begin

getsym;

expr;

ifsym='）'thengetsym

elseerror

end

elseerror

elsegetsym

elsegetsym

end;

（程序＞::=＜分程序＞

begin（*main*）

…（*initialize*）

…（*r/wfileset*）

getsym;

block（）;

ifsym＜＞periodthenerror...

end.

2.4.2PL/0編譯程序語義分析的設(shè)計與實現(xiàn)

PL/O編譯程序語法、語義分析的的核心程序是BLOCK過程

（1）說明部分的分析與處理

對每個過程（含主程序）說明的對象（變量，常量和過程）造符號表，登錄標(biāo)識符的屬性。

標(biāo)識符的屬性:種類，所在層次,值和分配的相對位置。

登錄信息由ENTER過程完成。

注意：所有標(biāo)識符保存在Table中，TX表示索引表的指針

LEV表示層次

Dx表示局部變量分配的位置

常量說明語句的處理

語法：（常量說明部分〉：：=const〈常量定義＞{,〈常量定義＞}；

〈常量定義〉：：=〈標(biāo)識符＞=〈無符號整數(shù)》

〈無符號整數(shù)）：：=〈數(shù)字＞{〈數(shù)字＞}

ifsym=constsymthen

begin

getsym;（*獲取下一個token,正常應(yīng)為用作常量名的標(biāo)識符*）

repeat（*反復(fù)進行常量聲明*）

constdeclaration;（*聲明以當(dāng)前token為標(biāo)識符的常量*）

whilesym=commado（*如果遇到了逗號則反復(fù)聲明下一常量*）

begin

getsym;（*獲取下一個token,這里正好應(yīng)該是標(biāo)識符*）

constdeclaration（*聲明以當(dāng)前token為標(biāo)識符的常量*）

end;

《編譯原理》教案

ifsym=semicolonthen（*如果常量聲明結(jié)束，應(yīng)遇到分號*）

getsym（*獲取下一個token,為下一輪循環(huán)做好準(zhǔn)備*）

else

error（5）（*提示5號錯誤*）

untilsym<>ident（*如果遇到非標(biāo)識符,則常量聲明結(jié)束*）

end;

常量說明處理

procedureconstdeclaration;

begin

ifsym=identthen

begin

getsym;

ifsymin[eql,becomes]then（*如果是等號或賦值號*）

ifsym=becomesthen（*如果是賦值號（常量生明中應(yīng)該是等號）*）

error（1）;（*提示1號錯誤*）

getsym;（*獲取下一個token,等號或賦值號后應(yīng)接上數(shù)字*）

ifsym=numberthen（*如果的確是數(shù)字*）

begin

enter（constant）;（*把這個常量登陸到符號表*）

getsym（*獲取下一個token,為后面作準(zhǔn)備*）

end

elseerror（2）（*如果等號后接的不是數(shù)字，提示2號錯誤*）

elseerror（3）（*如常量標(biāo)識符后不是等號或賦值號，提示3號錯誤*）

end

elseerror（4）

end（*constdeclaration*）;

變量定義語句的處理

語法：〈變量說明部分》：：二var〈標(biāo)識符>{,〈標(biāo)識符>}；

程序：

ifsym=varsynithen

begin

getsym;

repeat

vardeclaration;（*變量說明處理*）

whilesym=commado

begin

getsym;

vardeclaration

end;

ifsym=semicolonthen

getsym

elseerror（5）

untilsymOident;

end;

《編譯原理》教案一

變量說明處理

procedureardeclaration;

begin

ifsym=identthen

begin

enter(variable);

getsym

end

elseerror(4)

end(*vardeclaration*);

過程定義語句的處理

程序：

whilesym=procsymdo(*循環(huán)聲明各子過程*)

begin

getsym;(*獲取下一個token,此處正常應(yīng)為作為過程名的標(biāo)識符*)

ifsym=identthen(*如果token確為標(biāo)識符*)

begin

enter(procedur);(*把這個過程登錄到名字表中*)

getsym(