第一講引論

?課程信息

?編譯程序概述

?高級語言的語法描述

§1.課程信息

一、課程名稱：編譯原理

基本內容是介紹編譯程序構造的基本原理、

方法和技術，包括詞法分析、語法分析、

語義分析與中間代碼產生、代碼優化及目

標代碼產生等。簡言之，就是介紹如何將

源程序翻譯成目標代碼程序。

CompilerPrinciples3

二、課程性質：專業基礎課，必修

。編譯程序（器）出現于上世紀50年代后期

（第一個高級語言1958年）

?60年代?70年代是研究高峰期

60年代中期開始在高校中開設課程

。80年代開始作為計算機科學與技術專業的

必修基礎課程

CompilerPrinciples4

三、課程特點：

充分體現了計算學科中抽象、理論和設計三個學科

形態

。該課程涉及多門課程的內容綜合運用，涉及面廣，內

容龐雜，學習艱難

9程序設計語言、計算機體系結構、語言理論及算法等；

9離散數學、數據結構'

。該課程涉及的原理、方法和技術具有十分普遍的意

義

小每一個計算機科學與技術工作者的職業生涯中反復用到，

“享用一輩子”

《這兒接受的訓練很難在其他地方獲得：

如：抽象與形式化方法、局部與全局優化方法、構造技術、

證明方法等

CompilerPrinciples5

四、學習該課程的意義

?編譯程序是計算機系統不可缺少的重要組成

部分

力對程序設計語言的設計與實現能有更深刻的理

解

9對程序設計語言有關理論有所了解

。從宏觀上把握程序設計語言—掌握了編譯原

理后，就不能再說：“某語言未學過，所以不

會”

i有助于快速理解、定位和解決程序調試與運行

中出現的問題

CompilerPrinciples6

。編譯方法與技術有著廣泛應用

《安全技術、程序理解、軟件逆向工程、應用軟件與軟

件工具開發、軟件測試與驗證等

。編譯課程蘊含著計算學科中解決問題的思路、抽

象和方法，這些與高等數學一樣，使你“享用一

輩子”

課程所涉及的內容至今非常活躍

9自然語言的翻譯

9軟件移植

9網絡安全」

9形式化方法

力形式語義學等

CompilerPrinciples7

鑒于以上所述，作為計算機科

學與技術專業的學生必須學習和

掌握編譯原理這門課程，當然由

于其綜合性、處理問題的復雜性

等，學習起來有一定難度，這就

需要艱苦奮斗的精神和良好的學

習方法I

CompilerPrinciples8

五、學習方法

*編譯程序的構造是一個龐大而復雜的系統工

程，無論是概念還是理論、方法，對初學者

來說許多都是新的，學習起來會感到困難大

一些，這一點必須有充分認識，為此建議學

習方法上注意以下幾點：

CompilerPrinciples9

1.課前預習，課堂認真聽講，課后復習加深理

解，特別要經常有意識地將前后內容聯系起

來融會貫通。因為編譯程序是一個龐大的程

序系統，講解過程必須“分而治之”，這也

是人們處理復雜問題的基本方法，這就要求

大家在學習過程中，始終以處理過程為主線,

把前后聯系起來考慮。

CompilerPrinciples10

2.理論聯系實際——親自動手，構造一個

演示性編譯程序，至少要完成掃描器和

語法分析器，以及語法制導翻譯產生中

間代碼

3,認真完成作業，進一步鞏固并加深理解

所學知識

4.特別要下功夫認真學習如何從實際問題

進行抽象并形式化，最終建立實際問題

的模型（上升為理性認識），并借助模

型進一步設計實現，這將對你的能力提

高大有益處

CompilerPrinciples11

六、教材選擇：

《程序設計語言編譯原理》（第3版）

國防工業出版社陳火旺等

1.內容詳實豐富，理論與技術相結合

2.新版充分考慮了新的研究成果——屬

性文法、LR分析法、全局優化等

