編譯原理 1 緒論學(xué)習(xí)課件

編譯原理第一章緒論哈爾濱工業(yè)大學(xué)陳鄞1.1什么是編譯1.2編譯系統(tǒng)的結(jié)構(gòu)1.3為什么要學(xué)習(xí)編譯原理1.4編譯技術(shù)的應(yīng)用本章內(nèi)容1.1什么是編譯？機器語言(MachineLanguage)匯編語言

(AssemblyLanguage)高級語言(HighLevelLanguage)匯編器

(Assembler)編譯器

(Compiler)C70600000002MOVX,2x=2編譯器

(Compiler)可以被計算機直接理解與人類表達習(xí)慣相去甚遠難記憶難編寫、難閱讀易寫錯依賴于特定機器，非計算機專業(yè)人員使用受限制編寫效率依然很低引入助記符接近人類表達習(xí)慣與任何機器無關(guān)編寫效率高類似于數(shù)學(xué)定義或自然語言的簡潔形式編譯：將高級語言程序翻譯成匯編語言或機器語言程序的過程源程序目標(biāo)程序編譯器在語言處理系統(tǒng)中的位置預(yù)處理器

(Preprocessor)源程序編譯器經(jīng)過預(yù)處理的源程序匯編器

(Assembler)

匯編語言程序鏈接器(Linker)/加載器

(Loader)可重定位的機器代碼目標(biāo)機器代碼把存儲在不同文件中的源程序聚合在一起把被稱為宏的縮寫語句轉(zhuǎn)換為原始語句編譯器在語言處理系統(tǒng)中的位置預(yù)處理器

(Preprocessor)源程序編譯器經(jīng)過預(yù)處理的源程序匯編器

(Assembler)

匯編語言程序鏈接器(Linker)/加載器

(Loader)可重定位的機器代碼目標(biāo)機器代碼可重定位(Relocatable)：在內(nèi)存中存放的起始位置L不是固定的起始地址

+相對地址=絕對地址加載器：修改可重定位地址；將修改后的指令和數(shù)據(jù)放到內(nèi)存中適當(dāng)?shù)奈恢镁幾g器在語言處理系統(tǒng)中的位置預(yù)處理器

(Preprocessor)源程序編譯器經(jīng)過預(yù)處理的源程序匯編器

(Assembler)

匯編語言程序鏈接器(Linker)/加載器

(Loader)可重定位的機器代碼目標(biāo)機器代碼庫文件；其它可重定位目標(biāo)程序鏈接器將多個可重定位的機器代碼文件（包括庫文件）連接到一起解決外部內(nèi)存地址問題1.1什么是編譯1.2編譯系統(tǒng)的結(jié)構(gòu)1.3為什么要學(xué)習(xí)編譯原理1.4編譯技術(shù)的應(yīng)用提綱1.2編譯系統(tǒng)的結(jié)構(gòu)高級語言程序匯編語言程序/機器語言程序編譯器計算機是怎么實現(xiàn)自動翻譯的？Intheroom,hebrokeawindowwithahammer.

人工英漢翻譯的例子第1步分析源語言源語言句子句子的語義第2步生成目標(biāo)語言目標(biāo)語言句子語義分析（SemanticAnalysis）~~~~~~~~~~[]<>在房間里，他用錘子砸了一扇窗戶。中間表示，獨立于具體的語言補語狀語主語謂語

賓語Intheroom,hebrokeawindowwithahammer.

人工英漢翻譯的例子源語言句子句子的語義第2步生成目標(biāo)語言目標(biāo)語言句子語義分析（SemanticAnalysis）~~~~~~~~~~[]<>補語狀語主語謂語

賓語介短

名短動短名短介短介詞冠詞名詞代詞動詞冠詞名詞介詞冠詞名詞語法分析（SyntaxAnalysis）詞法分析（LexicalAnalysis）第1步分析源語言Intheroom,hebrokeawindowwithahammer.詞法分析人工英漢翻譯的例子Intheroom,hebrokeawindowwithahammer.詞法分析語法分析人工英漢翻譯的例子Intheroom,hebrokeawindowwithahammer.詞法分析語法分析語義分析人工英漢翻譯的例子編譯器的結(jié)構(gòu)分析部分/前端（Frontend）：與源語言相關(guān)綜合部分/后端（Backend）：與目標(biāo)語言相關(guān)詞法分析的主要任務(wù)從左向右逐行掃描源程序的字符，識別出各個單詞，確定單詞的類型。將識別出的單詞轉(zhuǎn)換成統(tǒng)一的機內(nèi)表示——詞法單元(token)形式token：<種別碼，屬性值>Phase1：詞法分析/掃描(Scanning)一字一碼統(tǒng)一作為一種單詞一型一碼一符一碼一符一碼單詞類型種別種別碼1關(guān)鍵字program、if、else、then、…一詞一碼2標(biāo)識符變量名、數(shù)組名、記錄名、過程名、…多詞一碼3常量整型、浮點型、字符型、布爾型、…一型一碼4運算符算術(shù)（+-*/++--）關(guān)系（>

<

==

!=

