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

Language Implementation Patternsという本がある。翻訳もされていて、邦題は「言語実装パターン―コンパイラ技術によるテキスト処理から言語実装まで」。作者はTerrence Parrで、ANTLRというJavaベースのパーサ・ジェネレータの開発者。

パーサ作成から始めて、構文木の歩き方から型検査、バイトコードインタプリタやトランスパイラなどの話題を実装例を出しながら解説している。以前ぱらっと読んで大変面白かったのだが、手を動かして実装はしたことがなかった。実装言語がJavaで、私はJavaはなんとか読めるけどほとんど書いたことがないので少し敬遠してしまっていた。

最近Python3.10にパターンマッチが入ったので、それを使ってちょっとした言語処理系を実装してみたいという気分になっている。PythonだったらJavaコードのオブジェクト指向もそれなりに忠実に実装できるのでは？と思ってLanguage Implementation Patternsの最初の実装例であるLL(1) Lexerを試してみた。

パースしたい「言語」

今回のパースしたい言語（≠プログラミング言語）は「ネスト可能なリスト。アトミックな要素は一個以上のアルファベットからなる」というもの。

以下がその文法（Language Implementation Patternsより引用）：

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

今回はLexerのみの実装なので'['、']'、','、'a'..'z'|'A'..'Z'の部分をトークンとして出力できるようになれば完了。

トークン

Pythonのdataclassを使ってトークンを表す（dataclassにするとプリント出力を自動的にいい感じに整えてくれたりする。今回の実装では出てこないがパターンマッチとの相性も非常に良さそうで、今後Pythonで代数的データ型を表現する場合はdataclassを使うのが主流になるんじゃないか？）：

from dataclasses import dataclass

@dataclass
class Eof:
    pass

@dataclass
class Comma:
    pass

@dataclass
class Lbrack:
    pass

@dataclass
class Rbrack:
    pass

@dataclass
class Name:
    s : str

これはLanguage Implementation Patternsの実装とは結構違っている。LIPではTokenクラスが定義されていて、トークンの種類を表す整数とLexされた文字列の二つをデータとして保持している。

Lexer実装１

というわけでLexer自体の実装にうつる。

まずLanguage Implementation PatternsのJava実装にまあまあ忠実なやり方：

import string

from liptoken import Eof, Comma, Lbrack, Rbrack, Name

class Lex:
    def __init__(self, s):
        self.s = s
        self.p = 0
        self.c = s[0] if s else 'EOF'

    def next_token(self):
        while True:
            match self.c:
                case c if c in string.whitespace:
                    self._consume()
                    continue
                case 'EOF':
                    return Eof()
                case ',':
                    self._consume()
                    return Comma()
                case '[':
                    self._consume()
                    return Lbrack()
                case ']':
                    self._consume()
                    return Rbrack()
                case c if _is_letter(c):
                    return self._name()
                case c:
                    raise ValueError(f"Invalid character {c}")

    def _consume(self):
        self.p += 1
        try:
            self.c = self.s[self.p]
        except IndexError:
            self.c = 'EOF'

    def _name(self):
        cs = []
        while _is_letter(self.c):
            cs.append(self.c)
            self._consume()
        return Name(''.join(cs))


def _is_letter(c):
    return c in string.ascii_letters

Lexerクラスに入力を文字列self.sとして持たせ、どの文字まで消費したかを表す「ポインタ」的なデータself.pをself._consumeメンバ関数を使って進めながら、１トークンごとにself.next_tokenで返していく。

self.next_tokenでは現在の文字であるself.cにパターンマッチして何のトークンを出力するかを決めていく。アルファベットに遭遇した場合はself._name関数を呼び出して複数の文字を消費するが、それ以外だと１文字につき１トークンなので楽だ。

ファイル終端に関してはちょっとPythonのダイナミックさやら文字列・文字の関係やらを少し悪用して、self.cに"EOF"という文字列をそのまま入れる形で扱っている。複数の文字からなる文字列はこのケース以外ではself.cに入らないので、この文字列に対してパターンマッチしても入力とかぶるリスクはない。

（ちなみに「Language Implementation Patternsに忠実」とは言っても、LIPではLexerをベースクラスにして継承したNameListLexerを作成しているのに対してここではそのまま一つのクラスとして実装しているので微妙な違いはある）

使ってみる：

>>> tokens = []
>>> lexer = Lex("[abc, def,[g,h,i],[]]")
>>> while not tokens or tokens[-1] != Eof():
...   tokens.append(lexer.next_token())
...
>>> tokens
[Lbrack(), Name(s='abc'), Comma(), Name(s='def'), Comma(), Lbrack(), Name(s='g'), Comma(), Name(s='h'), Comma(), Name(s='i'), Rbrack(), Comma(), Lbrack(), Rbrack(), Rbrack(), Eof()]

Lexer実装２ - Iterator Protocol

