編譯原理編譯引論

會(huì)計(jì)學(xué)1編譯原理編譯引論2一什么是編譯程序？計(jì)算機(jī)經(jīng)過幾十年的發(fā)展，在程序設(shè)計(jì)語言方面,已經(jīng)從低級(jí)語言發(fā)展到高級(jí)語言;然而,計(jì)算機(jī)內(nèi)部的本質(zhì)只能識(shí)別0,1代碼序列（機(jī)器語言）,而對(duì)高級(jí)語言甚至符號(hào)語言仍然一竅不通。因此用高級(jí)語言編寫的程序,必須先翻譯為機(jī)器語言，才能被計(jì)算機(jī)理解執(zhí)行。第一個(gè)完成這種翻譯任務(wù)的編譯程序?yàn)镕ORTRAN編譯程序,是上世紀(jì)五十年代設(shè)計(jì)的.第一章引論第一節(jié)、編譯程序概述第1頁/共32頁3定義:設(shè)源語言為L1,目標(biāo)語言為L2,

翻譯程序是一個(gè)程序,它能將L1轉(zhuǎn)換為邏輯上等價(jià)的L2。

若L1為高級(jí)語言，L2為低級(jí)語言或機(jī)器語言，稱這種翻譯程序?yàn)榫幾g程序。若L1為低級(jí)語言，L2為機(jī)器語言，稱這種翻譯程序?yàn)?/p>

匯編程序。解釋程序是指逐條翻譯L1的語句，并立即執(zhí)行翻譯出的目標(biāo)代碼序列。

編譯原理

就是介紹編譯程序的一般規(guī)律及設(shè)計(jì)方法的一門課程。高級(jí)語言程序機(jī)器語言程序翻譯為第2頁/共32頁4二編譯過程概述

編譯程序從接受源程序到輸出目標(biāo)代碼的整個(gè)過程，可邏輯的分為5個(gè)階段，詞法分析語法分析中間代碼生成代碼優(yōu)化目標(biāo)代碼生成

1）詞法分析：把源程序作為字符串進(jìn)行掃描，根據(jù)單詞詞法，識(shí)別出所有單詞，過濾無用符，并檢查是否為合法的單詞。單詞一般分為如下幾種：

基本字，標(biāo)識(shí)符，常數(shù)，算符，界符

第3頁/共32頁5例如：ifn<=1thenf:=1elsef:=n*f(n);

該程序經(jīng)過語法分析,得到如下單詞序列:ifn<=1thenf:=1elsef:=n*f(n);過濾掉回車換行,空格,注釋等第4頁/共32頁62)語法分析:根據(jù)語言的語法規(guī)則,從單詞符號(hào)串中識(shí)別出各種語法單位,進(jìn)行句子分析,并檢查整個(gè)輸入字串是否為合法的程序;重要的語法單位有:

程序,子程序,語句,短語,表達(dá)式等例如:programadd;vara,b:real;beginread(a,b);write(a+b);end.第5頁/共32頁7程序首部說明段執(zhí)行部program程序名及參數(shù)var說明語句add變量名表變量類型a,brealbegin多語句endread(a,b)write(a+b)第6頁/共32頁83)中間代碼生成:根據(jù)語義規(guī)則,把各種語法單位翻譯成中間代碼序列.中間代碼有三種:

四元式,三元式,逆波蘭式.中間代碼的特點(diǎn):結(jié)構(gòu)簡單,語義明確,易于理解及優(yōu)化.四元式可表示為:(操作符,操作數(shù)1,操作數(shù)2,結(jié)果)例如:語句

Z:=(x+0.4)*Y/W;翻譯后得到右面的四元式序列:四元式序列(+,x,0.4,T1)(*,T1,Y,T2)(/,T2,w,T3)(:=,T3,,Z)從示例可看出:每條四元式只進(jìn)行一次最基本的操作.第7頁/共32頁94)代碼優(yōu)化：對(duì)產(chǎn)生的中間代碼序列進(jìn)行加工變換，使變換后的代碼更為高效（時(shí)間，空間上）。優(yōu)化主要有：

循環(huán)優(yōu)化，公共表達(dá)式提取，強(qiáng)度削弱等。5)目標(biāo)代碼生成：把中間代碼程序翻譯為機(jī)器指令或匯編指令程序。這一部分的處理，與計(jì)算機(jī)硬件及操作系統(tǒng)密切相關(guān)。如寄存器數(shù)目，機(jī)器指令功能及指令條數(shù)；操作系統(tǒng)的

BIOS，內(nèi)存管理，文件管理等。三編譯程序的結(jié)構(gòu)

編譯程序可以劃分為如下幾個(gè)基本模塊：第8頁/共32頁10詞法分析器語法分析器中間代碼生成中間代碼優(yōu)化目標(biāo)代碼生成源程序單詞符號(hào)語法單位四元式四元式目標(biāo)程序

