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パーサを実装する。

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

前回のような固定数のトークン先読みではなく、任意のトークンを消費しつつパースし続け、失敗したらバックトラックするようなパーサを作りたい。

今回の記事はまずバックトラック機能を提供するトークンストリームのクラスを作成する。（パーサ本体は次回）

言語

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

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オブジェクトを使ってバックトラックありのパーサを実装する。

PythonでLanguage Implementation Patternsのパーサと戯れる LL(2)再帰的パーサ

先読み要素を増やすことで前回のLL(1)パーサより複雑な構文をパースできるようになる。

言語

ここまで見てきたリスト言語に変数間の代入を追加する：

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

例としては：

[a = b, c, [d, e, [f=g]]]

のようにリスト内要素の一つとしてx = yのような代入式が追加されている。

この変更の難しさはelementをパースする時にストリームの先頭がIdentトークンだった場合、NAME要素なのかassign要素なのかがわからないところ。NAME要素だと思ってelementパースを完了してしまって次のトークンがEqualだとそこでパースエラーになるし、逆にassignだと思ってEqualを期待してCommaやRbrackがくるのもエラーになってしまう。

先頭の２要素を先読みして、Identの次がEqualかどうか判定できれば回避できる。

パーサ

Peekableクラスがすでに先読みトークンを任意のk個にできるように実装されているので、実際のところパーサをLL(1)からLL(k)に拡張するのは難しくない。

まずparse関数でPeekableオブジェクトのkを2にする：

def parse(char_stream):
    tokens = Peekable(xl.lex(char_stream), 2) # Peekableのkを増やす
    _list(tokens)
    _match(tokens, t.Eof)

その上で_element関数のパターンマッチ対象を単一トークンから(tokens[0], tokens[1])と先頭２つのトークンのタプルにする：

def _element(tokens):
    match (tokens[0], tokens[1]): # 先頭２要素のタプルに対するパターンマッチ
        case (t.Ident(s), t.Equal()): # 第一要素がIdent、第二要素がEqual
            _assign(tokens)
        case (t.Ident(s), _): # 第一要素がIdent、第二要素はEqual以外
            next(tokens)
        case (t.Lbrack(), _):
           _list(tokens)
        case (token, _):
            raise ValueError(f"Invalid token {token}")

そしてcase (t.Ident(s), t.Equal())とcase (t.Ident(s), _)で場合分けし、前者の場合は_assign関数でパースする。

_assignは素直な実装：

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

文法の変更と比較してみると、やはり直接対応する形での_elementの変更と_assignの追加なのがわかる。

他は変更なし：

import xtokens as t
import xlexer as xl

from utils import Peekable

...

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 _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]")
>>> parse("[abc, d=e]")
>>> parse("[abc, d=e, [f, gh=i]]")
>>> parse("[abc, d=[e], [f, gh=i]]")
Traceback (most recent call last):
...
ValueError: Failed to match Lbrack() to type <class 'xtokens.Ident'>

今回のコード

Python Implementation of LL(2) Recursive Descent Parser based loosely on Language Implementation Patterns · GitHub

次回

必要となる先読みの数が定まらないような文法をパースするためにバックトラックできるトークンストリームとPEGパーサを実装する。

PythonでLanguage Implementation Patternsのパーサと戯れる ネストしたリストのLL(1)再帰的パーサ

前回の記事の言語とパーサを拡張して、ネストありリスト言語の再帰下降パーサを作る。

言語

文法はこの通り：

list     : '[' elements ']';
elements : element (',' element)*;
element  : NAME | list; # elementが再帰的にlistになり得る
NAME     : ('a'..'z' | 'A'..'Z')+;

前回に比べてelementが複雑化していてlistにもなり得るようになった。

許容される入力としては：

[a]
[abc, def]
[abc, [d, [e], f], g]

リストはいくらでも（Pythonのrecursion limitにぶつからない程度に）ネスト可能。

パーサ

変更は非常に簡単で、文法の変更に対応して_elementに分岐を追加するだけ：

def _element(tokens):
    match tokens[0]:
        case t.Ident(s):
            next(tokens)
        case t.Lbrack(): # ここだけ追加
            _list(tokens)
        case token:
            raise ValueError(f"Invalid token {token}")

_elementでパースする時に先頭のトークンがLbrack（つまり[）だった場合_listとしてパースする。

文法の変化箇所：

element  : NAME | list; # elementが再帰的にlistになり得る

に対応している。

それ以外は全く変更なし：

import xtokens as t
import xlexer as xl

from utils import Peekable

def parse(char_stream):
    tokens = Peekable(xl.lex(char_stream), 1)
    _list(tokens)
    _match(tokens, t.Eof)

...

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 _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}")

_listは_elementsを呼び出し、_elementsは_elementを呼び出すので、循環的に相互再帰になる。

使ってみる

>>> parse("[abc]")
>>> parse("[abc, [d, e, f]]")
>>> 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'>

