Language Implementation PatternsのLL(1) ParserをPythonで実装してみる

前回に続いてLanguage Implementation PatternsのJava実装例をPythonでやってみる。

今回はLL(1) Recursive Descent Parser。

パース対象

パースする言語は前回と同様：

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

（Language Implementation Patternsより引用）

基本方針

再帰下降構文解析でやっていくので、上記の文法に対応するような形の関数群が相互再帰しながらトークンのストリームを消費していく、という流れになる。

またLL(1)ということで「ストリームを消費せずに先頭のトークン１個を参照できる」という機能が必要になる。

実装１

まずは前回同様Language Implementation Patternsの実装にそれなりに忠実なやり方：

import liptoken as t
import liplex2 as l

class Parse:
    def __init__(self, str_input):
        self.input = l.lex(str_input)
        self.lookahead = next(self.input)

    def _consume(self):
        self.lookahead = next(self.input)

    def _match(self, target):
        if self.lookahead == target:
            self._consume()
        else:
            raise ValueError(f"{self.lookahead} encountered when expecting {target}")

    def list(self):
        self._match(t.Lbrack())
        self.elements()
        self._match(t.Rbrack())

    def elements(self):
        self.element()
        while self.lookahead == t.Comma():
            self._consume()
            self.element()

    def element(self):
        match self.lookahead:
            case t.Name(_):
                self._consume()
            case t.Lbrack():
                self.list()
            case token:
                raise ValueError(f"Invalid token {token} encountered at start of element {[token]+list(self.input)}")

Parseクラスを定義し、ストリームの状態管理（先頭要素のLookaheadも含めて）とパースするための相互再帰的なメソッドの両方を持たせている。

_consumeや_matchといった内部実装のメソッド（Pythonなのでprivateとして隠蔽はされていないが）で、メンバデータのトークンストリームに対するマッチや消費を行う。この実装ではストリームを消費しきった状態でself._consumeすると、StopIteration例外が発生するのをそのまま上に投げるようになっているが、もう少しエラーメッセージなどを頑張ってもいいかもしれない・・・

list、elements、elementといったメソッドがが文法の各項目に１対１で対応している。

このパーサは「文法に従っている文字列を受け取れば黙って消費して何も返さない、文法に違反していればエラー」というバリデータになっている。言語処理系などでみる「構文木を返す」ものではないことに注意。

>>> p1 = Parse("[abc, def, [x,y,z] , [a]]")
>>> p1.element()
>>> p2 = Parse("[abc, def, [x,y,z] , []]")
>>> p2.element()
Traceback (most recent call last):
...
ValueError: Invalid token Rbrack() encountered at start of element [Rbrack(), Rbrack(), Eof()]

ちなみに明示的にEOFを調べないので、文字列の先頭にelementとしてパース可能な文字列が来ていればエラーは出ない。

>>> p = Parse("[abc, def, [x,y,z]] []")
>>> p.element()

実装２

次にパーサをクラス化せず、「Lookahead可能なストリームオブジェクトとそれに対する再帰下降な関数」という形での実装を試す。

まずはLookahead可能なストリームオブジェクト：

class Lookaheadable:
    def __init__(self, iterator):
        self.lookahead = [next(iterator)]
        self._stream = iterator

    def __iter__(self):
        return self

    def __next__(self):
        if not self.lookahead:
            raise StopIteration
        res = self.lookahead.pop()
        try:
            self.lookahead.append(next(self._stream))
        except StopIteration:
            pass
        return res

__iter__と__next__があるのでこのLookaheadableクラスもIteratorとして使える。さらにx.lookaheadというメンバ変数が要素数１か０となっていて、これで次の要素を参照できる（あれば）。ここでリストを使っているのはPoor man's option typeだが、LL(k)に拡張するときはこの方が便利かもしれない。

あとはこのストリームを消費する関数群を再帰下降で書く：

import liptoken as t
import liplex2 as l

def parse(s):
    tokens = Lookaheadable(l.lex(s))
    _element(tokens)

def _list(tokens):
    _match(tokens, t.Lbrack())
    _elements(tokens)
    _match(tokens, t.Rbrack())

def _elements(tokens):
    _element(tokens)
    while tokens.lookahead[0] != t.Rbrack():
        _match(tokens, t.Comma())
        _element(tokens)

def _element(tokens):
    match tokens.lookahead[0]:
        case t.Name(_):
            next(tokens)
        case t.Lbrack():
            _list(tokens)
        case token:
            raise ValueError(f"Invalid token {token} encountered at start of element {list(tokens)}")

def _match(tokens, target):
    if tokens.lookahead[0] == target:
        next(tokens)
    else:
        raise ValueError(f"{tokens.lookahead[0]} encountered when expecting {target}")

ここのロジックはクラスベースの実装とそこまで違いはない。ただ、トップレベルで使うparse関数を新たに定義し、_list、_elements、_elementはすべて内部実装とした。

ちなみに前回の実装に関して言及した「文字列の先頭さえちゃんとパースできればエラーにならない」問題はこの実装でも存在する。ただし解決法は簡単で、parse関数を少しいじってEOFを明示的にチェックすればいい：

def parse(s):
    tokens = Lookaheadable(l.lex(s))
    _element(tokens)
    _match(tokens, t.Eof())

これで"[abc, def, [x,y,z]] []"のように全体としては文法に従っていない文字列をパースしようとするとエラーになる：

>>> parse("[abc, def, [x,y,z]] []")
Traceback (most recent call last):
...
ValueError: Lbrack() encountered when expecting Eof()

実装３

実装２を修正して、ネストしたPythonリストと文字列をパース結果として返すようにしてみる：

def parse(s):
    tokens = Lookaheadable(l.lex(s))
    return _element(tokens)

def _list(tokens):
    _match(tokens, t.Lbrack())
    res = _elements(tokens)
    _match(tokens, t.Rbrack())
    return res

def _elements(tokens):
    res = [_element(tokens)]
    while tokens.lookahead[0] != t.Rbrack():
        _match(tokens, t.Comma())
        res.append(_element(tokens))
    return res

def _element(tokens):
    match tokens.lookahead[0]:
        case t.Name(s):
            next(tokens)
            return s
        case t.Lbrack():
            return _list(tokens)
        case token:
            raise ValueError(f"Invalid token {token} encountered at start of element {list(tokens)}")

def _match(tokens, target):
    if tokens.lookahead[0] == target:
        next(tokens)
    else:
        raise ValueError(f"{tokens.lookahead[0]} encountered when expecting {target}")

各関数にreturnを追加していくだけなのがほとんど（_listの場合は返す結果を集めるPythonリストを作成していく修正が少し入るが）。

以下のように使える：

>>> parse("[abc, def, [x,y,z] , [a]]")
['abc', 'def', ['x', 'y', 'z'], ['a']]

これだと文字列やリストをそのまま返しているが、言語処理系のためにASTのノードを作成していって返すのも変更量としては大して違わない。ノードを表すオブジェクトにラップしてから返すだけ。

結論

個人的には全部を一つのクラスにするより、Lookaheadを可能とする状態とそれに対する操作だけをまとめたクラスを定義し、パースはそれに対する関数群として作る方が好み。