表格管理

錯(cuò)誤處理編譯程序總框第9頁/共32頁11表格管理:對(duì)各種表格進(jìn)行管理,包括表格的構(gòu)造、查找、修改、刪除、插入等；編譯程序中，表格的種類較多，最主要的有如下幾種：

符號(hào)表，常量表，標(biāo)號(hào)表，子程序名表，四元式表等。表格由若干結(jié)構(gòu)相同的表格項(xiàng)組成，表格項(xiàng)由二元式表示：項(xiàng)名信息表格項(xiàng)表格項(xiàng)名1信息項(xiàng)名2信息項(xiàng)名n信息第10頁/共32頁12四設(shè)計(jì)編譯程序

編譯程序的設(shè)計(jì)方式可以分為兩類：方式人工設(shè)計(jì)自動(dòng)生成低級(jí)語言高級(jí)語言自動(dòng)生成掃描器自動(dòng)生成分析器自動(dòng)生成編譯程序第11頁/共32頁13第二節(jié)、高級(jí)語言概述一什么是程序設(shè)計(jì)語言程序設(shè)計(jì)語言是一符號(hào)系統(tǒng)，由語法和語義兩方面所定義。語法：是一組規(guī)則，規(guī)定了語言的形式結(jié)構(gòu)，包括單詞結(jié)構(gòu)，句子結(jié)構(gòu)，程序結(jié)構(gòu)等。語法={詞法規(guī)則+句法規(guī)則}

詞法規(guī)則：規(guī)定了形成單詞的規(guī)則；如常數(shù)，標(biāo)識(shí)符，基本字，算符等。

句法規(guī)則：規(guī)定了由單詞構(gòu)造更大語法單位的規(guī)則；

如表達(dá)式，短語，語句，程序等。第12頁/共32頁14語義：也是一組規(guī)則，規(guī)定了各語法單位的確切含義。例如：A=B，可解釋為：A賦值為B；（C語言）

也可以解釋為：A等于B（P語言）

這完全由語義規(guī)則所確定。二數(shù)據(jù)類型

各種語言都提供了一些最基本的數(shù)據(jù)類型,稱為初等數(shù)據(jù)類型，這些數(shù)據(jù)類型的特征是數(shù)據(jù)的單一性；還提供了由初等數(shù)據(jù)類型構(gòu)造復(fù)雜結(jié)構(gòu)類型的手段。1）初等數(shù)據(jù)類型數(shù)值類型：（整數(shù)，實(shí)數(shù)）可進(jìn)行算術(shù)運(yùn)算和比較運(yùn)算；邏輯類型：可進(jìn)行邏輯運(yùn)算；字符類型：可進(jìn)行比較遠(yuǎn)算及字符串操作；指針類型：指向另一變量的地址。第13頁/共32頁152）結(jié)構(gòu)類型-------數(shù)組

數(shù)組是由同一類型數(shù)據(jù)所組成的多維結(jié)構(gòu)，數(shù)組元素是多維空間的一個(gè)點(diǎn)，代表了一個(gè)存儲(chǔ)空間。數(shù)組的存儲(chǔ)，是通過按行或按列方式，把每個(gè)數(shù)組元素存放在一個(gè)連續(xù)的存儲(chǔ)空間中。設(shè)數(shù)組類型為A:array[L1..u1,L2..u2,......Ln..

un]ofelemtype,數(shù)組元素為A[i1,i2,......in],di=ui-Li+1則該元素的地址可按如下公式計(jì)算:

addr=a+{(i1-L1)*d2d3d4...dn

+

(i2-L2)*d3d4...dn

+

(in-1-Ln-1)*dn

+(in-Ln)}*elemlength第14頁/共32頁16addr=a-c+vc={(L1)*d2d3d4...dn

+

(L2)*d3d4...dn+

(Ln-1)*dn

+(Ln)}*elemlength={(...((L1d2+L2)d3+L3)d4+L4)......)dn+Ln}*elemlengthv={(...((i1d2+i2)d3+i3)d4+i4)......)dn+in}*elemlengthC是常量,在編譯時(shí)可以計(jì)算出;V是可變部分,只能在程序運(yùn)行時(shí)才能計(jì)算出。從上可知：計(jì)算數(shù)組元素地址涉及到如下幾個(gè)因素：

acL1..Lnd1..dnelemlengthi1..in

第15頁/共32頁17這些因素中,在編譯時(shí)能確定的部分,用一個(gè)數(shù)組內(nèi)情向量表來記錄,以便計(jì)算數(shù)組元素地址使用。換句話說：當(dāng)編譯程序掃描到數(shù)組說明語句時(shí)，就把數(shù)組的各確定部分登記到內(nèi)情向量表中。內(nèi)情向量表組織如下：L1u1d1L2u2d2Ln

