編譯原理第1章

編譯原理

袁彩虹

yuanch@程序設(shè)計(jì)語言什么是編譯？機(jī)器語言(MachineLanguage)0、1代碼匯編語言(AssembleLanguage)：助記符高級(jí)語言(HighLevelLanguage)：定義數(shù)據(jù)、描述算法（程序） 如：C、Pascal、C++、Java、SQL高級(jí)語言低級(jí)語言學(xué)習(xí)的意義(1)一門基礎(chǔ)專業(yè)課,對(duì)于”計(jì)算機(jī)專業(yè)”的同學(xué)而言,類似于”高等數(shù)學(xué)”對(duì)于”理工科”學(xué)生工作和學(xué)習(xí)的影響,使其”享用一輩子”.(2)作用

＊有利于大家對(duì)”程序設(shè)計(jì)語言”的理解

→較迅速掌握新的語言工具.

＊包含許多軟件技術(shù),對(duì)于以后從事軟件設(shè)計(jì)很有價(jià)值.→從軟件工程看，編譯器是一個(gè)很好的實(shí)例，所介紹的概念和技術(shù)能應(yīng)用到一般的軟件設(shè)計(jì)之中。

＊蘊(yùn)涵著計(jì)算機(jī)學(xué)科中解決問題的思路﹑抽象問題和解決問題的方法.課程要求1、認(rèn)真聽課，認(rèn)真理解書中基本概念、基本原理與基本算法；2、弄懂書中的例題與習(xí)題；3、在看書或理解例題時(shí)，一定要?jiǎng)邮之嫵鱿鄳?yīng)的細(xì)節(jié)變化過程，通過畫圖來加深理解；4、在理解的基礎(chǔ)上記憶；5、理論結(jié)合實(shí)踐?？己朔绞娇己朔绞剑?/p>

--平時(shí)成績(jī)占30%--期末考試成績(jī)占70%平時(shí)成績(jī)：

--考勤

--作業(yè)

--實(shí)驗(yàn)第1章引論第2章高級(jí)語言及其語法描述第3章詞法分析第4章語法分析——自上而下分析第5章語法分析——自下而上分析第6章屬性文法和語法制導(dǎo)翻譯第7章語義分析和中間代碼產(chǎn)生第8章符號(hào)表第9章運(yùn)行時(shí)存儲(chǔ)空間組織第10章優(yōu)化

第11章目標(biāo)代碼生成目錄第一章引論1.1什么叫編譯程序1.2編譯過程概述1.3編譯程序的結(jié)構(gòu)1.4編譯程序與程序設(shè)計(jì)環(huán)境（略）1.5編譯程序的生成1.什么是編譯程序？1.1什么叫編譯程序翻譯程序：一種語言程序---------->另一種語言程序源語言目標(biāo)語言編譯程序：高級(jí)語言程序---------->低級(jí)語言程序匯編程序：匯編語言程序---------->機(jī)器語言程序解釋程序：源語言程序---------->邊解釋邊執(zhí)行（1）編譯方式：先編譯后執(zhí)行。（2）解釋方式：以源程序作為輸入，但不產(chǎn)生目標(biāo)代碼，而是邊解釋邊執(zhí)行源程序本身。2.“高級(jí)語言程序”的執(zhí)行方式1.1什么叫編譯程序編譯和解釋的主要區(qū)別：是否產(chǎn)生目標(biāo)代碼！3.“編譯程序”在計(jì)算機(jī)系統(tǒng)中的位置較接近于“硬件”1.1什么叫編譯程序4.發(fā)展20世紀(jì)50年代第一個(gè)編譯程序——FORTRAN編譯程序目前：編譯原理與技術(shù)得到迅速發(fā)展，現(xiàn)已形成一套比較成熟的系統(tǒng)化的理論與方法，并開發(fā)出了一些好的編譯程序的實(shí)現(xiàn)語言、環(huán)境與工具。當(dāng)時(shí)普遍認(rèn)為設(shè)計(jì)和實(shí)現(xiàn)編譯程序是一件十分困難、令人生畏的事情1.1什么叫編譯程序1.2編譯過程概述Theelephantateanbanana.什么是語言？forK:=1to100do begin M:=I+10*K; N:=J+10*K end一.類比自然語言翻譯和編譯過程英→漢編譯的工作過程1)識(shí)別單詞……………詞法分析2)分析句子語法結(jié)構(gòu)…………………語法分析3)根據(jù)句子含義初步翻譯…………語義分析與中間代碼產(chǎn)生4)修飾譯文…………………優(yōu)化5)寫出最后譯文…………………目標(biāo)代碼生成1.2編譯過程概述1.詞法分析forK:=1to100do begin M:=I+10*K; N:=J+10*K end

