程序設(shè)計(jì)語言與編譯課件

編譯概述一.不同語言之間的翻譯1.翻譯程式:等價地變換2.編譯程序:高級語言

低級語言

3.組合語言程式:組合語言

機(jī)器語言二.編譯執(zhí)行和解釋執(zhí)行1.編譯執(zhí)行根源程式目標(biāo)程式計(jì)算結(jié)果組合語言程式目標(biāo)程式

2.解釋執(zhí)行:一邊翻譯一邊解釋執(zhí)行編譯編譯運(yùn)行組合語言程式初始數(shù)據(jù)三.編譯程序的組成1.詞法分析:輸入字串，根據(jù)詞法規(guī)則識別出單詞符號。2.語法分析:根據(jù)語法規(guī)則，將單詞符號構(gòu)成各類語法單位，並進(jìn)行語法檢查。3.語義分析與代碼生成:

根據(jù)語義規(guī)則,進(jìn)行初步編譯。4.優(yōu)化:對中間代碼進(jìn)行等價變換,以使代碼更有效。5.目標(biāo)代碼生成:生成機(jī)器語言程式或組合語言程式。6.符號表管理:完成符號表的建立,查找,更新。7.出錯處理根源程式字串詞法分析器語法分析器語義分析、中間代碼生成器代碼優(yōu)化器目標(biāo)代碼生成器單詞流語法單位中間代碼序列中間代碼序列目標(biāo)程式符號表管理程序出錯處理程序編譯程序的結(jié)構(gòu)第四章習(xí)題4-2、4-3(a)(b)、4-44-5(a)(c)、4-6(b)、4-9……NFA4-10(a)(b)(c)babaab均是必做題，第九周週五課後交作業(yè)第五章詞法分析與語法分析第一節(jié)詞法分析一.詞法分析的功能1.功能掃描根源程式的字串,按照詞法規(guī)則,識別出單詞符號作為輸出;對識別過程中發(fā)現(xiàn)的詞法錯誤,則輸出有關(guān)的錯誤資訊。2.詞法分析器和語法分析器的關(guān)係（1）詞法分析作為單獨(dú)的一遍輸出串詞法分析器語法分析器單詞流（2）詞法分析作為副程式輸入串詞法分析器語法分析器符號表取下一單詞返回下一單詞二.單詞的種類

(1)識別字:用來命名程式中出現(xiàn)的變數(shù)、數(shù)組、函數(shù)、過程、標(biāo)號等

(2)基本字:也可稱關(guān)鍵字或保留字,如if、while、for、do、goto等

(3)常數(shù):各種類型的常數(shù),如216、3.14159、TRUE等

(4)運(yùn)算符:如+、-、*、/等

(5)界符:如;、:、/*、*/等三.單詞的編碼1.單詞的輸出形式——二元式

(單詞類別,單詞的屬性)區(qū)分單詞所屬的類(整數(shù)編碼)單詞的值2.單詞類別的劃分基本字、運(yùn)算符、界符:一字一碼識別字:單列一種常數(shù):按類型分類四.詞法錯誤檢查非法字元不合規(guī)則的常數(shù)識別字首碼為保留字五.詞法分析器的生成1.詞法分析技術(shù)——超前搜索為了判定一個單詞符號的類別,必須掃描到某一地方,而該單詞符號並沒有這麼長,這種掃描方式叫做“超前搜索”。如：DO100I=1,10DO100I=1.10IF(5.EQ.M)GOTO100IF(5)=1002.狀態(tài)轉(zhuǎn)換圖有限的有向圖有限邊上標(biāo)記字元一個初態(tài)若干終態(tài)例:某語言允許識別字、基本字、數(shù)字串、

+、-、*、**、<、<=、<>、

=、>、>=、:=、：、；0412356789開始空白字母/數(shù)字字母非字母數(shù)字?jǐn)?shù)字非數(shù)字+-**非****數(shù)字101112<>=1314151617>其他=181920：其他=其他2122=；其他****3.實(shí)現(xiàn)方法每個狀態(tài)結(jié)對應(yīng)一小段程式分支狀態(tài)——if或case語句迴圈狀態(tài)——while語句終態(tài)——return語句

4.一個示意演算法start:token:=‘‘;getchar;getnb;casecharacterof‘a(chǎn)’…’z’:beginwhileletterordigitdobeginconcatenate;getcharend;retract;c:=reserve;ifc=0thenbeginbuildlist;return(id,id在符號表中的位置)endelsereturn(保留字碼,—)end;‘0’…’9’:beginwhiledigitdobeginconcatenate;getcharend;retract;return(num,num在常數(shù)表中的位置)end;‘+’:return(plus-op,—);‘-’:return(minus-op,—);‘*’:begingetchar;ifcharacter=‘*’thenreturn(power-op,—);retract;return(mul-op,—);end;‘<‘:begingetchar;ifcharacter=‘=‘thenreturn(rel-op,LE)elseifcharacter=‘>’thenreturn(rel-op,NE);retract;return(rel-op,LT)end;‘=‘:return(rel-op,EQ);‘>‘:begingetchar;ifcharacter=‘=‘thenreturn(rel-op,GE);retract;return(rel-op,GT)end;‘:‘:begingetchar;ifcharacter=‘=‘thenreturn(assign-op,—);retract;return(colon,—)end;‘;‘:return(semicolon,—)endofcase;error全局量及過程:(1)token(2)character(3)getchar(4)getnb(5)concatenate(6)letter和digit(7)reserve(8)retract:退一字元;character置空(9)buildlist:為識別字登記符號表第二節(jié)自頂向下語法分析語法分析:自上而下(自頂而下)

自下而上(自底而上)自頂向下語法分析法:或從開始符號出發(fā),找最左推導(dǎo);或從根開始,構(gòu)造推導(dǎo)樹。一.回溯分析法

1.一個實(shí)例

S→xAyA→ab│a輸入串為xay,說明分析過程SxAySxAyabSxAya2.存在的問題(1)回溯——公共左因數(shù)的存在