next_tokenのように一個ずつオブジェクトを返してくるストリーム的なものはIterator Protocolに従うように実装した方がよりPythonっぽい：

import string

from liptoken import Eof, Comma, Lbrack, Rbrack, Name

class Lex:
    def __init__(self, s):
        self.s = s
        self.p = 0
        self.c = s[0] if s else 'EOF'
        self.done = False

    def __iter__(self):
        return self

    def __next__(self):
        while not self.done:
            match self.c:
                case c if c in string.whitespace:
                    self._consume()
                    continue
                case 'EOF':
                    self.done = True
                    return Eof()
                case ',':
                    self._consume()
                    return Comma()
                case '[':
                    self._consume()
                    return Lbrack()
                case ']':
                    self._consume()
                    return Rbrack()
                case c if _is_letter(c):
                    return self._name()
                case c:
                    raise ValueError(f"Invalid character {c}")
        raise StopIteration

    def _consume(self):
        self.p += 1
        try:
            self.c = self.s[self.p]
        except IndexError:
            self.c = 'EOF'

    def _name(self):
        cs = []
        while _is_letter(self.c):
            cs.append(self.c)
            self._consume()
        return Name(''.join(cs))


def _is_letter(c):
    return c in string.ascii_letters

実装１とほとんど変わっていないが、これでLexオブジェクトはIteratorになる。

あるオブジェクトがIteratorであるためには__iter__と__next__が定義されている必要がある。__iter__はオブジェクトその物を返し、__next__はストリームの次の要素を返すか、ストリーム終端を表すStopIteration例外を投げる。

まず__iter__は簡単：

    __iter__(self):
        return self

__next__はnext_tokenを微修正しただけ。self.doneフラグを追加、EOFのパターンでTrueにし、フラグがTrueだと大元のwhileループから出てStopIterationを投げる。

Iteratorにすることで、こんな使いかたができる：

>>> for token in Lex("[abc, def,[g,h,i],[]]"):
...   print(token)
...
Lbrack()
Name(s='abc')
Comma()
Name(s='def')
Comma()
Lbrack()
Name(s='g')
Comma()
Name(s='h')
Comma()
Name(s='i')
Rbrack()
Comma()
Lbrack()
Rbrack()
Rbrack()
Eof()

Lexer実装３ - Character Stackを使ったGenerator

Generator関数を使うとIterator Protocolを持ったクラスを定義するよりも手軽にIteratorオブジェクトを作成できる。

Lexクラスが保持している状態というのは単に文字列とその中での位置であり、さらにいうと一旦消費してしまった文字には戻る必要がない。なのでその状態を「文字のスタック」として表してしまえば、あとはクラスである必要はない。

というわけでgenerator関数としてのLexer実装：

import string

from liptoken import Eof, Comma, Lbrack, Rbrack, Name

def lex(s):
    char_stack = list(reversed(s))
    while char_stack:
        match char_stack.pop():
            case c if c in string.whitespace:
                continue
            case ',':
                yield Comma()
            case '[':
                yield Lbrack()
            case ']':
                yield Rbrack()
            case c if _is_letter(c):
                yield _name(c, char_stack)
            case c:
                raise ValueError(f"Invalid character {c}")
    yield Eof()

def _name(c, char_stack):
    name_cs = [c]
    while char_stack and _is_letter(char_stack[-1]):
        name_cs.append(char_stack.pop())
    return Name(''.join(name_cs))

def _is_letter(c):
    return c in string.ascii_letters

Pythonのリストは末尾からのpopがO(1)なので、入力文字列のすべての文字を逆順に入れたリストを「文字スタック」として扱い、self.consumeの代わりにchar_stack.popしていく。あとはnext_tokenがlexそのものになり、returnの代わりにyieldすることでgenerator関数としてトークンのストリームを返すようになる。

>>> for token in lex("[abc, def,[g,h,i],[]]"):
...   print(token)
...
Lbrack()
Name(s='abc')
Comma()
Name(s='def')
Comma()
Lbrack()
Name(s='g')
Comma()
Name(s='h')
Comma()
Name(s='i')
Rbrack()
Comma()
Lbrack()
Rbrack()
Rbrack()
Eof()

結論

あまり複雑な状態管理が必要ないLexer（やパーサ）ならPythonだったらgenerator関数でスッキリ書ける。

ただし実際に言語処理系の実装などでLexerを自前で書く場合はエラーメッセージの出力だとかで複雑化してクラスにする必要が出てきそうだ。

どちらにせよ、Lexerのような遅延ストリームはまさにIterator Protocolで表現されるべきものなので、クラスで書く場合なら__iter__と__next__を実装するようにしたい。

疑問点

Language Implementation PatternsではこのLexerのことをLL(1)だとかrecursive descentだとか書いてあるのだが、Lexerに文法があるわけでもないのでLL(1)なのか？という点と構文木のようなネストした構造を出力するわけでもないので再帰する必要ないのでは？という点がもやもやしている。