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

次回

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