A→

1|

2(2)左遞歸

A→Aα或A

Aα*二.無回溯的遞歸下降分析法

1.提取公共左因數(shù)

A→

1|

2|...|

n|δ改寫為:A→αB|δB→

1|

2|...|

n|2.左遞歸的消除(1)直接左遞歸的消除

P→Pα│β改寫為:P→P＇

P＇→αP＇│εA→A

1|A

2|…|Am|1|2|…|n

（

i

ε，

j不以A開頭）改寫為:P→

1P’│

2P’│...│

nP’P’→

1P’│

2P’│...│

mP’│ε(2)間接左遞歸的消除

P

Pα(a)將文法G的所有非終結(jié)符按任一給定的順序排列,設(shè)為A1,A2,…An;+(b)消除可能的左遞歸;fori:=1tondoforj:=1toi-1dobegin

把一個形如Ai

Aj

的產(chǎn)生式改寫為

Ai

1|2|…|k

其中Aj

1|2|…|k是Aj的所有產(chǎn)生式;

消除Ai產(chǎn)生式的直接左遞歸

end(c)化簡以S→Qc│cQ→Rb│bR→Sa│a為例,按S,Q,R排列,或R,Q,S排列

1.程式單元:程式執(zhí)行過程中的獨(dú)立調(diào)用單元。如副程式,分程式,過程等。2.單元表示編譯時，一個單元的根源程式。運(yùn)行時，單元表示由一個代碼段和一個活動記錄組成，稱為單元實(shí)例。3.活動記錄:執(zhí)行單元所需要的資訊,以及該單元的局部變數(shù)所綁定的數(shù)據(jù)對象的存儲區(qū)。

程式單元ip代碼記憶體（C）數(shù)據(jù)記憶體（D）4.非局部變數(shù):一個程式單元可以引用未被本單元說明而被其他單元說明的變數(shù)。5.引用環(huán)境:局部變數(shù)+非局部變數(shù)。6.別名:同一單元的引用環(huán)境中有兩個變數(shù)綁定於同一數(shù)據(jù)對象，稱這些變數(shù)具有別名。7.副作用的產(chǎn)生:對綁定於一個非局部變數(shù)的對象進(jìn)行修改。8.程式單元可以遞歸啟動,從而一個單元可以有很多個實(shí)例,但代碼段相同。不同的僅僅是活動記錄。9.靜態(tài)分配和動態(tài)分配

FortranPascal或C

隨著電腦技術(shù)的發(fā)展,電腦應(yīng)用也日益廣泛,已經(jīng)滲透到社會的各個領(lǐng)域,對程式設(shè)計(jì)語言也提出了新的要求(諸如可維護(hù)性,可靠性,可移植性等)，從而促進(jìn)了語言的發(fā)展。第五節(jié)程式設(shè)計(jì)語言發(fā)展簡介一.早期的高級語言（50年代）

—追求效率1.FORTRANFORmulaTRANslation.主要用於科學(xué)計(jì)算.副程式獨(dú)立編譯.COMMON語句實(shí)現(xiàn)了模組之間的通信2.ALGOL60ALGOrithmicLanguage60.主要用於科學(xué)計(jì)算

.引入了分程式結(jié)構(gòu)和遞歸過程

.採用BNF形式描述語法3.COBOL

COmmonBusinessOrientedLanguage.廣泛應(yīng)用於各種事務(wù)處理領(lǐng)域.引入了檔和數(shù)據(jù)描述.類自然語言程式描述二.早期的突破

60年代初，不再盲目地追求效率,出現(xiàn)了基於良好刻畫數(shù)學(xué)原則的語言。1.LISP.具有很強(qiáng)的符號處理能力.統(tǒng)一的數(shù)據(jù)結(jié)構(gòu).數(shù)據(jù)和程式統(tǒng)一的表示方法.其基礎(chǔ)是函數(shù)和函數(shù)作用2.APL.支持函數(shù)式程式設(shè)計(jì)風(fēng)格.廣泛應(yīng)用於涉及大量矩陣運(yùn)算的科學(xué)計(jì)算中.具有豐富的操作符3.SNOBOL4.主要用於字串處理

.給出了一種與機(jī)器無關(guān)的宏功能,增加了程式的可移植性三.概念的集成（64年）

PL/1.希望將所有語言概念集成大全

.分程式概念和遞歸過程

.數(shù)據(jù)描述機(jī)能

.動態(tài)數(shù)據(jù)結(jié)構(gòu)

.異常處理

.多任務(wù)機(jī)能

.可用於科學(xué)數(shù)值計(jì)算,數(shù)據(jù)處理和開發(fā)系統(tǒng)軟體

.難以得到廣泛的應(yīng)用四.再一次突破(60年代後期)

引入了許多有趣的概念1.ALGOL68.以零型文法描述

.引入正交性和通用性原則2.SIMULA67.應(yīng)用於模擬領(lǐng)域

.增加了一個特殊結(jié)構(gòu)——協(xié)同程式

.引入了類的概念3.PASCAL.具有明顯的簡潔性

.體現(xiàn)結(jié)構(gòu)程式設(shè)計(jì)思想

.具有用戶自定義類型4.BASIC.簡單易學(xué)

.互動式工作環(huán)境

.解釋執(zhí)行五.大量的探索

70年代,支持系統(tǒng)軟體開發(fā)

1.語言研究涉及抽象數(shù)據(jù)類型,異常處理和並行處理機(jī)制

2.MODULA-2.支持模組結(jié)構(gòu),模組可以獨(dú)立編譯

.面向即時系統(tǒng)和並行系統(tǒng)綜合功能3.CCPL→BCPL→B→C.C的最大特點(diǎn)是具有高級語言和低級語言的優(yōu)點(diǎn)

.應(yīng)用於各種領(lǐng)域六.Ada和第四代語言

70年代以後,注重可移植性

1.Ada.面向?qū)ｉT領(lǐng)域的特殊要求

