第1章 編譯概述

Compiler

為什么要學(xué)習(xí)編譯原理

?程序設(shè)計語言是計算機軟件專業(yè)的重要核心

?學(xué)習(xí)編程的歷程：

-C語言--匯編語言--數(shù)據(jù)結(jié)構(gòu)

高級語言？翻譯程序?匯編語言

SOURCE

PROGRAM

編譯原理2011年7月7日SIST

Compiler

為什么要學(xué)習(xí)編譯原理

?必修主干課程，操作系統(tǒng)和編譯系統(tǒng)構(gòu)成程序

設(shè)計者與計算機之間的基本界面。

?通過學(xué)習(xí)該課程，掌握編譯的基本理論、常用

的編譯技術(shù)，了解編譯過程及編譯系統(tǒng)結(jié)構(gòu)和

機理。能運用所學(xué)技術(shù)解決實際問題，能獨立

編寫一個小型編譯系統(tǒng)。

?此外，通過學(xué)習(xí)編譯原理可以更好地理解程序

語言的內(nèi)部機制，從而更好地理廨和運用程序

設(shè)計語言。能運用編譯程序構(gòu)造的原理和技術(shù)

完成相關(guān)軟件工具的設(shè)計和開發(fā)工作。

編譯原理2011年7月7日SIST

Compiler

為什么要學(xué)習(xí)編譯原理

?計算機軟件學(xué)科理論與實踐相結(jié)合的典范。

?在學(xué)習(xí)過程中既要注重該領(lǐng)域在理論上取得

的完美結(jié)論，也要注重這些理論在實際中的

應(yīng)用。

編譯原理2011年7月7日SIST

Compiler

先修課程

?要求先學(xué)習(xí)以下課程

■1.程序設(shè)計語言

■2.算法與數(shù)據(jù)結(jié)構(gòu)：棧分配、堆分配、靜態(tài)分配等各

種存儲分配方式。線性表、二叉查找樹、哈希表等多

種數(shù)據(jù)結(jié)構(gòu)。

■3.離散數(shù)學(xué)：集合論與數(shù)理邏輯是進一步學(xué)習(xí)形式語

言與自動機理論的數(shù)學(xué)基礎(chǔ)。

?最好學(xué)習(xí)過或同時學(xué)習(xí)以下課程

■1.軟件工程：掌握大型程序設(shè)計以及工程化的軟件生

產(chǎn)方法。

■2.形式語言與自動機：相當(dāng)于本課程中詞法分析與語

法分析的理論基礎(chǔ)。

編譯原理2011年7月7日,1ST

Compiler

教材

?李冬梅，施?；ⅲ毒幾g原理》，人民郵電出版社

參考書

?李建中譯，《編譯原理》（龍書），機械工業(yè)出版社

?陳火旺劉春林等，《程序設(shè)計語言編譯原理》，國

防工業(yè)出版社

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

編譯原理2011年7月7日SIST

Compiler

要求及學(xué)習(xí)方法

課程特點：理論性強，算法復(fù)雜

?平時(30%)

?無故曠課：-5

?一本教材，認真聽課：以講義為主，板書為

輔-做適當(dāng)?shù)墓P記

?認真完成課堂和課后作業(yè)

?完成要求的課外實驗內(nèi)容

?期末(70%):閉卷筆試

編譯原理2011年7月7日SIST

Compiler

第1章編譯概述

教學(xué)目標(biāo)

1.掌握編譯程序中所涉及的有關(guān)名詞術(shù)語

2.理解編譯程序總的框架，明確編譯程序工

作的基本過程及各階段的基本任務(wù)

編鋒原理2011年7月7日StST

Compiler

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

LL程序的翻譯

1.2.編譯程序的組成

1.3.編譯程序構(gòu)造

1.4.編譯技術(shù)的應(yīng)用及發(fā)展

編譯原理2011年7月7日SIST

Compiler

1.1程序的翻譯

?低級語言(LowlevelLanguage)

-字位碼、機器語言、匯編語言

-特點：與特定的機器有關(guān)，功效高，但使用復(fù)雜、繁

瑣、費時、易出錯

?高級語言

—Fortran>Pascal、C語言等

-特點：不依賴具體機器，移植性好、對用戶要求低、

易使用、易維護等。

