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)に拡張する。