.是在引入了一個不大的,容易理解的概念集合的基礎(chǔ)上開發(fā)的

.是直接體現(xiàn)許多現(xiàn)代軟體設(shè)計(jì)方法學(xué)的語言

.提高程式的可讀性,可靠性,可維護(hù)性2.第四代語言——超高級語言面向問題

.表達(dá)力更強(qiáng),使用更方便,更接近於問題的描述

.著重關(guān)心的是”做什麼”七.新一代程式設(shè)計(jì)語言以拋棄馮.諾依曼概念為基礎(chǔ),包括函數(shù)式,對象式,邏輯式第一章習(xí)題1.必做題:1-2、1-6、1-112.思考題:1-3、1-5、1-10、1-12、1-14通知1.本週五的課暫停一次2.答疑時間改為:

第六周起,雙週四下午3:00起在806第二章數(shù)據(jù)類型

數(shù)據(jù)類型實(shí)質(zhì)上是對記憶體中所存儲的數(shù)據(jù)進(jìn)行的抽象。它包含了一組值的集合和一組操作。第一節(jié)引言1.數(shù)據(jù)類型的作用實(shí)現(xiàn)了數(shù)據(jù)抽象使程式員從機(jī)器的具體特徵中解脫出來提高了編程效率2.數(shù)據(jù)類型的分類內(nèi)部類型自定義類型第二節(jié)內(nèi)部類型一.內(nèi)部類型的特點(diǎn)

.反映基本硬體特性如：定點(diǎn)加

.在語言級,標(biāo)識共用某些操作的數(shù)據(jù)對象的抽象表示如：整型共用+、-、*、/二.內(nèi)部類型的優(yōu)越性1.基本表示的不可見性基本位串對程式員是不可見的。

25+9=34

基本表示00011001+00001001

結(jié)果00100010

從而具有優(yōu)點(diǎn)：不同的程式設(shè)計(jì)風(fēng)格，可寫性，可讀性，可修改性。

2.編譯時能檢查變數(shù)使用的正確性進(jìn)行靜態(tài)類型檢查,如非法運(yùn)算,形實(shí)參類型匹配3.編譯時可以確定無二義的操作超載(多態(tài))的概念:運(yùn)算符的意義依賴於運(yùn)算元的類型。如”+”可以表示整數(shù)加或?qū)崝?shù)加編譯時,可拒絕混合運(yùn)算,或提供類型轉(zhuǎn)換指令合理地使用超載,可以提高語言的可讀性和可用性4.精度控制

可以通過數(shù)據(jù)類型顯式定義數(shù)據(jù)的精度第三節(jié)用戶定義類型

許多語言允許程式員規(guī)定基本數(shù)據(jù)對象的聚合,乃至聚合的聚合1.笛卡爾積

N個集合A1,A2,…,An的笛卡爾積表示為A1

A2

…

An，它是一個集合,其元素為(a1,a2,…,an),ai

Ai

任意正多邊形可表示為

integer*real2.有限映像①定義：從定義域類型DT的值的有限集合，到值域類型RT的值的有限集合的函數(shù)稱為有限映像。

vara:array[1..50]ofchar;表示：整數(shù)1至50到字元集的有限映像②值域?qū)ο笸ㄟ^下標(biāo)選取。③下標(biāo)越界會出錯，動態(tài)檢查

④下標(biāo)可用來選取值域的多個元素

⑤SNOBOL4的ARRAY構(gòu)造符並不要求值域集的所有元素是同一類型的⑥D(zhuǎn)T到相應(yīng)值的特定子集的綁定策略：

.編譯時綁定(靜態(tài)數(shù)組).對象建立時綁定(執(zhí)行到分程式時,

動態(tài)數(shù)組).對象處理時綁定(對APL，子集範(fàn)圍可變)3.序列①序列由任意多個數(shù)據(jù)項(xiàng)組成,這些資料項(xiàng)目稱為該序列的成分,且類型相同②串是序列③順序檔的思想也是來自序列的概念,只能順序讀寫4.遞歸若數(shù)據(jù)類型T包含屬於同一類型T的成分，那麼類型T稱為遞歸類型。①允許在類型定義中使用被定義類型的名字②指針是建立遞歸數(shù)據(jù)對象的重要手段5.判定或判定或是一個選擇對象結(jié)構(gòu)的構(gòu)造機(jī)制,規(guī)定在兩個不同選擇對象之間作出適當(dāng)?shù)倪x擇。每一選擇對象結(jié)構(gòu)稱為變體。例如：PASCAL的變體記錄;C的聯(lián)合。6.冪集類型T的元素所有子集的集合，稱為冪集,記為Powerset(T),T稱為基類型。應(yīng)用:每次的操作對象僅僅是某個集合的子集。7.小結(jié)通過PASCAL的類型定義和變數(shù)說明，給出用戶定義類型顯式命名的優(yōu)點(diǎn):①可讀性（選擇名字）②可修改性（不修改變數(shù)說明）③可分性（重複使用）④一致性檢查（參考第8節(jié)）匿名類型vara:recordx:integer;y:array[1..10]ofcharend;顯式命名typecomplex=recordradius:real;angle:realend;varc1,c2,c3:complex;第三節(jié)PASCAL類型結(jié)構(gòu)一.非結(jié)構(gòu)類型1.內(nèi)部類型

integer,real,boolean,char2.有序類型每一元素都有唯一的前驅(qū)和後繼如:整型,布爾型,字元型3.定義新的有序類型的方法枚舉型其值不能直接讀/寫子界型動態(tài)檢查範(fàn)圍例：typeday=(sunday,monday,tuseday,wednesday,thursday,friday,saturday);work_day=monday..friday;varclass_day:work_day;class_day:=succ(class_day);二.聚合構(gòu)造1.數(shù)組構(gòu)造構(gòu)造符ARRAY允許程式員定義有限映象

array[t1]of[t2]PASCAL把下標(biāo)類型不同的數(shù)組看成不同的類型

