工學(xué)編譯原理-第一章課件

編譯原理

第一章引論王金偉計(jì)算機(jī)與信息工程學(xué)院天津師范大學(xué)7/21/20231TJNU-COCIE-WJW編譯原理課程類別：專業(yè)選修課適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、計(jì)算機(jī)軟件總學(xué)時(shí)：51（平均每周3學(xué)時(shí)）總學(xué)分：3先修課：C語言、數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)各班選一位同學(xué)擔(dān)任課代表（收發(fā)作業(yè)）考核方法考勤5%（隨機(jī)點(diǎn)名5次，每次1分）課后作業(yè)5%（5次，每次1分）上機(jī)作業(yè)20%（4個(gè)，試驗(yàn)報(bào)告，每個(gè)5分）期末70%7/21/20232TJNU-COCIE-WJW主要內(nèi)容編譯程序的基本構(gòu)造原理和基本實(shí)現(xiàn)技術(shù)形式語言基礎(chǔ)知識(shí)詞法分析語法分析語法制導(dǎo)翻譯程序優(yōu)化代碼生成7/21/20233TJNU-COCIE-WJW主要章節(jié)第1章．引論第2章．高級(jí)語言的定義和一般特征第3章．詞法分析第4章．語法分析——自上而下分析第5章．語法分析——自下而上分析第6章．屬性文法和語法制導(dǎo)翻譯第7章．語義分析和中間代碼生成第8章．符號(hào)表第9章．運(yùn)行時(shí)存儲(chǔ)空間組織第10章．優(yōu)化第11章．目標(biāo)代碼生成7/21/20234TJNU-COCIE-WJW教材和參考書1. 教材： 陳火旺等：程序設(shè)計(jì)語言編譯原理（第三版），國防工業(yè)出版社，2000年2. 參考書：編譯原理和技術(shù)（第二版，陳意云編著，中國科學(xué)技術(shù)大學(xué)出版社，1997）呂映芝、張素琴、蔣維杜：編譯原理；清華大學(xué)出版社1998杜淑敏、王永寧：編譯程序設(shè)計(jì)原理；北京大學(xué)出版社19867/21/20235TJNU-COCIE-WJW第一章引論1.1什么叫編譯程序1.2編譯過程概述1.3編譯程序的結(jié)構(gòu)1.4編譯程序與程序設(shè)計(jì)環(huán)境1.5編譯程序的生成1.6學(xué)習(xí)“編譯原理”課的注意事項(xiàng)7/21/20236TJNU-COCIE-WJW1.1什么叫編譯程序多數(shù)用戶用高級(jí)語言（C，C++，Pascal）編寫程序，以實(shí)現(xiàn)他們所需要的應(yīng)用但目前的計(jì)算機(jī)執(zhí)行的是非常低級(jí)的語言：機(jī)器語言。問題：高級(jí)語言寫出的程序最終是怎樣在計(jì)算機(jī)上執(zhí)行的呢？答案：編譯程序7/21/20237TJNU-COCIE-WJW1.現(xiàn)實(shí)例子

一、編譯程序的概念英文書中文書翻譯7/21/20238TJNU-COCIE-WJW2.翻譯程序 能夠把某一種語言程序轉(zhuǎn)換成另一種語言程序，并且，后者與前者在邏輯上是等價(jià)的。源語言程序目標(biāo)語言程序翻譯程序Main(){

int

i,j;…}…PROCEDURE

MAIN;

Var

I,J:Integer;

Begin…End…輸入輸出c程序pascal程序7/21/20239TJNU-COCIE-WJW3.編譯程序是翻譯程序的一種特點(diǎn)：目標(biāo)語言比源語言低級(jí)源語言程序目標(biāo)語言程序翻譯程序

….

int

a,b,c;a=1;b=2;c=a+b;……Mova,1Movb,2Addc,a,b…輸入輸出c程序匯編語言程序編譯程序7/21/202310TJNU-COCIE-WJW4.解釋程序特點(diǎn)：以源語言程序作為輸入，但不產(chǎn)生目標(biāo)語言程序，而是邊解釋邊執(zhí)行源語言程序