編譯原理2011年7月7日SIST

Compiler

?源程序

用匯編語言或高級語言編寫的程序稱為源程序

?目標(biāo)程序

用目標(biāo)語言所表示的程序

目標(biāo)語言：可以是介于源語言和機器語言之間的“中間

語言”，可以是某種機器的機器語言，也可以是某機器的匯

編語言。

將源程序轉(zhuǎn)換為目標(biāo)程序的程序稱為翻譯程序。它是

指各種語言的翻譯器，包括匯編程序和編譯程序，是匯編

程序、編譯程序以及各種變換程序的總稱。

_______________________________________________

編譯原理2011年7月7日▼、1ST

Compiler

s0

源程序、翻譯程序、目標(biāo)程序三者關(guān)系:I

源程序翻譯程序目標(biāo)程序

SOURCE

PROGRAM

即源程序是翻譯程序的輸入，目標(biāo)程序是翻譯程序的輸出

編譯原理2011年7月7日SIST

Compiler

?匯編程序

若源程序用匯編語言書寫，經(jīng)過翻譯程序得到用機器語言

表示的程序，這時的翻譯程序就稱之為匯編程序，這種翻譯過

程稱為“匯編”(Assemble)

?編譯程序

若源程序是用高級語言書寫，經(jīng)加工后得到目標(biāo)程序，上述

翻譯過程稱“編譯”(Compile)

匯編程序與編譯程序都是翻譯程序，主要區(qū)別是加工對象的

不同。由于匯編語言格式簡單，常與機器語言之間有一一對

應(yīng)的關(guān)系。匯編程序所要做的翻譯工作比編譯程序簡單的多。

_________________________________________________

編譯原理2011年7月7日▼、1ST

Compiler

至程序的編譯和運行

?編譯或匯編階段

編譯程序

源程序.目標(biāo)程序

或匯編程序

?運行階段

目標(biāo)程序

輸入數(shù)據(jù)+輸出數(shù)據(jù)

運行子程序

編譯原理2011年7月7日SIST

Compiler

解釋程序(Interpreter)(類似于口譯，不生成目標(biāo)代碼)

對源程序進行解釋執(zhí)行的程序。

?工作過程

源程序

輸入數(shù)據(jù)解釋程序輸出數(shù)據(jù)

?特點：與編譯系統(tǒng)比較，解釋系統(tǒng)較簡單、

可移植性好，易于查錯，但速度慢

編譯原理2011年7月7日SIST

Compiler

有譯■解釋執(zhí)行”系統(tǒng)

源程序

編譯程序

▼

?

源程序的中間形式

輸入數(shù)據(jù)，解釋程序輸出數(shù)據(jù)

編譯原理2011年7月7日SIST

Compiler

例如Java語言

.javajava源程序文件

.class二進制字節(jié)碼文件

Java虛擬機（JVM）

本地計算機系統(tǒng)

編鋒原理2011年7月7日StST

Compiler

L2編譯程序的組成

所謂編譯過程是指將高級語言程序翻譯為等價的目標(biāo)

程序的過程。

翻譯外文資料：

1、能識別出句子中的一個單詞；

2、分析句子的語法結(jié)構(gòu)；

3、根據(jù)句子的含義進行初步翻譯;

4、對譯文進行修飾；

5、寫出最后的譯文。

編譯原理2011年7月7日SIST

編譯過程

?翻譯和編譯工作的比較

翻譯外文編譯程序

識別單詞詞法分析

分析分析句子語法分析

根據(jù)語義進語義分析、生成中間代碼

行初步翻譯

修辭加工代碼優(yōu)化

綜合寫出譯文目標(biāo)代碼生成

編譯原理2011年7月7日SlST

編譯過程

習(xí)慣上是將編譯過程劃分為5個基本階段:

▼

編鋒原理2011年7月7日StST

Compiler

一、詞法分析第

任務(wù)：根據(jù)詞法規(guī)則分析和識別單翅

字符序列—?I編碼形式

A單詞:是語言的基本語法單位

<1>保留字（如if、else、while)

<2>標(biāo)識符（如max、min、str)

<3>常數(shù)（如12、6.8、'a')

<4>分界符（如:+、-、*、/、；、（、

Compiler

詞法分析程序的結(jié)果--二元式y(tǒng)=x+r*6

