上次課程小結(jié)-資料下載頁(yè)
2024-10-12 13:44本頁(yè)面
【導(dǎo)讀】否相等來(lái)進(jìn)行類型檢查。完全相同，則稱兩個(gè)類型表達(dá)式結(jié)構(gòu)等價(jià)。反映在類型表達(dá)式的語(yǔ)法樹上，就是兩棵語(yǔ)法樹完全相同。的函數(shù)值的類型為int。當(dāng)類型構(gòu)造符層次很多并且僅在最底。層不等價(jià)時(shí)，算法的效率較低。確可以確定不等價(jià)的情況排除。即為了提高效率，犧牲一些。次要信息是否也相等。一條從根到葉子的路徑。對(duì)鏈上每個(gè)節(jié)點(diǎn)編碼，形成一個(gè)類。型編碼的字符串或者整型數(shù)。標(biāo)類型保留數(shù)組元素類型。型保留返回值的類型。問(wèn)題：×與record的簡(jiǎn)化如何處理？簡(jiǎn)化后的類型表達(dá)式為array。將其從左到右轉(zhuǎn)換為編碼，得到1001110001。同的類型名，使得它們具有不同的類型。能進(jìn)行運(yùn)算，從而避免了潛在的錯(cuò)誤；
【正文】 end unify。 s := find(m)。 t := find(n)。 分別找到 m和 n所在等價(jià)類的代表 if s=t then return true。 elsif s和 t代表相同基本類型 then union(s,t)。 return true。 elsif s和 t代表相同類型構(gòu)造符并分別有孩子節(jié)點(diǎn) (s1, s2)和 (t1, t2) then union(s, t)。 構(gòu)造等價(jià)類 return unify(s1, t1) and unify(s2, t2)。 分別合一左右孩子 elsif s或 t代表一個(gè)變量 then union(s, t)。 return true。 else return false。 其它均不可合一 end if。 多態(tài)函數(shù)的類型檢查（續(xù) 3） 多態(tài)函數(shù)文法 ()中表達(dá)式類型檢查的語(yǔ)義規(guī)則： E→E 1(E2) { γ := mkleaf(newtypevar)。 unify(,mknode(39。→39。, ,γ) 。 := γ 。 } () |E1, E2 { := mknode(39。 39。, , )。 } |id { := fresh()。 } 函數(shù)調(diào)用 E→E1(E2) 的語(yǔ)義處理：設(shè) =α 且在函數(shù)聲明時(shí) α 已確定 (α=s→t )，設(shè) =β 。則應(yīng)有未知類型γ ，使得 S(α)=S(β→γ) 。 為此設(shè) α 語(yǔ)法樹的根節(jié)點(diǎn)為 n，并建立一個(gè)類型為 γ 的葉節(jié)點(diǎn)和一個(gè)類型為 β→γ 的新節(jié)點(diǎn) m。若 m與 n合一成功則其結(jié)果 γ 成為 。 m: →β γn: →s tderef(deref(q))的類型檢查 例 用算法 ()，對(duì) deref(deref(q))進(jìn)行類型檢查。 E→E 1(E2) { γ := mkleaf(newtypevar)。 unify(,mknode(39。→39。, ,γ) 。 := γ 。 } () |id { := fresh()。 } E5E1 ( E4 )deref E2 ( E3 )deref qE1 → deref =fresh()=pointer(α 0)→α 0 E2 → deref =fresh()=pointer(α 1)→α 1 E3 → q =fresh()=pointer(pointer(int)) E4 → E2(E3) =γ 1=pointer(int) E5 → E1(E4) =γ 0=int deref(deref(q))的類型檢查（續(xù) 1） 確定 ： 建立葉子 γ 1和→γ 1的新節(jié)點(diǎn) m： n2:→: 6pointer: 5α1:4pointer(α 1)→α 1 : n3:pointer: 9pointer: 8int: 7pointer(pointer(int)) : 合一 n2和 m，即unify(11, 6)： m : →: 11n3: pointer: 9 γ1: 10pointer: 8int: 7unify(11,6)union(11,6)→6unify(9,5) unfiy(10,4)union(9,5)→5 find(4)=8unify(8,4) union(10,8)→8union(8,4)→8得到 =pointer(int)： pointer: 5 pointer: 8int: 7m:→: 6: E4 → E2(E3) =γ 1=pointer(int) deref(deref(q))的類型檢查（續(xù) 2） 再確定 ： 建立葉子 γ 0和 →γ 0的新節(jié)點(diǎn) m39。： E5→E1(E4) pointer: 8 γ0: 13 m 39。 :→ : 12int: 7合一 n1和 m39。，即unify(12, 3)： n1:→: 3pointer: 2α0:1pointer(α 0)→α 0 : union(8,2)→2 find(1)=7unify(12,3)union(12,3)→3unify(8,2) unfiy(13,1)unify(7,1) union(13,7)→7union(7,1)→7得到 =int： pointer: 2int: 7 m 39。:→: 3有環(huán)類型的合一操作 real: 2→: 1real: 4→: 3→: 5real: 6union(1,5)→1unify(1,3)union(1,3)→1unify(2,4) unfiy(1,5)unify(2,6) unify(1,3)find(1)=find(3)real: 2→: 1→: 1real: 2結(jié) 束（ 2020年 5月 10日） ()與 () 聲明時(shí) id類型的確定 P → D。 E D → D。D D → id : T { addtype(entry(), )。} T → char { := char。 } () | integer { := integer。 } | ^T1 { := pointer()。} | array[num]of T1 { := array(, )。} 函數(shù)作為類型在語(yǔ)法上的描述： D → id : T { addtype(entry(), )。} () T → T1 → T2 { := → 。 } E → E1(E2) { := if =s and =s→t then t else type_error。 } 返回
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1