typea1=array[1..50]ofinteger;a2=array[1..70]ofinteger;“符合數(shù)組”的概念（見下頁）維數(shù)相同,成分類型相同PASCAL可定義多維數(shù)組typerow=array[-5..10]ofinteger;varmy_matrax:array[3..30]ofrow;或varmy_matrix:array[3..30,-5..10]ofinteger;proceduresort(vara:array[low..high:integer]ofctype);vari:integer;more:boolean;begin{sort}more:=true;whilemoredobeginmore:=false;fori:=lowtohigh-1dobeginifa[i]>a[i+1]thenbeginmove_right(i);more:=trueendendendend{sort};2.記錄構(gòu)造

①構(gòu)造符RECORD用以定義笛卡爾積

②記錄可以整體訪問，也可用圓點(diǎn)“.”

作為選擇符訪問單個的域

③PASCAL的變體記錄

④使用變體記錄不安全3.集合構(gòu)造SET構(gòu)造符是冪集構(gòu)造受限制的形式基本型只能是有序類型4.檔構(gòu)造PASCAL檔是任意類型的諸元素的序列PASCAL檔僅能順序處理PUT和GET操作三.指針指針可引用匿名數(shù)據(jù)對象

NEW,堆空指針的使用指針的操作:賦值,比較PASCAL指針只能指向匿名數(shù)據(jù)對象四.小結(jié).(P37圖2-4)

程式設(shè)計(jì)語言和編譯程序第一節(jié)上下文無關(guān)文法一.文法文法是描述語言的語法結(jié)構(gòu)的形式規(guī)則,必須準(zhǔn)確,易於理解,且描述能力強(qiáng)1.文法的形式定義

G=(VT,VN,S,P)例G0=(VT,VN,S,P):E→E+T|TT→T*F|FF→(E)|i顯然VT={+,*,(,),i}VN={E,T,F}S=EP為上述產(chǎn)生式的集合說明:①

→

的讀法,

其中

V*VNV*,

V*②

→

1

→

2...

→

n縮寫為

→

1|

2|…|

n2.文法的分類

①0型文法:產(chǎn)生式形如

→

②1型文法:│α│<=│β│或產(chǎn)生式形如αAβ→α

β(上下文有關(guān)文法)③2型文法:產(chǎn)生式形如A→α(上下文無關(guān)文法)④3型文法:產(chǎn)生式形如A→α或A→αB(正則文法,右線性文法)3.簡化的上下文無關(guān)文法①不含形如A→A的有害規(guī)則②不含多餘規(guī)則即A

VN,必有S

αAβ*二.文法產(chǎn)生的語言1.推導(dǎo)與歸約

①直接推導(dǎo):αβ

α

即由產(chǎn)生式右邊替換產(chǎn)生式左邊

②推導(dǎo):α1

αn、α1

αn③歸約:推導(dǎo)的逆過程*+舉例:已知G(E)E→E+E│E*E│(E)│ii+i*i的推導(dǎo)過程EE+EE+E*EE+E*iE+i*ii+i*iEE+Ei+Ei+E*Ei+i*Ei+i*iEE*EE*iE+E*iE+i*ii+i*i2.句型和句子設(shè)文法G=(VT,VN,S,P),若S

α,αV*,則稱α為文法G的一個句型。若上述αVT，則稱α是一個句子，即只含終結(jié)符的句型是一個句子。**

3.文法產(chǎn)生的語言

文法G=(VT,VN,S,P)的句子的全體,稱為由文法G產(chǎn)生的語言,記為L(G),即

L(G)={α│S

α

αVT*}+G2(I):I→L│LSS→T│STT→L│DL→a│b│...│zD→0│1│2│...│9G3(S):S→aS│aPP→bP│bQQ→cQ│cL(G3)={aibjck│i,j,k

1}G4(S):S→aSPQ│abQQP→PQbP→bbbQ→bccQ→ccL(G4)={aibici│i

1}Sai-1S(PQ)i-1(i-1次使用第一個產(chǎn)生式)aibQ(PQ)i-1

(使用第二個產(chǎn)生式)aib(PQ)i-1Q(i-1次使用第三個產(chǎn)生式)aib2(QP)i-2Q2

(使用第四個產(chǎn)生式)aib3(QP)i-3Q3

(i-2次使用第三個產(chǎn)生式)……aibiQi

aibicQi-1

(使用第五個產(chǎn)生式)aibici

(i-1次使用第三個產(chǎn)生式)*********①文法的重要特性:用有限規(guī)則描述無窮語言②文法的等價:兩個文法G和G’,如果有L(G)=L(G’),則稱G和G’等價4．短語和句柄①短語:設(shè)αβ

是上下文無關(guān)文法G的一個句型,如果有S

αA,並且Aβ,則稱β是句型αβ

關(guān)於非終結(jié)符A的一個短語,或稱β是句型αβ

的一個短語。②直接短語（簡單短語）：Aβ③句柄：一個句型的最左直接短語。*+例:G0(E)E→E+T|TT→T*F|FF→(E)|i求E+T*F的短語、直接短語、句柄④素短語：含有終結(jié)符的短語，並且它的真子串不具有這種特性⑤最右推導(dǎo)（規(guī)範(fàn)推導(dǎo)）⑥最左推導(dǎo)

5．推導(dǎo)樹

——以圖的方式表示推導(dǎo)過程

①推導(dǎo)樹是一棵有序的標(biāo)記樹每個結(jié)點(diǎn)的標(biāo)記是文法G的非終結(jié)符或終結(jié)符；標(biāo)記為A的內(nèi)部結(jié)點(diǎn)從左到右有子結(jié)點(diǎn)X1，X2，…,Xn,則A→X1…Xn是一個產(chǎn)生式;如果有結(jié)點(diǎn)標(biāo)記為