3.大多數院校一直采用，碩士入學考試

參考書

4,較為全面介紹了編譯程序構造的基本

原理、方法與技術

CompilerPrinciples12

七、考試

平時成績：30%

期終考試成績：70%

八、參考書目

1.《編譯原理》陳意云張昱高教出版社

2.《編譯原理》李建中姜守旭譯

A.V.Aho,RavSethi,J.D.Ullman著

機械工業出版社

3.《編譯原理及實踐》廿馮博琴馮嵐等譯

KennethC.Louden著）

機械工業出版社

CompilerPrinciples13

§2.編譯程序概述

，翻譯程序（Translator）

能夠把一種語言程序（稱為源語言

程序）轉換成邏輯上等價的另一種

語言程序（稱為目標語言程序）的

程序

Compilerprinciples14

?任何非機器語言程序都需要翻譯程序

。翻譯程序的工作就是進行等價變換（映射）

兩個程序邏輯上等價是指對相同輸入得到

相同的輸出

CompilerPrinciples15

1.匯編程序(Assembler)

把匯編語言程序轉變為機器語言程序的翻譯程序

2.解釋程序(Interpreter)

把源程序作為輸入接收，邊解釋邊執行的翻譯程序

r源程序解釋＞結果

數據程序

CompilerPrinciples16

3.編譯程序

將高級語言程序轉變為低級語言程序的翻譯程序

源程序

CompilerPrinciples17

。編譯程序又可根據用途和側重點的不同，

進一步分類為：

①診斷編譯程序(DiagnosticCompiler)

專門用于幫助程序開發和調試的編譯程序

②優化編譯程序(OptimizingCompiler)

著重于提高目標代碼效率的編譯程序

③交叉編譯程序(CrossCompiler)

能夠產生不同于其宿主機機器代碼的編譯程序

④可變目標編譯程序(Retargetablecompiler)

無須重寫與機器無關部分就能改變目標機的

編譯程序

CompilerPrinciples18

二、與編譯程序相關的程序

本講義只介紹編譯程序（器）構造的基本原

理、方法與技術，但在一個完整的語言開發

（或稱程序設計）環境中，除了編譯器這一I

主要工具外，還需要其他一些工具，如編輯

器、連接器、裝入程序等。現代計算機系統

常將這些相互獨立的程序設計工具集成起來,

構成一個集成化的程序開發環境，以提高程

序設計效率和程序的質量。如TurboC、

VisualC++等語言環境都是集成化的程序設

計環境。而Ada語言的集成環境是這方面的

J

如Ada語言的集成環境是一個分層的程序開發環境

這兒要強調的是：盡

管本課程只介紹編譯

的基本理論、方法和

技術，但這些基本理

論、方法與技術對其

他工具的構造同樣起

作用！

CompilerPrinciples21

1編輯器（Editor）

.完成源程序輸入、編輯并產生標準文件

（如ASCII文件）的程序。

近來已與編譯器和其他程序捆綁進一個交

互開發環境——IDE中

盡管這樣的編輯器仍生成標準文件，但會

轉向正被討論的程序設計語言的格式或結

構（稱為基于結構的），且已包含了編譯

器的某些操作；因此在程序編寫時而不是

編譯時就可得知錯誤，甚至也可調用編譯

器

CompilerPrinciples22

2,預處理程序(Preprocessor)

在真正翻譯開始之前產生編譯程序的輸入

的程序

。處理宏及注釋：宏是被經常使用的較長結

構的縮寫

處理文件包含：把頭文件包含到程序正文

中(如C的文件包含includev..?.h>)

。“理解”預處理器：把現代控制流和數據

結構機制添加到比較老式的語言中

。語言擴充：通過大量的內部宏定義來增強

語言的能力，如Equel語言是一種嵌套在C

,樟司中的數據庫查詢語言

CompilerPrmciples二2323

K連接程序(Linker)——又稱為連接編輯器。