單詞值單詞類別

y標(biāo)識符

—分界符（賦值）

X標(biāo)識符

+分界符（加號）

r標(biāo)識符

*分界符（乘號）

6常數(shù)

編鋒原理2011年7月7日StST

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

?詞法分析(lexicalanalysisorscanning)

一一Thestreamofcharactersmakingupa

sourceprogramisreadfromlefttoright

andgroupedintotokens,whichare

sequencesofcharactersthathavea

collectivemeaning.

單

詞---token

保

一一reservedword

標(biāo)

--identifier(user-definedname)

編譯原理2011年7月7日SIST

Compiler

二、語法分析（編譯程序的核心）產(chǎn)胃

任務(wù)：根據(jù)語法規(guī)則（即語言的文法），分析并識

別出各種語法成分（如表達式、語句、函數(shù)等），

并進行語法正確性檢查。

文法

＜賦值語句）：：=＜標(biāo)識符＞“="＜表達式＞

＜表達式）:：=＜表達式＞"+”＜表達式）?＜表達式＞"*”＜表達式）

＜表達式＞：：="（”＜表達式＞“）”?＜標(biāo)識符）?＜整數(shù)＞?＜實數(shù)）

編譯原理2011年7月7日SIST

|〈賦值語句〉::二V標(biāo)識符〉“二”〈表達式〉

V表達式》::二V表達式,“+”〈表達式〉|V表達式＞“*"V表達式,

IV表達式＞：：="（”＜表達式＞"）”IV標(biāo)識符〉IV整數(shù)〉IV實數(shù)〉

CnmnilaK

語

法

分

析

的

結(jié)

果

表達式

語

法

整數(shù)

r

6

Compiler

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

?語法分析(syntaxanalysisorparsing)

Thepurposeofsyntaxanalysisisto

determinethesourceprogram'sphrase

structure.Thisprocessisalsocalled

parsing.Thesourceprogramisparsedto

checkwhetheritconformstothesource

language'ssyntax,andtoconstructa

suitablerepresentationofitsphrase

structure.

編譯原理2011年7月7日SlST

Compiler

三、語義分析及中間代碼生成方］

任務(wù)：依據(jù)語義規(guī)則對識別出的各種語法成金析其

含義，并進行初步翻譯，生成中間代碼。

?靜態(tài)：

分析語法成份的含義，進行語義上的正確性檢查

?動態(tài)：

根據(jù)相應(yīng)語義，生成中間代碼（介于源語言和目

標(biāo)語言之間的中間語言形式）

編譯原理2011年7月7日SIST

Compiler

A生成中間代碼的目的：

?1、利于代碼優(yōu)化

?2、利于目標(biāo)代碼的移植

A中間代碼的形式：

?四元式、三元式、逆波蘭表示

編譯原理2011年7月7日SIST

Compiler

★四元式|例：y=x+r*

運算符左運算對象右運算對象結(jié)果

(1)inttoreal6一一tl

⑵*rtlt2

(3)+t2X13

—

(4)t3y

其中tl、t2、t3為編譯程序引入的臨時工作單元

編譯原理2011年7月7日-SiST

Compiler

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

?語義分析(semanticanalysis)

Theparsedprogramisfurtheranalyzedto

determinewhetheritconformstothe

sourcelanguage'scontextual

constraints:scoperules,typerules

e.g.Torelateeachappliedoccurrenceofan

identifierinthesourceprogramtothe

correspondingdeclaration.

編譯原理2011年7月7日SlST

Compiler

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

?中間代碼生成(intermediatecode

generation)

Thisiswheretheintermediate

representationofthesourceprogramis

created.Wewantthisrepresentationtobe

easytogenerate,andeasytotranslateinto

thetargetprogram.Therepresentation

canhaveavarietyofforms,butacommon

oneiscalledthree-addresscodeor4-

tuplecode.

編譯原理2011年7月7日SlST

Compiler

四、代碼優(yōu)化吞

|例：y=x+r*6

任務(wù)：對中間代碼進行加工變換,以得到高質(zhì)量的目

標(biāo)代碼

運算符左運算對象右運算對象結(jié)果

inttoreal6一一tl

⑵*rtlt2

⑶+t2Xt3

（伏t3y

