Arantium Maestum

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

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