Mercurial > hg > Members > nobuyasu > SampleSource

comparison boost-spirit/Compiler-boost-spirit/parser.cpp @ 0:db40c85cad7a default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
upload sample source
author nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
date Mon, 09 May 2011 03:11:59 +0900
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:db40c85cad7a
1 //
2 // boost::spiritによる、C言語風構文パーサー
3 //
4 // 2008/06/05 Chihiro.SAKAMOTO
5 // Copyright Chihiro.SAKAMOTO
6 //
7 #include "stdafx.h"
8 #include "compiler.h"
9 #include "node.h"
10
11 using namespace std;
12 using namespace boost::spirit;
13
14 // 入力用のイテレータを定義
15 typedef position_iterator<string::const_iterator> iterator_t;
16
17 // エラー処理パーサー定義
18 struct error_parser {
19 typedef nil_t result_t; // パーサーの結果型（nil_t）
20
21 error_parser(char const *msg)
22 : msg_(msg)
23 {
24 }
25
26 template <typename ScannerT>
27 int operator()(ScannerT const &scan, result_t &result) const
28 {
29 // 終わりまで来たら-1を返す
30 if (scan.at_end()) {
31 return -1;
32 }
33
34 // 改行までをスキャンし、そこまでを表示する。
35
36 iterator_t b = scan.first;
37 size_t length = (*(anychar_p - '\n')).parse(scan).length();
38 file_position fpos = scan.first.get_position();
39 cout << fpos.file << ": " << fpos.line << "." << fpos.column << ": "
40 << msg_ << " : " << string(b, scan.first) << endl;
41
42 // spiritのバックトラックの影響を受けるので、エラー処理は
43 // 細かく入れる必要が生じる
44 // そうしないと、大量のエラーに埋没する
45 // ここでは、エラー１つで中断している。
46 // return (int)length + 1;
47 return -1;
48 }
49
50 private:
51 const char *msg_;
52 } ;
53
54 // エラー処理パーサー
55 typedef functor_parser<error_parser> error_p;
56
57 // 文法エラー処理パーサー
58 error_p syntax_error_p = error_parser("文法エラー");
59
60 // 単項演算子ノードを生成する
61 struct unary_node_impl {
62 template <typename Ty1, typename Ty2>
63 struct result { typedef cnode_t type; } ;
64
65 template <typename Ty1, typename Ty2>
66 cnode_t operator()(Ty1 op, const Ty2 &left) const
67 {
68 return cnode::make_node(op, left);
69 }
70 } ;
71
72 // 二項演算子ノードを生成する
73 struct binary_node_impl {
74 template <typename Ty1, typename Ty2, typename Ty3>
75 struct result { typedef cnode_t type; } ;
76
77 template <typename Ty1, typename Ty2, typename Ty3>
78 cnode_t operator()(Ty1 op, const Ty2 &left, const Ty3 &right) const
79 {
80 return cnode::make_node(op, left, right);
81 }
82 } ;
83
84 // 値を追加
85 struct push_back_impl {
86 template <typename Ty1, typename Ty2>
87 struct result { typedef Ty1 type; } ;
88
89 template <typename Ty1, typename Ty2>
90 Ty1 operator()(Ty1 &list, const Ty2 &node) const
91 {
92 list->add(node);
93 return list;
94 }
95 } ;
96
97 // ノードリストを生成する
98 struct make_argument_impl {
99 template <typename Ty>
100 struct result { typedef cnode_list_t type; } ;
101
102 template <typename Ty>
103 cnode_list_t operator()(const Ty &node) const
104 {
105 return cnode_list_t(new cnode_list(node));
106 }
107 } ;
108
109 // ステートメントの生成
110 struct make_statement_impl {
111 template <typename Ty>
112 struct result { typedef cstatement_t type; } ;
113
114 template <typename Ty>
115 cstatement_t operator()(Ty state) const
116 {
117 return cstatement::make_statement(state);
118 }
119 } ;
120
121 // ステートメントの生成
122 struct make_statement1_impl {
123 template <typename Ty1, typename Ty2>
124 struct result { typedef cstatement_t type; } ;
125
126 template <typename Ty1, typename Ty2>
127 cstatement_t operator()(Ty1 state, const Ty2 &node) const
128 {
129 return cstatement::make_statement(state, node);
130 }
131 } ;
132
133 // ステートメントにインデックス付きで値を追加
134 struct add_statement_impl {
135 template <typename Ty1, typename Ty2, typename Ty3>
136 struct result { typedef cstatement_t type; } ;
137
138 template <typename Ty1, typename Ty2, typename Ty3>
139 cstatement_t operator()(Ty1 &statement, Ty2 index, const Ty3 &node) const
140 {
141 statement->add(index, node);
142 return statement;
143 }
144 } ;
145
146 // 宣言の生成
147 struct make_decl_impl {
148 template <typename Ty>
149 struct result { typedef cdeclaration_t type; } ;
150
151 template <typename Ty>
152 cdeclaration_t operator()(Ty type) const
153 {
154 return cdeclaration_t(new cdeclaration(type));
155 }
156 } ;
157
158 // 宣言の生成
159 struct make_decl1_impl {
160 template <typename Ty1, typename Ty2>
161 struct result { typedef cdeclaration_t type; } ;
162
163 template <typename Ty1, typename Ty2>
164 cdeclaration_t operator()(Ty1 type, const Ty2 &node) const
165 {
166 return cdeclaration_t(new cdeclaration(type, node));
167 }
168 } ;
169
170 // 引数宣言の型を参照にする
171 struct arg_ref_impl {
172 template <typename Ty1>
173 struct result { typedef cargdef type; } ;
174
175 template <typename Ty1>
176 cargdef operator()(Ty1 &decl) const
177 {
178 decl.set_ref();
179 return decl;
180 }
181 } ;
182
183 // 引数の名前を設定
184 struct arg_name_impl {
185 template <typename Ty1, typename Ty2>
186 struct result { typedef cargdef type; } ;
187
188 template <typename Ty1, typename Ty2>
189 cargdef operator()(Ty1 &decl, const Ty2 &name) const
190 {
191 decl.set_name(name);
192 return decl;
193 }
194 } ;
195
196 // 関数の生成
197 struct make_function_impl {
198 template <typename Ty1, typename Ty2>
199 struct result { typedef cfunction_t type; } ;
200
201 template <typename Ty1, typename Ty2>
202 cfunction_t operator()(Ty1 type, const Ty2 &name) const
203 {
204 return cfunction_t(new cfunction(type, name));
205 }
206 } ;
207
208 // 最終登録
209 struct analyze_impl {
210 template <typename Ty1, typename Ty2>
211 struct result { typedef void type; } ;
212
213 template <typename Ty1, typename Ty2>
214 void operator()(const Ty1 &decl, Ty2 driver) const
215 {
216 decl->analyze(driver);
217 }
218 } ;
219
220 // phoenixが使用する「無名関数」用の関数
221 phoenix::function<binary_node_impl> const binary_node = binary_node_impl();
222 phoenix::function<unary_node_impl> const unary_node = unary_node_impl();
223 phoenix::function<push_back_impl> const push_back = push_back_impl();
224 phoenix::function<make_argument_impl> const make_argument = make_argument_impl();
225 phoenix::function<make_statement_impl> const make_statement = make_statement_impl();
226 phoenix::function<make_statement1_impl> const make_statement1 = make_statement1_impl();
227 phoenix::function<add_statement_impl> const add_statement = add_statement_impl();
228 phoenix::function<make_decl_impl> const make_decl = make_decl_impl();
229 phoenix::function<make_decl1_impl> const make_decl1 = make_decl1_impl();
230 phoenix::function<arg_ref_impl> const arg_ref = arg_ref_impl();
231 phoenix::function<arg_name_impl> const arg_name = arg_name_impl();
232 phoenix::function<make_function_impl> const make_function = make_function_impl();
233 phoenix::function<analyze_impl> const analyze = analyze_impl();
234
235 // 文法定義
236 struct script_grammer: public grammar<script_grammer> {
237 script_grammer(compiler *driver)
238 :driver_(driver)
239 {
240 }
241
242 compiler *driver_; // コンパイラ
243
244 // 文字列のクロージャ
245 struct string_val: closure<string_val, std::string> {
246 member1 str;
247 } ;
248 // 数字のクロージャ
249 struct number_val: closure<number_val, unsigned int> {
250 member1 number;
251 } ;
252 // ノードのクロージャ
253 struct node_val: closure<node_val, cnode_t, int> {
254 member1 node;
255 member2 op;
256 } ;
257 // ノードのクロージャ
258 struct nodelist_val: closure<nodelist_val, cnode_list_t, int> {
259 member1 node;
260 member2 op;
261 } ;
262 // 文のクロージャ
263 struct state_val: closure<state_val, cstatement_t> {
264 member1 statement;
265 } ;
266 // 型のクロージャ
267 struct type_val: closure<type_val, int> {
268 member1 type;
269 } ;
270
271 // 変数定義のクロージャ
272 struct decl_val: closure<decl_val, cdeclaration_t, int> {
273 member1 node;
274 member2 type;
275 } ;
276
277 // 関数定義のクロージャ
278 struct func_val: closure<func_val, cfunction_t, int> {
279 member1 node;
280 member2 type;
281 } ;
282
283 // 引数定義のクロージャ
284 struct argdef_val: closure<argdef_val, cargdef> {
285 member1 node;
286 } ;
287
288 // 文ブロックのクロージャ
289 struct block_val: closure<block_val, cblock_t> {
290 member1 node;
291 } ;
292
293 template <typename ScannerT>
294 struct definition {
295 rule<ScannerT, string_val::context_t> identifier;
296 rule<ScannerT, string_val::context_t> string_node;
297 rule<ScannerT, number_val::context_t> number;
298 rule<ScannerT, type_val::context_t> type;
299 rule<ScannerT, node_val::context_t> func_node;
300 rule<ScannerT, node_val::context_t> value;
301 rule<ScannerT, node_val::context_t> prime;
302 rule<ScannerT, node_val::context_t> unary;
303 rule<ScannerT, node_val::context_t> mul_expr;
304 rule<ScannerT, node_val::context_t> add_expr;
305 rule<ScannerT, node_val::context_t> shift_expr;
306 rule<ScannerT, node_val::context_t> bit_expr;
307 rule<ScannerT, node_val::context_t> equ_expr;
308 rule<ScannerT, node_val::context_t> and_expr;
309 rule<ScannerT, node_val::context_t> expr;
310 rule<ScannerT, node_val::context_t> assign;
311 rule<ScannerT, nodelist_val::context_t> argument;
312 rule<ScannerT, state_val::context_t> statement;
313 rule<ScannerT, func_val::context_t> function;
314 rule<ScannerT, type_val::context_t> arg;
315 rule<ScannerT, decl_val::context_t> decl_value;
316 rule<ScannerT, decl_val::context_t> decl_func;
317 rule<ScannerT, argdef_val::context_t> argdef;
318 rule<ScannerT, block_val::context_t> block;
319 rule<ScannerT> input;
320 rule<ScannerT> ident;
321
322 symbols<> keywords;
323 symbols<> mul_op, add_op, shift_op, bit_op, equ_op, assign_op;
324 dynamic_distinct_parser<ScannerT> keyword_p;
325
326 definition(script_grammer const& self)
327 :keyword_p(alnum_p | '_')
328 {
329 using phoenix::arg1;
330 using phoenix::arg2;
331 using phoenix::var;
332 using phoenix::new_;
333 using phoenix::construct_;
334
335 keywords = "if", "for", "while", "switch", "case", "default", "break", "return";
336 // 識別子
337 ident = lexeme_d[
338 ((alpha_p | '_') >> *(alnum_p | '_')) - (keywords >> anychar_p - (alnum_p | '_'))
339 ];
340 // 識別子（クロージャに登録）
341 identifier = ident[identifier.str = construct_<string>(arg1, arg2)];
342 // 数値
343 number = uint_p[number.number = arg1];
344 // 文字列
345 string_node = lexeme_d[
346 confix_p(ch_p('"')[string_node.str = ""], *c_escape_ch_p[string_node.str += arg1], '"')
347 ];
348
349 // 変数
350 value = identifier[value.node = unary_node(OP_IDENTIFIER, arg1)]
351 >> !('[' >> expr[value.node = binary_node(OP_ARRAY, value.node, arg1)] >> ']');
352
353 // 関数の引数
354 argument = expr[argument.node = make_argument(arg1)]
355 >> *(',' >> expr[argument.node = push_back(argument.node, arg1)]);
356
357 // 関数呼び出し
358 func_node = identifier[func_node.node = unary_node(OP_FUNCTION, arg1)] >>
359 '(' >> !argument[func_node.node = binary_node(OP_FUNCTION, func_node.node, arg1)] >> ')';
360
361 // 計算のprimeノード
362 prime = func_node[prime.node = arg1]
363 | value[prime.node = arg1]
364 | number[prime.node = unary_node(OP_NUMBER, arg1)]
365 | string_node[prime.node = unary_node(OP_STRING, arg1)]
366 | '(' >> expr[prime.node = arg1] >> ')'
367 ;
368
369 // 単項演算子
370 unary = prime[unary.node = arg1]
371 | '-' >> prime[unary.node = unary_node(OP_NEG, arg1)];
372
373 // 二項演算子（*, /, %）
374 mul_op.add("*", OP_MUL)("/", OP_DIV)("%", OP_MOD);
375 mul_expr = unary[mul_expr.node = arg1]
376 >> *(mul_op[mul_expr.op = arg1]
377 >> unary[mul_expr.node = binary_node(mul_expr.op, mul_expr.node, arg1)]);
378
379 // 二項演算子（+, -）
380 add_op.add("+", OP_ADD)("-", OP_SUB);
381 add_expr = mul_expr[add_expr.node = arg1]
382 >> *(add_op[add_expr.op = arg1]
383 >> mul_expr[add_expr.node = binary_node(add_expr.op, add_expr.node, arg1)]);
384
385 // 二項演算子（<<, >>）
386 shift_op.add("<<", OP_LSHIFT)(">>", OP_RSHIFT);
387 shift_expr = add_expr[shift_expr.node = arg1]
388 >> *(shift_op[shift_expr.op = arg1]
389 >> add_expr[shift_expr.node = binary_node(shift_expr.op, shift_expr.node, arg1)]);
390
391 // 二項演算子（&, |）
392 bit_op.add("&", OP_AND)("|", OP_OR);
393 bit_expr = shift_expr[bit_expr.node = arg1]
394 >> *(bit_op[bit_expr.op = arg1]
395 >> shift_expr[bit_expr.node = binary_node(bit_expr.op, bit_expr.node, arg1)]);
396
397 // 二項演算子（比較）
398 equ_op.add("==", OP_EQ)("!=", OP_NE)(">=", OP_GE)(">", OP_GT)("<=", OP_LE)("<", OP_LT);
399 equ_expr = bit_expr[equ_expr.node = arg1]
400 >> !(equ_op[equ_expr.op = arg1]
401 >> bit_expr[equ_expr.node = binary_node(equ_expr.op, equ_expr.node, arg1)]);
402
403 // 二項演算子（&&）
404 and_expr = equ_expr[and_expr.node = arg1]
405 >> *("&&" >> equ_expr[and_expr.node = binary_node(OP_LOGAND, and_expr.node, arg1)]);
406
407 // 二項演算子（||）
408 expr = and_expr[expr.node = arg1]
409 >> *("||" >> and_expr[expr.node = binary_node(OP_LOGOR, expr.node, arg1)]);
410
411 // 代入
412 assign_op.add
413 ("=", OP_ASSIGN)
414 ("+=", OP_ADD_ASSIGN)
415 ("-=", OP_SUB_ASSIGN)
416 ("*=", OP_MUL_ASSIGN)
417 ("/=", OP_DIV_ASSIGN)
418 ("%=", OP_MOD_ASSIGN)
419 ("&=", OP_AND_ASSIGN)
420 ("|=", OP_OR_ASSIGN)
421 ("<<=", OP_LSHIFT_ASSIGN)
422 (">>=", OP_RSHIFT_ASSIGN);
423 assign = value[assign.node = arg1]
424 >> assign_op[assign.op = arg1]
425 >> expr[assign.node = binary_node(assign.op, assign.node, arg1)];
426
427 // 型宣言
428 type = keyword_p("int")[type.type = TYPE_INTEGER] >> !ch_p('&')[type.type |= TYPE_REF]
429 | keyword_p("string")[type.type = TYPE_STRING] >> !ch_p('&')[type.type |= TYPE_REF]
430 | keyword_p("void")[type.type = TYPE_VOID]
431 ;
432
433 // 関数宣言の引数
434 arg = type[arg.type = arg1]
435 >> !identifier
436 >> !str_p("[]")[arg.type |= TYPE_REF];
437
438 // 変数宣言
439 decl_value = type[decl_value.node = make_decl(arg1)]
440 >> value[decl_value.node = push_back(decl_value.node, arg1)] % ',' >> ';';
441 // 関数宣言
442 decl_func = type[decl_func.type = arg1]
443 >> identifier[decl_func.node = make_decl1(decl_func.type, arg1)]
444 >> '(' >> !(arg[decl_func.node = push_back(decl_func.node, arg1)] % ',') >> ')' >> ';';
445
446 // 関数定義の引数
447 argdef = type[argdef.node = construct_<cargdef>(arg1)]
448 >> !identifier[argdef.node = arg_name(argdef.node, arg1)]
449 >> !str_p("[]")[argdef.node = arg_ref(argdef.node)];
450
451 // 関数定義
452 function = type[function.type = arg1]
453 >> identifier[function.node = make_function(function.type, arg1)]
454 >> '(' >> !(argdef[function.node = push_back(function.node, arg1)] % ',') >> ')'
455 >> block[function.node = push_back(function.node, arg1)];
456
457 // 文ブロック
458 block = ch_p('{')[block.node = construct_<cblock_t>(new_<cblock>())]
459 >> *decl_value[block.node = push_back(block.node, arg1)]
460 >> *statement[block.node = push_back(block.node, arg1)]
461 >> '}';
462
463 // 文
464 statement = ch_p(';')[statement.statement = make_statement(NOP_STATE)]
465 | assign[statement.statement = make_statement1(ASSIGN_STATE, arg1)] >> ';'
466 | str_p("case") >> expr[statement.statement = make_statement1(CASE_STATE, arg1)] >> ':'
467 | str_p("default")[statement.statement = make_statement(DEFAULT_STATE)] >> ':'
468 | str_p("break")[statement.statement = make_statement(BREAK_STATE)] >> ';'
469 | str_p("return")[statement.statement = make_statement(RETURN_STATE)]
470 >> !expr[statement.statement = push_back(statement.statement, arg1)] >> ';'
471 | str_p("if")[statement.statement= make_statement(IF_STATE)]
472 >> '(' >> expr[statement.statement = push_back(statement.statement, arg1)] >> ')'
473 >> statement[statement.statement = add_statement(statement.statement, 0, arg1)]
474 >> !("else"
475 >> statement[statement.statement = add_statement(statement.statement, 1, arg1)])
476 | str_p("for")[statement.statement = make_statement(FOR_STATE)] >> '('
477 >> assign[statement.statement = add_statement(statement.statement, 0, arg1)] >> ';'
478 >> expr[statement.statement = add_statement(statement.statement, 1, arg1)] >> ';'
479 >> assign[statement.statement = add_statement(statement.statement, 2, arg1)] >> ')'
480 >> statement[statement.statement = push_back(statement.statement, arg1)]
481 | str_p("while")[statement.statement = make_statement(WHILE_STATE)] >> '('
482 >> expr[statement.statement = push_back(statement.statement, arg1)] >> ')'
483 >> statement[statement.statement = push_back(statement.statement, arg1)]
484 | str_p("switch") >> '('
485 >> expr[statement.statement = make_statement1(SWITCH_STATE, arg1)] >> ')'
486 >> '{'
487 >> *statement[statement.statement = push_back(statement.statement, arg1)]
488 >> '}'
489 | func_node[statement.statement = make_statement1(CALL_STATE, arg1)] >> ';'
490 | block[statement.statement = make_statement1(BLOCK_STATE, arg1)]
491 ;
492
493 // 入力された構文
494 input = *(decl_value[analyze(arg1, self.driver_)]
495 | decl_func[analyze(arg1, self.driver_)]
496 | function[analyze(arg1, self.driver_)]
497 | syntax_error_p
498 );
499 }
500
501 rule<ScannerT> const& start() const
502 {
503 return input;
504 }
505 } ;
506 } ;
507
508 // スキップイテレーター
509 // コメントのスキップを加える
510 struct skip_parser: public grammar<skip_parser> {
511 template <typename ScannerT>
512 struct definition {
513 rule<ScannerT> skip_p;
514
515 definition(skip_parser const& self)
516 {
517 skip_p = space_p
518 | comment_p("//") // C++コメント用
519 | comment_p("/*", "*/") // Cコメント用
520 ;
521 }
522 rule<ScannerT> const& start() const
523 {
524 return skip_p;
525 }
526 } ;
527 } ;
528
529 // 全部スキップしてみて、エンドまで来たか？
530 template <typename IteratorT, typename DerivedT>
531 bool skip_all(IteratorT first, IteratorT last, parser<DerivedT> const &p)
532 {
533 for (;;) {
534 parse_info<IteratorT> info = parse(first, last, p);
535 if (info.full)
536 return true;
537 if (!info.hit)
538 return false;
539 first = info.stop;
540 }
541 }
542
543 // 構文解析
544 bool script_parser(const string &path, compiler *driver)
545 {
546 ifstream fin(path.c_str());
547
548 if (!fin) {
549 driver->error("ファイル" + path + "がオープンできません。");
550 return false;
551 }
552
553 // ファイルを一度メモリーに読み込む
554 istreambuf_iterator<char> fbegin(fin);
555 istreambuf_iterator<char> fend;
556 string input(fbegin, fend);
557
558 // ポジションイテレータ
559 iterator_t begin(input.begin(), input.end(), path);
560 iterator_t end;
561 begin.set_tabchars(4); // tab=4に設定
562
563 script_grammer gr(driver);
564 skip_parser skip_p;
565 parse_info<iterator_t> info = parse(begin, end, gr, skip_p);
566 if (info.hit && (info.full || skip_all(info.stop, end, skip_p))) {
567 return true;
568 }
569
570 driver->error("構文解析失敗");
571
572 return false;
573 }