竜 TatSu (PEG parsers in Python) のへろわるど

Parsing In Python: Tools And Libraries より。

竜 TatSuArpeggioと同じく PEG 系。そしてここまでみてきた PEG 系とは明らかに異端、だけれども、初見での第一印象は「最もフレキシブルで完成度も高そう」というもの。

異端:

竜 TatSu (the successor to Grako) is a tool that takes grammars in a variation of EBNF as input, and outputs memoizing (Packrat) PEG parsers in Python.

EBNF (の変種?) から PEG パーサを生成する、ということは、「orderd choice」でパーサの振る舞いが変わりうる、ということだと思うが、この差異は脳内変換せよ、ちぅこと? ながーい rational に書かれてるかもしれんけど長過ぎて読む気になれない。

というわけで構文の定義は EBNF (の変種)でこんな具合らしい:

 1 GRAMMAR = '''
 2     @@grammar::Calc
 3 
 4     start = expression $ ;
 5 
 6     expression
 7         =
 8         | term '+' ~ expression
 9         | term '-' ~ expression
10         | term
11         ;
12 
13     term
14         =
15         | factor '*' ~ term
16         | factor '/' ~ term
17         | factor
18         ;
19 
20     factor
21         =
22         | '(' ~ @:expression ')'
23         | number
24         ;
25 
26     number = /\d+/ ;
27 '''

随分拡張されているようで、本物の EBNF だけ知っててもこれは想像もつかんわな。

さて、「竜 TatSu」がフレキシブルだ、について。すなわち、「あたかも re モジュール」的ノリで使われることを想定してんのね:

 1 # -*- coding: utf-8 -*-
 2 import tatsu
 3 
 4 # the grammar of my calc
 5 GRAMMAR = '''
 6     @@grammar::Calc
 7 
 8     start = expression $ ;
 9 
10     expression
11         =
12         | term '+' ~ expression
13         | term '-' ~ expression
14         | term
15         ;
16 
17     term
18         =
19         | factor '*' ~ term
20         | factor '/' ~ term
21         | factor
22         ;
23 
24     factor
25         =
26         | '(' ~ @:expression ')'
27         | number
28         ;
29 
30     number = /\d+/ ;
31 '''
32 
33 # like "rgx = re.compile(r'...')"
34 calcp = tatsu.compile(GRAMMAR, name="Calc")
35 print(calcp.parse("3 + 2 - (1 + 3 * 4)"))

無論 re モジュールのノリと同じで、

1 # like "re.match(r'...', '...')"
2 print(tatsu.parse(GRAMMAR, "3 + 2 - (1 + 3 * 4)"))

もオケ。さらにはコンパイル済みパーサを「python モジュールとして」書き出せる:

1 # generate parser as python module
2 open("mycalc.py", "w").write(
3     tatsu.to_python_sourcecode(GRAMMAR, name="mycalc"))

まぁ「自分の製品が動的に python モジュールを吐き出して動作する」というもんは作らんよねフツーは。Windows ならともかく、Unix でシステムインストールされるようなライブラリを書くつもりなら、モジュールを書き出す場所がないでしょ。そうではなくて「tatsu を静的ジェネレータとして使いたいならば」ということよね。ともあれ tatsu.to_python_sourcecode はこんな python コードを生成してくれた:

  1 #!/usr/bin/env python
  2 # -*- coding: utf-8 -*-
  3 
  4 # CAVEAT UTILITOR
  5 #
  6 # This file was automatically generated by TatSu.
  7 #
  8 #    https://pypi.python.org/pypi/tatsu/
  9 #
 10 # Any changes you make to it will be overwritten the next time
 11 # the file is generated.
 12 
 13 
 14 from __future__ import print_function, division, absolute_import, unicode_literals
 15 
 16 from tatsu.buffering import Buffer
 17 from tatsu.parsing import Parser
 18 from tatsu.parsing import tatsumasu
 19 from tatsu.util import re, generic_main  # noqa
 20 
 21 
 22 KEYWORDS = {}  # type: ignore
 23 
 24 
 25 class mycalcBuffer(Buffer):
 26     def __init__(
 27         self,
 28         text,
 29         whitespace=None,
 30         nameguard=None,
 31         comments_re=None,
 32         eol_comments_re=None,
 33         ignorecase=None,
 34         namechars='',
 35         **kwargs
 36     ):
 37         super(mycalcBuffer, self).__init__(
 38             text,
 39             whitespace=whitespace,
 40             nameguard=nameguard,
 41             comments_re=comments_re,
 42             eol_comments_re=eol_comments_re,
 43             ignorecase=ignorecase,
 44             namechars=namechars,
 45             **kwargs
 46         )
 47 
 48 
 49 class mycalcParser(Parser):
 50     def __init__(
 51         self,
 52         whitespace=None,
 53         nameguard=None,
 54         comments_re=None,
 55         eol_comments_re=None,
 56         ignorecase=None,
 57         left_recursion=True,
 58         parseinfo=True,
 59         keywords=None,
 60         namechars='',
 61         buffer_class=mycalcBuffer,
 62         **kwargs
 63     ):
 64         if keywords is None:
 65             keywords = KEYWORDS
 66         super(mycalcParser, self).__init__(
 67             whitespace=whitespace,
 68             nameguard=nameguard,
 69             comments_re=comments_re,
 70             eol_comments_re=eol_comments_re,
 71             ignorecase=ignorecase,
 72             left_recursion=left_recursion,
 73             parseinfo=parseinfo,
 74             keywords=keywords,
 75             namechars=namechars,
 76             buffer_class=buffer_class,
 77             **kwargs
 78         )
 79 
 80     @tatsumasu()
 81     def _start_(self):  # noqa
 82         self._expression_()
 83         self._check_eof()
 84 
 85     @tatsumasu()
 86     def _expression_(self):  # noqa
 87         with self._choice():
 88             with self._option():
 89                 self._term_()
 90                 self._token('+')
 91                 self._cut()
 92                 self._expression_()
 93             with self._option():
 94                 self._term_()
 95                 self._token('-')
 96                 self._cut()
 97                 self._expression_()
 98             with self._option():
 99                 self._term_()
