yacc/bison 系列 (3) bison 與 c++

千丈之堤, 以螻蟻之穴潰

「yacc/bison 系列 (2) - 輸出 AST, if statement」展示了 bison 和 c++ 的用法, 雖然可以用, 但不算是正式的用法, bison 有「支援真正的 c++」用法, 輸出的 parser 是 c++ 版本, 還跟上 c++20 的標準, 對於我這個 c++ 愛好者來說, 這樣很棒。

但是我不會用 ...

好不容易花了很大的力氣才有點會用 bison, 突然要改用 c++ 版本, 又要突破一些障礙才行, 感覺又要重學。我真的應該為了使用 c++ 而去學習嗎?

而且網路上的文章很少這樣用, 用 bison, c++ keyword 找到的文章, 大部份找到和 c++ 的搭配都是我之前的那種用法; 另外的就是 bison 文件裡頭的 c++ 說明 - 10.1.1 A Simple C++ Example

還有範例: https://github.com/akimd/bison/tree/master/examples/c%2B%2B

bison 文件除了 c++ 還有 d, java 的說明。

其中的 calc++ 範例從 bison 弄出可以編譯的版本有點麻煩, 我直接把 calc++ 這個範例放在 bitbucket。

另外找到這篇: Flex and Bison in C++

flex 也有個輸出 c++ lexer 的版本, 組合下來的情況有點亂, 都不知道怎麼相互搭配了。另外還有一個 bisoncpp, 讓情況更複雜了。

以 calc++ 來說明 flex/bison 怎麼搭配使用。bison 輸出的是 c++ code parser, flex 輸出的是 c++ code, 但不是 class 版本的 yylex(), 然後使用的 yylex() prototype 是 yy::parser::symbol_type yylex(driver& drv), 看傳回值的部份, 不是原本的 int, 所以這邊用了

driver.hh

26 // Give Flex the prototype of yylex we want ...
27 # define YY_DECL \
28   yy::parser::symbol_type yylex (driver& drv)
29 // ... and declare it for the parser's sake.
30 YY_DECL;

這樣會就使用 yy::parser::symbol_type yylex() 而不是 int yylex(), 那一定要用 yy::parser::symbol_type yylex(), 不能用 int yylex() 嗎? 看起來是不行, 如果可以 return token::NUMBER 也許還可以, 不過 list 1 定義的 enum 是被放在 class private, 所以無法直接存取, 還是得透過 make_XXXX 來使用這些 token enum, 就算可以好了, 也沒有 yylval 來把 yylex 的 token 傳給 bison。補充的 hoc_cpp_1.yy 勉強可以這樣用。

