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