今回のコード

Python Implementation of LL(1) Recursive Descent Parser based loosely on Language Implementation Patterns · GitHub

次回

複数のトークンを先読みする必要のある構文を追加して、パーサをLL(2)に拡張する。

PythonでLanguage Implementation Patternsのパーサと戯れる 簡単なリスト言語の非再帰的なパーサ

（注：この記事を出した当初はパースが成功した場合Trueを返す実装にしていたが、Language Implementation Patternsと同じように成功した場合は何も返さないように修正した。実装がスッキリするということと、失敗は例外で表現しているので返り値には意味がなかったことが理由）

ネストのないリスト言語のパーサを作る。

今回のシリーズで作るのはLanguage Implementation Patternsで紹介されているパーサと同じように「言語の文法に入力が従っているかを調べるパーサ」である。ASTのノードを返したりはしない。その方が実装が簡略化されてパーサ自体の特性がわかりやすい。ただし、試したところASTを返すように修正するのは非常に簡単である。

言語

今回パースする言語の文法：

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

前述の通り、ネストしないリストの言語で、例としては

[a]
[abc, de, f]

などが許容される入力。空リストは受け入れられない。

パーサ

import xtokens as t
import xlexer as xl

from utils import Peekable

def parse(char_iterable):
    tokens = Peekable(xl.lex(char_iterable), 1)
    _list(tokens)
    _match(tokens, t.Eof)

外部インタフェースであるparse関数は文字iterableをとり、lex関数（前回の記事参照）に渡してトークンストリーム化し、それを先読み要素１のPeekableに変換。_list関数でlistとしてパースして最後にEofトークンが残っていることを確認する。

パーサ本体であるプライベート（ちっくな）関数たち：

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 _element(tokens):
    match tokens[0]:
        case t.Ident(s):
            next(tokens)
        case token:
            raise ValueError(f"Invalid token {token}")

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}")

_list、_elementsそして_elementが文法の各行に非常に直感的な形で対応している。直感的なのが再帰的下降パーサのいいところだ（この場合は再起していないが）。

状態の塊であるPeekableなトークンストリームを消費する（そしてトークンが期待通りじゃない場合は例外を投げる！）副作用もりもりな関数ばかりなので、純粋関数型プログラミングから極端にかけ離れている・・・　がまあその割にはわかりやすい印象。

リストがネストしないので非再帰で、_listが_elementsを呼び出し、_elementsがループで_elementを呼び出す。_matchは次のトークンが特定のクラスであることを確認した上で消費する。

使ってみる

>>> parse("[abc]")
>>> parse("[abc, def]")
>>> parse("[abc, def, gh]")
>>> parse("[abc, def, [gh]]")
Traceback (most recent call last):
..
ValueError: Invalid token Lbrack()
>>> parse("[]")
Traceback (most recent call last):
..
ValueError: Invalid token Rbrack()

今回のコード

Python Implementation of LL(1) Non-Recursive Parser based loosely on Language Implementation Patterns · GitHub

次回

ネスト可能なリストを扱うためにパーサ関数を相互再帰的に変更する。

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

パーサを作るにあたってまずはlexerから。

lexerと簡単なパーサで共通しているのは「消費可能なストリームの先頭を『消費することなく』先読みする必要がある」という点。lexerだと入力の文字のストリーム、パーサだとlexerの返すトークンストリーム、と対象は異なるがどちらも「先読み」が必要。

Peekable

Pythonのストリームであるiteratorは__next__で消費しないと次の要素が何かわからない。iteratorを拡張してpeekが可能なクラスをまず定義する：

class Peekable:
    def __init__(self, input_, k, sentinel=None):
        self.sentinel = sentinel
        self._k = k
        self._stream = iter(input_)
        self._peek = [next(self._stream, sentinel) for _ in range(k)]

    def __getitem__(self, n):
        if isinstance(n, int) and n >= self._k:
            raise IndexError(f"Invalid lookahead index {n} on Peekable with k={self._k}")
        return self._peek[n]

    def __iter__(self):
        return self

    def __next__(self):
        if self._peek[0] == self.sentinel:
            raise StopIteration
        res = self._peek[0]
        self._peek = self._peek[1:]
        self._peek.append(next(self._stream, self.sentinel))
        return res

__iter__と__next__でiteratorにしてあり、さらに__getitem__を定義して先頭k個の要素を消費せずに先読みできるようにしてある。

正直Peekableは__getitem__を実装しないで利用者側にpeekable._peekに直接アクセスさせてもいい気もするのだけど、あとで出てくるBacktrackableとの兼ね合いもあって定義しておいた。

使い方としてはこんな感じ：

>>> p = Peekable("abcdefg", 2)
>>> p[0]
'a'
>>> p[1]
'b'
>>> next(p)
'a'
>>> p[0]
‘B’
>>> p[1]
'c'
>>> p[2]
Traceback (most recent call last):
...
IndexError: Invalid lookahead 2 on Peekable with k=2
>>> list(p)
['b', 'c', 'd', 'e', 'f', 'g']