list 1. hoc_cpp.cpp

 695     /// Token kinds.
 696     struct token
 697     {
 698       enum token_kind_type
 699       {
 700         YYEMPTY = -2,
 701     END_OF_FILE = 0,               // END_OF_FILE
 702     YYerror = 256,                 // error
 703     YYUNDEF = 257,                 // "invalid token"
 704     NUMBER = 258,                  // NUMBER
 705     ASSIGN = 259,                  // ":="
 706     MINUS = 260,                   // "-"
 707     PLUS = 261,                    // "+"
 708     STAR = 262,                    // "*"
 709     SLASH = 263,                   // "/"
 710     LPAREN = 264,                  // "("
 711     RPAREN = 265,                  // ")"
 712     NEWLINE = 266                  // "\n"
 713       };

目前我遇到的困境是, 使用 bison 輸出 c++ parser 的版本, 不知道怎麼和 flex 輸出的 lexer 搭配。原本的 c parser 是搭配 int yylex(), 但是 c++ parser 是搭配 parser::symbol_type yylex(), 我目前還不知道怎麼用 flex 輸出 parser::symbol_type yylex()。

不過沒關係, 先來搞定 bison 輸出 c++ parser 的用法。為什麼要這麼麻煩呢? 因為我想要用 std::string, 但是原本的 c parser union 在使用 std::string 時, 會有問題, bison 會輸出類似 u.cpp 的 union, 用 c++ 編譯會有問題, 需要自己補上相關的 ctor 才行, 而要讓 bison 輸出 c parser 編譯可以過, 還要 copy ctor。

u.cpp

 2 #include <cstdio>
 3 #include <string>
 4 using namespace std;
 5
 6 union YYSTYPE
 7 {
 8   string id;
 9   int num;
10   #if 0
11   YYSTYPE(){};
12   ~YYSTYPE(){};
13   YYSTYPE operator=(const YYSTYPE&){}
14   #endif
15 };
16
17 YYSTYPE yylval;
18
19 int main(int argc, char *argv[])
20 {
21
22   return 0;
23 }
24
25 g++ -g -std=c++17 -Wall a1.cpp -o a1
26 a1.cpp:16:9: error: use of deleted function ‘YYSTYPE::YYSTYPE()’
27    16 | YYSTYPE yylval;

前言說完了, 該進入正題, 來把最一開始的四則運算改寫為 c++ 版本的 bison 語法。

hoc_cpp.yy

  1 %require "3.2"
  2 %debug
  3 %language "c++"
  4 %define api.token.constructor
  5 %define api.value.type variant
  6 %define api.location.file none
  7 %define parse.assert
  8 %locations
  9 
 10 %code requires // *.hh
 11 {
 12 #include <string>
 13 #include <vector>
 14 typedef std::vector<std::string> strings_type;
 15 }
 16 
 17 %code // *.cc
 18 {
 19 #include <iostream>
 20 #include <sstream>
 21 
 22   namespace yy
 23   {
 24     // Prototype of the yylex function providing subsequent tokens.
 25     static parser::symbol_type yylex ();
 26 
 27     // Print a vector of strings.
 28     std::ostream&
 29     operator<< (std::ostream& o, const strings_type& ss)
 30     {
 31       o << '{';
 32       const char *sep = "";
 33       for (strings_type::const_iterator i = ss.begin (), end = ss.end ();
 34            i != end; ++i)
 35         {
 36           o << sep << *i;
 37           sep = ", ";
 38         }
 39       return o << '}';
 40     }
 41   }
 42 
 43   // Convert to string.
 44   template <typename T>
 45     std::string
 46     to_string (const T& t)
 47   {
 48     std::ostringstream o;
 49     o << t;
 50     return o.str ();
 51   }
 52 }
 53 
 54 %token <int> NUMBER;
 55 %token <char> CHAR;
 56 %token END_OF_FILE 0;
 57 %token
 58   ASSIGN  ":="
 59   PLUS    "+"
 60   MINUS   "-"
 61   MUL     "*"
 62   DIV     "/"
 63   LPAREN  "("
 64   RPAREN  ")"
 65   NEWLINE  "\n"
 66 ;
 67 
 68 %type <int> list;
 69 %type <int> expr;
 70 
 71 %left "+" "-"
 72 %left "*" "/"
 73 
 74 %%
 75 
 76 list:    {printf("\taaempty\n");}
 77      | list "\n" {printf("list \\n\n");}
 78      | list expr "\n" { printf("%d\n", $2); }
 79 
 80 expr: NUMBER {$$ = $1; printf("xx num %d\n", $1);}
 81        | expr "+" expr {$$ = $1 + $3;}
 82        | expr "-" expr {$$ = $1 - $3;}
 83        | expr "*" expr {$$ = $1 * $3;}
 84        | expr "/" expr {$$ = $1 / $3;}
 85        | "(" expr ")"
 86        {
 87          $$ = $2;
 88        }
 89 
 90 
 91 %%
 92 
 93 char *progname;
 94 int lineno = 1;
 95 
 96 namespace yy
 97 {
 98   // Use nullptr with pre-C++11.
 99 #if !defined __cplusplus || __cplusplus < 201103L
100 # define NULLPTR 0
101 #else
102 # define NULLPTR nullptr
103 #endif
104 
105   // The yylex function providing subsequent tokens:
106   // TEXT         "I have three numbers for you."
107   // NUMBER       1
108   // NUMBER       2
109   // NUMBER       3
110   // TEXT         "And that's all!"
111   // END_OF_FILE
112 
113   static
114   parser::symbol_type
115   yylex ()
116   {
117     int c;
118     int input_val;
119     static int count = 0;
120     const int stage = count;
121     ++count;
122     parser::location_type loc (NULLPTR, stage + 1, stage + 1);
123 
124     while ((c=getchar()) == ' ' || c == '\t')
125       ;
126 
127     if (c == EOF)
128       return parser::make_END_OF_FILE (loc);
129     if (c == '.' || isdigit(c) )
130     {
131       ungetc(c, stdin);
132       //scanf("%lf", &input_val);
133       scanf("%d", &input_val);
134       //val = 5;
135       return parser::make_NUMBER (input_val, loc);
136     }
137 
138     switch (c)
139     {
140       case '+':
141       {
142         return parser::make_PLUS(loc);
143         break;
144       }
145       case '-':
146       {
147         return parser::make_MINUS(loc);
148         break;
149       }
150       case '*':
151       {
152         return parser::make_MUL(loc);
153         break;
154       }
155       case '/':
156       {
157         return parser::make_DIV(loc);
158         break;
159       }
160       case '(':
161       {
162         return parser::make_LPAREN(loc);
163         break;
164       }
165       case ')':
166       {
167         return parser::make_RPAREN(loc);
168         break;
169       }
170     }
171 
172     if (c == '\n')
173     {
174       ++lineno;
175       return parser::make_NEWLINE(loc);
176     }
177     //return c;
178     //return parser::make_CHAR(c, loc);
179     char str[2] = {0};
180     str[0] = c;
181     throw yy::parser::syntax_error (loc, "invalid character: " + std::string(str));
182   }
183 
184   // Mandatory error function
185   void parser::error (const parser::location_type& loc, const std::string& msg)
186   {
187     std::cerr << loc << ": " << msg << '\n';
188   }
189 }
190 
191 int main ()
192 {
193   yy::parser p;
194   p.set_debug_level (!!getenv ("YYDEBUG"));
195   return p.parse ();
196 }
197 
198 // Local Variables:
199 // mode: C++
200 // End:

hoc_cpp.yy L1 ~ 52 從 https://github.com/akimd/bison/blob/master/examples/c%2B%2B/variant.yy 這邊照抄, 其他部份也是從這個檔案改寫而來。

最主要是 parser::symbol_type yylex (); 的改寫, 本來 return NUMBER 這樣的 macro 改為 return parser::make_NUMBER (input_val, loc), 另外也要定義 hoc_cpp.yy L55 ~ L65 的 token, 這樣才能用 parser::make_END_OF_FILE(), parser::make_NEWLINE(), parser::make_PLUS(), parser::make_MINUS() 這些 member function。

來看看 make_NUMBER (int v, location_type l) ref: list 2, 怎麼那麼巧, 第一個參數是 int, 那就是 hoc_cpp.yy L54 定義的 54 %token <int> NUMBER;, 如果是寫成 %token <std::string> NUMBER;, 那 make_NUMBER(std::string v, location_type l) 就會長這樣。

list 2. hoc_cpp.cpp

1071 #if 201103L <= YY_CPLUSPLUS
1072       static
1073       symbol_type
1074       make_NUMBER (int v, location_type l)
1075       {
1076         return symbol_type (token::NUMBER, std::move (v), std::move (l));
1077       }
1078 #else
1079       static
1080       symbol_type
1081       make_NUMBER (const int& v, const location_type& l)
1082       {
1083         return symbol_type (token::NUMBER, v, l);
1084       }
1085 #endif

比較麻煩的是本來可以 return getch 的 c, 我不知道要怎麼產生一個類似 make_CHAR 的 member function, 所以用 parser::make_NUMBER 代替, 另外要處理 parser::make_PLUS(), parser::make_MINUS() 也比原本 return c 麻煩不少。

L58, L59 MINUS, PLUS 似乎要用 "+", 用 '+' 就會有奇怪的錯誤, 這個經過測試有點複雜, 某些組合是可以用 '+', 但是要改規則寫法, 就不多提了。

再來 main call parse() 也不一樣, 變成 member function 了。

以下是編譯指令:

g++ -g -std=c++17 -Wall -c hoc_cpp.cpp
g++ -g -std=c++17 -Wall hoc_cpp.o -o hoc_cpp

這樣就完成一個 c++ 版本的 bison parser。

另外補充一個寫法 hoc_cpp_1.yy, 沒有使用 %define api.token.constructor, 影響到什麼呢? yylex 的 function prototype, hoc_cpp_1.yy L24 那樣, 而 yylex return 也不同, 改成 hoc_cpp_1.yy L133, L134, 使用了 emplace(), 相當奇怪的用法。「10.1.7 C++ Scanner Interface」提到了這個, 有興趣的朋友自己看, 就不說明了。

hoc_cpp_1.yy

  1 %language "c++"
  2 %require "3.2"
  3 %debug
  4 %define api.value.type variant
  5 %define parse.assert
  6 %locations
  7 
  8 %code requires // *.hh
  9 {
 10 #include <string>
 11 #include <vector>
 12 typedef std::vector<std::string> strings_type;
 13 
 14 #include "hoc_cpp_1.tab.hh"
 15 }
 16 
 17 %code // *.cc
 18 {
 19 #include <iostream>
 20 #include <sstream>
 21 
 22   namespace yy
 23   {
 24     int yylex (yy::parser::value_type *yylval, yy::parser::location_type *yylloc);
 25 
 26     // Print a vector of strings.
 27     std::ostream&
 28     operator<< (std::ostream& o, const strings_type& ss)
 29     {
 30       o << '{';
 31       const char *sep = "";
 32       for (strings_type::const_iterator i = ss.begin (), end = ss.end ();
 33            i != end; ++i)
 34         {
 35           o << sep << *i;
 36           sep = ", ";
 37         }
 38       return o << '}';
 39     }
 40   }
 41 
 42   // Convert to string.
 43   template <typename T>
 44     std::string
 45     to_string (const T& t)
 46   {
 47     std::ostringstream o;
 48     o << t;
 49     return o.str ();
 50   }
 51 }
 52 
 53 %token <int> NUMBER;
 54 %token END_OF_FILE 0;
 55 %token
 56   ASSIGN  ":="
 57   MINUS   "-"
 58   PLUS    "+"
 59   STAR    "*"
 60   SLASH   "/"
 61   LPAREN  "("
 62   RPAREN  ")"
 63   NEWLINE  "\n"
 64 ;
 65 
 66 %type <int> list;
 67 %type <int> expr;
 68 
 69 %left "+" "-"
 70 %left "*" "/"
 71 
 72 %%
 73 
 74 list:    {printf("\taaempty\n");}
 75      | list "\n" {printf("list \\n\n");}
 76      | list expr "\n" { printf("%d\n", $2); }
 77 
 78 expr: NUMBER {$$ = $1; printf("xx num %d\n", $1);}
 79        | expr "+" expr {$$ = $1 + $3;}
 80        | expr "-" expr {$$ = $1 - $3;}
 81        | expr "*" expr {$$ = $1 * $3;}
 82        | expr "/" expr {$$ = $1 / $3;}
 83        | '(' expr ')'
 84 
 85 
 86 %%
 87 
 88 char *progname;
 89 int lineno = 1;
 90 
 91 namespace yy
 92 {
 93   // Use nullptr with pre-C++11.
 94 #if !defined __cplusplus || __cplusplus < 201103L
 95 # define NULLPTR 0
 96 #else
 97 # define NULLPTR nullptr
 98 #endif
 99 
100   // The yylex function providing subsequent tokens:
101   // TEXT         "I have three numbers for you."
102   // NUMBER       1
103   // NUMBER       2
104   // NUMBER       3
105   // TEXT         "And that's all!"
106   // END_OF_FILE
107 
108   int yylex (yy::parser::value_type *yylval, yy::parser::location_type *yylloc)
109   {
110     int c;
111     int input_val;
112     static int count = 0;
113     const int stage = count;
114     ++count;
115     //parser::location_type loc (NULLPTR, stage + 1, stage + 1);
116 
117     while ((c=getchar()) == ' ' || c == '\t')
118       ;
119 
120     if (c == EOF)
121     {
122       ;//return parser::make_END_OF_FILE (loc);
123       return yy::parser::token::END_OF_FILE;
124     }
125     if (c == '.' || isdigit(c) )
126     {
127       ungetc(c, stdin);
128       //scanf("%lf", &input_val);
129       scanf("%d", &input_val);
130       //scanf("%d", yyla->value);
131       //val = 5;
132       ;//return parser::make_NUMBER (input_val, loc);
133       yylval->emplace<int>() = input_val;
134       return yy::parser::token::NUMBER;
135     }
136 
137     switch (c)
138     {
139       case '+':
140       {
141         ;//return parser::make_PLUS(loc);
142         return yy::parser::token::PLUS;
143         break;
144       }
145       case '-':
146       {
147         ;//return parser::make_MINUS(loc);
148         return yy::parser::token::MINUS;
149         break;
150       }
151     }
152 
153     if (c == '\n')
154     {
155       ++lineno;
156       ;//return parser::make_NEWLINE(loc);
157       return yy::parser::token::NEWLINE;
158     }
159       yylval->emplace<int>() = c;
160       //return yy::parser::token::NUMBER;
161     return c;
162     //return parser::make_NUMBER (c, loc);
163 
164   #if 0
165     static int count = 0;
166     const int stage = count;
167     ++count;
168     parser::location_type loc (NULLPTR, stage + 1, stage + 1);
169     switch (stage)
170       {
171       case 0:
172         return parser::make_TEXT ("I have three numbers for you.", loc);
173       case 1:
174       case 2:
175       case 3:
176         return parser::make_NUMBER (stage, loc);
177       case 4:
178         return parser::make_TEXT ("And that's all!", loc);
179       default:
180         return parser::make_END_OF_FILE (loc);
181       }
182   #endif 
183   }
184 
185   // Mandatory error function
186   void parser::error (const parser::location_type& loc, const std::string& msg)
187   {
188     std::cerr << loc << ": " << msg << '\n';
189   }
190 }
191 
192 int main ()
193 {
194   yy::parser p;
195   p.set_debug_level (!!getenv ("YYDEBUG"));
196   return p.parse ();
197 }
198 
199 // Local Variables:
200 // mode: C++
201 // End:

編譯指令:

bison -d hoc_cpp_1.yy
g++ hoc_cpp_1.tab.cc -o hoc_cpp_1

另外 flex 不是 gnu 套件的一部份, 有點驚訝, 不知道為什麼?

f

1 lftp ftp.gnu.org:/gnu/flex> cat flex.README
2 Flex is a free implementation of the well-known Lex program for lexical
3 analysis. Since it is not (and never was) a GNU package, we don't
4 distribute it here. Please see http://flex.sourceforge.net for the
5 latest release and information.

ref:

• 文本解析工具使用总结 (覺得不太正確)
• Flex and Bison in C++