基本字for

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

賦值號(hào):=

常數(shù)1

基本字to

常數(shù)100

基本字do

基本字begin......1.2編譯過程概述詞法分析

——

規(guī)則：規(guī)則描述工具：任務(wù)：依循詞法規(guī)則正規(guī)式和有限自動(dòng)機(jī)（FA）輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)的單詞符號(hào)，如基本字、標(biāo)識(shí)符、常數(shù)、算符、界符等。1.2編譯過程概述2.語法分析forK:=1to100do begin M:=I+10*K; N:=J+10*K end規(guī)則：規(guī)則描述工具：任務(wù)：依循語法規(guī)則上下文無關(guān)文法在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，對(duì)單詞符號(hào)串進(jìn)行語法分析，識(shí)別出各類語法單位，最終判斷輸入串是否構(gòu)成語法上正確的“程序”。1.2編譯過程概述3.語義分析和中間代碼產(chǎn)生規(guī)則：規(guī)則描述工具：任務(wù)：語義規(guī)則屬性文法兩部分工作：1、對(duì)每種語法范疇進(jìn)行靜態(tài)語義檢查2、若語義正確，則進(jìn)行中間代碼翻譯對(duì)語法分析器識(shí)別出的各類語法單位，分析其含義并進(jìn)行初步翻譯（產(chǎn)生中間代碼）。

中間代碼：一種獨(dú)立于具體硬件的記號(hào)系統(tǒng)，更接近于機(jī)器代碼

1.2編譯過程概述forK:=1to100dobeginM:=I+10*K;N:=J+10*Kend；

K:=1L1:if100<KgotoL2T1:=10*KM:=I+T1T2:=10*KN:=J+T2

K:=K+1gotoL1L2:語義分析后產(chǎn)生的中間代碼：三地址代碼具體實(shí)現(xiàn)：三元式，四元式，間接三元式1.2編譯過程概述

K:=1L1:if100<KgotoL2T1:=10*KM:=I+T1T2:=10*KN:=J+T2

K:=K+1gotoL1L2:序號(hào)OPARG1ARG2RESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=j<*+*++j110010I10JKKKT1KT21K(9)T1MT2NK(2)四元式序列：1.2編譯過程概述任務(wù)：對(duì)中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生出更為高效（省時(shí)間和空間）的目標(biāo)代碼。規(guī)則:等價(jià)變換規(guī)則包括：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無用代碼等1.2編譯過程概述4.優(yōu)化序號(hào)OPARG1ARG2RESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=j<*+*++j110010I10JKKKT1KT21K(9)T1MT2NK(2)序號(hào)OPARG1ARG2RESULT(1)(2)(3)(4)(5)(6)(7)(8)(9):=:=:=j<+++jII1100MNK

K10101MNK(9)MNK(2)優(yōu)化前優(yōu)化后1.2編譯過程概述任務(wù)：把中間代碼變換成特定機(jī)器上的低級(jí)語言代碼，實(shí)現(xiàn)最后的翻譯。5.目標(biāo)代碼生成

絕對(duì)指令代碼/可重定位的指令代碼/匯編指令代碼有賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義1.2編譯過程概述1.3編譯程序的結(jié)構(gòu)一.編譯程序總框圖1.表格管理編譯各階段都要涉及到構(gòu)造、查找或 更新有關(guān)表格。表格的作用：

登記源程序的各類信息和編譯各階段的進(jìn)展?fàn)顩r。符號(hào)表：

用來登記源程序中出現(xiàn)的每個(gè)名字以及名字的各種屬性。

舉例：名字——變量名/常量名/過程名…？ 變量名——類型？/內(nèi)存？/地址？1.3編譯程序的結(jié)構(gòu)2.出錯(cuò)處理每一階段都可能檢測(cè)出錯(cuò)誤，絕大多 數(shù)錯(cuò)誤可在前三階段檢測(cè)出來任務(wù)：設(shè)法發(fā)現(xiàn)錯(cuò)誤，并把有關(guān)錯(cuò)誤信息報(bào)告給用戶

