PythonでLanguage Implementation Patternsのパーサと戯れる Packratパーサ
前回の記事は同じパースを何回も繰り返すので非効率だと書いたが、まずはどの程度非効率なのかを計測してからPackratパーサで効率化を図る。
計測
まずは問題の程度を計測したい。
こんなデコレータを定義する：
def _print_call(func): @functools.wraps(func) def f(tokens): print(f"{func} called in pos {tokens.i}") return func(tokens) return f
Pythonのデコレータは関数をとり関数を（修飾して）返す高階関数で、@decorator_nameと他の関数定義の前の行に書くことで定義される関数を修飾できる：
@_print_call def _list(tokens): _match(tokens, t.Lbrack) _elements(tokens) _match(tokens, t.Rbrack)
これで_list関数は一旦定義され、その関数が_print_call関数に渡され、そして_print_call内で定義され返されるf関数が_listという名前に再束縛される（functools.wrapを使うことでf関数は外部からは_list関数そのもののように見える）。
_list以外にも_element、_elements、_assign、_assign_list、_nameといったパーサ関数にデコレータをつける。これらの関数が呼び出された場合その関数と現在のトークンストリームの位置が標準出力にプリントされる。
試してみる：
>>> parse("[abc=xyz, [d, [e]=[x], f, g]]") <function _list at 0x10a8976d0> called in pos 0 <function _elements at 0x10a8977f0> called in pos 1 <function _element at 0x10a8975b0> called in pos 1 <function _assign at 0x10a897910> called in pos 1 <function _assign at 0x10a897910> called in pos 1 ~中略~ <function _element at 0x10a8975b0> called in pos 18 <function _assign at 0x10a897910> called in pos 18 <function _name at 0x10a897b50> called in pos 18 <function _name at 0x10a897b50> called in pos 18
長いので中略したが、全部で139行出力される。重複が多く、例えば
<function _name at 0x10a897b50> called in pos 9
という行は12回出現する。
フィボナッチ数を再帰関数で算出するのが非常に非効率になるのと同じ理由で、ツリー状に分岐していく計算の至るところで同じ計算がくり返されているのが問題。そして解決法もまったく同じで、計算をメモ化してしまえばいい。
具体的にはトークンストリームの現在地に対しての成功・失敗をメモ化で記憶しておくことで、同じ地点で同じパーサ関数が適用された場合計算せずに結果を返すように変更したい。
メモ化デコレータ
今回はPackratパーサのキモであるメモ化もデコレータで実装する：
def _memo(func): d = {} @functools.wraps(func) def f(tokens): match d.get(tokens.i, None): case int(n): tokens.i = n case ValueError() as e: raise e case None: current_pos = tokens.i try: func(tokens) d[current_pos] = tokens.i except ValueError as e: d[current_pos] = e raise return f
デコレータの返す関数にディクショナリーをクロージャで持たせて、トークンストリームの位置であるtokens.iをキーとして「結果」をキャッシュしている。
結果として可能なのは「パースが成功した場合のトークンストリームのポジションを表す整数」と「パースが失敗した場合のValueError」の二つ。それに「キャッシュにキーが入っていない場合のデフォルト値のNone」を加えた三つのケースに対してパターンマッチしている。
パターンマッチの結果が整数だった場合は、トークンストリームのポジションをその数に変更して終了。ValueErrorだった場合はそのエラーをそのまま投げる。Noneだった場合はパース関数を呼び出してその結果をキャッシュする。
_print_callのようにパース関数を修飾する：
@_memo def _list(tokens): _match(tokens, t.Lbrack) _elements(tokens) _match(tokens, t.Rbrack)
_element、_elements、_assign、_assign_list、_nameなどもすべてデコレータを付ける。
使ってみる
とりあえず計測・比較のために
@_memo @_print_call def _list(tokens): _match(tokens, t.Lbrack) _elements(tokens) _match(tokens, t.Rbrack)
のように「メモ化されていない結果を計算して返す場合のみ_print_callする」形でデコレータをつけてみる：
parsers$ python -i xparser_bt3.py >>> parse("[abc=xyz, [d, [e]=[x], f, g]]") <function _list at 0x104b6f7f0> called in pos 0 <function _elements at 0x104b6f9a0> called in pos 1 <function _element at 0x104b6f640> called in pos 1 <function _assign at 0x104b6fb50> called in pos 1 <function _element at 0x104b6f640> called in pos 5 <function _assign at 0x104b6fb50> called in pos 5 <function _name at 0x104b6feb0> called in pos 5 <function _assign_list at 0x104b6fd00> called in pos 5 <function _list at 0x104b6f7f0> called in pos 5 <function _elements at 0x104b6f9a0> called in pos 6 <function _element at 0x104b6f640> called in pos 6 <function _assign at 0x104b6fb50> called in pos 6 <function _name at 0x104b6feb0> called in pos 6 <function _element at 0x104b6f640> called in pos 8 <function _assign at 0x104b6fb50> called in pos 8 <function _name at 0x104b6feb0> called in pos 8 <function _assign_list at 0x104b6fd00> called in pos 8 <function _list at 0x104b6f7f0> called in pos 8 <function _elements at 0x104b6f9a0> called in pos 9 <function _element at 0x104b6f640> called in pos 9 <function _assign at 0x104b6fb50> called in pos 9 <function _name at 0x104b6feb0> called in pos 9 <function _list at 0x104b6f7f0> called in pos 12 <function _elements at 0x104b6f9a0> called in pos 13 <function _element at 0x104b6f640> called in pos 13 <function _assign at 0x104b6fb50> called in pos 13 <function _name at 0x104b6feb0> called in pos 13 <function _element at 0x104b6f640> called in pos 16 <function _assign at 0x104b6fb50> called in pos 16 <function _name at 0x104b6feb0> called in pos 16 <function _element at 0x104b6f640> called in pos 18 <function _assign at 0x104b6fb50> called in pos 18 <function _name at 0x104b6feb0> called in pos 18
今度は中略なし。全部で33行と、4分の１以下になった。
_print_callを外して使ってみる：
$ python -i xparser.py
>>> parse("[abc=xyz, [d, [e]=[x], f, g]]")
うまくいっているように見える。
しかし再起動なしに二回parseを使おうとすると問題が起きる：
$ python -i xparser.py >>> parse("[x=a]") >>> parse("[[[[[") >>> parse("[abc=xyz, [d, [e]=[x], f, g]]") Traceback (most recent call last): ... ValueError: Failed to match Lbrack() to type <class 'xtokens.Eof'>
parseが使うパーサ関数のキャッシュが残ってしまっているので、関数を使えるのが一回限りになってしまっている。（二回目以降は第一回とトークン数が合えばパース成功、合わなければ失敗する）
今回のコード
次回
次回はパーサのキャッシュをparse呼び出しごとにクリアするような実装にして、何回でも利用できるように修正する話。