將分別在不同的目標文件中編譯(或匯編)

的代碼、所用標準庫函數的代碼以及操作

系統提供的資源(如存儲分配程序及輸入/

輸出設備)收集到一個可直接執行的文件

中的程序

4.裝配程序(Loader)

完成程序的裝入和連接編輯兩項功能。

裝入過程包括讀入可重定位機器代碼、修

改可重定位地址、并將修改后的指令和數

據放到內存的適當位置。

裝入程序使得可執行代碼更加靈活

CompilerPrinciples24

5,調試程序（Debugger）

可在被編譯了的程序中判定執行錯誤的程

序

?它經常與編譯程序一起放在IDE中

。運行一個帶有調試程序的程序與直接執行

不同，這是因為調試程序保存著所有的或

大多數源代碼信息，它可以在預先指定的

位置（斷點Breakpoint）暫停執行，并提供

有關信息（已調用的函數、變量名的當前

值等）

CompilerPrinciples25

6.其他有關的還有

。描述器(Profiler)——執行中搜集目標程序行

為統計的程序

項目管理程序(ProjectManager)-----如

Unix系統中的SCCS(源代碼控制系統)和

RCS(修正控制系統)和匯編程序等

綜上所述可給出一個“語言處理系統”的圖示:

CompilerPrinciples26

源程序梗概

_______1_______

預處理器

丁

源程序

編全器

丁

目標匯編程序

—

匯編器

可重定位機器代碼

____________+

裝載器/連接編輯器;一庫、可重定位目標程序

可執行機器代碼

我們這個課只介紹編譯程序這一部分

CompilerPrinciples27

三、編譯過程與編譯程序結構

1.編譯過程：

輸入---------編譯程序--------輸出

（高級語言源程序）（低級語言目標程序）

編譯程序工作過程如下：

?識別出一個個的單詞

?分析句子的語法結構

?分析句子的語義并進行初步翻譯.

?對初步翻譯進行優化

?整理出目標程序

對以上過程進一步整理可得如下編譯程序結構總框:

CompilerPrinciples

3.五個階段簡介

?第一階段：詞法分析——依據語言構詞規

貝I」，識別出一個個單詞（符號）

?單詞種類

?基本字：for,if,while等、

?算符：+,一，X,/等、有窮性!

?界符：，；O等J

?標識符：a123,pi等

無窮性

?常數：9,36,486E6等

CompilerPrinciples30

?詞法分析工作由詞法分析器（或稱掃描

器）完成。

?掃描器輸出為等長度的單詞符號（二元

式）流。

?例：

(06,'Position')。l,-X06,'initial'X12,-X06,'rate')(13,—)(07,'60的二進制')

CompilerPrinciples31

?第二階段：語法分?如：Position=initial+rate*60是——

析——依據語言的個“賦值表達式”（C語言中）

語法規則，把掃描

器提供的單詞符號

串分解成各種語法

單位（范疇），如

“短語”、“子Position

句”、“句子”乃

至“程序”。同時

進行語法檢查，以

確定輸入串是否正

確，該工作是由語initial標示符常數

法分析器完成的。

rate60

CompilerPrinciples32

?第三階段：語義分析與中間代碼產生——針對

各類不同的語法范疇，按語言的語義規則進行

語義分析和初步翻譯工作，產生某種中間語言

形式的中間代碼（即一種結構簡單，含義明確

的記號系統）

該階段工作通常包括兩個方面的工作：

?對每種語法范疇進行靜態語義檢查，包括：

?變量是否定義過.

?類型是否正確1

?是否用了。作除數等

CompilerPrinciples33

J?將語法范疇翻譯成某種形式的中間代碼,

如四元式：

OpARG1ARG2Result

*rate60T1

+initialT1T2

■T2Position

CompilerPrinciples34

?第四階段：優化——對前階段產生的中間

代碼進行加工變換，以期在最后階段能產

生出高效（節省時、空）的目標代碼，這