，則它必是葉結(jié)點(diǎn)，且它是該父結(jié)點(diǎn)的唯一子結(jié)點(diǎn)。②推導(dǎo)樹的構(gòu)造例（i+i*i）E（E）EE*EE+iiiE（E）EE+EEiii*③推導(dǎo)樹的邊緣：一棵推導(dǎo)樹所有葉結(jié)點(diǎn)的從左到右的連接。④文法的二義性：一個句子有兩棵不同的推導(dǎo)樹。⑤由推導(dǎo)樹確定短語等(見下頁)E（E）EE*EE+iiiE（E）EE+EEiii*例（i+i*i）第二節(jié)自動機(jī)

文法是語言的生成系統(tǒng)，而自動機(jī)是語言的識別系統(tǒng)。自動機(jī)分為:圖靈機(jī)、線性有界自動機(jī)、下推自動機(jī)、有限自動機(jī)一.有限自動機(jī)的定義1.確定的有限自動機(jī)

DFAMd=(

,S,s0,F,

)

:S

→S例:

={0,1}s0是初態(tài)

S={s0,s1,s2,s3}F={s0}

(s0,0)=s2

(s0,1)=s1

(s1,0)=s3

(s1,1)=s0

(s2,0)=s0

(s2,1)=s3

(s3,0)=s1

(s3,1)=s22.非確定的有限自動機(jī)

NFAMn=(

,S,s0,F,

)

:S

→2S例:

={0,1}s0是初態(tài)

S={s0,s1,s2,s3,s4}F={s2,s4}

(s0,0)={s0,s3}

(s0,1)={s0,s1}

(s1,0)=

(s1,1)={s2}

(s2,0)={s2}

(s2,1)={s2}

(s3,0)={s4}

(s3,1)=

(s4,0)={s4}

(s4,1)={s4}

抽象數(shù)據(jù)類型1.用戶定義類型與內(nèi)部類型的異同①都建立某種基本表示的抽象如:integer是位串的抽象;reg_polygon是記錄的抽象②每一類型都關(guān)聯(lián)一組操作③內(nèi)部類型隱蔽了基本表示，不能對它的成分進(jìn)行操作;用戶定義類型具有更高級別的抽象，可以對其基本表示的成分進(jìn)行操作。2.抽象數(shù)據(jù)類型的定義滿足下述特性的用戶定義類型稱為抽象數(shù)據(jù)類型:①在實(shí)現(xiàn)該類型的程式單元中,建立與表示有關(guān)的基本操作;②對使用該類型的程式單元來說,該類型的表示是隱蔽的。一.SIMULA67的類機(jī)制

1.類的說明

<類頭>;<類體><類頭>包括類名和形式參數(shù)<類體>是傳統(tǒng)的分程式,可包含變數(shù)、過程和類的局部說明，以及一些執(zhí)行語句例：複數(shù)表示(幅角,半徑)classcomplex（x，y）；realx，y；beginrealangle，radius；

radius：=sqrt（x**2+y**2）；

ifabs（x）<epsilon

thenbeginifabs(y)<epsilon

thenerror

elsebeginify>epsilon

thenangle:=pi/2

elseangle:=3*pi/2

end

end

elseangle:=arctan(y/x)endcomplex2.類的有關(guān)性質(zhì)①類說明定義了一類數(shù)據(jù)對象的原型或樣板②類的每個實(shí)例是一個可操作的數(shù)據(jù)對象③類的實(shí)例可多次動態(tài)建立,且僅能通過指針引用例:ref(complex)c;c:-newcomplex(1.0,1.0);c0.781.421.01.0angleradiusxy④類實(shí)例的屬性是指類體的局部變數(shù)和類頭中的參數(shù)my_angle:=c.angle;my_radius:=c.radius;my_x:=c.x;my_y:=c.y;⑤類支持抽象數(shù)據(jù)類型的封裝機(jī)制,它可以封裝實(shí)現(xiàn)對數(shù)據(jù)操作的各種過程例:可將複數(shù)加和乘的過程add和multiply封裝入類complex的類體說明中,作為complex的屬性。procedureadd(operand);ref(complex)operandproceduremultiply(operand);ref(complex)operand變數(shù)c1、c2引用的兩個複數(shù)相加可表示為：c1.add(c2)或c3.angle:=c1.angle;c3.radius:=c1.radius+c2.radius;用戶可以直接訪問複數(shù)的內(nèi)部表示,故add和multiply不是複數(shù)對象的唯一操作3.子類用以定義類型的判定或和類屬。要求：定義一個棧，完成引用棧頂元素入棧出棧判棧是否空(這些操作與棧中元素的類型無關(guān))棧內(nèi)成員的元素類classstack_member;beginref(stack_member)next_member;next_member:-noneend指針型局部變數(shù)classstack;beginref(stack_member)first;ref(stack_member)proceduretop;top:-first;procedurepop;if?emptythenfirst:-first.next_member;procedurepush(e);ref(stack_member)e;beginiffirst=/=nonethene.next_member:-first;first:-eendpush;booleanprocedureempty;empty:=first==none;first:-noneendstackstack_memberclasscomplex(……);……endcomplex定義了一個複數(shù)棧其中complex稱為stack_member的子類加在類說明之前①子類complex具有自己的屬性,同時繼承了stack_member的屬性

newcomplex產(chǎn)生的對象具有stack_member和complex的所有屬性ref(stack)s;s:-newstack;s.push(c1);s.push(c2);s.push(c3);建立一個複數(shù)棧②具有ref(stack_member)的變數(shù)可引用多種類型的量,但不同類型的元素不得壓入同一棧實(shí)例中下述語句說明向量也可是棧中元素:stack_memberclassvector(…);……endvector二.CLU的抽象數(shù)據(jù)類型例:定義複數(shù)完成:建立、加、判等complex=clusteriscreate,add,equal

rep=record[x,y:real]create=proc(a,b:real)returns(cvt)

return(rep${x:a,y:b})

endcreateadd=proc(a,b:cvt)returns(cvt)

return(rep${x:a.x+b.x,y:a.y+b.y})

