PythonでLanguage Implementation Patternsのパーサと戯れる Backtrack可能なパーサ

前回実装したBacktrackableストリームを使って「任意のトークンを消費してパースを試した上でバックトラックできる」パーサを実装していく。

言語

前回同様の言語。再掲するとこのようなもの：

list        : '[' elements ']';
elements    : element (',' element)*;
element     : NAME | assign | list | list_assign;
assign      : NAME '=' NAME;
list_assign : list '=' list;
NAME        : ('a'..'z' | 'A'..'Z')+;

list_assignでリスト間の代入が可能になっており、elementでlistとlist_assignのどちらのパースを行うかを決めるのに固定数のトークン先読みでは足りなくなってしまう可能性が出る。

パーサ

今回実装するパーサはLanguage Implementation Patternsのものと同じように、「失敗する可能性のあるパースは必ずバックトラック。もし最初のパースが成功したらもう一回同じパースをバックトラックなしで。もし失敗したら別のパースを試す」という流れになっている。

この実装だと成功する場合同じパースを必ず二回実行することになるので「試したパースが失敗した場合のみバックトラックして別のパースを試す」の方が効率が良さそうなものだが、Language Implementation Patternsでは「パース時に副作用がある場合、『バックトラックする予定の試験的パース時は副作用は飛ばす』という処理ができる」「副作用なしの場合、後に紹介するPackratで効率化できる」という観点からこの実装になっているようだ。

まずparse関数がPeekableではなくBacktrackableでストリームを作成する：

import xtokens as t
import xlexer as xl

from utils import Backtrackable

def parse(char_stream):
    tokens = Backtrackable(xl.lex(char_stream)) # ここを変更
    _list(tokens)
    _match(tokens, t.Eof)

Backtrackableのbacktrack_alwaysコンテキストマネジャーを使って「必ずバックトラックする試験的パース」の関数_testを実装：

def _test(tokens, f):
    with tokens.backtrack_always():
        try:
            f(tokens)
        except ValueError:
            return False
    return True

トークンストリームと試したいパース関数を受け取り、パースが成功するかどうかを真偽値で返す。必ずバックトラックするのでトークンストリームのポジションは_testが呼ばれる前と後とで変わらない。

今まで先読みでパターンマッチしていた_element関数を_testを使うように変更：

def _element(tokens):
    if _test(tokens, _assign):
        _assign(tokens)
    elif _test(tokens, _name):
        _name(tokens)
    elif _test(tokens, _assign_list):
        _assign_list(tokens)
    elif _test(tokens, _list):
        _list(tokens)
    else:
        raise ValueError(f"Invalid token {tokens[0]}")

各パース関数を_testで試していって、うまくいった場合は_testなしでもう一度パース。すべての_testが失敗した場合は例外を投げる。

新たに追加したパース関数：

def _assign_list(tokens):
    _list(tokens)
    _match(tokens, t.Equal)
    _list(tokens)

def _name(tokens):
    _match(tokens, t.Ident)

_assign_listが今回の文法の変更箇所であるlist_assign : list '=' list;の実装。

_nameは今までは_element関数の中で直接判定していたのだが、_testに渡せるように新たに関数として定義した。

他の部分は以前と変わらず：

def _list(tokens):
    _match(tokens, t.Lbrack)
    _elements(tokens)
    _match(tokens, t.Rbrack)

def _elements(tokens):
    _element(tokens)
    while tokens[0] == t.Comma():
        next(tokens)
        _element(tokens)

def _assign(tokens):
    _match(tokens, t.Ident)
    _match(tokens, t.Equal)
    _match(tokens, t.Ident)

...

def _match(tokens, token_type):
    if isinstance(tokens[0], token_type):
        next(tokens)
    else:
        raise ValueError(f"Failed to match {tokens[0]} to type {token_type}")

使ってみる

>>> parse("[abc, [d, [e], f, g]]")
>>> parse("[abc, [d, [e], f, g]")
Traceback (most recent call last):
...
ValueError: Failed to match Eof() to type <class 'xtokens.Rbrack'>
>>> parse("[abc, [d, [e]=[x], f, g]]")
>>> parse("[abc=xyz, [d, [e]=[x], f, g]]")
>>> parse("[abc=[xyz], [d, [e]=[x], f, g]]")
Traceback (most recent call last):
...
ValueError: Failed to match Equal() to type <class 'xtokens.Rbrack'>

今回のコード

Python Implementation of Backtracking Recursive Descent Parser based loosely on Language Implementation Patterns · GitHub

次回

前述の通りこの実装はかなり効率が悪い。具体的にどれくらい無駄にパースを繰り返すのかを計測して、その解決方法であるPackratパーサを実装する。