一任務是由優化器來完成的I

?根據優化的范圍不同，可分為：

局部優化，循環優化和全局優化

?一個循環優化的例子：

■

循環語句為：For(k=1;k<=100;k++){M=l+10*k;N=J+10*k;}

⑴=1K(1)=IM

(2)J<10°K(9)⑵=JN

⑶*10KT1⑶=1K

(4)+IT1M(4)J<1。。K⑼

⑸*10KT2⑸+M10M

(6)+JT2N(6)+N10N

⑺+K1K⑺+K1K

(8)J(2)(8)J(4)

?優化前用了兩個臨時工作單元(T1,T2),優化后沒有用臨時單元

?優化前循環體中要做300次加、200次乘，

就施簫循環體內只做30。次加36

?第五階段：目標代碼生成——把中間代碼

翻譯成目標代碼

?顯然這階段要依賴于硬體系統結構和指

令系統

?涉及存貯分配、寄存器調度

這一階段工作是由代碼生成器完成的

說明：

以上各階段（或稱工序）并不是截然分開

的，尤其編譯程序結構十分復雜、體積相

當龐大，所以有時人們把幾個階段的工作

有機地組合在一起、穿插進行，構成遍。

Compilerprinciples37

。遍(Pass)：對源程序或源程序的中間代

碼從頭到尾掃描一次并做相應處理加工

?分遍的好處是結構清晰、節省內存(每

遍都從外存獲取前一遍的結果作為開始,

工作結果仍記入外存，每遍幾乎可使用

全部內存)

?分不分遍、如何分遍要視具體情況----

計算機內存容量、源語言的繁簡、從事

編譯程序設計人員的情況等

CompilerPrinciples38

如最早的基本BASIC語言采用一遍掃描的編譯程序:

CompilerPrinciples39

又如PL/O編譯程序的結構

PL/O源程序

格

表

錯

出

理

管

理

處

序

程

程

序

目標程序

CompilerPrinciples40

再如COBOL編譯程序采用了四遍掃描的編譯程序:

序

程

源U

詞法分析與

名等內碼內

碼生成器

1山I

文

配

基

外

字

對

詞

名

信

矩

表

表

息

陣

表

表

CompilerPrinciples41

4.前端與后端：概念上講，編譯程序的五個階

）段可進一步劃分為前端和后端：

?前端：主要由與源語言有關而與目標機無

關的部分組成，包括詞法分析、語法分析、

語義分析和中間代碼產生。代碼優化一般

也包含在前端。J

?后端：主要由與目標機有關的部分組成，（

包括目標代碼生成和與目標機有關的優化

等。

詳見下圖：

CompilerPrinciples42

前端后端

中

義

詞

語

語

目

目

中

目

源

析

間

據

法

分

令

標

間

標

程

分

分

中

代

和

代

代

語

語

序

析

析

代

間

碼

碼

碼

言

言

產

碼

優

優

生

主

件

化

化

成

CompilerPrinciples43

?劃分前端和后端，就可以僅改寫后端

而生成不同目標機上的目標程序，當然

也可考慮對不同語言僅稍加改變前端而

產生相同的中間代碼，經同一后端生成

相同目標機的目標代碼。就目前來說，

針對相同中間代碼適應不同目標機的工

作較多，如Ada語言的APSE（Ada程序設

計環境）中使用的Diana中間代碼，Java

語言定義的虛擬機代碼---Bytecode中

間語言，都是定義良好的中間語言。

詳見下圖：

Compilerprinciples44

Java的傳統環境

編譯環境

Java源程序

(Java)

Java編譯器

Java字節碼

（本地或

網絡傳輸）,

Java字節碼

(,class)

CompilerPrinciples45

5,表格與表格管理

?表格記錄源程序中的各類有用信息——名

字、函數、標號、過程、數值等

?每個階段的工作都要與表格打交道：查、

填、改等

?表格的結構與處理方法：統一的大表與分