endaddequal=proc(a,b:cvt)returns(bool)

return(a.x=b.xanda.y=b.y)

endequalendcomplex1.簇（Cluster）是CLU用來定義抽象數(shù)據(jù)類型的機(jī)制

①簇內(nèi),需要內(nèi)部表示

②簇外,看到的是抽象表示

rep說明數(shù)據(jù)對象的具體表示

cvt用於抽象表示和具體表示之間的相互轉(zhuǎn)換,僅能在簇內(nèi)使用

return(rep$…)的含義為返回一個具體表示類型的對象2.CLU的性質(zhì)

①CLU變數(shù)的作用域和生存期互不相干P:complex僅僅是一個說明而P:=complex$create(h,k)才產(chǎn)生一個對象賦於P②CLU變數(shù)被一致看成是對數(shù)據(jù)對象的引用如x:=e

其中x類似於指針變數(shù)

③CLU的參數(shù)傳遞由賦值定義

complex$add(x,y)

把x和y分別賦予形式參數(shù)a和b三.Ada的抽象數(shù)據(jù)類型

1.Ada用程式包描述抽象數(shù)據(jù)類型程式包包括規(guī)格說明和程式包體

2.“移出”的概念這是程式包向外部世界提供的可以訪問的實(shí)體，是程式包的可見部分3.私有類型

①私有類型的表示細(xì)節(jié)在程式包外是不可見的

②允許的操作:移出的副程式、函數(shù)；賦值、相等、不等packageCOMPLEX-NUMBERSistypeCOMPLEXisprivate；

procedureINITIALIZE（A,B:inREAL;X:outCOMPLEX);functionADD(A,B:inCOMPLEX)returnCOMPLEX;privatetypeCOMPLEXisrecordR,I:REAL;endrecord;endCOMPLEX-NUMBERS;packagebodyCOMPLEX-NUMBERisprocedureINITIALIZE(A,B:inREAL;X:outCOMPLEX)isbeginX.R:=A;X.I:=B;endINITIALIZE;functionADD(A,B:inCOMPLEX)returnCOMPLEXisTEMP:COMPLEX;beginTEMP.R:=A.R+B.R;TEMP.I:=A.I+B.I;returnTEMP;endADD;endCOMPLEX-NUMBER;

4.受限私有類型只允許程式包移出的副程式和函數(shù),不允許賦值、相等和不相等

5.類屬的描述使用generic子句說明類型是一個參數(shù)，實(shí)例化時代以具體的類型例:packageINTEGERisnewSET-MANIPULATION（INTEGER）；

packageFLAVORSisnewSET-MANIPULATION（FLAVOR）；generictypeCOMPONENTisprivate;packageSET-MANIPULATIONistypeSETislimitedprivate;procedureINSERT(S:outSET;ELEM:inCOMPONENT);procedureDELETE(S:outSET;ELEM:inCOMPONENT);

procedureIS-IN(S:inSET;ELEM)inCOMPONENT)returnBOOLEAN;privatetypeSETis

recordSTORE:array(1..MAX-CARDINALITY)ofCOMPONENT;CARDINALITY:INTEGERrange0..MAX-cardinality:=0;endrecord;endSET-MANIPULATION;四.Modula-2的抽象數(shù)據(jù)類型

1.移入(Inport)和移出(Export)子句說明模塊的移入和移出實(shí)體

2.Modula-2的模組可以封裝一組相關(guān)副程式

3.抽象數(shù)據(jù)類型的描述由定義模組和實(shí)現(xiàn)模組兩部分組成

4.Modula-2的模組可以移出類型，類型的細(xì)節(jié)可通過“不透明移出”加以遮罩definitionmoduleComplexNumber;exportqualifiedComplex,Initialize,Add;typeComplex;/*不透明移出*/ProcedureInitialize(A,B:real;varx:Complex);ProcedureAdd(A,B:Complex):ComplexendComplexNumber.implementationmoduleComplexNumber;typeC=recordR,I:realend;typeComplex=pointertoC;procedureInitialize(A,B:real;varx:Complex);beginnew(x);x.R:=A;x.I:=BendInitialize;

procedureAdd(A,B:Complex):Complex;varT:Complex;beginnew(T);T.R:=A.R+B.R;T.I:=A.I+B.I;return(T)endAddendComplexNumber.第十節(jié)實(shí)現(xiàn)模型

描述符:描述數(shù)據(jù)對象的所有屬性數(shù)據(jù)數(shù)據(jù)對象(存儲區(qū)及其值)一.內(nèi)部類型和用戶定義的非結(jié)構(gòu)類型

1.描述符一般由“類型”和一個指針組成

2.子界的描述符必須包括子界的界值

3.布爾型和字元型可以壓縮存儲如:整型integer二.結(jié)構(gòu)類型1.笛卡爾積①各成分順序排列②描述符包含:類型名、構(gòu)造符、若干三元式。每個域?qū)?yīng)一個三元式(選擇符名,域類型,指針)③每個成分占整數(shù)個可編址的存儲單元(字編址或位元組編址）

④可以用packed顯式說明壓縮存儲數(shù)據(jù)對象浮點(diǎn)值定點(diǎn)值描述符類型名構(gòu)造符選擇符選擇符類型類型引用引用trecordarealbinteger域1域2typet=recorda：real；

b：integer；

end；2.有限映象

①為每一成分分配整數(shù)個可編址的存儲單元

②描述符包括:類型名、構(gòu)造符、定義域的基類型、下界、上界、成分類型、單元個數(shù)、首地址

③地址公式的計(jì)算

b+k(i-m)=b-km+ki

其中b為首地址，k為所占單元數(shù)，m為下界

④內(nèi)情向量描述符類型名構(gòu)造符基類型成分類型下界單元個數(shù)上界引用aarrayinteger0real1下標(biāo)類型10數(shù)據(jù)對象浮點(diǎn)值浮點(diǎn)值浮點(diǎn)值typea=array[1..10]ofreal;3.序列可變長串的表示:

靜態(tài)描述符+動態(tài)描述符+堆string5ALPHAnil4.判定或①判定或類型的變數(shù)分配的空間應(yīng)足以容納需要最大空間的變體的值

②Pascal的變數(shù)記錄的表示包括:描述符、數(shù)據(jù)對象、case表、若干變體描述符typev=recorda:integer;caseb:booleanoftrue:(c:integer);false:(d:integer;e:real)end;vvariantrecordaintegerbboolean????????(false)(true)dintegererealcinteger定點(diǎn)值布爾值truefalsecase表描述符數(shù)據(jù)對象變體描述符

5.冪集①集合關(guān)聯(lián)一個機(jī)器字,通過每一位的取值可知該集合中有基類型的哪些元素

②位操作

6.指針指針變數(shù)的表示類似於內(nèi)部類型，只是其值為一地址，並且它指向的數(shù)據(jù)對象分配在堆上

7.層次結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)對象的表示

