Arpeggio (recursive descent parser generator for Python) のへろわるど

Parsing In Python: Tools And Libraries より。

Arpeggio。parsimonious と同じく PEG 系。parsimonious 同様にやってみる前から好印象を抱いている。どうか?

parsimonious でフライングで言及しちゃったビジターの話はまず置いておくとしても、ドキュメントをちょっと斜め読みしただけでもすぐにわかるチャームポイントが、構文の定義方法が「選べる」(のみならず「作れる」)こと。「作る」ことをしないなら、出来合いで3種類選べる:

個人的にはこれが一番「ありがたい」。既知のものを読む方が楽だろ。

 1 # -*- coding: utf-8 -*-
 2 from __future__ import unicode_literals
 3 from arpeggio.peg import ParserPEG  # use traditional PEG
 4 
 5 # Calc grammar in traditional PEG language
 6 grammar = """
 7 // Calc grammar in traditional PEG language
 8 
 9 number <- r'\d*\.\d*|\d+';
10 factor <- ("+" / "-")?
11           (number / "(" expression ")");
12 term <- factor (( "*" / "/") factor)*;
13 expression <- term (("+" / "-") term)*;
14 calc <- expression+ EOF;
15 """
16 # we will make a parser.
17 parser = ParserPEG(
18     grammar,
19     "calc",  # root rule name
20     debug=True)
21 print(parser.parse("-(4-1)*5+(2+4.67)+5.89/(.2+7)"))

clean PEG。こちらだけ先に知ってれば確かに読みやすく書きやすかろう。

 1 # -*- coding: utf-8 -*-
 2 from __future__ import unicode_literals
 3 from arpeggio.cleanpeg import ParserPEG  # use clean PEG
 4 
 5 # Calc grammar in clean PEG language
 6 grammar = r"""
 7 # Calc grammar in clean PEG language
 8 
 9 number = r'\d*\.\d*|\d+'
10 factor = ("+" / "-")?
11           (number / "(" expression ")")
12 term = factor (( "*" / "/") factor)*
13 expression = term (("+" / "-") term)*
14 calc = expression+ EOF
15 """
16 
17 # we will make a parser.
18 parser = ParserPEG(
19     grammar,
20     "calc",  # root rule name
21     debug=True)
22 print(parser.parse("-(4-1)*5+(2+4.67)+5.89/(.2+7)"))

Python 文、式で定義。これを好む人々がどうやら多そうだがワタシの好みではない。

 1 # -*- coding: utf-8 -*-
 2 from __future__ import unicode_literals
 3 
 4 try:
 5     text=unicode
 6 except:
 7     text=str
 8 # The canonical grammar format uses Python statements and expressions.
 9 from arpeggio import Optional, ZeroOrMore, OneOrMore, EOF, \
10     ParserPython
11 from arpeggio import RegExMatch as _
12 
13 # Calc grammar in the canonical grammar format uses Python statements and expressions.
14 def number():     return _(r'\d*\.\d*|\d+')
15 def factor():     return Optional(["+","-"]), [number,
16                           ("(", expression, ")")]
17 def term():       return factor, ZeroOrMore(["*","/"], factor)
18 def expression(): return term, ZeroOrMore(["+", "-"], term)
19 def calc():       return OneOrMore(expression), EOF
20 
21 # we will make a parser.
22 parser = ParserPython(
23     calc,  # root rule (see def calc)
24     debug=True)
25 print(parser.parse("-(4-1)*5+(2+4.67)+5.89/(.2+7)"))

traditional PEG, clean PEG がお気に召さないなら好きに作りなはれやなんてことを言えるのはパーサジェネレータならではね。

それと上の例を動作させてみてすぐにわかったのだが、debug=True によって、ご丁寧に DOT (GraphViz) を生成してくれた。ここで例にした「calc」では4つの dot ファイル calc_parse_tree.dot、calc_peg_parser_model.dot、peggrammar_parse_tree.dot、peggrammar_parser_model.dot が作られた。それぞれレンダリングしてみた(dot -Tpng calc_parse_tree.dot > calc_parse_tree.png のように):

たぶん「peggrammar_」の方(三つ目と四つ目)は calc 固有ではなくて、「PEG 言語」そのものの方なので普段はいらないね。(PEG の書き方を間違えた、みたいなケースで少しは役立つ? いやぁ、むしろ「オレさま PEG 似方言」を作りたい場合のデバッグだろう、これはたぶん。)

さて、木の横断。「ビジター」。以下公式サンプルほぼそのまま:

 1 # -*- coding: utf-8 -*-
 2 from __future__ import unicode_literals
 3 from arpeggio.peg import ParserPEG
 4 from arpeggio import PTNodeVisitor, visit_parse_tree
 5 
 6 # Calc grammar in traditional PEG language
 7 grammar = r"""
 8 // Calc grammar in traditional PEG language
 9 
10 number <- r'\d*\.\d*|\d+';
11 factor <- ("+" / "-")?
12           (number / "(" expression ")");
13 term <- factor (( "*" / "/") factor)*;
14 expression <- term (("+" / "-") term)*;
15 calc <- expression+ EOF;
16 """
17 
18 # Visitor for semantic evaluation
19 class CalcVisitor(PTNodeVisitor):
20 
21     def visit_number(self, node, children):
22         """
23         Converts node value to float.
24         """
25         if self.debug:
26             print("Converting {}.".format(node.value))
27         return float(node.value)
28 
29     def visit_factor(self, node, children):
30         """
31         Applies a sign to the expression or number.
32         """
33         if self.debug:
34             print("Factor {}".format(children))
35         if len(children) == 1:
36             return children[0]
37         sign = -1 if children[0] == '-' else 1
38         return sign * children[-1]
39 
40     def visit_term(self, node, children):
41         """
42         Divides or multiplies factors.
43         Factor nodes will be already evaluated.
44         """
45         if self.debug:
46             print("Term {}".format(children))
47         term = children[0]
48         for i in range(2, len(children), 2):
49             if children[i - 1] == "*":
50                 term *= children[i]
51             else:
52                 term /= children[i]
53         if self.debug:
54             print("Term = {}".format(term))
55         return term
56 
57     def visit_expression(self, node, children):
58         """
59         Adds or substracts terms.
60         Term nodes will be already evaluated.
61         """
62         if self.debug:
63             print("Expression {}".format(children))
64         expr = children[0]
65         for i in range(2, len(children), 2):
66             if i and children[i - 1] == "-":
67                 expr -= children[i]
68             else:
69                 expr += children[i]
70         if self.debug:
71             print("Expression = {}".format(expr))
72         return expr
73 
74 
75 # we will make a parser.
76 parser = ParserPEG(
77     grammar,
78     "calc",  # root rule name
79     debug=False)
80 tree = parser.parse("-(4-1)*5+(2+4.67)+5.89/(.2+7)")
81 result = visit_parse_tree(tree, CalcVisitor(debug=True))
82 print(result)