100             self._error('no available options')
101 
102     @tatsumasu()
103     def _term_(self):  # noqa
104         with self._choice():
105             with self._option():
106                 self._factor_()
107                 self._token('*')
108                 self._cut()
109                 self._term_()
110             with self._option():
111                 self._factor_()
112                 self._token('/')
113                 self._cut()
114                 self._term_()
115             with self._option():
116                 self._factor_()
117             self._error('no available options')
118 
119     @tatsumasu()
120     def _factor_(self):  # noqa
121         with self._choice():
122             with self._option():
123                 self._token('(')
124                 self._cut()
125                 self._expression_()
126                 self.name_last_node('@')
127                 self._token(')')
128             with self._option():
129                 self._number_()
130             self._error('no available options')
131 
132     @tatsumasu()
133     def _number_(self):  # noqa
134         self._pattern(r'\d+')
135 
136 
137 class mycalcSemantics(object):
138     def start(self, ast):  # noqa
139         return ast
140 
141     def expression(self, ast):  # noqa
142         return ast
143 
144     def term(self, ast):  # noqa
145         return ast
146 
147     def factor(self, ast):  # noqa
148         return ast
149 
150     def number(self, ast):  # noqa
151         return ast
152 
153 
154 def main(filename, startrule, **kwargs):
155     with open(filename) as f:
156         text = f.read()
157     parser = mycalcParser()
158     return parser.parse(text, startrule, filename=filename, **kwargs)
159 
160 
161 if __name__ == '__main__':
162     import json
163     from tatsu.util import asjson
164 
165     ast = generic_main(main, mycalcParser, name='mycalc')
166     print('AST:')
167     print(ast)
168     print()
169     print('JSON:')
170     print(json.dumps(asjson(ast), indent=2))
171     print()

生成されたこれをモジュールとして使うには無論こう:

1 # -*- coding: utf-8 -*-
2 import mycalc  # my parser, was generated by tatsu
3 
4 parser = mycalc.mycalcParser()
5 print(parser.parse("3 + 2 - (1 + 3 * 4)"))

パーサではなく「オブジェクトモデルとして」書き出すことも出来る、とあるが、どういう意味だ? 実際やってみると:

1 # generate model as python module
2 open("mycalcmodel.py", "w").write(
3     tatsu.to_python_model(GRAMMAR, name="mycalcmodel"))

こんなん出ました:

 1 #!/usr/bin/env python
 2 # -*- coding: utf-8 -*-
 3 
 4 # CAVEAT UTILITOR
 5 #
 6 # This file was automatically generated by TatSu.
 7 #
 8 #    https://pypi.python.org/pypi/tatsu/
 9 #
10 # Any changes you make to it will be overwritten the next time
11 # the file is generated.
12 
13 from __future__ import print_function, division, absolute_import, unicode_literals
14 
15 from tatsu.objectmodel import Node
16 from tatsu.semantics import ModelBuilderSemantics
17 
18 
19 class mycalcmodelModelBuilderSemantics(ModelBuilderSemantics):
20     def __init__(self):
21         types = [
22             t for t in globals().values()
23             if type(t) is type and issubclass(t, ModelBase)
24         ]
25         super(mycalcmodelModelBuilderSemantics, self).__init__(types=types)
26 
27 
28 class ModelBase(Node):
29     pass

うーん、多分 tatsu.to_python_sourcecodetatsu.to_python_model に渡す name は同じものにするのが正解だろうな。にしてもこれはなんだろうか。Semantic Actions に関係してることはさすがにわかるが、何に使うのだろう? まだわかんない。

さて。その Semantic Actions だが、ものによっては戻りをそのまま自力でトラバースしちゃった方がラクなケースも多そうだ。今例にしてるヤツだと:

1 # -*- coding: utf-8 -*-
2 import mycalc  # my parser, was generated by tatsu
3 
4 parser = mycalc.mycalcParser()
5 print(parser.parse("3 + 2 - (1 + 3 * 4)"))
1 [u'3', u'+', [u'2', u'-', [u'1', u'+', [u'3', u'*', u'4']]]]

これを翻訳するのは簡単であろう。セマンティクスアクションを書きたければたとえばこう:

python モジュールとしてパーサを書き出したとして。
 1 # -*- coding: utf-8 -*-
 2 import mycalc  # my parser, was generated by tatsu
 3 
 4 class MyCalcSemantics(object):
 5     def number(self, ast):
 6         """
 7         number = /\d+/ ;
 8         """
 9         return int(ast)
10 
11     def _default(self, ast):
12         return ast
13 
14 parser = mycalc.mycalcParser()
15 print(parser.parse("3 + 2 - (1 + 3 * 4)", semantics=MyCalcSemantics()))
16 # [3, '+', [2, '-', [1, '+', [3, '*', 4]]]]

いいねぇ。parsimonious に感じたストレスは一切存在しない。そう、こういうことがやりたいんだと思うぞ、ふつー。

竜 TatSu は色々力作なようで、「左再帰」が(PEG なのに)書けたり、だとか、他にもチャームポイントが結構あるように見受けられる。少なくともワタシがここ数日でみた PEG 系の中では、最も印象が良い。きっと間違いなくオススメ、に違いないと思っている。