un

dnac

n

elemlength

第16頁/共32頁183）結(jié)構(gòu)類型-------記錄是由多種類型的數(shù)據(jù)組合起來的一種數(shù)據(jù)結(jié)構(gòu)。Pascal語言中，可如下定義一種記錄類型

type<記錄類型名>=record <域名1>:<類型1>; <域名2>:<類型2>;<域名n>:<類型n>;

end;

域名即記錄分量,域的類型可以是簡單數(shù)據(jù)類型,也可以是已經(jīng)定義過的數(shù)據(jù)類型?？刹捎梅至宽樞蚍绞?分配記錄的地址空間。由于每個(gè)域類型及空間大小都可能不同,因此,只能通過表映射方式計(jì)算各個(gè)域在記錄中的地址。第17頁/共32頁19記錄分量表：域名相對(duì)位移域類型name1offset1type1name2offset2type2

namenoffsetntypen因此，namei

在記錄中的地址為：addr=a+offsetia為記錄的第一個(gè)分量的地址；第18頁/共32頁20三表達(dá)式

表達(dá)式是由算符和運(yùn)算量組成,可遞規(guī)定義如下:1>變量,常量,函數(shù)為表達(dá)式E;2>若E1,E2為表達(dá)式,則:

E1opE2,opE,(E)為表達(dá)式。

算符間存在如下優(yōu)先順序：

乘冪（**）負(fù)號(hào)（—）乘除（*/） 加減（+-） 關(guān)系符（<>=<>>=<=)非(not)

與(and)

或(or)等優(yōu)先級(jí)高優(yōu)先級(jí)低第19頁/共32頁21四語句語句可以分為兩類:

說明性語句 執(zhí)行性語句

說明語句用于定義各種數(shù)據(jù)類型,變量,函數(shù)或過程.執(zhí)行語句用于描述數(shù)據(jù)處理的過程和動(dòng)作.1>類型定義段

type<類型名>=setof<基類型>;<類型名>=arrayof<基類型>;<類型名>=

record

end;第20頁/共32頁222>變量說明段var

<變量名表1>:<類型1>; <變量名表2>:<類型2>; <變量名表n>:<類型n>;3>函數(shù)及過程定義

function

<函數(shù)名>(參數(shù)說明):<函數(shù)類型>;<函數(shù)體>;

procedure

<過程名>(參數(shù)說明);<過程體>;4>賦值句

<V>:=<

E>

;

左邊變量取其地址,右邊表達(dá)式取其值.第21頁/共32頁235>分支語句

if<B>then<S>

else<S>;

case<有序表達(dá)式>

of<值1>:<S1>;

<值n>:<Sn

>

else

:<Sn+1>

end;

goto

<標(biāo)號(hào)>;第22頁/共32頁246>循環(huán)控制語句

while<B>do<S>;

for<V>:=<E1>to<E2>do<S>;

repeat<S1>;<S2>;......<Sn>

until<B>7>

子程序調(diào)用函數(shù)調(diào)用一般出現(xiàn)在表達(dá)式中,形式如下:

<函數(shù)名>(實(shí)際參數(shù))過程調(diào)用一般作為語句,形式如下:

<過程名>(實(shí)際參數(shù));第23頁/共32頁258>輸入輸出語句

read(<變量名表>);

write(<輸出元表>);9>簡單句和復(fù)合句

簡單句是指不包含其它語句的基本語句,復(fù)合句是指句中有句.例如:V:=E,gotoL,read(a,b)等都是簡單句;

ifBthenSelseS,whileBdoS等都是復(fù)合句.第24頁/共32頁26五子程序參數(shù)傳遞當(dāng)調(diào)用一個(gè)子程序時(shí),首先應(yīng)將所需的數(shù)據(jù)傳遞給子程序,傳遞方式主要有三種:

傳值,傳地址,傳名設(shè)有如下函數(shù):

functiondistence(x1,y1,x2,y2):real;begindistence:=sqrt((x2-x1)**2+(y2-y1)**2)end;x1,y1,x2,y2稱為形式參數(shù)設(shè)主程序調(diào)用如下:

d=distence(a1,b1,a2,b2);a1,b1,a2,b2稱為實(shí)際參數(shù).第25頁/共32頁271>傳值

調(diào)用程序把實(shí)際參數(shù)的值傳遞到形式參數(shù)的空間中.1145x1y1x2y21145a1b1a2b2主程序空間子程序空間這種方式,子程序一般不改變實(shí)際參數(shù)的值.第26頁/共32頁282>傳地址

調(diào)用程序把實(shí)際參數(shù)的地址傳遞到形式參數(shù)的空間中.

addr(a1)

addr(b1)

addr(a2)

addr(b2)x1y1x2y21145a1b1a2