花了兩天的時間終于完成了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) 閱讀(2577)
評論(4) 編輯 收藏 引用 所屬分類:
Vczh Lazy Script