運算符左運算對象右運算對象結(jié)果

*

(1)r6.0tl

(2)+tlXy

Compiler

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

?代石馬優(yōu)化(Intermediatecodeoptimization)

Theoptimizeracceptsinputinthe

intermediaterepresentationandoutputa

versionstillintheintermediate

representation.Inthisphase,thecompiler

attemptstoproducethesmallest,fastest

andmostefficientrunningresultby

applyingvarioustechniques.

編譯原理2011年7月7日SlST

Compiler

五、目標(biāo)代碼生成至0

任務(wù)：把中間代碼變換成特定機器上的低級語言代碼

運算符左運算對象右運算對象結(jié)果

(1)*r6.0tl

(2)+tlXy

movr,RI

mul#6.0,RI

movx,R2

addRI,R2

編譯2011年7月7日?SIST

movR2,y

Compiler

編譯過程小結(jié)

詞法分析\語法分析\\代碼優(yōu)化\目標(biāo)代碼\k

S.P程序節(jié)卜序刑;髓;；'）程序又J生最義序\OP

J——____/\_____/I____/

編譯原理2011年7月7日SIST

Compiler

按邏輯功能不同，可將編譯過程劃分為五個基本階

段，與此相對應(yīng)，我們修實現(xiàn)整個編譯過程的編譯程序劃

分為五個邏輯階段（即五個邏輯子過程）。

每個階段中都要有：

符號表管理和錯誤處理

編譯原理2011年7月7日SIST

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

★符號表管理

填表：把源程序中的信息和編譯過程中所產(chǎn)生的

信息登記在裝格中

查表：在隨后的編譯過程中同時又要不斷的查找

這些表落中的信息

★錯誤處理

診察錯誤，并能報告用戶錯誤性質(zhì)和位置

出錯處理能力的優(yōu)劣是衡量編譯程序質(zhì)量好壞的

一個重要指標(biāo)。

編譯原理2011年7月7日SIST

Compiler

典型的編譯程序具有7個邏輯部分

S.P

詞法分析程序

符

錯

號

誤

表

處

管

理

理

編譯原理2011年7月7日SIST

編譯程序的前端和后端

根據(jù)編譯程序各部分功能，將編譯程序分成前端和后端

前端：通常修與源程序有關(guān)的編譯部分稱為前端。

詞法分析、語法分析、語義分析、中間代碼生成

---分析部分

特點：與源語言有關(guān)

后端：與目標(biāo)機有關(guān)的部分稱為后端。

代碼優(yōu)化、代碼生成---綜合部分

特點：與目標(biāo)機有關(guān)

編譯原理2011年7月7日SIST

同一前端+不同后端少不同機器構(gòu)成同一語言的編譯程序

例如Java語言

.javajava源程序文件

.class二進制字節(jié)碼文件

Java虛擬機（JVM）

本地計算機系統(tǒng)

編鋒原理2011年7月7日StST

同一前端+不同后端少不同機器構(gòu)成同一語言的編譯程序

例如.NET框架

不同前端+同一后端少同一機器生成幾個語言的編譯程序

例如GCC

對源程序（包括源程序中間形式）從頭到尾掃描

一次，并做有關(guān)的加工處理，里成新的源程序中

間形式或目標(biāo)程序，通常稱之為一遍。

上一1遍的結(jié)果是下一■遍的輸入，最后一1遍生成目標(biāo)程序。

編譯原理2011年7月7日SIST

Compiler

一遍掃描即可完成整個編譯工作的稱為一遍掃描編譯程序

遍的劃分視具體情況而定（內(nèi)存的大小、源語言的繁簡、

目標(biāo)程序質(zhì)量的高低）

優(yōu)點：

1、減少對內(nèi)存容量的要求

2、編譯程序結(jié)構(gòu)清晰、各遍功能獨立、相互聯(lián)系簡單

缺點：

增加讀寫中間文件的次數(shù)，降低效率

______________________________________________

編譯原理20U年7月7日"'1ST

Compiler

L3編譯程序的構(gòu)造

構(gòu)造編玲程序必須精通:

?源語言

?目標(biāo)語言

?編譯方法

編譯原理2011年7月7日

Compiler

開發(fā)編譯程序的途徑:

,自展法

,工具法

,自動生成法

?移植法

編譯原理