類的小表

?統一大表NAMEINFORMATION

名字欄為主欄（關鍵字欄），信息欄又分

成若干子欄——種屬、類型等

CompilerPrinciples46

?分類小表：每類一張表，如:

?符號名表(SNT)X啞元實型

A數組整型...

?常數表(CT)3.1415926

48

Compilerprinciples47

?入口表(ENT)Swap二目子程序入口地址

?標號表

(LBT)L1入口地址

?基本字表DO編號(03)

(KWT)

CompilerPrinciples48

6.出錯處理：

這是編譯程序的又一重要組成部分，

因為編譯的各個階段都有可能發現源

程序中的錯誤。一旦發現這樣或那樣

的錯誤，就應把錯誤的性質及位置報

告給用戶，并且使編譯能繼續下去。

Compilerprinciples49

四、編譯程序的構造過程

1.需求分析，確定語言文本

（1）確定語言的種類：

?按語言范型分類，當今大多數程序語言可分為四類:

過程式（強制式語言）：命令驅動，面向語句，如

FORTRAN>PASCAL>Ada及C等

函數式（應用式）語言：功能驅動，面向函數，如

LISP、SNOBOL及ML等

邏輯式（基于規則的）語言：依據條件進行邏輯推演,

如Prolog等

00語言：支持封裝性、繼承性、多態性及動態聚

束等，以對象為運行單位，如Smalltalk、Java、

C++等

CompilerPrinciples50

?通過用戶提供的應用范圍，決定采用何種語

、A

H。

例如：

偏重于科學計算的則選用Fortran；

偏重于符號處理的則選用Lisp或Snobol；

偏重于事務處理的則選用Cobol或數據庫管理

語言；

CompilerPrinciples51

(2)深刻理解語言的結構、語法及語義

這就是說不僅僅是用程序設計語言編幾個程序的

問題，而是要在語法和語義方面下一些功夫。具

體說來有以下幾個方面：

①程序語言的定義：

任何程序語言都是某個確定的字符集上的符號按

照一定規則組成的有窮序列。

這里所謂的規則是從兩個方面來談的：

-語法規則：用于形成和產生一個正確的程序的

一組規則。

?語義規則：用于定義程序意義的一組規則。

CompilerPrinciples52

例如：

從語法的角度看，標識符和名字是一個東

西，都是以字母開頭的字母數字串；但從語

義的角度看，標識符是一個沒有任何意義的

字符序列，而名字卻有確定的意義和屬性，

而且具有一定的作用域和定義域，即有局部

和全部之分。

又如：....

程序從語法角度看，是一些語法范疇構成

的如下層次結構：

CompilerPrinciples53

程序

I

分程序或子程序（過程、函數等）

PBT

語句

I

表達式

數據引用算符函數調用

而從語義的角度來說，程序是描述一定

的數據結構及其處理過程。

CompilerPrinciples54

②程序結構：

現代高級語言程序通常由若干子程序段

（過程、函數等）構成，許多語言還引入了

類、程序包等更高級的結構。

例如,Fortran、C程序是塊結構的;

Pascal程序是過程嵌套的；Algol既有分程序

嵌套，又有過程嵌套；Java與C++是面向對象

的，它們很重要的方面是類和繼承的概念，

同時支持多態性和動態聚束等特性；而在Ada

中引入了程序包，它可以把數據和操作代碼

封裝在一起，支持數據抽象。

（詳見教材P15.18）

CompilerPrinciples55

③語言的基本成分：

包括數據類型、表達式、語句、過程或函數等，

這些在學習語言課時都已經學過了，但從編譯的角

度出發，應如何了解這些基本成分呢？

?初等數據類型：牽扯到存儲空間的問題；

■結構數據類型：牽扯到下標、維數、存放方式、

分配時間動態與靜態等；

?表達式：牽扯到運算分量、運算符、形成規則、

運算順序等；

?語句：順序、控制、循環等；