人體汽肛 - 風馳電掣, 人車一體: compiler [1]

螣蛇無足而飛,梧鼠五枝而窮。

parser 是第二個難關, 這個比 lexer 難了不止一點, 放張更好看的圖來吸引你的注意。

從計算機開始是個不錯的想法, 幾乎在每個平台上都可以看到計算機, 不過要寫出計算機程式可沒那麼簡單, 如果你感覺不出來計算機的難度, 你不是高手就是一個新手。

UNIX 编程环境 (Brian W.Kernighan, Rob Pike) 第八章在談一個計算機怎麼寫, 其中使用了 lex, yacc。

Bjarne Stroustrup 寫的 Programming: Principles and Practice using C++ (這本有 Second Edition, 談及 c++11, c++14) 6, 7 章也在談怎麼寫一個計算機, 沒有使用 lex/yacc。C++ 程序设计原理与实践 (Programming: Principles and Practice using C++ 的簡體中文版本 - 第一版) p109 提到: 「這是 50 年來的經驗, 想要一夜打破 50 年來的經驗不是個好主意。」

Bjarne Stroustrup 花了兩章說明這個計算機程式, 你就知道這不簡單了。

parser 有 yacc/bison 可用, 不過這樣在學習 compiler 的道路上就走了捷徑, 會在技能圖上少一塊拼圖, 所以還是手工打造一個來學習。

寫個印出 hello world 程式的難度若是 1, 計算機的難度可能是 100。所以寫不出來不可恥, 經典程式就和數學題目一樣, 有很多的難題, 有興趣再來學習就好。寫計算機程式有好幾個方法, 有一種是使用 stack, 本篇要介紹的是和 compiler 相關的技術, 所以會有 EBNF 這樣的規則。

list 1. L1 ~ 3 是四則運算的 EBNF, 就是 3 條這麼簡單, 但要看懂他就沒這麼簡單了, 而要自己寫出來這 3 條規則那就更難了。被 {} 包起來的表示可以 0 ~ 多個, | 就《或》囉! 參考 fig 1 的 EBNF 符號。

list 1. 4op rule

1 factor: NUMBER | "(" expression ")"
2 term: factor { ("*" | "/") factor}
3 expression: term {("+" | "-") term}

fig 1. EBNF

轉成程式碼大概規則
| -> if (xxx) {} else {}
{} -> while (xxx) {}

list 2 使用 LL parser 的 recursive descent (不好意思, 沾光了) 方法, 以 list 1 的 EBNF 為例:

list 2. pseudo code

factor()
{
  if NUMBER -> return ASTNode(NUMBER)
  if "("
    expression()
  if_end ")"
}

term()
{
  factor()
  while(* | /)
    factor()
}

expression()
{
  term()
  while( + | - )
    term()
}

pseudo code 很簡單, 把他們變成真的 c++ 程式就很難了。但是 pseudo code 可以幫我們思考, 我在 A4 紙上畫了很多圖, 才理解這個簡單的 recursive function, 想出這方法的人真是天才。

目標是什麼呢? 不是要計算出來, 而是要產生 AST:
e1.tree 紅色就是 AST 的樣子, 本來我很煩惱要怎麼印出 AST, 還好有之前寫 map 的經驗, 需要用到 tree, 參考

https://github.com/descent/progs/tree/master/tree

/parser_4op < e1 | ~/git/progs/tree/tree/tree

可以看到漂亮的樹狀圖形, ref L205 ~ L207 程式碼, 能夠印出 AST, 才能對所謂的 AST 有了形象上的理解。

這是 Greg Lee 寫的 The Tree Preprocessor, 用起來像這樣, 所以要想辦法印出 \tree(abc()(def()(xyz(lmn()())()))), 就可以透過 Tree Preprocessor 印出漂亮的樹狀圖形, 這個 Tree Preprocessor 說不定還比較難寫。

echo "\tree(abc()(def()(xyz(lmn()())())))" | ~/git/progs/tree/tree/tree

