これの実践。
Contents
「xpath のような記述で辞書検索」をパーサジェネレータを使って自作 (in Python)
動機のおさらいと作りたい式の構文
これに書いた通り。「「辞書探索のためのリッチなクエリ式」として、XPath そのものは使えない」、「出来合いのものを探すのが結構大変」、「せっかくいいパーサジェネレータ見つけたので、いいお題だよね」てことで。
作りたい式のデザインはこんな感じ:
1 dquery(d, '**/[`"akey"`]/[`1:-1`]/`"xyz" in k.lower()`/..')
スラッシュが XPath のそれと同じなのはいいだろう。「..
」は親ノード。「**
」は任意の深さ潜る。「[]
」は辞書・リストの「[]」そのもの(リストならスライスも出来るとして)、「``
」は「[]
」内にあるならそのまま「[]
」内に展開し、そうでないものは「filter(lambda k, v: {}, node.items())
」の「{}
」部分に埋めて評価する。そんな感じ。
スラッシュは今回のターゲットの場合なくてもいいんだけれど、あった方が読みやすいので。
式の構文解析、まで
ここまでで2時間ほど費やしてしまったのだが、これははじめ Lark で書き始めて、セマンティクスアクションが書きにくかったもんで 竜 TatSu に乗り換えた時間も含む。のでまぁ「順調なほう」だろう、たぶん。
まだ「辞書探索の実現」がない、ただのパース:
1 # -*- coding: utf-8 -*-
2 #
3 from __future__ import absolute_import
4 from __future__ import unicode_literals
5 from __future__ import print_function
6
7 import tatsu
8
9 # '**/[`"akey"`]/[`1:-1`]/`"xyz" in k.lower()`/..'
10 parser = tatsu.compile("""
11 start = q_chain $ ;
12
13 q_chain = q_curnode {q_chain_following}* ;
14
15 q_chain_following = "/" q_curnode ;
16
17 q_curnode = expression
18 | expression_getitem
19 | any_hier
20 | parent
21 ;
22
23 expression_getitem = "[" expression "]" ;
24
25 expression = "`" expression_str "`" ;
26 expression_str = {expression_chars}* ;
27 expression_chars = {"\\`"|/[^`]/}
28 | expression_chars {expression_chars}* ;
29
30 any_hier = "**" ;
31
32 parent = ".." ;
33
34 """, start="q_chain")
35
36 class _Semantics(object):
37 def q_chain(self, ast):
38 """
39 q_chain = q_curnode {q_chain_following}* ;
40 """
41 # flatten
42 res = [ast[0]]
43 for f in ast[1]:
44 if isinstance(f[0], (tuple,)):
45 res.append(f[0])
46 else:
47 res.append(f)
48 return res
49
50 def q_chain_following(self, ast):
51 """
52 q_chain_following = "/" q_curnode ;
53 """
54 return tuple([ast[1]])
55
56 def expression_getitem(self, ast):
57 """
58 expression_getitem = "[" expression "]" ;
59 """
60 return tuple(ast[:-1])
61
62 def expression(self, ast):
63 """
64 expression = "`" expression_str "`" ;
65 """
66 return (ast[0][0], ast[1])
67
68 def expression_str(self, ast):
69 """
70 expression_str = {expression_chars}* ;
71 """
72 return "".join(ast[0])
73
74 def any_hier(self, ast):
75 """
76 any_hier = "**" ;
77 """
78 return (ast,)
79
80 def parent(self, ast):
81 """
82 parent = ".." ;
83 """
84 return (ast,)
85
86 tree = parser.parse(
87 '[`"bkey"`]/**/[`"akey"`]/[`1:-1`]/`"xyz" in k.lower()`/..',
88 semantics=_Semantics())
89 print(*tree)
Lark だろうが Tatsu だろうが共通の「悩ましい部分」は、Lark の共通定義にあるこれ:
1 //
2 // Strings
3 //
4 STRING_INNER: ("\\\""|/[^"]/)
5 ESCAPED_STRING: "\"" STRING_INNER* "\""
に似たことをしようとするとハマる、という点。この例の「STRING_INNER
」は非常に貪欲な正規表現であるため、最優先でマッチするように書いてしまうと、ほかのどのルールにもマッチ出来なくなってしまう。
うろ覚えの知識をフル動員してこれを理解するならば、「たぶん終端(terminal)として STRING_INNER
(に似たもの)を定義しようとしてはいけない」てことだと思う。
ワタシの例の場合は expression_chars
がそれにあたるんだけれど、ただ Lark で LALR でやってたのと Tatsu が PEG であるのとでの違いは出てたかも。Lark 側でこの問題をクリアした後で乗り換えたんで「Tatsu でも同じだった」かどうかがわからない。
STRING_INNER
、expression_chars
には「貪欲過ぎる」こと以外にも使い勝手の問題があって、読めばわかると思うけれどこれは「一文字ずつ逐一トークンにバラける」。
この問題はもう避けようがないんだよね。ワタシの例の場合は「`(バッククオート)で囲まれた完全なフリーテキスト(バッククオート自身はバックスラッシュでエスケープ可)」というもので、「完全なフリーテキスト」とその他キーワード(「**
」など)を共存させるために。これはどんな定義を書く場合もほとんど共通と思う。
セマンティクスアクションの方は簡単に言えばこういう構造に読み替えてるだけ:
1 全体: (コマンド[, 引数]), ...
2 コマンド: "**", "..", "`"
例えば:
1 INPUT: '[`"bkey"`]/**/[`"akey"`]/[`1:-1`]/`"xyz" in k.lower()`/..'
2
3 RESULT:
4 ('[', ('`', '"bkey"')),
5 ('**',),
6 ('[', ('`', '"akey"')),
7 ('[', ('`', '1:-1')),
8 ('`', '"xyz" in k.lower()'),
9 ('..',)
ここまで来ればもう「実際の辞書探索実装を書くだけ」。
実際の辞書探索実装、のポイント
昨日脳内だけで考えていた際に一番苦労していたのが「**
」。これは(昔懐かしい) ant なんかで提供されていたのと同じもので、「カレントノードのもの全てとその配下ノード全て」の意味。xpath ではこれは出来なかったような気がするがどうだったっけか? 一番これこそが欲しいのよ。つまり、「aaa/Xxx/Yyy
」「aaa/bbb/Xxx/Yyy
」という相手に対して「**/Xxx/Yyy
」でどちらもマッチさせたいのだ。
これは深さ方向にノードを潜っていく際、「**
」に続く記述が真になるまでコマンドリストを先に進めない、というような考え方でいけるはずだ。今まだ実装書いてないが、たぶんそんな感じ。
まずは「**」実装なし
辞書トラバースの実装を (今の場合の) _Semantics
に埋め込むかそうしないかはケースバイケースと思う。今の例の場合は既に書いた _Semantics
が返す形が既に十分扱いやすいので、 _Semantics
とは完全に分けてしまう。
一気に全部書こうかとも思ったが、想定通り「**
」の実現はムゴいことになるので、まずはないものだけ先に書いてみる:
1 # ... (省略) ...
2
3 def query(d, expr):
4 r"""
5 >>> query({
6 ... "x1": {
7 ... "lst": [1, 3, 5, 7, 9],
8 ... },
9 ... "x2": {
10 ... "lst": [9, 3, 1, 7, 5],
11 ... },
12 ... }, '[`"x1"`]/[`"lst"`]/[`::2`]')
13 [[1, 5, 9]]
14 """
15 def _query(node, q, result, parents):
16 def _eval(node, cur_q, parents):
17 F1 = 'node[{}]'
18 F2 = '[(k, v) for k, v in node.items() if {}]'
19 cmd = cur_q[0]
20 if cmd == "..":
21 return parents.pop(-1)
22 elif cmd == "[":
23 # ex. '1:-1' -> 'node[1:-1]'
24 # ex. '"x1"' -> 'node["x1"]'
25 try:
26 return eval(F1.format(cur_q[1][1]))
27 except Exception:
28 # unsupported operation in current node
29 pass
30 elif cmd == "`":
31 # ex. '"xyz" in k.lower()'
32 # -> '[(k, v) for k, v in node.items() if "xyz" in k.lower()]'
33 try:
34 return [v for k, v in eval(F2.format(cur_q[1]))]
35 except Exception:
36 # unsupported operation in current node
37 pass
38
39 cur_q = q[0]
40 nextq = q[1:]
41 cmd = cur_q[0]
42 cands = None
43 cands = _eval(node, cur_q, parents)
44 if nextq:
45 _query(cands, nextq, result, parents + [node])
46 elif cands is not None:
47 # leaf query
48 result.append(cands)
49
50 q = parser.parse(expr, semantics=_Semantics())
51 result = []
52 _query(d, q, result, [])
53 return result
54
55
56 if __name__ == '__main__':
57 import doctest
58 doctest.testmod()
既に若干使用感に不満があったりもする。けどまぁこのまま進めるとする。動いてるとこだけ見てるぶんにはいい感じには見えるね。
parent
の振る舞いがおかしいことは今時点でわかっている(二つ上に上がれないとか色々)が、ひとまず放置。
ひとまずの初版
ひとまずこんなだね:
1 # -*- coding: utf-8 -*-
2 #
3 from __future__ import absolute_import
4 from __future__ import unicode_literals
5 from __future__ import print_function
6
7 import sys
8
9 import tatsu
10
11
12 # '**/[`"akey"`]/[`1:-1`]/`"xyz" in k.lower()`/..'
13 parser = tatsu.compile("""
14 start = q_chain $ ;
15
16 q_chain = q_curnode {q_chain_following}* ;
17
18 q_chain_following = "/" q_curnode ;
19
20 q_curnode = expression
21 | expression_getitem
22 | any_hier
23 | parent
24 ;
25
26 expression_getitem = "[" expression "]" ;
27
28 expression = "`" expression_str "`" ;
29 expression_str = {expression_chars}* ;
30 expression_chars = {"\\`"|/[^`]/}
31 | expression_chars {expression_chars}* ;
32
33 any_hier = "**" ;
34
35 parent = ".." ;
36
37 """, start="q_chain")
38
39 class _Semantics(object):
40 def q_chain(self, ast):
41 """
42 q_chain = q_curnode {q_chain_following}* ;
43 """
44 # flatten
45 res = [ast[0]]
46 for f in ast[1]:
47 if isinstance(f[0], (tuple,)):
48 res.append(f[0])
49 else:
50 res.append(f)
51 return res
52
53 def q_chain_following(self, ast):
54 """
55 q_chain_following = "/" q_curnode ;
56 """
57 return tuple([ast[1]])
58
59 def expression_getitem(self, ast):
60 """
61 expression_getitem = "[" expression "]" ;
62 """
63 return tuple(ast[:-1])
64
65 def expression(self, ast):
66 """
67 expression = "`" expression_str "`" ;
68 """
69 return (ast[0][0], ast[1])
70
71 def expression_str(self, ast):
72 """
73 expression_str = {expression_chars}* ;
74 """
75 return "".join(ast[0])
76
77 def any_hier(self, ast):
78 """
79 any_hier = "**" ;
80 """
81 return (ast,)
82
83 def parent(self, ast):
84 """
85 parent = ".." ;
86 """
87 return (ast,)
88
89 #tree = parser.parse(
90 # '[`"bkey"`]/**/[`"akey"`]/[`1:-1`]/`"xyz" in k.lower()`/..',
91 # semantics=_Semantics())
92 #print(*tree)
93
94 def query(d, expr):
95 r"""
96 >>> query({
97 ... "x1": {
98 ... "lst": [1, 3, 5, 7, 9],
99 ... },
100 ... "x2": {
101 ... "lst": [9, 3, 1, 7, 5],
102 ... },
103 ... }, '[`"x1"`]/[`"lst"`]/[`::2`]')
104 [[1, 5, 9]]
105 >>> list(sorted(query({
106 ... "x1": {
107 ... "lst": [1, 3, 5, 7, 9],
108 ... },
109 ... "x2": {
110 ... "lst": [9, 3, 1, 7, 5],
111 ... },
112 ... }, '**/[`"lst"`]/[`::2`]')))
113 [[1, 5, 9], [9, 1, 5]]
114 >>> list(sorted(query({
115 ... "x1": {
116 ... "lst": [1, 3, 5, 7, 9],
117 ... },
118 ... "x2": {
119 ... "lst": [9, 3, 1, 7, 5],
120 ... },
121 ... }, '**/[`"lst"`]/`v > 2`')))
122 [[3, 5, 7, 9], [9, 3, 7, 5]]
123 >>> query({
124 ... "x1": {
125 ... "lst": [1, 3, 5, 7, 9],
126 ... },
127 ... "x2": {
128 ... "lst": [9, 3, 1, 7, 5],
129 ... },
130 ... }, '`k.endswith("2")`')
131 [[{'lst': [9, 3, 1, 7, 5]}]]
132 """
133 def _query(node, q, result, parents):
134 def _eval(node, cur_q, parents):
135 F1 = 'node[{}]'
136 F2 = '[v for k, v in node.items() if {}]'
137 F3 = '[v for v in node if {}]'
138 cmd = cur_q[0]
139 if cmd == "..":
140 return parents.pop(-1)
141 elif cmd == "[":
142 # ex. '1:-1' -> 'node[1:-1]'
143 # ex. '"x1"' -> 'node["x1"]'
144 try:
145 return eval(F1.format(cur_q[1][1]))
146 except Exception:
147 # unsupported operation in current node
148 pass
149 elif cmd == "`":
150 if isinstance(node, (dict,)):
151 # ex. '"xyz" in k.lower()'
152 # -> '[v for k, v in node.items() if "xyz" in k.lower()]'
153 return eval(F2.format(cur_q[1]))
154 elif isinstance(node, (list,)):
155 return eval(F3.format(cur_q[1]))
156 else:
157 # what should we do?
158 pass
159
160 cur_q = q[0]
161 nextq = q[1:]
162 cmd = cur_q[0]
163 cands = None
164 if cmd == "**":
165 if isinstance(node, (dict,)):
166 childs = node.values()
167 elif isinstance(node, (list,)):
168 childs = list(node)
169 else:
170 # what should we do?
171 childs = []
172 for child in childs:
173 _query(child, nextq, result, parents + [node])
174 else:
175 cands = _eval(node, cur_q, parents)
176 if nextq:
177 _query(cands, nextq, result, parents + [node])
178 elif cands is not None:
179 # leaf query
180 result.append(cands)
181
182 q = parser.parse(expr, semantics=_Semantics())
183 result = []
184 _query(d, q, result, [])
185 return result
186
187
188 if __name__ == '__main__':
189 import doctest
190 doctest.testmod()
完成させないの? ⇒ させないよ、今は
入り口には立ったぞ、てことで、完成までやるのはやめとく。ほかにやることたんまりあるんで、こればっかやってるわけいんはいかんのよ。
parent
はおかしいままだし、期待した結果になってないとこもある。実際にイザ使おうとしたら全然使えないことがわかるであろう。
まぁこの記事が言いたいことは「辞書に対するリッチな検索を完成させる」ことにはなくて、「やってやれないことはない、やれば?」と言うがためのもんであって、まぁこれ自分でも欲しいやつなんで、いずれはちゃんと完成させようとは思わないでもないけれど、いつになるかは知らんよ、一年後かもしらんし、五年後かもしらん。そんときは追記するかもしれん。ただその前に出来合いのものを見つけてしまいそうな気がするわね。
もしこの手のことに興味があって、自分で続けてみたいと思うのであれば、以下のことには注意してくたさい:
- 必ずパーサジェネレータがないと書けない、と主張しているのではないので、「どうありがたいのか」を理解しながら遊んで欲しい。
- セマンティクスアクション部分の書き方は色々考え方があるので、ワタシの書き方をみて「こういうもんだ」と思わない方がいいよ。ここは実際に自分で動かしてみて感覚をつかんだほうがいい。
- 性能の件。これはワタシの今回のこれは、「まったくもって無頓着」にやってる。てことはお忘れなく。
eval
の是非について。eval
を使うことで「Python で出来ること全てが出来てしまう」ことは、危険も背負い込むことになることに注意。DSL (ドメイン固有言語)の動機の一つには「出来ることを制限する」ことにもあったりするので、それが目的なのであれば、構文のほうをもっと頑張る必要があります。(ワタシのは`~`
内は完全に無法地帯。)