….public

class

student

{

public

static

void

main(String

args[]){

StringBuffer

string[]=

new

StringBuffer[10];

….

}

}…輸入執(zhí)行JAVA程序解釋程序JVM（JAVA虛擬機(jī)）輸入編譯程序字節(jié)流輸入JAVA字節(jié)流javac（JAVA編譯器）7/21/202311TJNU-COCIE-WJW按編譯目的不同分類：1.診斷編譯程序?qū)ｉT用于幫助程序開發(fā)和調(diào)試的編譯程序2.優(yōu)化編譯程序著重于提高目標(biāo)代碼運(yùn)行效率的編譯程序二、編譯程序的分類7/21/202312TJNU-COCIE-WJW按編譯目標(biāo)不同分類：目標(biāo)機(jī)：運(yùn)行編譯程序所產(chǎn)生目標(biāo)代碼的計(jì)算機(jī)宿主機(jī)：運(yùn)行編譯程序的計(jì)算機(jī)1.交叉編譯程序產(chǎn)生不同于其宿主機(jī)的機(jī)器代碼2.可變目標(biāo)編譯程序不需重寫編譯程序中與機(jī)器代碼無關(guān)的部分就能改變目標(biāo)機(jī)二、編譯程序的分類（續(xù)）7/21/202313TJNU-COCIE-WJW1.機(jī)器語言計(jì)算機(jī)能夠直接執(zhí)行的機(jī)器指令系統(tǒng)例如某種計(jì)算機(jī)的指令為1011011000000000 加法操作1011010100000000 減法操作2.匯編語言用一些助記符號(hào)來表示機(jī)器指令例如A+BLD R AADD R B三、幾個(gè)概念7/21/202314TJNU-COCIE-WJW3.高級(jí)語言其語法和結(jié)構(gòu)類似于自然語言，容易記憶和書寫例如C語言，Java等4.源語言把被翻譯（或編譯）的語言稱為源語言5.目標(biāo)語言把翻譯（或編譯）之后得到的語言稱為目標(biāo)語言6.源程序用源語言編寫的程序7.目標(biāo)程序用目標(biāo)語言編寫的程序7/21/202315TJNU-COCIE-WJW1.2編譯過程概述過程復(fù)雜，可與自然語言翻譯作類比翻譯自然語言識(shí)別句子中的單詞分析句子的語法結(jié)構(gòu)進(jìn)行初步翻譯對(duì)譯文進(jìn)行修飾寫出最后的譯文編譯程序詞法分析語法分析語義分析與中間代碼生成中間代碼優(yōu)化目標(biāo)代碼成成7/21/202316TJNU-COCIE-WJW任務(wù)：輸入源程序，根據(jù)詞法規(guī)則，對(duì)構(gòu)源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)單詞符號(hào)單詞符號(hào)是程序語言的基本成分例：A=B*C

由5個(gè)單詞構(gòu)成：A，等號(hào)，B，乘號(hào)，C

forI:=1to100do

單詞符號(hào)：for,I,:=,1,to,100,do實(shí)現(xiàn)方法： 構(gòu)造詞法分析程序（掃描器）一、詞法分析階段7/21/202317TJNU-COCIE-WJW任務(wù)： 在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則把識(shí)別出的單詞符號(hào)串，分解成各類語法單位（語法范疇，如表達(dá)式、語句、程序段、過程、函數(shù)、程序等），以確定整個(gè)輸入串是否構(gòu)成語法上正確的“程序”。

例：A=B*CB*C是表達(dá)式，A=B*C是賦值語句實(shí)現(xiàn)方法： 構(gòu)造語法分析程序（語法分析器）二、語法分析階段7/21/202318TJNU-COCIE-WJW任務(wù)： 對(duì)語法分析所識(shí)別出的各類語法范疇，分析其含義，并進(jìn)行初步翻譯（產(chǎn)生中間代碼）靜態(tài)語義檢查：變量是否定義、類型是否正確等進(jìn)行中間代碼翻譯例：C語言中，變量需要在使用前聲明實(shí)現(xiàn)方法： 構(gòu)造語義分析程序三、語義分析和中間代碼生成階段7/21/202319TJNU-COCIE-WJW中間代碼： 是一種含義明確，便于記憶的記號(hào)系統(tǒng)，獨(dú)立于硬件，與機(jī)器指令在形式上有所接近，容易替換成機(jī)器指令。