>=

<=）邏輯（&

|

~）一詞一碼或一型一碼5界限符;

(

)

=

{

}

…一詞一碼輸入while(value!=100){num++;}輸出 1 while <WHILE,_ > 2( <SLP,_

> 3value <IDN

,value > 4!= <

NE

,_

> 5100 <CONST,100 > 6) <SRP,_

> 7{ <LP,_

> 8num <IDN

,num > 9++ <

INC,_ > 10; <SEMI,_ > 11} <RP,_ >例：詞法分析后得到的token序列如何實現(xiàn)詞法分析器？編譯器的結(jié)構(gòu)語法分析器（parser）從詞法分析器輸出的token序列中識別出各類短語，并構(gòu)造句子的分析樹(parsetree)分析樹描述了句子的語法結(jié)構(gòu)Phase2：語法分析(Parsing)position:=initial+rate*60<id,position><:=><id,initial><+><id,rate><*><num,60>例1：賦值語句的分析樹;文法：<D>→<T><IDS>;<T>→int|real|char|bool<IDS>→id|<IDS>,id輸入：inta,b,c;例2：變量聲明語句的分析樹，;<D><IDS>id(a)<T><IDS>id(c)int，<IDS>id(b)如何根據(jù)語法規(guī)則為輸入句子構(gòu)造分析樹？編譯器的結(jié)構(gòu)語義分析的主要任務(wù)獲取標(biāo)識符的屬性種屬

(Kind)簡單變量、復(fù)合變量（數(shù)組、記錄、…）、過程、…Phase3：語義分析語義分析的主要任務(wù)獲取標(biāo)識符的屬性種屬

(Kind)類型

(Type)整型、實型、字符型、布爾型、指針型、…Phase3：語義分析語義分析的主要任務(wù)獲取標(biāo)識符的屬性種屬

(Kind)類型

(Type)存儲位置、長度Phase3：語義分析例：begin realx[8]; integeri,j;……end名字相對地址x0i64j68x[1]x[2]……x[8]ij08566468語義分析的主要任務(wù)獲取標(biāo)識符的屬性種屬

(Kind)類型

(Type)存儲位置、長度值(Value)作用域

(Scope)參數(shù)和返回值信息參數(shù)個數(shù)、參數(shù)類型、參數(shù)傳遞方式、返回值類型、…Phase3：語義分析語義分析的主要任務(wù)獲取標(biāo)識符的屬性種屬

(Kind)類型

(Type)存儲位置、長度值(Value)作用域

(Scope)參數(shù)和返回值信息Phase3：語義分析符號表(SymbolTable)符號表是用于存放標(biāo)識符的屬性信息的數(shù)據(jù)結(jié)構(gòu)字符串表NAME字段為什么要這樣設(shè)計數(shù)據(jù)結(jié)構(gòu)？語義分析的主要任務(wù)獲取標(biāo)識符的屬性語義檢查變量或過程是否未經(jīng)聲明就使用變量或過程名是否重復(fù)聲明

運算分量類型是否不匹配

操作符與操作數(shù)之間的類型是否不匹配對整型變量使用數(shù)組訪問或過程調(diào)用操作符數(shù)組下標(biāo)不是整數(shù)過程調(diào)用參數(shù)類型或數(shù)目不匹配函數(shù)返回類型有誤Phase3：語義分析編譯器的結(jié)構(gòu)常用的中間表示形式三地址碼

(Three-addressCode)語法結(jié)構(gòu)樹/語法樹

(SyntaxTrees)三地址碼由類似于匯編語言的指令序列組成，每個指令最多有三個操作數(shù)（operand）Phase4：中間代碼生成常用的三地址指令序號指令類型指令形式1賦值指令x=y

op

zx=op

y

2復(fù)制指令x

=

y3條件跳轉(zhuǎn)ifx

relop

y

goto

n

4非條件跳轉(zhuǎn)goto

n

5參數(shù)傳遞param

x

6過程調(diào)用call

p,n

7過程返回return

x

8數(shù)組引用x

=

y[i]9數(shù)組賦值x[i]

=

y10地址及指針操作x

=&y

x

=*y

*x

=

y地址可以具有如下形式之一源程序中的名字（name）常量（constant）編譯器生成的臨時變量(temporary)四元式

(Quadruples)

(op,y,z,x)三元式

(Triples)間接三元式(Indirecttriples)三地址指令的表示x=y

op

z

（op

,y,z ,x

）x=op

y

（op

,y,_ ,x）x

=

y

（:=

,y,_ ,x）ifx

relop

