經過了5個小時的艱苦奮斗，符號表終于計算出來了，而且也做了一部分語法分析。接下來的工作是類型推導。今天的結果如下。
為了檢查符號表，特意在昨天的程序里面加入了以下代碼：
1 data pair T1 T2 = pair T1 T2
2 type environment
3 type IO T = environment -> pair T environment
4 type string = list char
5 type TypeOfPrint = string -> IO void
語法改了一下，讓data用于定義新類型，而type用于重命名類型。然后加上了module和import子句。
符號表包含了類型重命名、data構造函數名、函數名以及表達式名四種類型。其中表達式名用于模式匹配的時候產生的新符號。然后讓所有的符號表構成了一個有向圖。在這個圖中，節點的符號在引用了它的節點中是可見的。在構造這個圖的過程當中順便解決了import循環的問題。
然后遍歷表達式，得到了完整的符號表。每當有新符號產生的地方就構造新的節點。符號表完成之后，同時也確保了整個程序中所有表達式中的名字都是已經定義過的。于是輸入昨天的程序，得到如下結果。
首先，編譯器自己產生一個API語法樹：
1 module system
2 type void
3 type int
4 type char
5 data bool = (false | true)
6 data list T = (empty | (list T (list T)))
7 func iadd :: (int -> (int -> int)) alias "iadd"
8 func isub :: (int -> (int -> int)) alias "isub"
9 func imul :: (int -> (int -> int)) alias "imul"
10 func idiv :: (int -> (int -> int)) alias "idiv"
11 func imod :: (int -> (int -> int)) alias "imod"
12 func ilg :: (int -> (int -> bool)) alias "ilg"
13 func ism :: (int -> (int -> bool)) alias "ism"
14 func iequ :: (int -> (int -> bool)) alias "iequ"
15 func chr :: (int -> char) alias "chr"
16 func ord :: (char -> int) alias "ord"
然后，讀入代碼。下面是格式化后的結果：
1 module main
2 import system
3
4 data pair T1 T2 = (pair T1 T2)
5
6 type environment
7
8 type IO T = (environment -> (pair T environment))
9
10 type string = (list char)
11
12 type TypeOfPrint = (string -> (IO void))
13
14 func not :: (bool -> bool)
15 def not a =
16 select a of
17 case true : false
18 case false : true
19 end
20
21 func and :: (bool -> (bool -> bool))
22 def and a b =
23 select a of
24 case true : b
25 case false : false
26 end
27
28 func or :: (bool -> (bool -> bool))
29 def or a b =
30 select a of
31 case true : true
32 case false : b
33 end
34
35 func xor :: (bool -> (bool -> bool))
36 def xor a b =
37 select a of
38 case true : (not b)
39 case false : b
40 end
41
42 func if T :: (bool -> (T -> T))
43 def if cond t f =
44 select cond of
45 case true : t
46 case false : f
47 end
48
49 func ineg :: (int -> int)
50 def ineg num = ((isub 0) num)
51
52 func coffset :: (char -> (int -> char))
53 def coffset c i = (chr ((iadd (ord c)) i))
54
55 func itoa :: (int -> (list char))
56 def itoa a = (((if ((iequ a) 0)) ((list '0') empty)) (((if ((ism a) 0)) ((list '-') (itoa (ineg a))))
57 (let
58 func _itoa :: (int -> ((list char) -> (list char)))
59 def _itoa a chs =
60 select a of
61 case 0 : chs
62 else : ((_itoa ((idiv a) 10)) ((list ((coffset '0') ((imod a) 10))) chs))
63 end
64 in((_itoa a) empty))))
65
66 func atoi :: ((list char) -> int)
67 def atoi chs =
68 select chs of
69 case empty : 0
70 case ((list '-') chs) : (ineg (atoi chs))
71 case ((list c) chs) : ((iadd ((imul 10) ((isub (ord c)) (ord '0')))) (atoi chs))
72 end
經過一些檢查并得到符號表之后，就有了如下的結果：
1 【ID表】
2 module main::main
3 import system
4 type IO T = (main.environment -> (main.pair <T> main.environment))
5 type TypeOfPrint = ((system.list system.char) -> (main.environment -> (main.pair system.void main.environment)))
6 type environment
7 type pair T1 T2
8 type string = (system.list system.char)
9 ctor pair = <T1> -> <T2> -> type pair T1 T2
10 func and :: (system.bool -> (system.bool -> system.bool)) codefrom 8
11 func atoi :: ((system.list system.char) -> system.int) codefrom 22
12 func coffset :: (system.char -> (system.int -> system.char)) codefrom 18
13 func if T :: (system.bool -> (<T> -> <T>)) codefrom 14
14 func ineg :: (system.int -> system.int) codefrom 16
15 func itoa :: (system.int -> (system.list system.char)) codefrom 20
16 func not :: (system.bool -> system.bool) codefrom 6
17 func or :: (system.bool -> (system.bool -> system.bool)) codefrom 10
18 func xor :: (system.bool -> (system.bool -> system.bool)) codefrom 12
19 【ID表】
20 module main::main.0
21 import main
22 name a
23 【ID表】
24 module main::main.1
25 import main
26 name a
27 name b
28 【ID表】
29 module main::main.2
30 import main
31 name a
32 name b
33 【ID表】
34 module main::main.3
35 import main
36 name a
37 name b
38 【ID表】
39 module main::main.4
40 import main
41 name cond
42 name f
43 name t
44 【ID表】
45 module main::main.5
46 import main
47 name num
48 【ID表】
49 module main::main.6
50 import main
51 name c
52 name i
53 【ID表】
54 module main::main.7
55 import main
56 name a
57 【ID表】
58 module main::main.7.0
59 import main.7
60 func _itoa :: (system.int -> ((system.list system.char) -> (system.list system.char))) codefrom 1
61 【ID表】
62 module main::main.7.0.0
63 import main.7.0
64 name a
65 name chs
66 【ID表】
67 module main::main.8
68 import main
69 name chs
70 【ID表】
71 module main::main.8.1
72 import main.8
73 name chs
74 【ID表】
75 module main::main.8.2
76 import main.8
77 name c
78 name chs
79 【ID表】
80 module system::system
81 type bool
82 type char
83 type int
84 type list T
85 type void
86 ctor empty = type list T
87 ctor false = type bool
88 ctor list = <T> -> (system.list <T>) -> type list T
89 ctor true = type bool
90 func chr :: (system.int -> system.char) alias chr codefrom -1
91 func iadd :: (system.int -> (system.int -> system.int)) alias iadd codefrom -1
92 func idiv :: (system.int -> (system.int -> system.int)) alias idiv codefrom -1
93 func iequ :: (system.int -> (system.int -> system.bool)) alias iequ codefrom -1
94 func ilg :: (system.int -> (system.int -> system.bool)) alias ilg codefrom -1
95 func imod :: (system.int -> (system.int -> system.int)) alias imod codefrom -1
96 func imul :: (system.int -> (system.int -> system.int)) alias imul codefrom -1
97 func ism :: (system.int -> (system.int -> system.bool)) alias ism codefrom -1
98 func isub :: (system.int -> (system.int -> system.int)) alias isub codefrom -1
99 func ord :: (system.char -> system.int) alias ord codefrom -1
這張表中的每一個type的定義都被充分地展開，每一個data的構造函數(ctor)的引用也被分析出。函數的類型也被展開，codefrom代表函數的代碼所在的原語法樹的某個位置中。
那寫名字是XXX.1.2.3的是函數體、lambda表達式或case里面的子表。因為這三中表達式產生了新的符號。可以通過讀取import節來還原出整個圖的樣貌。這個圖是沒有環的，也就是說可以用智能指針安全方便地管理。注意看那些有name節的符號表，要么是函數參數，要么是case中用于記錄子模式表達式的新符號。還有一些帶有func、ctor和type的則是let in表達式產生的新符號。
posted on 2008-10-02 07:46
陳梓瀚(vczh) 閱讀(1713)
評論(1) 編輯 收藏 引用 所屬分類:
腳本技術