今天是 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.y
1 %{
2 #include <stdio.h>
3 #include <ctype.h>
4 #include <stdlib.h>
5 #include <unistd.h>
6
7 #include <string>
8 #include <vector>
9 #include <iostream>
10
11 using namespace std;
12
13 //#define YYSTYPE double
14 #define YYDEBUG 1
15
16
17 enum NodeType
18 {
19 IF_TYPE,
20 PLUS,
21 MINUS,
22 MUL,
23 DIV
24 };
25
26 //#define YYSTYPE AstNode
27
28 class AstNode
29 {
30 public:
31 AstNode(const string str):str_(str), val_(0)
32 {
33 }
34 string str_;
35 void set_val(const double val)
36 {
37 val_ = val;
38 }
39 int add_child(AstNode *n)
40 {
41 children_.push_back(n);
42 return 0;
43 }
44 double val_;
45 vector<AstNode *> children_;
46 private:
47 NodeType node_type_;
48 };
49
50 AstNode root{"root"};
51
52 static int cnt;
53
54 int yylex();
55 int yyerror(const char *s);
56 %}
57
58
59 %union
60 {
61 AstNode *node_;
62 double num_;
63 } 64
65 %token <num_> NUMBER
66 %token IF
67 %left '+' '-'
68 %left '*' '/'
69
70 %type <node_> expr selection_statement
71
72 %%
73
74
75 selection_statement: {}
76 | selection_statement IF '(' expr ')' '{' expr ';' '}' '\n'
77 {
78 // if (6-3) {2-(1+5);}
79 AstNode *n = new AstNode{"if"};
80 n->add_child($4);
81 n->add_child($7);
82 cout << "$4->str_: " << $4->str_ << endl;
83 cout << "$7->str_: " << $7->str_ << endl;
84
85 $$ = n;
86 root.add_child(n);
87
88 printf("new if/then node, cnt: %d\n", cnt);
89 ++cnt;
90 }
91
92 expr: NUMBER
93 {
94 AstNode *n = new AstNode{"num"};
95 n->set_val($1);
96 $$ = n;
97
98 }
99 | expr '+' expr
100 {
101 AstNode *n = new AstNode{"plus"};
102 n->add_child($1);
103 n->add_child($3);
104 cout << "$1.val: " << $1->val_ << endl;
105 cout << "$3.val: " << $3->val_ << endl;
106 $$ = n;
107 ++cnt;
108 }
109 | expr '-' expr
110 {
111 AstNode *n = new AstNode{"minus"};
112 n->add_child($1);
113 n->add_child($3);
114 cout << "$1.val: " << $1->val_ << endl;
115 cout << "$3.val: " << $3->val_ << endl;
116 $$ = n;
117 ++cnt;
118 }
119 | '(' expr ')'
120 {
121 $$ = $2;
122 }
123
124 %%
125 char *progname;
126 int lineno = 1;
127
128
129 int yylex()
130 {
131 int c;
132 while ((c=getchar()) == ' ' || c == '\t')
133 ;
134
135 if (c == EOF)
136 return 0;
137 if (c == '.' || isdigit(c) )
138 {
139 ungetc(c, stdin);
140 scanf("%lf", &yylval.num);
141 return NUMBER;
142 }
143
144 if (c == 'i')
145 {
146 int ch;
147
148 ch = getchar();
149 if (ch == 'f')
150 return IF;
151 else
152 {
153 ungetc(ch, stdin);
154 }
155 }
156
157 if (c == '\n')
158 ++lineno;
159 return c;
160 }
161
162 int warning(const char *s, const char *t)
163 {
164 fprintf(stderr, "%s: %s", progname, s);
165 if (t)
166 fprintf(stderr, " %s", t);
167
168 fprintf(stderr, " near line %d\n", lineno);
169 return 0;
170 }
171
172 int yyerror(const char *s)
173 {
174 return warning(s, 0);
175 }
176
177 void print_node(const AstNode *n)
178 {
179 cout << "n: (" << n->str_ << ", "<< n->val_ << ")" << endl;
180 for (auto i: n->children_)
181 {
182 print_node(i);
183 }
184 }
185
186 void print_tree(const AstNode *n)
187 {
188 if (n->children_.size() == 0) // leaf node
189 {
190 cout << "(" << n->str_ << ", "<< n->val_;
191 cout << ")";
192 }
193 else
194 {
195 cout << "(" << n->str_ << ", "<< n->val_;
196 for (auto i: n->children_)
197 {
198 print_tree(i);
199 }
200 cout << ")";
201 }
202
203 }
204
205
206 int main(int argc, char *argv[])
207 {
208 int opt;
209 progname = argv[0];
210
211 while ((opt = getopt(argc, argv, "d:h?")) != -1)
212 {
213 switch (opt)
214 {
215 case 'd':
216 {
217 yydebug = strtol(optarg, 0, 10);
218 if (yydebug == 1)
219 printf("enable bison debug mode\n");
220 break;
221 }
222 }
223 }
224
226 yyparse();
227 cout << "\\tree";
228 print_tree(&root);
229 cout << endl;
230 }
list 1 編譯指令
bison -y hoc_if_ast.y -o hoc_if_ast.cpp
g++ -g -std=c++17 -Wall hoc_if_ast.cpp -o hoc_if_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。
list 2. if (6-3) {2-(1+5);} 處理順序
1 if (6-3) {1+5;}
2 6
3 3
4 -
5 1
6 5
7 +
8 if minus plus
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
