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

低級語言

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

機器語言二.編譯執行和解釋執行1.編譯執行根源程式目標程式計算結果組合語言程式目標程式

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

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

(1)識別字:用來命名程式中出現的變數、數組、函數、過程、標號等

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

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

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

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

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

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

=、>、>=、:=、：、；0412356789開始空白字母/數字字母非字母數字數字非數字+-**非****數字101112<>=1314151617>其他=181920：其他=其他2122=；其他****3.實現方法每個狀態結對應一小段程式分支狀態——if或case語句迴圈狀態——while語句終態——return語句

4.一個示意演算法start:token:=‘‘;getchar;getnb;casecharacterof‘a’…’z’:beginwhileletterordigitdobeginconcatenate;getcharend;retract;c:=reserve;ifc=0thenbeginbuildlist;return(id,id在符號表中的位置)endelsereturn(保留字碼,—)end;‘0’…’9’:beginwhiledigitdobeginconcatenate;getcharend;retract;return(num,num在常數表中的位置)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:為識別字登記符號表第二節自頂向下語法分析語法分析:自上而下(自頂而下)

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

1.一個實例

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

A→

1|

2(2)左遞歸

A→Aα或A

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

1.提取公共左因數

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的所有非終結符按任一給定的順序排列,設為A1,A2,…An;+(b)消除可能的左遞歸;fori:=1tondoforj:=1toi-1dobegin

把一個形如Ai

Aj

的產生式改寫為

Ai

1|2|…|k

其中Aj

1|2|…|k是Aj的所有產生式;

消除Ai產生式的直接左遞歸

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

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

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

FortranPascal或C

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

—追求效率1.FORTRANFORmulaTRANslation.主要用於科學計算.副程式獨立編譯.COMMON語句實現了模組之間的通信2.ALGOL60ALGOrithmicLanguage60.主要用於科學計算

.引入了分程式結構和遞歸過程

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

COmmonBusinessOrientedLanguage.廣泛應用於各種事務處理領域.引入了檔和數據描述.類自然語言程式描述二.早期的突破

60年代初，不再盲目地追求效率,出現了基於良好刻畫數學原則的語言。1.LISP.具有很強的符號處理能力.統一的數據結構.數據和程式統一的表示方法.其基礎是函數和函數作用2.APL.支持函數式程式設計風格.廣泛應用於涉及大量矩陣運算的科學計算中.具有豐富的操作符3.SNOBOL4.主要用於字串處理

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

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

.分程式概念和遞歸過程

.數據描述機能

.動態數據結構

.異常處理

.多任務機能

.可用於科學數值計算,數據處理和開發系統軟體

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

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

.引入正交性和通用性原則2.SIMULA67.應用於模擬領域

.增加了一個特殊結構——協同程式

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

.體現結構程式設計思想

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

.互動式工作環境

.解釋執行五.大量的探索

70年代,支持系統軟體開發

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

2.MODULA-2.支持模組結構,模組可以獨立編譯

.面向即時系統和並行系統綜合功能3.CCPL→BCPL→B→C.C的最大特點是具有高級語言和低級語言的優點

.應用於各種領域六.Ada和第四代語言

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

1.Ada.面向專門領域的特殊要求

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

.是直接體現許多現代軟體設計方法學的語言

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

.表達力更強,使用更方便,更接近於問題的描述

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

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

數據類型實質上是對記憶體中所存儲的數據進行的抽象。它包含了一組值的集合和一組操作。第一節引言1.數據類型的作用實現了數據抽象使程式員從機器的具體特徵中解脫出來提高了編程效率2.數據類型的分類內部類型自定義類型第二節內部類型一.內部類型的特點

.反映基本硬體特性如：定點加

.在語言級,標識共用某些操作的數據對象的抽象表示如：整型共用+、-、*、/二.內部類型的優越性1.基本表示的不可見性基本位串對程式員是不可見的。

25+9=34

基本表示00011001+00001001

結果00100010

從而具有優點：不同的程式設計風格，可寫性，可讀性，可修改性。

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

可以通過數據類型顯式定義數據的精度第三節用戶定義類型

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

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

A2

…

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

Ai

任意正多邊形可表示為

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

vara:array[1..50]ofchar;表示：整數1至50到字元集的有限映像②值域對象通過下標選取。③下標越界會出錯，動態檢查