描述符中的類型可以指向另外的描述符typet1=array[0..3]ofinteger;t=recorda:real;b:t1;c:integerend;t4=array[0..5]ofinteger;t2=array[0..2]oft4;trecordarealbcinteger浮點(diǎn)值定點(diǎn)值定點(diǎn)值定點(diǎn)值定點(diǎn)值定點(diǎn)值t1arrayinteger03integer1t2arrayinteger026t4arrayinteger05integer1定點(diǎn)值第二章習(xí)題必做題:2-2、2-8、

2-16：請談?wù)勀銓?shù)據(jù)類型的認(rèn)識思考題：

2-3、2-13、2-14

代碼生成和代碼優(yōu)化第o節(jié)符號表在程式中,用戶用識別字定義了不少名字來代表不同的數(shù)據(jù)對象,編譯程序?qū)⑦@些名字保存在符號表中。符號表除了記錄名字本身而外,還記錄了與名字關(guān)聯(lián)的各種屬性資訊。一.符號表的一般形式每個名字對應(yīng)一個表項(xiàng),一個表項(xiàng)包括名字域和資訊域。名字資訊其中,資訊域通常設(shè)若幹子域及標(biāo)誌位，其內(nèi)容可以是和名字有關(guān)的任何資訊：類型,種屬,長度,相對地址,數(shù)組的內(nèi)情向量,記錄與分量的聯(lián)繫,形參標(biāo)誌,說明標(biāo)誌,賦值標(biāo)誌等。因名字的長度、資訊域的組成及長度可能是各不相同的,一般採用間接表技術(shù)。二.常用的符號表結(jié)構(gòu)1.線性表:用N個數(shù)組A1,A2,…,AN來存放符號表的N個子域

2.HASH表第一節(jié)語義分析和中間代碼生成O.概述1.語義分析的主要工作(1)語義檢查:如類型是否一致,數(shù)組維數(shù)是否正確。(2)語義處理:對說明語句,登記資訊;對可執(zhí)行語句,生成中間代碼。2.語法制導(dǎo)翻譯為每個產(chǎn)生式配上一個語義副程式,在語法分析過程中,當(dāng)用一個產(chǎn)生式進(jìn)行匹配或歸約時,就調(diào)用相應(yīng)的語義程式。上述語義副程式既可能包含了語義檢查,也可能包含了語義處理,其核心是為了生成相應(yīng)的中間代碼。例：語法分析採用自底向上的LR分析法XABYCDZXY狀態(tài)棧符號棧語義棧BA

B的語義值A(chǔ)的語義值

狀態(tài)棧符號棧語義棧X

X的語義值

狀態(tài)棧符號棧語義棧DCX

D的語義值C的語義值X的語義值

狀態(tài)棧符號棧語義棧YX

Y的語義值X的語義值

狀態(tài)棧符號棧語義棧Z

Z的語義值

語義可以是：“值”、“類型”、“種屬”、“地址”等?？梢姡涸诜治鲞^程中必須保存語義值。一.四元式形式:(op,ARG1,ARG2,RESULT)op—運(yùn)算符,ARG1—第一運(yùn)算量,ARG2—第二運(yùn)算量,RESULT—結(jié)果如:A:=-B*(C+D)翻譯成

(@,B,_,t1)(+,C,D,t2)(*,t1,t2,t3)(:=,t3,_,A)由此可見:四元式出現(xiàn)順序和運(yùn)算式計(jì)值順序一致;四元式之間的聯(lián)繫是通過臨時變數(shù)實(shí)現(xiàn)的。二.簡單賦值語句的翻譯1.語義變數(shù)及過程(1)X.a:文法符X的相應(yīng)屬性a

如,E.place(2)lookup(a):語義函數(shù),為名字a查符號表;返回:a在符號表中的位置或nil(3)newtemp:語義函數(shù),每調(diào)用一次就返回一個可用的臨時變數(shù)地址(4)emit:語義過程,產(chǎn)生四元式並送到GAM的代碼記憶體ip指向位置(5)ip:指令指針,一般設(shè)初值為0,也可指定一個初值,每調(diào)用一次emit,ip自動加4(6)error:語義過程,錯誤處理2.翻譯方案A→i:=E{p:=lookup();ifp<>nilthenemit(:=,E.place,_,p)elseerror}E→E1opE2{E.place:=newtemp;emit(op,E1.place,E2.place,E.place)}E→-E1

{E.place:=newtemp;emit(@,E1.place,_,E.place)}E→(E1){E.place:=E1.place}E→i{p:=lookup();ifp<>nilthenE.place:=pelseerror}舉例:a:=-b*(c+d)的移進(jìn)-歸約過程a:=-b*(c+d)a:=-E1*(c+d)a:=E2*(c+d)a:=E2*(E3+d)a:=E2*(E3+E4)a:=E2*(E5)a:=E2*E6a:=E7Aii:=i:=-i:=-ii:=-E1i:=E2i:=E2*i:=E2*(i:=E2*(ii:=E2*(E3i:=E2*(E3+i:=E2*(E3+ii:=E2*(E3+E4i:=E2*(E5i:=E2*(E5)i:=E2*E6i:=E7A

aa_a__a__ba__ba_t1a_t1_a_t1__a_t1__ca_t1__ca_t1__c_a_t1__c_da_t1__c_da_t1__t2a_t1__t2_a_t1_t2a_t3

a:=-b*(c+d):=-b*(c+d)-b*(c+d)b*(c+d)*(c+d)*(c+d)*(c+d)(c+d)c+d)+d)+d)d))))

