編譯原理 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什么是編譯？機(jī)器語言(MachineLanguage)匯編語言

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

(Assembler)編譯器

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

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

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

(Assembler)

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

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

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

(Assembler)

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

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

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

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

(Assembler)

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

(Loader)可重定位的機(jī)器代碼目標(biāo)機(jī)器代碼庫文件；其它可重定位目標(biāo)程序鏈接器將多個(gè)可重定位的機(jī)器代碼文件（包括庫文件）連接到一起解決外部?jī)?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)高級(jí)語言程序匯編語言程序/機(jī)器語言程序編譯器計(jì)算機(jī)是怎么實(shí)現(xiàn)自動(dòng)翻譯的？Intheroom,hebrokeawindowwithahammer.

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

賓語Intheroom,hebrokeawindowwithahammer.

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

賓語介短

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

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

(Kind)類型

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

(Kind)類型

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

(Kind)類型

(Type)存儲(chǔ)位置、長(zhǎng)度值(Value)作用域

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

(Kind)類型

(Type)存儲(chǔ)位置、長(zhǎng)度值(Value)作用域

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

運(yùn)算分量類型是否不匹配

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

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

(SyntaxTrees)三地址碼由類似于匯編語言的指令序列組成，每個(gè)指令最多有三個(gè)操作數(shù)（operand）Phase4：中間代碼生成常用的三地址指令序號(hào)指令類型指令形式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）編譯器生成的臨時(shí)變量(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

）四元式表示三地址指令序列唯一確定了運(yùn)算完成的順序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)語言需要為程序使用的每個(gè)變量選擇寄存器或內(nèi)存位置目標(biāo)代碼生成的一個(gè)至關(guān)重要的方面是合理分配寄存器以存放變量的值編譯器的結(jié)構(gòu)代碼優(yōu)化為改進(jìn)代碼所進(jìn)行的等價(jià)程序變換，使其運(yùn)行得更快一些、占用空間更少一些，或者二者兼顧1.1什么是編譯1.2編譯系統(tǒng)的結(jié)構(gòu)1.3為什么要學(xué)習(xí)編譯原理1.4編譯技術(shù)的應(yīng)用提綱

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

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

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

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

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

（7學(xué)時(shí)）7．運(yùn)行時(shí)的存貯組