④下標可用來選取值域的多個元素

⑤SNOBOL4的ARRAY構造符並不要求值域集的所有元素是同一類型的⑥DT到相應值的特定子集的綁定策略：

.編譯時綁定(靜態數組).對象建立時綁定(執行到分程式時,

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

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

array[t1]of[t2]PASCAL把下標類型不同的數組看成不同的類型

typea1=array[1..50]ofinteger;a2=array[1..70]ofinteger;“符合數組”的概念（見下頁）維數相同,成分類型相同PASCAL可定義多維數組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.記錄構造

①構造符RECORD用以定義笛卡爾積

②記錄可以整體訪問，也可用圓點“.”

作為選擇符訪問單個的域

③PASCAL的變體記錄

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

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

程式設計語言和編譯程序第一節上下文無關文法一.文法文法是描述語言的語法結構的形式規則,必須準確,易於理解,且描述能力強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為上述產生式的集合說明:①

→

的讀法,

其中

V*VNV*,

V*②

→

1

→

2...

→

n縮寫為

→

1|

2|…|

n2.文法的分類

①0型文法:產生式形如

→

②1型文法:│α│<=│β│或產生式形如αAβ→α

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

VN,必有S

αAβ*二.文法產生的語言1.推導與歸約

①直接推導:αβ

α

即由產生式右邊替換產生式左邊

②推導:α1

αn、α1

αn③歸約:推導的逆過程*+舉例:已知G(E)E→E+E│E*E│(E)│ii+i*i的推導過程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.句型和句子設文法G=(VT,VN,S,P),若S

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

3.文法產生的語言

文法G=(VT,VN,S,P)的句子的全體,稱為由文法G產生的語言,記為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次使用第一個產生式)aibQ(PQ)i-1

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

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

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

aibicQi-1

(使用第五個產生式)aibici

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

是上下文無關文法G的一個句型,如果有S

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

關於非終結符A的一個短語,或稱β是句型αβ

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

5．推導樹

——以圖的方式表示推導過程

①推導樹是一棵有序的標記樹每個結點的標記是文法G的非終結符或終結符；標記為A的內部結點從左到右有子結點X1，X2，…,Xn,則A→X1…Xn是一個產生式;如果有結點標記為

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

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

DFAMd=(

,S,s0,F,

)

:S

→S例:

={0,1}s0是初態

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.非確定的有限自動機

NFAMn=(

,S,s0,F,

)

:S

→2S例:

={0,1}s0是初態

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}

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

1.類的說明

<類頭>;<類體><類頭>包括類名和形式參數<類體>是傳統的分程式,可包含變數、過程和類的局部說明，以及一些執行語句例：複數表示(幅角,半徑)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.類的有關性質①類說明定義了一類數據對象的原型或樣板②類的每個實例是一個可操作的數據對象③類的實例可多次動態建立,且僅能通過指針引用例:ref(complex)c;c:-newcomplex(1.0,1.0);c0.781.421.01.0angleradiusxy④類實例的屬性是指類體的局部變數和類頭中的參數my_angle:=c.angle;my_radius:=c.radius;my_x:=c.x;my_y:=c.y;⑤類支持抽象數據類型的封裝機制,它可以封裝實現對數據操作的各種過程例:可將複數加和乘的過程add和multiply封裝入類complex的類體說明中,作為complex的屬性。procedureadd(operand);ref(complex)operandproceduremultiply(operand);ref(complex)operand變數c1、c2引用的兩個複數相加可表示為：c1.add(c2)或c3.angle:=c1.angle;c3.radius:=c1.radius+c2.radius;用戶可以直接訪問複數的內部表示,故add和multiply不是複數對象的唯一操作3.子類用以定義類型的判定或和類屬。要求：定義一個棧，完成引用棧頂元素入棧出棧判棧是否空(這些操作與棧中元素的類型無關)棧內成員的元素類classstack_member;beginref(stack_member)next_member;next_member:-noneend指針型局部變數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定義了一個複數棧其中complex稱為stack_member的子類加在類說明之前①子類complex具有自己的屬性,同時繼承了stack_member的屬性

newcomplex產生的對象具有stack_member和complex的所有屬性ref(stack)s;s:-newstack;s.push(c1);s.push(c2);s.push(c3);建立一個複數棧②具有ref(stack_member)的變數可引用多種類型的量,但不同類型的元素不得壓入同一棧實例中下述語句說明向量也可是棧中元素:stack_memberclassvector(…);……endvector二.CLU的抽象數據類型例:定義複數完成:建立、加、判等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用來定義抽象數據類型的機制

