花了两天的时间终于完成了Vczh Lazy Script的语法分析工作。语法分析是编译的第一步，旨在把输入的字符串（代码）分析称跟代码结构一致的语法树，以便后续工作。
藉着去年开发的Syngram工具包，这两天过得还算轻松，仅仅对语言做了一份配置，不过这份配置也花掉了1200多行代码。语法分析其余的部分是数据结构。目前的数据结构仅仅用于再现语言的结构，而没有附加任何的数据。接下来的工作是检查所有的identifier，看看有没有哪些identifier是使用错误的。一般来说都是在左值使用函数、类构造标签参数不全、转移运算符指向的函数并没有声明成函数等等比较基本的东西。但是后续的工作就相当地麻烦了。
作为一门lazy+pure的函数范式程序语言，我模仿了Haskell的大部分语法，加上自己的一点点修改（因为Haskell的语法实在是太诡异了），但是主要功能是没有变化的。等上面所说的identifier完成以后，我就要开始写Lazy的类型推导程序了。类型推导程序用于计算出代码中省略的类型声明，相当于把整份代码转换成类型方程然后求解。理论上解有无穷多个，因此需要找到一个最好的解。当然如果程序写错的话，也是有可能无解的，这个时候就需要处理错误信息了。
这个类型推导跟c#的var关键字还是相差很大的。Lazy语言的所有类型声明都允许省略，只要类型推导程序能够找到一个最好的类型解就可以了。譬如如下代码：
makelist num list = if (num<=0)
list
(makelist (num-1) ([num]++list));
makelist的意思其实很简单，如果你输入makelist 5 []的话，你就可以得到数组[1 , 2 , 3 , 4 , 5]。类型推导过程如下：
1：Lazy是强类型的（不允许任何隐式类型转换），所以为了让num<=0合法，num的类型就必须是Int。
2：因为[num]++list，所以list的类型必须是[Int]。
3：因为if的第二个参数是list，所以makelist的返回值是[Int]。
4：我们得到makelist的类型声明是makelist :: Int -> [Int] -> [Int]。
5：检查makelist (num-1) ([num]++list)，发现符合要求。找到一个最优解。
所以上述函数的类型就被确定了。而且因为上述函数的类型可以被如此确定，所以类型声明makelist::Int->[Int]->[Int]就可以被省略了。
除此之外Lazy还有其他各种各样的表达式，形式复杂多变，而且类型系统包含tuple（匿名struct）和复合类型（你可以定义一个量的类型是“整数或字符串”，因此这个变量就可以保存两种类型的数值了，而且Lazy也提供了获取这种量的内容的渠道）。这几天得好好计划一下。
在此贴一下目前语法分析的成果：
源程序：
1 module main exports
2 main
3 where
4 import System.IO;
5
6 qsort::Ord T,[T]->[T];
7 qsort [] = [];
8 qsort (x:xs) = left ++ [x] ++ right where
9 left = qsort [y|y<-xs,y<x];
10 right = qsort [y|y<-xs,y>=x];
11 end;
12
13 readints::[int]->IO [int];
14 readints ints = do
15 num <- read;
16 if (num<0)
17 (return ints)
18 (readints (ints++[nums]));
19 end;
20
21 main::IO unit;
22 main = do
23 ints <- readints;
24 write (qsort ints);
25 end;
26
27 end;
分析结果：
1 正在读取文件
2 正在构造自动机
3 正在分析代码
4 module main {
5 exports {
6 main
7 }
8 declarations {
9 import System.IO
10 funchead main :: (IO unit)
11 funcbody main {
12 parameters {
13 }
14 do {
15 left-exp {
16 ints
17 readints
18 }
19 invoke {
20 write
21 invoke {
22 qsort
23 ints
24 }
25 }
26 }
27 }
28 funchead qsort :: Ord T, ([T] -> [T])
29 funcbody qsort {
30 parameters {
31 list {
32 }
33 }
34 list {
35 }
36 }
37 funcbody qsort {
38 parameters {
39 cons {
40 x
41 xs
42 }
43 }
44 where {
45 invoke {
46 invoke {
47 ++
48 invoke {
49 invoke {
50 ++
51 left
52 }
53 list {
54 x
55 }
56 }
57 }
58 right
59 }
60 declarations {
61 funcbody left {
62 parameters {
63 }
64 invoke {
65 qsort
66 array builder {
67 y
68 constructors {
69 left-exp {
70 y
71 xs
72 }
73 invoke {
74 invoke {
75 <
76 y
77 }
78 x
79 }
80 }
81 }
82 }
83 }
84 funcbody right {
85 parameters {
86 }
87 invoke {
88 qsort
89 array builder {
90 y
91 constructors {
92 left-exp {
93 y
94 xs
95 }
96 invoke {
97 invoke {
98 >=
99 y
100 }
101 x
102 }
103 }
104 }
105 }
106 }
107 }
108 }
109 }
110 funchead readints :: ([int] -> (IO [int]))
111 funcbody readints {
112 parameters {
113 ints
114 }
115 do {
116 left-exp {
117 num
118 read
119 }
120 invoke {
121 invoke {
122 invoke {
123 if
124 invoke {
125 invoke {
126 <
127 num
128 }
129 0
130 }
131 }
132 invoke {
133 return
134 ints
135 }
136 }
137 invoke {
138 readints
139 invoke {
140 invoke {
141 ++
142 ints
143 }
144 list {
145 nums
146 }
147 }
148 }
149 }
150 }
151 }
152 }
153 }
154
今天就写到这里了。看看电影休息一下……
posted on 2008-04-22 04:03
陈梓瀚(vczh) 阅读(2523)
评论(4) 编辑 收藏 引用 所属分类:
Vczh Lazy Script