語法錯(cuò)誤：源程序中不符合語法/詞法規(guī)則的錯(cuò)誤。 詞法/語法分析時(shí)檢測(cè)語義錯(cuò)誤：源程序中不符合語義規(guī)則的錯(cuò)誤。

語義分析/運(yùn)行時(shí)檢測(cè)出來1.3編譯程序的結(jié)構(gòu)二.遍1.編譯過程的劃分：上述劃分的五個(gè)階段僅僅是邏輯功能上的一種劃分2.遍（Pass）對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。具體實(shí)現(xiàn)時(shí)，受各方面（如源語言、設(shè)計(jì)要求等）限制，往往組織成若干遍1.3編譯程序的結(jié)構(gòu)3.注意：既可以將幾個(gè)不同階段合為一遍，也可以把一個(gè)階段的工作分為若干遍例如：詞法分析+語法分析 一遍語法分析+語義分析與中間代碼產(chǎn)生一遍優(yōu)化

若干遍單遍代碼不太有效。根據(jù)系統(tǒng)資源的狀況、運(yùn)行目標(biāo)的要求等，可以將一個(gè)編譯程序設(shè)計(jì)形成多遍掃描的形式，在每一遍掃描中完成不同的任務(wù)。1.3編譯程序的結(jié)構(gòu)當(dāng)一遍中包含若干階段時(shí)，各階段的工作是穿插進(jìn)行的。例如：識(shí)別出一個(gè)語法單位時(shí)語法分析器詞法分析器語義分析和中間代碼產(chǎn)生器識(shí)別語法結(jié)構(gòu)需要下一個(gè)單詞時(shí)單詞符號(hào)1.3編譯程序的結(jié)構(gòu)三.編譯前端與后端1、前端：

由與源語言有關(guān)但與目標(biāo)機(jī)無關(guān)的那些部分組成包括——詞法分析、語法分析、語義分析與中間代碼產(chǎn)生、部分代碼優(yōu)化工作

2、后端： 包括編譯程序中與目標(biāo)機(jī)有關(guān)的那些部分，如與目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。不依賴于源語言而僅僅依賴于中間語言1.3編譯程序的結(jié)構(gòu)1.5編譯程序的生成一.設(shè)計(jì)目標(biāo)

目標(biāo)程序小，執(zhí)行速度快編譯程序小，執(zhí)行速度快診斷能力強(qiáng)，可靠性強(qiáng)可移植性，可擴(kuò)充性

如何實(shí)現(xiàn)編譯器？直接用可運(yùn)行的代碼編制太費(fèi)力！STI源語言編譯程序?qū)崿F(xiàn)語言目標(biāo)語言一般采用高級(jí)語言實(shí)現(xiàn)，可用T形圖表示如下：表現(xiàn)語言翻譯的T形圖1.5編譯程序的生成問題：已知A機(jī)上有一個(gè)用A代碼實(shí)現(xiàn)的高級(jí)語言L1的編譯程序，可以用L1實(shí)現(xiàn)在A機(jī)上能運(yùn)行一個(gè)新語言L2編寫的程序。

L1AA已知條件目標(biāo)L2L1A二.多級(jí)編譯程序

1、本機(jī)編譯器利用

分析：1.5編譯程序的生成條件目標(biāo)L2L1AL1AAL2AAL1語言寫成的L2語言的編譯程序A代碼寫成的L1語言的編譯程序得到A代碼寫成的L2語言的編譯程序P0P1P2說明：P0——L2語言的編譯程序，用L1語言實(shí)現(xiàn)

P1——L1語言的編譯程序，用A代碼實(shí)現(xiàn)

P2——L2語言的編譯程序，用A代碼實(shí)現(xiàn)

1.5編譯程序的生成問題：能否用A機(jī)上有的高級(jí)語言L實(shí)現(xiàn)在B機(jī)上運(yùn)行L語言程序？LAA條件目標(biāo)LLB2、交叉編譯/移植（思考）1.5編譯程序的生成LAA條件LLB目標(biāo)LLBLAALABLLBLBB說明：過程在A機(jī)上運(yùn)行的產(chǎn)生B代碼的L編譯程序源程序（L語言編寫）1.5編譯程序的生成1.5編譯程序的生成3、自編譯過程

通過一系列自展途徑而形成編譯程序的過程叫做自編譯過程。

1.5編譯程序的生成三.