①簇內,需要內部表示

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

rep說明數據對象的具體表示

cvt用於抽象表示和具體表示之間的相互轉換,僅能在簇內使用

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

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

其中x類似於指針變數

③CLU的參數傳遞由賦值定義

complex$add(x,y)

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

1.Ada用程式包描述抽象數據類型程式包包括規格說明和程式包體

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

①私有類型的表示細節在程式包外是不可見的

②允許的操作:移出的副程式、函數；賦值、相等、不等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.受限私有類型只允許程式包移出的副程式和函數,不允許賦值、相等和不相等

5.類屬的描述使用generic子句說明類型是一個參數，實例化時代以具體的類型例: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的抽象數據類型

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

2.Modula-2的模組可以封裝一組相關副程式

3.抽象數據類型的描述由定義模組和實現模組兩部分組成

4.Modula-2的模組可以移出類型，類型的細節可通過“不透明移出”加以遮罩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.第十節實現模型

描述符:描述數據對象的所有屬性數據數據對象(存儲區及其值)一.內部類型和用戶定義的非結構類型

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

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

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

④可以用packed顯式說明壓縮存儲數據對象浮點值定點值描述符類型名構造符選擇符選擇符類型類型引用引用trecordarealbinteger域1域2typet=recorda：real；

b：integer；

end；2.有限映象

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

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

③地址公式的計算

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

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

④內情向量描述符類型名構造符基類型成分類型下界單元個數上界引用aarrayinteger0real1下標類型10數據對象浮點值浮點值浮點值typea=array[1..10]ofreal;3.序列可變長串的表示:

靜態描述符+動態描述符+堆string5ALPHAnil4.判定或①判定或類型的變數分配的空間應足以容納需要最大空間的變體的值

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

5.冪集①集合關聯一個機器字,通過每一位的取值可知該集合中有基類型的哪些元素

②位操作

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

7.層次結構數據結構對象的表示

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

2-16：請談談你對數據類型的認識思考題：

2-3、2-13、2-14

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

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

B的語義值A的語義值

狀態棧符號棧語義棧X

X的語義值

狀態棧符號棧語義棧DCX

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

狀態棧符號棧語義棧YX

Y的語義值X的語義值

狀態棧符號棧語義棧Z

Z的語義值

語義可以是：“值”、“類型”、“種屬”、“地址”等。可見：在分析過程中必須保存語義值。一.四元式形式:(op,ARG1,ARG2,RESULT)op—運算符,ARG1—第一運算量,ARG2—第二運算量,RESULT—結果如:A:=-B*(C+D)翻譯成

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

如,E.place(2)lookup(a):語義函數,為名字a查符號表;返回:a在符號表中的位置或nil(3)newtemp:語義函數,每調用一次就返回一個可用的臨時變數地址(4)emit:語義過程,產生四元式並送到GAM的代碼記憶體ip指向位置(5)ip:指令指針,一般設初值為0,也可指定一個初值,每調用一次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)的移進-歸約過程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.類型轉換對運算式E增加類型屬性E.type;引進類型轉換指令(itr,x,_,t)E→E1opE2的語義副程式如後t:=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;

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

1.根源程式階段的優化：考慮DS和演算法

2.編譯優化——中間代碼優化和目標代碼優化

3.中間代碼優化——局部優化和全局優化局部優化：在基本塊內的優化全局優化：超越基本塊，在基本塊之間的優化三.劃分基本塊和構造程式流圖

1.劃分基本塊

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

………………

入口語句轉向語句停語句

(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=(N,E,n0)(1)基本塊集即為結點集N;(2)含程式第一個語句的基本塊為首結點n0;(3)設Bi,Bj∈N，若滿足下列條件之一，則Bi

Bj

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

Bi的出口語句為轉向語句，其轉向點恰為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四.局部優化1.合併已知量2.刪除公共子運算式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)優化後例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優化後例2五.迴圈優化1.迴圈的定義迴圈是程式流圖中有唯一入口結點的強連通子圖。(1)入口結點子圖中滿足下列條件的結點n:或者n是流圖的首結點,或者在子圖外有一結點m,