(@,b,_,t1)(+,c,d,t2)(*,t1,t2,t3)(:=,t3,_,a)

符號棧PLACE輸入四元式a:=-b*(c+d)的翻譯過程3.類型轉(zhuǎn)換對運(yùn)算式E增加類型屬性E.type;引進(jìn)類型轉(zhuǎn)換指令(itr,x,_,t)E→E1opE2的語義副程式如後t(yī):=newtemp;ifE1.type=integerandE2.type=integerthenbeginemit(opi,E1.place,E2,place,t);E.type:=integerendelseifE1.type=realandE2.type=realthenbeginemit(opr,E1.place,E2.place,t);E.type:=realendelseifE1.type=integerthenbegint1:=newtemp;emit(itr,E1.place,_,t1);emit(opr,t1,E2.place,t);E.type:=realendelsebegint1:=newtemp;emit(itr,E2.place,_,t1);emit(opr,E1.place,t1,t);E.type:=realend;E.place:=t;

代碼優(yōu)化一.優(yōu)化的定義優(yōu)化是一種等價的，有效的程式變換等價——不改變程式運(yùn)行結(jié)果有效——時空效率要高二.不同階段的優(yōu)化

1.根源程式階段的優(yōu)化：考慮DS和演算法

2.編譯優(yōu)化——中間代碼優(yōu)化和目標(biāo)代碼優(yōu)化

3.中間代碼優(yōu)化——局部優(yōu)化和全局優(yōu)化局部優(yōu)化：在基本塊內(nèi)的優(yōu)化全局優(yōu)化：超越基本塊，在基本塊之間的優(yōu)化三.劃分基本塊和構(gòu)造程式流圖

1.劃分基本塊

(1)找入口語句程式的第一條語句能由條件或無條件轉(zhuǎn)向語句轉(zhuǎn)移到的語句緊跟在條件轉(zhuǎn)向語句後的那個語句(2)確定基本塊入口語句入口語句入口語句

………………

入口語句轉(zhuǎn)向語句停語句

(3)刪除未被劃入基本塊的語句(1)i:=m-1(2)j:=n(3)t1:=4*n(4)v:=a[t1](5)i:=i+1(6)t2:=4*i(7)t3:=a[t2](8)ift3<vgoto(5)(9)j:=j-1(10)t4:=4*j(11)t5:=a[t4](12)ift5>vgoto(9)(13)ifi>=jgoto(23)(14)t6:=4*i(15)x:=a[t6](16)t7:=4*i(17)t8:=4*j(18)t9:=a[t8](19)a[t7]:=t9(20)t10:=4*j(21)a[t10]:=x(22)goto(5)(23)t11:=4*i(24)x:=a[t11](25)t12:=4*i(26)t13:=4*n(27)t14:=a[t13](28)a[t12]:=t14(29)t15:=4*n(30)a[t15]:=x2.構(gòu)造流圖G=(N,E,n0)(1)基本塊集即為結(jié)點(diǎn)集N;(2)含程式第一個語句的基本塊為首結(jié)點(diǎn)n0;(3)設(shè)Bi,Bj∈N，若滿足下列條件之一，則Bi

Bj

Bj緊跟在Bi之後，且Bi的出口語句不是無條件轉(zhuǎn)向或停止語句

Bi的出口語句為轉(zhuǎn)向語句，其轉(zhuǎn)向點(diǎn)恰為Bj的入口語句(1)i:=m-1(2)j:=n(3)t1:=4*n(4)v:=a[t1](5)i:=i+1(6)t2:=4*i(7)t3:=a[t2](8)ift3<vgoto(5)(9)j:=j-1(10)t4:=4*j(11)t5:=a[t4](12)ift5>vgoto(9)(13)ifi>=jgoto(23)(14)t6:=4*i(15)x:=a[t6](16)t7:=4*i(17)t8:=4*j(18)t9:=a[t8](19)a[t7]:=t9(20)t10:=4*j(21)a[t10]:=x(22)goto(5)(23)t11:=4*i(24)x:=a[t11](25)t12:=4*i(26)t13:=4*n(27)t14:=a[t13](28)a[t12]:=t14(29)t15:=4*n(30)a[t15]:=xB1B2B3B4B5B6四.局部優(yōu)化1.合併已知量2.刪除公共子運(yùn)算式3.刪除死代碼（a）if的條件為定值;（b）定值後不引用或僅是A:=A±C的遞歸賦值。(14)t6:=4*i(15)x:=a[t6](16)t7:=4*i(17)t8:=4*j(18)t9:=a[t8](19)a[t7]:=t9(20)t10:=4*j(21)a[t10]:=x(22)goto(5)(14)t6:=4*i(15)x:=a[t6](17)t8:=4*j(18)t9:=a[t8](19)a[t6]:=t9(21)a[t8]:=x(22)goto(5)優(yōu)化後例1T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2

B:=AT3:=2*T0T4:=R+rT5:=T3*T4

T6:=R－rB:=T5*T6S1:=R+rA:=6.28*S1S2:=R－rB:=A*S2優(yōu)化後例2五.迴圈優(yōu)化1.迴圈的定義迴圈是程式流圖中有唯一入口結(jié)點(diǎn)的強(qiáng)連通子圖。(1)入口結(jié)點(diǎn)子圖中滿足下列條件的結(jié)點(diǎn)n:或者n是流圖的首結(jié)點(diǎn),或者在子圖外有一結(jié)點(diǎn)m,