今天是 2022/2/1 是農曆 2022 大年初一, 照例發篇文章來慶祝一下。
 |
| 黑暗越是深邃, 顯現出來的光芒就越是璀璨耀眼 |
可以 eval if statement 之後, 我想要印出 if AST, 這個比 eval if statement 還要難。本來應該先寫 eval if statement, 但是我剛做完 if AST, 印象深刻, 先發此文。
找了 ref 列出的參考資料, 看過之後還是覺得難, 程式太完整, 不容易看, 在我自己的經驗中, 教學文必須要簡單, 怎麼樣才能簡單, 拆解, 所以我這篇只做 「if statement」加上「四則運算」, 當然如果只做「四則運算」的 ast 會更簡單, 但 ... 就讓我偷懶一下。
然後範例程式也簡單, 一個檔案就包含全部, 再來是編譯指令也要提供, 這樣看的人才能完整測試。
範例程式雖然簡單, 但不代表這個主題很簡單, bison 我挑戰好幾次了, 直到這次才有一點小進展, 我相信 bison 帶來的回報是可觀的, 所以我願意花時間在上面。
搭配參考資料的範例加上我自己一步一步分析之後, 終於搞出一個版本, 很簡單, 只針對 if statement, 本來更簡單應該要先嘗試四則運算, 但這次我懶得從這裡開始, 跳個一小步, 從「if statement」加上「四則運算」開始。
所謂的一步一步分析是什麼麼意思? 就是修改 bison 檔案之後, 觀察輸出的 .cpp 是長什麼樣, 會有哪些資料結構, 文法規則的程式碼怎麼執行, 推敲出這些執行順序。
我有自信這個範例是最小集合, 只有一個 .y 檔案, 也很容易理解, 程式也沒用上什麼難懂的技巧, 使用 c++ 來搭配 bison, bison 原本是和 c 搭配使用, 但 c++ 憑藉了與 c 的相容性, 輕鬆搭上 bison 列車, 也順便展示 bison 和 c++ 的搭配。c++ 也來到了 c++20 的標準, 還沒能搭上 c++20 的列車, 目前學的 c++ 技能還算夠用。fig 1 是我辛苦後的成果, 當然比之前手工寫法輕鬆很多。
parser 是什麼意思呢? 就是根據輸入的字串分析之後產生對應的動作, 以 if statement 來說:
if (6-3) {2-(1+5);}
分析之後要做什麼動作?
得到 -4 嗎? 不一定哦, 像我是想得到一個 ast, 我並不想 eval 這個敘述句。另外也可能輸出某個機器的組合語言來完成這個 if statement, 這是 bison 另外一個難的地方, bison 幫你處理文法了, 你要怎麼寫程式達到你要的目的呢? 只是要求值 -4 簡單很多。
 |
| fig 1. 使用 bison 輸出 AST |
執行 hoc_if_ast 輸入 if (6-3) {2-(1+5);} 就可以看到結果, 如果要輸出 fig 1 的樹狀圖, 需要 tree 這個工具, 之前也介紹過了。
hoc_if_ast.y L28 定義一個 class AstNode, 用來處理 ast node, 之前做過, 弄個簡化版, 這個要怎麼用呢? 在規則內指定給 $$, 問題來了, $$ 要怎麼指定成 AstNode type, 目的想做 $$ = new AstNode 這樣。
hoc_if_ast.y L59 ~ 63, L70 就是在做這件事, 把 node_ type 也就是 AstNode 指定給 expr, selection_statement 這些規則, 之前一直搞不懂 %type 的意思, 原來是這樣用。
NUMBER 這個希望 $1 是 double type, 得用 hoc_if_ast.y L65 token 語法來定義。
65 %token <num_> NUMBER
59 %union
60 {
61 AstNode *node_;
62 double num_;
63 }
70 %type <node_> expr selection_statement
對照 bison 寫法轉出來的 c++ code。
92 expr: NUMBER
93 {
94 AstNode *n = new AstNode{"num"};
95 n->set_val($1);
96 $$ = n;
98 }
轉出的 c++ code。
1202 case 4: /* expr: NUMBER */
1203 #line 93 "hoc_if_ast.y"
1204 {
1205 AstNode *n = new AstNode{"num"};
1206 n->set_val((yyvsp[0].num_));
1207 (yyval.node_) = n;
1209 }
有點感覺了吧, 來看看 yyvsp, yyval type 是什麼? YYSTYPE, 這個 YYSTYPE 是什麼? hoc_if_ast.y L59 ~ L63 union 定義出來的資料結構。
181 /* Value type. */
182 #if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED
183 union YYSTYPE
184 {
185 #line 60 "hoc_if_ast.y"
186
187 AstNode *node_;
188 double num_;
189
190 #line 191 "hoc_if_ast.cpp"
192 };
再來看看 if (6-3) {2-(1+5);} bison 是怎麼處理的, 參考 list 2。
bison 會依序處理 6, 3, -, 1, 5, +, if, 所以想法是這樣, 在處理 6 的地方, 產生一個 6 的 AstNode, 在 3 的地方產生一個 AstNode, 在 - 的地方產生一個 - AstNode 並把 6, 3 這 2 個 AstNode 加入到 - AstNode。這個就是四則運算的 AST。
加入 if statement 之後, 麻煩的是怎麼把這個 - AstNode 接到 if AstNode 的子 node。我是看了參考資料的程式碼才知道要這麼寫的, 但我想不透為什麼是這樣。
不過也不用想的太複雜, 反正 $$ 就是規則的傳回值, 我在 expr '+' expr 回傳 + node, expr '-' expr 回傳 - node, selection_statement IF '(' expr ')' '{' expr ';' '}' '\n' 也照樣做就好, $4 就是 - node, $7 就是 + node, 不用管 bison 是怎麼做的, 然後把 - node 放在第一個子 node, then 的部份放在第二個子 node, 如果有 else 的話就放在第三個子 node, 這樣就搞定了。
使用 gdb debug bison 產生的 .c 或是 .cpp 時, 吃到的 source file 是 .y, 有時候你可能不想這樣, 想要對應的是 .c 或是 .cpp 檔案, 這時候可以在 bison 使用 -l, bison 就不會產生 #line, 這樣 gdb 的 source file 就會是 .c 檔。
另外, 使用 --graph 就可以輸出 .dot 檔案, 搭配 dot 這個工具, 就可以輸出一個 svg 圖, 展示 bison grammer 是如何工作的。使用以下指令就可以輸出對應的圖檔。
dot -Tpng hoc_if_ast.dot -o hoc_if_ast.png
dot -Tsvg hoc_if_ast.dot -o hoc_if_ast.svg
最後來談談這個 if 文法規則, 這是我胡亂自己湊出來的, 不是正規的文法, 不過由於符合我的需求, 就這麼用了。參考連結 3 提供了 if 文法規則, 可以參考看看。
ref:
-
How to use C++ with Bison, V 1.0.2
- How to create an abstract syntax tree while parsing an input stream.
- if 陳述式 (C)
-
5 The Bison Parser Algorithm
-
8 Debugging Your Parser
