经过了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) 阅读(1680)
评论(1) 编辑 收藏 引用 所属分类:
脚本技术