編譯原理編譯引論

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

翻譯程序是一個程序,它能將L1轉換為邏輯上等價的L2。

若L1為高級語言，L2為低級語言或機器語言，稱這種翻譯程序為編譯程序。若L1為低級語言，L2為機器語言，稱這種翻譯程序為

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

編譯原理

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

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

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

基本字，標識符，常數(shù)，算符，界符

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

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

程序,子程序,語句,短語,表達式等例如: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ī)則,把各種語法單位翻譯成中間代碼序列.中間代碼有三種:

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

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

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

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

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

表格管理

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

符號表，常量表，標號表，子程序名表，四元式表等。表格由若干結構相同的表格項組成，表格項由二元式表示：項名信息表格項表格項名1信息項名2信息項名n信息第10頁/共32頁12四設計編譯程序

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

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

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

如表達式，短語，語句，程序等。第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ù)類型構造復雜結構類型的手段。1）初等數(shù)據(jù)類型數(shù)值類型：（整數(shù)，實數(shù)）可進行算術運算和比較運算；邏輯類型：可進行邏輯運算；字符類型：可進行比較遠算及字符串操作；指針類型：指向另一變量的地址。第13頁/共32頁152）結構類型-------數(shù)組

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

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

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是常量,在編譯時可以計算出;V是可變部分,只能在程序運行時才能計算出。從上可知：計算數(shù)組元素地址涉及到如下幾個因素：

acL1..Lnd1..dnelemlengthi1..in

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

un

dnac

n

elemlength

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

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

end;

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

namenoffsetntypen因此，namei

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

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

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

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

乘冪（**）負號（—）乘除（*/） 加減（+-） 關系符（<>=<>>=<=)非(not)

與(and)

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

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

說明語句用于定義各種數(shù)據(jù)類型,變量,函數(shù)或過程.執(zhí)行語句用于描述數(shù)據(jù)處理的過程和動作.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>

;

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

if<B>then<S>

else<S>;

case<有序表達式>

of<值1>:<S1>;

<值n>:<Sn

>

else

:<Sn+1>

end;

goto

<標號>;第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)在表達式中,形式如下:

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

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

read(<變量名表>);

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

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

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

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

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

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

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

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

addr(a1)

addr(b1)

addr(a2)

addr(b2)x1y1x2y21145a1b1a2