compiler [2] - 四則運算 + 運算符號優先法

藜羹麥飯冷不嘗，要足平生五車書。

運用 BNF 可以為運算符號制定優先權, 這帶來了一些問題, 若臨時要加入一個 BNF 規則, 很可能 parser 程式碼會需要某種程度的改寫。

以前一個例子來說, 目前只有 +-*/, 若還要 =, >, >=, -, !, %, ^, &, * 還有左結合、右結合, 那可能會加入不少 BNF 規則, 只要 BNF 規則變了, 程式就要改寫了。因為不是用 yacc/bison, 所以改變規則對手工撰寫的 parser 會有一些影響, 原本對的東西可能就改錯了。

《两周自制脚本语言》介紹了優先權運算的方法來避免這個問題。這樣可以讓程式變得很簡單, 但要理解其中的 recursive function 就沒那麼容易。

BNF rule 只要這兩條:

list 1. 4op_precedence 4op rule

1 factor: NUMBER | "(" expression ")"
2 expression: factor { OP factor}

term 的部份可被移除了。原理是這樣:
1 + 2 * 3
在讀取到 + 時, 還要往下繼續讀到 *, 這樣才能知道到底是 1+2 先做, 還是 2*3 先做, 當有了 +, * 之後, 就去判斷 +, * 的優先順序, 然後產生對應的 ASTNode。

請參閱 https://github.com/descent/simple_compiler/blob/func_call/parser_4op.cpp

• expression()
• do_shift()
• next_op()

在紙上畫過一次流程或是用 debugger 跑過一次, 應該就清楚了。我得承認, 沒有書上的範例, 要自己寫出這個不容易。

在追完 1 + 2 * 3 後, 我建議再追 x == 1 + 2 * 3 + 5, 這樣應該就清楚了。

程式碼還真的不好解釋。

結果

 1 descent@u64:simple_compiler$ cat e1
 2 x == 1+2*3+5
 3 descent@u64:simple_compiler$ ./parser_4op < e1  | ~/git/progs/tree/tree/tree
 4 ast node type: EQUAL
 5 ( == x ( + ( + 1 ( * 2 3 ))5 ))
 6  ==
 7 _|__
 8 |  |
 9 x  +
10   _|__
11   |  |
12   +  5
13  _|__
14  |  |
15  1  *
16    _|__
17    |  |
18    2  3

只要克服了那個 recursive function, 就可以享受到 precedence 的便利。