表示形式：后綴式：表示表達(dá)式，把運(yùn)算量（操作數(shù)）寫在前面，把運(yùn)算符寫在后面（后綴）例：A+B寫成AB+7/21/202320TJNU-COCIE-WJW三元式：算符第一操作對(duì)象第二操作對(duì)象表示二地址指令：四元式： 算符第一操作對(duì)象第二操作對(duì)象結(jié)果表示三地址指令：操作碼第一地址第二地址操作碼第一地址第二地址第三地址7/21/202321TJNU-COCIE-WJW任務(wù)： 對(duì)中間代碼進(jìn)行等價(jià)變換，使生成目標(biāo)代碼更高效。

例：實(shí)現(xiàn)方法： 構(gòu)造代碼優(yōu)化程序優(yōu)化fork:=1to100dobeginM:=i+10*kN:=j+10*kend遞歸加法M:=iN:=jfork:=1to100dobeginM:=M+10N:=N+10end四、代碼優(yōu)化階段7/21/202322TJNU-COCIE-WJW任務(wù)： 把中間代碼變換成特定機(jī)器上的低級(jí)語言代碼。 目標(biāo)代碼：機(jī)器語言代碼、匯編語言代碼

例：A+B LD R A ADD R B實(shí)現(xiàn)方法： 構(gòu)造生成目標(biāo)代碼程序五、目標(biāo)代碼生成階段7/21/202323TJNU-COCIE-WJW1.3編譯程序的結(jié)構(gòu)由上述5個(gè)階段的實(shí)現(xiàn)程序組成7/21/202324TJNU-COCIE-WJW

源程序語義分析和中間代碼生成器語法分析器詞法分析器代碼優(yōu)化器目標(biāo)代碼生成器

目標(biāo)程序表格管理出錯(cuò)處理(字符串)單詞符號(hào)語法單位中間代碼中間代碼一、編譯程序總框架7/21/202325TJNU-COCIE-WJW 編譯程序在工作過程中需要建立一系列表格，以登記源程序中所提供的或在編譯過程中所產(chǎn)生的一些信息，編譯各個(gè)階段的工作都涉及到構(gòu)造、查找、修改或存取有關(guān)表格中的信息。

例

符號(hào)表 用來登記源程序中出現(xiàn)的每個(gè)名字以及名字的屬性（常量名、變量名（什么類型）、過程名）名字信息二、表格管理7/21/202326TJNU-COCIE-WJW 在翻譯各階段把原程序錯(cuò)誤性質(zhì)和地點(diǎn)通知用戶。

語法錯(cuò)誤：源程序中不符合語法（詞法）規(guī)則的錯(cuò)誤

例如：拼寫錯(cuò)誤，括號(hào)不匹配，非法字符等

語義錯(cuò)誤：源程序中不符合語義規(guī)則的錯(cuò)誤

例如：說明錯(cuò)誤，作用域錯(cuò)誤，類型不一致等三、出錯(cuò)處理7/21/202327TJNU-COCIE-WJW編譯五個(gè)過程是邏輯上劃分，具體實(shí)現(xiàn)組織成“遍”

遍（pass）： 對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。例如：詞法分析單獨(dú)一遍

詞法分析和語法分析合為一遍語法分析和語義分析合為一遍 詞法分析、語法分析、語義分析合為一遍（三個(gè)不同階段，語法分析為核心）四、遍7/21/202328TJNU-COCIE-WJW前端： 主要由與源語言有關(guān)但與目標(biāo)語言無關(guān)的那些部分組成

例如：詞法分析、語法分析、中間代碼產(chǎn)生、（代碼優(yōu)化）后端：

