【正文】 訪問(wèn)文件 ? 索引文件 8 June 5, 2023 類(lèi)型檢查基礎(chǔ)（ 6） ? 用戶(hù)定義的數(shù)據(jù)類(lèi)型 ? 結(jié)構(gòu)化的數(shù)據(jù) ?規(guī)范： ? 成員的數(shù)目 ? 每個(gè)成員的類(lèi)型 ? 用來(lái)選擇成員的名字 ? 最多成員數(shù)目 ? 成員的組織 ?操作 ? 對(duì)數(shù)據(jù)結(jié)構(gòu)類(lèi)型上的定義域和值域的規(guī)定和基本類(lèi)型的方法差不多 ? 要增加一些新的重要操作： ? 成員選擇操作 ? 全數(shù)據(jù)結(jié)構(gòu)操作 ? 成員的插入和刪除 ? 建立和消除數(shù)據(jù)結(jié)構(gòu) 9 June 5, 2023 類(lèi)型檢查基礎(chǔ)（ 7） ? 抽象數(shù)據(jù)類(lèi)型 ? 數(shù)據(jù)抽象，把封裝的概念推廣到程序員自定義的數(shù)據(jù)，抽象的數(shù)據(jù)類(lèi)型是 ? 數(shù)據(jù)對(duì)象的集合，一般使用一個(gè)或多個(gè)類(lèi)型定義 ? 在所定義的數(shù)據(jù)對(duì)象上的抽象操作的集合 ? 將上述兩個(gè)集合封裝： ? 新的數(shù)據(jù)類(lèi)型的使用者不能直接操作這個(gè)類(lèi)型的數(shù)據(jù)對(duì)象，只能通過(guò)已定義的操作來(lái)使用和操作數(shù)據(jù)對(duì)象 ? 信息隱藏 ? 繼承 ? 多態(tài) 10 June 5, 2023 類(lèi)型檢查基礎(chǔ)（ 8） ? 聲明 ? 將程序執(zhí)行時(shí)所需的數(shù)據(jù)對(duì)象的名字和類(lèi)型的信息傳給語(yǔ)言翻譯器的程序語(yǔ)句 ? 聲明可以表明數(shù)據(jù)對(duì)象的生存期 ? 聲明的種類(lèi) ? 顯式聲明 ? 隱式聲明 ? 如果數(shù)據(jù)對(duì)象是常量，聲明可以指定它的值，變量可以指定初始值 ? 聲明也可以指明具體存儲(chǔ)的一些信息等，如 cobol中存儲(chǔ)形式的聲明 ? 操作的聲明：操作形式 ? 聲明的目的 ? 存儲(chǔ)表示的選擇 ? 存儲(chǔ)管理 ? 多態(tài)操作 ? 類(lèi)型檢查 11 June 5, 2023 類(lèi)型體制（ 1） ? 類(lèi)型表達(dá)式： ? 語(yǔ)言結(jié)構(gòu)的類(lèi)型可以用類(lèi)型表達(dá)式指稱(chēng) ? 類(lèi)型構(gòu)造器 ? 在一個(gè)已經(jīng)說(shuō)明類(lèi)型的集合上創(chuàng)建新的類(lèi)型 ? 數(shù)組、記錄、指針等 ? 類(lèi)型表達(dá)式的形式定義 ? 基本類(lèi)型是類(lèi)型表達(dá)式 ? 一般有 boolean, char, integer, real, type_error, void ? 其中 ? type_error表示類(lèi)型檢查期間的錯(cuò)誤 ? void表示沒(méi)有值，用于語(yǔ)句的檢查 12 June 5, 2023 類(lèi)型體制（ 2） ? 類(lèi)型表達(dá)式可以命名，類(lèi)型名是類(lèi)型表達(dá)式 ? 如記錄名或結(jié)構(gòu)名可以作為類(lèi)型表示用于變量的類(lèi)型聲明 1)名字直接用 struct或 union等構(gòu)造器關(guān)聯(lián) struct Hchain { int objp。 int next。 struct Hchain dimchain[100]。 int next。 Hchain dimchain[100]。 int val。 } 但通過(guò)指針是可以解決上述問(wèn)題的： struct intBST *left, * right。 array[ 0..9, color ] of integer如何存放？ a)行主序（行優(yōu)先等）：在內(nèi)存中的存放次序是 a[ 0, red], a[ 0, green], a[ 0, blud], a[ 1, red], a[ 1, green], … b)列主序（列優(yōu)先等）：在內(nèi)存中的存放次序是 a[ 0, red], a[ 1, red], … , a[ 9, red], a[ 0, green], … ? 開(kāi)放索引數(shù)組：在聲明時(shí)沒(méi)有說(shuō)明索引區(qū)間，常見(jiàn)于參數(shù) 15 June 5, 2023 類(lèi)型體制（ 5） ? 積： ? 如果 T1和 T2是類(lèi)型表達(dá)式，則它們的笛卡兒積 T1 T2也是類(lèi)型表達(dá)式，假定是左結(jié)合的 ? ML語(yǔ)言中的類(lèi)型定義 ? 記錄（結(jié)構(gòu)）： ? 從某種意義上說(shuō)是它各域類(lèi)型的積 ? 記錄的各個(gè)域是有名字的（與積的區(qū)別） ? 對(duì)記錄中某個(gè)域的引用必須與記錄關(guān)聯(lián) ? 記錄類(lèi)型構(gòu)造器 record作用于域名和它們的類(lèi)型組成的元組，形成類(lèi)型表達(dá)式，進(jìn)而可以完成記錄的類(lèi)型檢查 type row = record address: integer。 var table: array [ 1 .. 101 ] of row。 E D→D 。 key mod 19999 25 June 5, 2023 簡(jiǎn)單類(lèi)型檢查器的說(shuō)明（ 2） ? 語(yǔ)言的簡(jiǎn)單分析 ? 兩個(gè)基本類(lèi)型 ? char ? integer ? 數(shù)組類(lèi)型的下標(biāo)都從 1開(kāi)始 ? array[ 256 ] of char的類(lèi)型表達(dá)式是 array( 1 .. 256, char) ? 指針類(lèi)型 ? ↑integer的類(lèi)型表達(dá)式是 pointer( integer ) ? id↑中的 ↑表示解除指針引用 ? 引入一個(gè)新的基本類(lèi)型： type_error， 用于報(bào)告錯(cuò)誤 26 June 5, 2023 簡(jiǎn)單類(lèi)型檢查器的說(shuō)明（ 3） ? 語(yǔ)言的聲明部分的翻譯方案 P→D 。 D D→id : T { addtype( , ) } T→char { := char } T→integer { := integer } T→array[num] of T1 { := array(, )} T→↑T1 { := pointer() } ? 在 P→D 。 S D→D 。 S E→literal | num | id | E mod E | E [ E ] | E↑ 29 June 5, 2023 簡(jiǎn)單類(lèi)型檢查器的說(shuō)明（ 6） 關(guān)于語(yǔ)句的類(lèi)型檢查的翻譯方案： S→id := E { := if = then void else type_error } S→if E then S1 { := if = boolean then else type_error } S→while E do S1 { := if = boolean then else type_error } S→S1 。 int x1。 int y1[100]。 }。 begin if s和 t是相同的基本類(lèi)型 then return true else if s = array( s1 , s2 ) and t = array( t1 , t2 ) then return sequiv( s1 , t1 ) and sequiv( s2 , t2 ) else if s = s1 s2 and t = t1 t2 then return sequiv( s1 , t1 ) and sequiv( s2 , t2 ) else if s = pointer( s1 ) and t = pointer( t1 ) then return sequiv( s1 , t1 ) else if s = s1 → s2 and t = t1 → t2 then return sequiv( s1 , t1 ) and sequiv( s2 , t2 ) else return false end 37 June 5, 2023 類(lèi)型表達(dá)式的等價(jià)（ 4） ? 數(shù)據(jù)類(lèi)型結(jié)構(gòu)等價(jià)的例子 ? 兩個(gè)數(shù)組是等價(jià)的當(dāng)且僅當(dāng)它們有相同的大小和元素類(lèi)型 ? 兩個(gè)結(jié)構(gòu)是等價(jià)的當(dāng)且僅當(dāng)它們有相同的元素，并且元素有相同的名字和順序 ? 結(jié)構(gòu)中，元素的順序是重要的 ? 如果不考慮數(shù)組的界，則數(shù)組等價(jià)的測(cè)試可以重寫(xiě)為： 如果有： s = array( s1 , s2 ) t = array( t1 , t2 ) 測(cè)試算法中的第 4和第 5行改寫(xiě)為： else if s = array( s1 , s2 ) and t = array( t1 , t2 ) then return sequiv( s2 , t2 ) 38 June 5, 2023 類(lèi)型表達(dá)式的等價(jià)（ 5） ? 類(lèi)型表達(dá)式的名字等價(jià) ? 類(lèi)型表達(dá)式的名字 ? 在某些語(yǔ)言中類(lèi)型是可以命名的 ? 如果有下述的 Pascal的聲明 type link = ↑c(diǎn)ell。 last: link。 q, r: ↑c(diǎn)ell。 begin if s和 t是相同的基本類(lèi)型 then return true else if s 和 t 是類(lèi)型名 then return s = t else return false end ? 名字等價(jià)的測(cè)試也可以通過(guò)構(gòu)造類(lèi)型圖來(lái)實(shí)現(xiàn) ? 每當(dāng)看見(jiàn)類(lèi)型構(gòu)造器或基本類(lèi)型對(duì)應(yīng)，構(gòu)造一個(gè)新的結(jié)點(diǎn) ? 每看見(jiàn)一個(gè)新的類(lèi)型名，就構(gòu)造一個(gè)葉結(jié)點(diǎn) ? 記錄名字引用的是哪個(gè)類(lèi)型表達(dá)式 cellp o i n t e r p o i n t e rp o i n t e rl i n k =next last p q r42 June 5, 2023 類(lèi)型表達(dá)式的等價(jià)（ 9） ? 類(lèi)型表示中的環(huán) ? 類(lèi)型的遞歸定義 ? 如鏈表、樹(shù)等，在類(lèi)型定義中要引用自身 ? 類(lèi)型名起重要的作用 ? 例子： struct cell { int info。 } 43 June 5, 2023 類(lèi)型表達(dá)式的等價(jià)（ 10） ? 當(dāng)碰到記錄構(gòu)造器時(shí)，結(jié)構(gòu)等價(jià)的測(cè)試停止，被比較的類(lèi)型或者由于它們有同樣的命名記錄