人體汽肛 - 風馳電掣, 人車一體: yacc/bison 系列 (2)

今天是 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:

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

blog 文章

2022年2月1日星期二

yacc/bison 系列 (2) - 輸出 AST, if statement

沒有留言:

張貼留言

blog 文章

2022年2月1日 星期二

yacc/bison 系列 (2) - 輸出 AST, if statement

沒有留言:

張貼留言

2022年2月1日星期二