compiler [3] eval 運算式

思則睿，睿則聖。

本來打算先介紹 if/else, while, function call, function declare 的 ast 建構方式, 不過剛好完成 eval 運算式, 腦筋的記憶比較深刻, 先寫這篇。

在之前《compiler [1] - 四則運算》有提到, 在建構出 ast 之後, 再寫個 eval 就可以求出這個運算式的值了, 果真是說的比做的簡單, 道理雖然知道, 但在實作上, 我還是吃了不少苦頭。

經過了一個月我才開始做 eval 這功能, 在這一個月之間, 我思考還有什麼不足之處, 修修補補之後, 決定可以完成eval 這功能了, 這是思考之後的舉動, 並非興奮衝動下的實作。

首先 AST 的操作並不容易, tree 是一個很難處理的資料結構, 幾乎都要使用遞迴來對付它。eval 也是用了遞迴來實作。

eval 在不同的 ASTNode 上實作的程式碼不同, 例如 node: 3 只要單純回傳本身就可以; 而 node: + 則要呼叫 child node 左的 eval, child node 右的 eval, 再把兩個 node 回傳的結果做加法運算。

而 node 如果是 =, if, while, 更是有各式各樣的的實作, 由於我不是使用物件導向的寫法, 就是會有一堆 switich/case, if, 程式碼拉的很長, 我本來還想學習 SICP list-of-values, eval, apply 的實作, 發現有點困難, 老是不知道死在哪個遞迴過程中。

而使用物件導向寫法, 只要針對每個不同的 node, 直接實作其 eval 就可以, 不會有一堆 switch/case, if/else 寫法在其中。這會是比較好的寫法嗎? 嗯 ... 這是個困難的抉擇, 我目前不想用物件導向的作法, 雖然我用的是 c++。

astnode.cpp eval()

  1 #include "astnode.h"
  2 
  3 #include <map>
121 ASTNode* ASTNode::eval()
122 {
123   if (children_.size() == 0) // leaf node
124   {
125     if (ast_type() == NAME)
126     {
128       if (env.count(str()))
129       {
130         ASTNode *n = env[str()];
131         cout << "eval name '" << str() << "' : " << n->str() << endl;
132         return env[str()];
133       }
134       else
135         return this;
136     }
137     else
138       return this;
139   }
140   else
141   {
142     cout << "cur node: " << str() << endl;
143 
147     if (token_.str_ == "+" || token_.str_ == "-" || token_.str_ == "*")
148     {
149       if (children_.size() == 2)
150       {
151         ASTNode *c1 = children_[0]->eval();
152         cout << "xx cur: " << str() << endl;
153         cout << "c1: " << c1->str() << endl;
154         ASTNode *c2 = children_[1]->eval();
155         cout << "c2: " << c2->str() << endl;
156 
174 
192         int n1 = stoi(c1->str());
193         int n2 = stoi(c2->str());
194         int ret = 0;
195         if (token_.str_ == "+")
196           ret = n1 + n2;
197         if (token_.str_ == "-")
198           ret = n1 - n2;
199         if (token_.str_ == "*")
200           ret = n1 * n2;
201 
203         cout << "eval: " << n1 << " " << str() << " " << n2 << " = " << ret << endl;
204 
211         Token t(std::to_string(ret), NUMBER);
213         eval_result_ = new ASTNode(t);
214 
216         return eval_result_;
218       }

而目前這個版本是我改了好幾次之後覺得比較好的版本。單純求值倒不困難, 但我想表達每次在 eval 後的過程, 像是 list 1. 這樣。

所以需要改變 ASTNode 的內容, 這造成很多問題, 為了不要 memory leak, 要記得 delete 被 eval 置換後的 ASTNode, 這讓我大吃苦頭, 常常遇到 delete 不該砍掉的 ASTNode, 這時候就想到有 GC 的好了, 但是身為系統底層開發人員, 還是得面對這問題。

目前的作法是 eval 後會傳回一個 ASTNode*, 再由呼叫 eval 的程式碼去決定要不是取代目前的 node, 要取代目前的 node 自然就要先釋放該 node。之前有個版本是 eval 後, 直接傳回被取代的內容, 覺得這樣不是很好。

而我的多此一舉為自己帶來了麻煩, 在實作 while 的 eval 時, 由於我把計算結果取代掉, 所以再下一次的 while loop 時, 就無法在計算一次了。

ex: a=1 while (a<5) a=a+1;
第一次 while loop 就變成 a = 2, 再下一次還是執行 a=2, 這就不對了。

要怎麼處理這兩難的問題呢? 還沒想到好辦法。

eval 的順序是 (list 1 的行號):
L5 + 的 eval 會去執行 L8 左邊 + 的 eval(), 然後是 L11 * 的 eval(), 再回到 L8 右邊 + 的eval(), 若是 = 運算符號的話, 會比較特別, 談到環境的時候再說。

list 1. eval 1+2*3+(4+5);

 1    root
 2     |
 3    prog
 4     |
 5     +
 6  ___|___
 7  |     |
 8  +     +
 9 _|__  _|__
10 |  |  |  |
11 1  *  4  5
12   _|__
13   |  |
14   2  3
15 ret: 6, n1: 2, n2: 3
16 ===========================
17    root
18     |
19    prog
20     |
21     +
22  ___|___
23  |     |
24  +     +
25 _|__  _|__
26 |  |  |  |
27 1  6  4  5
28 ---------------------------
29 ret: 7, n1: 1, n2: 6
30 ===========================
31 root
32  |
33 prog
34  |
35  +
36 _|__
37 |  |
38 7  +
39   _|__
40   |  |
41   4  5
42 ---------------------------
43 ret: 9, n1: 4, n2: 5
44 ===========================
45 root
46  |
47 prog
48  |
49  +
50 _|__
51 |  |
52 7  9
53 ---------------------------
54 ret: 16, n1: 7, n2: 9
55 ===========================
56 root
57  |
58 prog
59  |
60  16
61 ---------------------------
62 ===========================
63 root
64  |
65 prog
66  |
67  16
68 ---------------------------
  

單純要做 eval 就比較簡單, 以 1 + 2 來說, 產生一個 3 的 ASTNode 就回傳, 很容易。L147 ~ L216 就在做這件事情, 程式碼看來就很簡單。遇到 + 時, 就去遞迴呼叫 eval children[0], children[1], 它們會回傳 1, 2, 再用 stoi 轉成 int 相加就結束。

花了好大功夫, 終於把計算機完成了。總共要做:

1. lexer
2. parser
3. eval