而 1+2 得先用 lexer 把他切成 1, +, 2 這 3 個 token, 再餵給這些 rule function。和 lexer 類似, 一樣要有預先讀取的能力, 用 vector<token> 很容易就可以完成這樣的操作, 甚至可以預先讀取多個, 也就是 LL(k)。

例如 1, +, 2, 目前讀到 1, 但我可能得先把 + 讀進來, vector<token> 可以很輕易的幫助我們, 這是好處也是壞處, 用 c 的朋友就要先打造類似的資料結構。

對 vector<token> 有兩種操作:
peek_token(): 從 vector<token> 讀取一個 token, 但不從 vector<token> 移掉這個 token。
pop_token: 從 vector<token> 的最開始位址讀取一個 token, 並移掉這個 token。

這就是預先讀取的相關操作。

用 c 的朋友沒有 vector<token> 可用怎麼辦? 雖然我用 c++, 但有時候不得不用 c 時, 也得為自己想辦法。

簡單的辦法: token[] array 的大小記得開大點。
困難的辦法: 先寫個類似 vector 的資料結構。

e1.tree

 0 1+2
 2 token: 1
 3 token: +
 4 token: 2
 5 ast node type: ADD
 6 ( + 1 2 )
 7  +
 8 _|__
 9 |  |
10 1  2

e2.tree

 1 5*6
 2 token: 5
 3 token: *
 4 token: 6
 5 ast node type: MUL
 6 ( * 5 6 )
 7  *
 8 _|__
 9 |  |
10 5  6

e3.tree, e4.tree 可以看到, 要先計算的都會長在 AST 的下方。

e3.tree

 1 1+2*3
 2 token: 1
 3 token: +
 4 token: 2
 5 token: *
 6 token: 3
 7 ast node type: ADD
 8 ( + 1 ( * 2 3 ))
 9  +
10 _|__
11 |  |
12 1  *
13   _|__
14   |  |
15   2  3

e4.tree

 1 (1+2)*3
 2 token: (
 3 token: 1
 4 token: +
 5 token: 2
 6 token: )
 7 token: *
 8 token: 3
 9 ast node type: MUL
10 ( * ( + 1 2 )3 )
11   *
12  _|__
13  |  |
14  +  3
15 _|__
16 |  |
17 1  2

ASTNode 是很簡單的 tree node, 只要把所需要的 ASTNode 回傳, 就會長成 AST 了。

parser_4op.cpp

  1 #include <cstdio>
  2 #include <string>
  3 #include <cctype>
  4 
  5 #include <iostream>
  6 #include <deque>
  7 #include <map>
  8 #include <string>
  9 
 10 using namespace std;
 11 
 12 #include "astnode.h"
 13 #include "parser.h"
 14 #include "token.h"
 15 #include "op.h"
 16 
 18 
 19 std::map<std::string, Precedence*> operators;
 20 
 21 extern std::deque <Token> tokens;
 22 
 24 
 25 Token peek_token()
 26 {
 27   if (tokens.size() == 0)
 28     return invalid_token;
 29   else
 30     return tokens[0];
 31 }
 32 
 33 Token pop_token()
 34 {
 35   if (tokens.size() == 0)
 36     return invalid_token;
 37   else
 38   {
 39     Token t = tokens.front();
 40     tokens.pop_front();
 41     return t;
 42   }
 43 }
 44 
 45 bool is_token(const std::string &str)
 46 {
 47   Token t = peek_token();
 48   if (t.str_ == str)
 49     return true;
 50   else
 51     return false;
 52 }
 53 
 54 
 55 ASTNode* factor()
 56 {
 57   Token token = peek_token(); 
 58   if (token.str_ == "(")
 59   {
 60     Token t = pop_token();
 61     ASTNode *e = expression();
 62     t = pop_token();
 63     if (t.str_ != ")")
 64     {
 65       cout << "fail: should ')'" << endl;
 66       exit(1);
 67     }
 68     return e;
 69   }
 70   else if (token.type_ == NUMBER || token.type_ == NAME) // number || variable name
 71        {
 72          Token t = pop_token();
 73          return new ASTNode(t);
 74        }
 75        else
 76        {
 77        }
 78   return 0;
 79 }
 80 
 81 ASTNode* term()
 82 {
 83   ASTNode *left = factor();
 84   while(is_token("*") || is_token("/"))
 85   {
 86     Token t = pop_token();
 87     ASTNode *op = new ASTNode(t);
 88     ASTNode *right = factor();
 89     op->add_child(left, right);
 90     left = op;
 91   }
 92 
 93   return left;
 94 }
 95 
