第1章 編譯概述

Compiler

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

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

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

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

高級(jí)語言？翻譯程序?匯編語言

SOURCE

PROGRAM

編譯原理2011年7月7日SIST

Compiler

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

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

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

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

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

機(jī)理。能運(yùn)用所學(xué)技術(shù)解決實(shí)際問題，能獨(dú)立

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

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

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

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

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

編譯原理2011年7月7日SIST

Compiler

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

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

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

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

應(yīng)用。

編譯原理2011年7月7日SIST

Compiler

先修課程

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

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

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

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

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

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

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

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

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

產(chǎn)方法。

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

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

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

Compiler

教材

?李冬梅，施海虎，《編譯原理》，人民郵電出版社

參考書

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

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

防工業(yè)出版社

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

編譯原理2011年7月7日SIST

Compiler

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

課程特點(diǎn)：理論性強(qiáng)，算法復(fù)雜

?平時(shí)(30%)

?無故曠課：-5

?一本教材，認(rèn)真聽課：以講義為主，板書為

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

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

?完成要求的課外實(shí)驗(yàn)內(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程序的翻譯

?低級(jí)語言(LowlevelLanguage)

-字位碼、機(jī)器語言、匯編語言

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

瑣、費(fèi)時(shí)、易出錯(cuò)

?高級(jí)語言

—Fortran>Pascal、C語言等

-特點(diǎn)：不依賴具體機(jī)器，移植性好、對(duì)用戶要求低、

易使用、易維護(hù)等。

編譯原理2011年7月7日SIST

Compiler

?源程序

用匯編語言或高級(jí)語言編寫的程序稱為源程序

?目標(biāo)程序

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

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

語言”，可以是某種機(jī)器的機(jī)器語言，也可以是某機(jī)器的匯

編語言。

將源程序轉(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)過翻譯程序得到用機(jī)器語言

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

程稱為“匯編”(Assemble)

?編譯程序

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

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

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

不同。由于匯編語言格式簡(jiǎn)單，常與機(jī)器語言之間有一一對(duì)

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

_________________________________________________

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

Compiler

至程序的編譯和運(yùn)行

?編譯或匯編階段

編譯程序

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

或匯編程序

?運(yùn)行階段

目標(biāo)程序

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

運(yùn)行子程序

編譯原理2011年7月7日SIST

Compiler

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

對(duì)源程序進(jìn)行解釋執(zhí)行的程序。

?工作過程

源程序

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

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

可移植性好，易于查錯(cuò)，但速度慢

編譯原理2011年7月7日SIST

Compiler

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

源程序

編譯程序

▼

?

源程序的中間形式

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

編譯原理2011年7月7日SIST

Compiler

例如Java語言

.javajava源程序文件

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

Java虛擬機(jī)（JVM）

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

編鋒原理2011年7月7日StST

Compiler

L2編譯程序的組成

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

程序的過程。

翻譯外文資料：

1、能識(shí)別出句子中的一個(gè)單詞；

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

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

4、對(duì)譯文進(jìn)行修飾；

5、寫出最后的譯文。

編譯原理2011年7月7日SIST

編譯過程

?翻譯和編譯工作的比較

翻譯外文編譯程序

識(shí)別單詞詞法分析

分析分析句子語法分析

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

行初步翻譯

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

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

編譯原理2011年7月7日SlST

編譯過程

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

▼

編鋒原理2011年7月7日StST

Compiler

一、詞法分析第

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

字符序列—?I編碼形式

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

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

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

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

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

Compiler

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

單詞值單詞類別

y標(biāo)識(shí)符

—分界符（賦值）

X標(biāo)識(shí)符

+分界符（加號(hào)）

r標(biāo)識(shí)符

*分界符（乘號(hà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í)

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

并進(jìn)行語法正確性檢查。

文法

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

＜表達(dá)式）:：=＜表達(dá)式＞"+”＜表達(dá)式）?＜表達(dá)式＞"*”＜表達(dá)式）

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

編譯原理2011年7月7日SIST

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

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

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

CnmnilaK

語

法

分

析

的

結(jié)

果

表達(dá)式

語

法

整數(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ī)則對(duì)識(shí)別出的各種語法成金析其

含義，并進(jìn)行初步翻譯，生成中間代碼。

?靜態(tài)：

分析語法成份的含義，進(jìn)行語義上的正確性檢查

?動(dòng)態(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*

運(yùn)算符左運(yùn)算對(duì)象右運(yùn)算對(duì)象結(jié)果

(1)inttoreal6一一tl

⑵*rtlt2

(3)+t2X13

—

(4)t3y

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

編譯原理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ù)：對(duì)中間代碼進(jìn)行加工變換,以得到高質(zhì)量的目

標(biāo)代碼

運(yùn)算符左運(yùn)算對(duì)象右運(yùn)算對(duì)象結(jié)果

inttoreal6一一tl

⑵*rtlt2

⑶+t2Xt3

（伏t3y

運(yùn)算符左運(yùn)算對(duì)象右運(yùn)算對(duì)象結(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ù)：把中間代碼變換成特定機(jī)器上的低級(jí)語言代碼

運(yùn)算符左運(yùn)算對(duì)象右運(yùn)算對(duì)象結(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

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

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

分為五個(gè)邏輯階段（即五個(gè)邏輯子過程）。

每個(gè)階段中都要有：

符號(hào)表管理和錯(cuò)誤處理

編譯原理2011年7月7日SIST

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

★符號(hào)表管理

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

信息登記在裝格中

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

這些表落中的信息

★錯(cuò)誤處理

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

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

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

編譯原理2011年7月7日SIST

Compiler

典型的編譯程序具有7個(gè)邏輯部分

S.P

詞法分析程序

符

錯(cuò)

號(hào)

誤

表

處

管

理

理

編譯原理2011年7月7日SIST

編譯程序的前端和后端

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

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

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

---分析部分

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

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

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

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

編譯原理2011年7月7日SIST

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

例如Java語言

.javajava源程序文件

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

Java虛擬機(jī)（JVM）

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

編鋒原理2011年7月7日StST

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

例如.NET框架

不同前端+同一后端少同一機(jī)器生成幾個(gè)語言的編譯程序

例如GCC

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

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

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

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

編譯原理2011年7月7日SIST

Compiler

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

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

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

優(yōu)點(diǎn)：

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

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

缺點(diǎn)：

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

______________________________________________

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

Compiler

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

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

?源語言

?目標(biāo)語言

?編譯方法

編譯原理2011年7月7日

Compiler

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

,自展法

,工具法

,自動(dòng)生成法

?移植法

編譯原理