ygoton(

relop

,x,y ,n

）goto

n

（goto

,_,_,n）param

x

（param

,_,_,x

）

callp,n

（

call

,p,n,_）

return

x

（return

,_,_,x

）x

=

y[i]

（=[]

,y,i ,x

）

x[i]=y

（[]=

,y,x ,i

）x

=&y

（

&

,y,_ ,x）

x

=*y

（=*

,y,_ ,x

）

*x

=

y

（*=

,y,_ ,x

）四元式表示三地址指令序列唯一確定了運算完成的順序while

a<b

do

ifc<5then

while

x>y

do

z=x+1;else

x=y;100: (j<,a,b,102

)101:

(j,-,-,-)102:

(j<,c,5,104)103:

(j,-,-,110)104:

(j>,x,y,106)105:

(j,-,-,100)106:

(+,x,1,t1

)107:

(=,t1

,-,z)108:

(j,-,-,104)109:

(j,-,-,100)110:

(=,y,-,x)111:

(j,-,-,100)112:?Sid(a)whileB

do

SErelopEif

B

then

S

else

Sid(b)(<)id(c)ErelopEwhile

B

do

SErelopEid=

E

;(z)E

+

Eid=

E

;(x)(<)num(5)id(x)id(y)(>)id(x)num(1)id(y)例編譯器的結(jié)構(gòu)目標(biāo)代碼生成以源程序的中間表示形式作為輸入，并把它映射到目標(biāo)語言目標(biāo)語言需要為程序使用的每個變量選擇寄存器或內(nèi)存位置目標(biāo)代碼生成的一個至關(guān)重要的方面是合理分配寄存器以存放變量的值編譯器的結(jié)構(gòu)代碼優(yōu)化為改進代碼所進行的等價程序變換，使其運行得更快一些、占用空間更少一些，或者二者兼顧1.1什么是編譯1.2編譯系統(tǒng)的結(jié)構(gòu)1.3為什么要學(xué)習(xí)編譯原理1.4編譯技術(shù)的應(yīng)用提綱

編寫編譯器的原理和技術(shù)具有十分普遍的意義，以至于在每個計算機科學(xué)家的研究生涯中，本課程中的原理和技術(shù)都會反復(fù)用到?！狝lfredV.Aho1.3為什么要學(xué)習(xí)編譯原理更深刻地理解高級語言程序的內(nèi)部運行機制教給我們?nèi)绾螄乐數(shù)厝ニ伎?、編寫程序編譯原理蘊含了計算機科學(xué)解決問題的思路和方法，即“形式化→自動化”。所涉及的理論和方法在很多領(lǐng)域都會被用到自然語言處理、模式識別、人工智能、……很多應(yīng)用軟件都會用到編譯技術(shù)1.1什么是編譯1.2編譯系統(tǒng)的結(jié)構(gòu)1.3為什么要學(xué)習(xí)編譯原理1.4編譯技術(shù)的應(yīng)用提綱結(jié)構(gòu)化編輯器（Structureeditors）引導(dǎo)用戶在語言的語法約束下編制程序能自動地提供關(guān)鍵字和與其匹配的關(guān)鍵字1.4編譯技術(shù)的應(yīng)用結(jié)構(gòu)化編輯器（Structureeditors）智能打印機（Prettyprinters）對程序進行分析，打印出結(jié)構(gòu)清晰的程序注釋以一種特殊的字體打印根據(jù)各個語句在程序的層次結(jié)構(gòu)中的嵌套深度進行縮進1.4編譯技術(shù)的應(yīng)用結(jié)構(gòu)化編輯器（Structureeditors）智能打印機（Prettyprinters）靜態(tài)檢查器（Staticcheckers）檢測出程序中永遠不能被執(zhí)行的語句1.4編譯技術(shù)的應(yīng)用結(jié)構(gòu)化編輯器（Structureeditors）智能打印機（Prettyprinters）靜態(tài)檢查器（Staticcheckers）文本格式器（Textformatters）文本格式器處理的字符流中除了需要排版輸出的字符以外，還包含一些用來說明字符流中的段落、圖表或者上標(biāo)和下標(biāo)等數(shù)學(xué)結(jié)構(gòu)的命令1.4編譯技術(shù)的應(yīng)用結(jié)構(gòu)化編輯器（Structureeditors）智能打印機（Prettyprinters）靜態(tài)檢查器（Staticcheckers）文本格式器（Textformatters）數(shù)據(jù)庫查詢解釋器（

DatabaseQueryInterpreters）數(shù)據(jù)庫查詢語句由包含了關(guān)系和布爾運算的謂詞組成。查詢解釋器把這些謂詞翻譯成數(shù)據(jù)庫命令，在數(shù)據(jù)庫中查詢滿足條件的記錄。1.4編譯技術(shù)的應(yīng)用結(jié)構(gòu)化編輯器（Structureeditors）智能打印機（Prettyprinters）靜態(tài)檢查器（Staticcheckers）文本格式器（Textformatters）數(shù)據(jù)庫查詢解釋器（

DatabaseQueryInterpreters）高級語言的翻譯工具1.4編譯技術(shù)的應(yīng)用什么是編譯編譯系統(tǒng)的結(jié)構(gòu)為什么要學(xué)習(xí)編譯原理編譯技術(shù)的應(yīng)用本章小結(jié)1．緒論 （2學(xué)時）2.語言及其文法

（2學(xué)時）3．詞法分析 （4學(xué)時）4．語法分析 （9學(xué)時）5．語法制導(dǎo)翻譯

（6學(xué)時）6．中間代碼生成

（7學(xué)時）7．運行時的存貯組