166 /*
167  *  factor: NUMBER | "(" expression ")"
168  *  term: factor { ("*" | "/") factor}
169  *  expression: term {("+" | "-") term}
170  */
171 
172 ASTNode* expression()
173 {
174   ASTNode *left = term();
175   while(is_token("+") || is_token("-"))
176   {
177     Token t = pop_token();
178     ASTNode *op = new ASTNode(t);
179     ASTNode *right = term();
180     op->add_child(left, right);
181     left = op;
182     // left = new ASTNode(left, , right);
183   }
184 
185   return left;
186 }
187 
190 
191 #ifdef DEBUG_PARSER
192 int main(int argc, char *argv[])
193 {
198 
199   int lexer();
200   lexer(); 
201   ASTNode* root = expression();
202   cout << "ast node type: " << root->type_str() << endl;
203   root->print();
204   cout << endl;
205   cout << "\\tree"
206   root->print_tree();
207   cout << endl;
227   return 0;
228 }
229 #endif

完整 source code (不要定義 OP_PRECEDENCE):
https://github.com/descent/simple_compiler/blob/master/parser_4op.cpp

有了 AST 後, 對每個 node 作 eval 就可以算出值了, 我不急著做這個, 因為我在 simple scheme 已經做過了, simpe scheme 的經驗給我很大的幫助, 有注意到我還將 AST 以 preorder 方式印出來嗎? 最最差的作法就是把這個丟到 simple scheme 去, 就算出該式子的值了。

所以要懂:

lexer
parser
eval AST

才能寫出計算程式, 我沒騙你吧, 真的很難。如果還要加上定義變數, 難度再加上 30 吧! 要能定義變數需要導入「環境」這個東西。

如果用 stack 可能難度降為 50 吧?

中國有個 vczh，本名陳梓瀚, 個人信息介紹上寫有「專業造輪子」, 所以江湖人稱「輪子哥」。你一定看到很多類似的說法, 幹嘛自己造輪子呢? 造不造輪子你自己決定, 我還蠻喜歡造輪子的, 縱使造出來的是破輪子。

在 AST 的設計上, 《两周自制脚本语言》使用了~~面向對象~~ (這詞怎麼看怎麼不對) 物件導向來完成 AST, 我很猶豫要不要用物件導向的方法, 他是用 java 沒得選, 我是用 c++, 有得選, 有時候選擇太多也是個煩惱, 最後憑著 simple scheme 的經驗, 我沒用上 OO, 我用了被人家詬病的 switch/case 來寫 AST 這部份的程式。

simple compiler 暫時沒有考慮 bare-metal 的版本, 我沒有太多顧慮, oo, template, exception handle, 標準程式庫的東西我都可以盡情使用, 不過為了不同 ASTNode 要寫很多不同的 class 好像沒有必要 (以 simple compier 來說), 就先這樣了。

四則運算的 AST 你很常看到, if/else 的看過嗎? while 的呢? function declare? function call 呢?

希望 fig 2 的結果能讓你興奮, 寫出這個時, 我 high 上一整天, 不過 while 那部份有點問題, 我一直到寫了 eval while 才發現。加油, 從這關到 fig 2 還有點遠哦!

fig 2

人體汽肛 - 風馳電掣, 人車一體

blog 文章

2016年6月6日星期一

compiler [1] - 四則運算

沒有留言:

張貼留言

blog 文章

2016年6月6日 星期一

compiler [1] - 四則運算

沒有留言:

張貼留言

2016年6月6日星期一