言語

前回の変数間の代入に加えて、リスト間の代入も追加した言語を対象にする：

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

こんな入力が許容される：

[abc, [def, g] = [h], i]

変数代入の場合とは違い、１要素が単なるリストなのかリスト代入なのかを判断するのには、それを可能とするトークン先読みの個数が定まらない（最初のリストをパースするのに任意のトークンを確認する必要が出てくるため）。というわけでPeekableのkパラメータを増やすだけでは対応できない。

解決の一案として「とりあえず一つのやり方（リスト代入）でパースしてみて、失敗したらトークンストリームの状態を巻き戻して（バックトラックして）別のやり方（単なるリスト）でパースしてみる」というやり方がある。

Backtrackableクラス

Peekableの強化版として「無限先読み」そして「バックトラック」を実装したBacktrackableクラスを作る：

from contextlib import contextmanager

class Backtrackable:
    def __init__(self, input_, sentinel=None):
        self._stream = iter(input_)
        self.sentinel = sentinel
        self.i = 0
        self.buffer = []
        self.backtrack_points = []

self._streamやself.sentinelはPeekable同様。Backtrackable特有なのは「現在消費したトークン数」であるself.i、「今まで見たすべてのトークンのバッファ」であるself.buffer、そして「バックトラックで戻るべき位置のスタック」であるself.backtrack_points。

まずPeekable同様__getitem__、__iter__そして__next__を実装して「無限先読み」を可能にする：

    def __getitem__(self, n):
        if isinstance(n, int):
            self._fill(n+1)
            return self.buffer[self.i + n]
        else:
            raise IndexError(f"Unsupported operation: Indexing into Backtrackable with {n}")

    def __iter__(self):
        return self

    def __next__(self):
        self._fill(1)
        res = self.buffer[self.i]
        self.i += 1
        return res

    def _fill(self, n):
        for _ in range(self.i + n - len(self.buffer)):
            self.buffer.append(next(self._stream, self.sentinel))

ポイントは最後の_fillメソッドで、現在のポジションiとバッファのサイズを元に「バッファに足りないトークンをiteratorから取ってきてバッファに追加する」という機能を持つ。これが__getitem__と__next__の両方で使われていて、無限先読みを可能にしている。

この実装だと読み込んだトークンが全部メモリの保持され続けるのが気になるが、とりあえずこれで行って機会があれば最適化を施したい。

最後にバックトラックを可能とする機能：

    @contextmanager
    def backtrack_always(self):
        self.backtrack_points.append(self.i)
        try:
            yield
        finally:
            self.i = self.backtrack_points.pop()

Pythonのwith構文で扱えるcontext managerになっているのが少し工夫したところ。

こんな使い方ができる：

bt = Backtrackable(...)
with bt.backtrack_always():
    xyz(bt) # ここでトークンを消費
# ここで元の位置に巻き戻っている

ちなみに失敗したときのみバックトラックするようなbacktrack_on_exceptionというメソッドも比較的簡単に追加できるのだが、今回のパーサでは使わないので割愛。

使ってみる

>>> bt = Backtrackable("abcd.efgh")
>>> bt[0]
'a'
>>> bt[5]
'e'
>>> bt[10]
>>> with bt.backtrack_always():
...   while bt[0] != '.':
...     print(next(bt))
...
a
b
c
d
>>> bt[0]
'a'

今回と次回のコード

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

Backtrackableクラスはutils.pyに定義してある。

次回

Backtrackableオブジェクトを使ってバックトラックありのパーサを実装する。

Arantium Maestum

プログラミング、囲碁、読書の話題

PythonでLanguage Implementation Patternsのパーサと戯れる　Backtrackableストリームオブジェクト

言語

Backtrackableクラス

使ってみる

今回と次回のコード

次回