トークン

Lexerが返すトークンは以下の通り：

LBRACK : [
RBRACK : ]
EQUAL : =
COMMA : ,
EOF : EOF
NAME : ('a'..'z' | 'A'..'Z')+;

これらを愚直にdataclassとして別モジュールxtokens.pyに定義：

from dataclasses import dataclass

@dataclass
class Lbrack:
    pass

@dataclass
class Rbrack:
    pass

@dataclass
class Equal:
    pass

@dataclass
class Comma:
    pass

@dataclass
class Eof:
    pass

@dataclass
class Ident:
    s : str

Lexer

LexerはPeekableを使えば非常に簡単な非再帰関数として書ける：

import string

from utils import Peekable
import xtokens as t

def lex(char_iterable):
    stream = Peekable(char_iterable, 1)
    return _lex(stream)

lex関数が外部インタフェースとなっており、文字iterableを引数にとる（まあ大抵は文字列だけど、例えばfileをラップして１文字ずつのストリームにしたものでも受け取れる）。そのiterableを先頭要素１個が先読み可能なPeekableにして、generatorを返す_lexに渡している。

def _lex(stream):
    while True:
        match stream[0]:
            case stream.sentinel:
                yield t.Eof()
                break
            case '[':
                next(stream)
                yield t.Lbrack()
            case ']':
                next(stream)
                yield t.Rbrack()
            case '=':
                next(stream)
                yield t.Equal()
            case ',':
                next(stream)
                yield t.Comma()
            case c if _is_letter(c):
                yield _lex_ident(stream)
            case c if c in string.whitespace:
                next(stream)
            case c:
                raise ValueError(f"Invalid character {c}")

def _lex_ident(stream):
    cs = []
    while _is_letter(stream[0]):
        cs.append(next(stream))
    return t.Ident(''.join(cs))

def _is_letter(c):
    return c in string.ascii_letters

_lex関数は無限ループでPeekableな文字ストリームの先頭にパターンマッチしてトークンをyieldしていく。Peekableの終端要素であるsentinelに当たったらEofトークンを返して終了。

そもそもなぜlexerに先読みが必要になるかというと_lex_ident関数の中でwhile _is_letter(stream[0]):とやっているから。このループ条件チェックで文字を消費してしまうと、ascii_lettersではない文字に当たってループ停止した後で、その文字をトークン化するのに困ってしまう。

_lexで使われているのがPython3.10のStructural Pattern Matchingで、ここではあまり構造の分解などはしていないのであくまでswitch的な使い方をしている。if ... elif ... elseといった構文でも問題ないが、パターンマッチの方がスッキリする印象。

使ってみる

>>> lex("[abc, def, ghi , j, k, l]")
<generator object _lex at 0x106c5a180>
>>> list(lex("[abc, def, ghi , j, k, l]"))
[Lbrack(), Ident(s='abc'), Comma(), Ident(s='def'), Comma(), Ident(s='ghi'), Comma(), Ident(s='j'), Comma(), Ident(s='k'), Comma(), Ident(s='l'), Rbrack(), Eof()]
>>> list(lex("[abc = def, ghi , [j, k], l]"))
[Lbrack(), Ident(s='abc'), Equal(), Ident(s='def'), Comma(), Ident(s='ghi'), Comma(), Lbrack(), Ident(s='j'), Comma(), Ident(s='k'), Rbrack(), Comma(), Ident(s='l'), Rbrack(), Eof()]

今回のコード

Python Implementation of LL(1) Lexer based loosely on Language Implementation Patterns · GitHub

次回

lexerができたので次はネストしないリストのための非常に簡単なパーサを実装する。

PythonでLanguage Implementation Patternsのパーサと戯れる 序

前２回の記事でも書いたとおり、Language Implementation Patternsのはじめの方をPythonで実装している。

具体的にはPackrat Parsingまで、本に出てくるクラスベースな実装ではなく、lookaheadやbacktrackの機能はトークンストリームの方に持たせた上で相互再帰関数の集まりとして実装してみた。ちなみにPython3.10の新機能であるStructural Pattern Matchingを多用している。

パースする言語はまず簡単なリストからはじめて：

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

リストのネスト：

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

変数間の代入：

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

そしてリスト間の代入：

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

へと拡張していく。

流れとしては：

• lexerとPeekableストリームオブジェクト
• 簡単なリスト言語の非再帰的なパーサ
• ネストしたリストのLL(1)再帰的パーサ
• 変数間代入のLL(2)再帰的パーサ
• Backtrackableストリームオブジェクトとリスト間代入のBacktrackパーサ
• Backtrack実行時間効率化のためのPackratパーサ
• Packratのキャッシュクリアとメモリ効率化

これらを個別の記事で解説していく。