由與目標(biāo)機(jī)有關(guān)的那些部分組成，不依賴于源語言而僅僅依賴于中間語言。

例如：（代碼優(yōu)化）、目標(biāo)代碼生成等五、編譯前端和后端7/21/202329TJNU-COCIE-WJW

源程序語義分析和中間代碼生成器語法分析器詞法分析器代碼優(yōu)化器目標(biāo)代碼生成器

目標(biāo)程序(字符串)單詞符號(hào)語法單位中間代碼中間代碼五、編譯前端和后端（續(xù)1）

前端

后端7/21/202330TJNU-COCIE-WJW五、編譯前端和后端（續(xù)2）C語言編譯器前端中間代碼C語言編譯器后端（X86）C語言編譯器后端（ARM）中間代碼X86代碼ARM代碼7/21/202331TJNU-COCIE-WJW1.4編譯程序與程序設(shè)計(jì)環(huán)境程序開發(fā)過程程序設(shè)計(jì)環(huán)境編輯程序編譯程序鏈接程序庫代碼源代碼目標(biāo)代碼可執(zhí)行代碼UEVI等Linkld等Windbggdb等調(diào)試程序Masmas等程序設(shè)計(jì)環(huán)境7/21/202332TJNU-COCIE-WJW1.4編譯程序與程序設(shè)計(jì)環(huán)境（續(xù)）傳統(tǒng)的程序設(shè)計(jì)環(huán)境編輯、編譯、鏈接、調(diào)試各自獨(dú)立集成化的程序設(shè)計(jì)環(huán)境（IDE）TurboCVisualC++PowerBuilderJBuilder等等7/21/202333TJNU-COCIE-WJW1.5編譯程序的生成早期用機(jī)器或匯編語言現(xiàn)在用高級(jí)語言編寫7/21/202334TJNU-COCIE-WJW1.直接編寫機(jī)器語言、匯編語言、高級(jí)語言2.自舉的方法先對(duì)語言的核心部分用機(jī)器語言編寫核心部分：程序語言的三個(gè)支柱：條件、循環(huán)、調(diào)用返回然后以此為基礎(chǔ)，再編寫更多的語言成分3.移植的方法將一個(gè)已有的A機(jī)器上的編譯器移植到B機(jī)器上一、編譯程序的構(gòu)造方法7/21/202335TJNU-COCIE-WJW二、T形圖描述源語言S、目標(biāo)語言T和編譯程序?qū)崿F(xiàn)語言I間的關(guān)系7/21/202336TJNU-COCIE-WJW三、T形圖的組合方式1.將第一個(gè)T形圖的輸出作為第二個(gè)T形圖的輸入已有將語言A編譯為語言B的編譯器和將語言B到語言C的編譯器，用上述方法得到A到C的編譯器7/21/202337TJNU-COCIE-WJW三、T形圖的組合方式（續(xù)）2.編譯器實(shí)現(xiàn)語言的變換例：我們用C語言開發(fā)了一個(gè)將FORTRAN語言程序編譯為JAVA程序的編譯器FOR2J，如果我們已經(jīng)有一個(gè)將C語言編譯為X86代碼的編譯器，利用上述的方式可以得到一個(gè)在X86機(jī)器上執(zhí)行的FOR2J編譯器編譯7/21/202338TJNU-COCIE-WJW四、編譯器的自舉的開發(fā)方式?jīng)]有高級(jí)語言可以用來寫編譯器，怎么辦？用匯編語言開發(fā)一個(gè)完整的編譯器？太繁瑣用自舉的方式：首先用匯編語言M開發(fā)一個(gè)實(shí)現(xiàn)源語言A的一個(gè)子集A’的編譯器，這個(gè)編譯器只要正確即可用這個(gè)子集語言A’開發(fā)語言全集的編譯器上述過程可以重復(fù)多次，直至得到性能良好的、正確的對(duì)語言全集有效的編譯器編譯7/21/202339TJNU-COCIE-WJW五、編譯器的移植的開發(fā)方式以PC機(jī)為工具開發(fā)M芯片的C