PythonでLanguage Implementation Patternsのパーサと戯れる lexerとPeekableストリームオブジェクト
パーサを作るにあたってまずはlexerから。
lexerと簡単なパーサで共通しているのは「消費可能なストリームの先頭を『消費することなく』先読みする必要がある」という点。lexerだと入力の文字のストリーム、パーサだとlexerの返すトークンストリーム、と対象は異なるがどちらも「先読み」が必要。
Peekable
Pythonのストリームであるiteratorは__next__で消費しないと次の要素が何かわからない。iteratorを拡張してpeekが可能なクラスをまず定義する：
class Peekable: def __init__(self, input_, k, sentinel=None): self.sentinel = sentinel self._k = k self._stream = iter(input_) self._peek = [next(self._stream, sentinel) for _ in range(k)] def __getitem__(self, n): if isinstance(n, int) and n >= self._k: raise IndexError(f"Invalid lookahead index {n} on Peekable with k={self._k}") return self._peek[n] def __iter__(self): return self def __next__(self): if self._peek[0] == self.sentinel: raise StopIteration res = self._peek[0] self._peek = self._peek[1:] self._peek.append(next(self._stream, self.sentinel)) return res
__iter__と__next__でiteratorにしてあり、さらに__getitem__を定義して先頭k個の要素を消費せずに先読みできるようにしてある。
正直Peekableは__getitem__を実装しないで利用者側にpeekable._peekに直接アクセスさせてもいい気もするのだけど、あとで出てくるBacktrackableとの兼ね合いもあって定義しておいた。
使い方としてはこんな感じ：
>>> p = Peekable("abcdefg", 2) >>> p[0] 'a' >>> p[1] 'b' >>> next(p) 'a' >>> p[0] ‘B’ >>> p[1] 'c' >>> p[2] Traceback (most recent call last): ... IndexError: Invalid lookahead 2 on Peekable with k=2 >>> list(p) ['b', 'c', 'd', 'e', 'f', 'g']
トークン
Lexerが返すトークンは以下の通り：
LBRACK : [
RBRACK : ]
EQUAL : =
COMMA : ,
EOF : EOF
NAME : ('a'..'z' | 'A'..'Z')+;
これらを愚直にdataclassとして別モジュールxtokens.pyに定義：
from dataclasses import dataclass @dataclass class Lbrack: pass @dataclass class Rbrack: pass @dataclass class Equal: pass @dataclass class Comma: pass @dataclass class Eof: pass @dataclass class Ident: s : str
Lexer
LexerはPeekableを使えば非常に簡単な非再帰関数として書ける：
import string from utils import Peekable import xtokens as t def lex(char_iterable): stream = Peekable(char_iterable, 1) return _lex(stream)
lex関数が外部インタフェースとなっており、文字iterableを引数にとる（まあ大抵は文字列だけど、例えばfileをラップして１文字ずつのストリームにしたものでも受け取れる）。そのiterableを先頭要素１個が先読み可能なPeekableにして、generatorを返す_lexに渡している。
def _lex(stream): while True: match stream[0]: case stream.sentinel: yield t.Eof() break case '[': next(stream) yield t.Lbrack() case ']': next(stream) yield t.Rbrack() case '=': next(stream) yield t.Equal() case ',': next(stream) yield t.Comma() case c if _is_letter(c): yield _lex_ident(stream) case c if c in string.whitespace: next(stream) case c: raise ValueError(f"Invalid character {c}") def _lex_ident(stream): cs = [] while _is_letter(stream[0]): cs.append(next(stream)) return t.Ident(''.join(cs)) def _is_letter(c): return c in string.ascii_letters
_lex関数は無限ループでPeekableな文字ストリームの先頭にパターンマッチしてトークンをyieldしていく。Peekableの終端要素であるsentinelに当たったらEofトークンを返して終了。
そもそもなぜlexerに先読みが必要になるかというと_lex_ident関数の中でwhile _is_letter(stream[0]):とやっているから。このループ条件チェックで文字を消費してしまうと、ascii_lettersではない文字に当たってループ停止した後で、その文字をトークン化するのに困ってしまう。
_lexで使われているのがPython3.10のStructural Pattern Matchingで、ここではあまり構造の分解などはしていないのであくまでswitch的な使い方をしている。if ... elif ... elseといった構文でも問題ないが、パターンマッチの方がスッキリする印象。
使ってみる
>>> lex("[abc, def, ghi , j, k, l]") <generator object _lex at 0x106c5a180> >>> list(lex("[abc, def, ghi , j, k, l]")) [Lbrack(), Ident(s='abc'), Comma(), Ident(s='def'), Comma(), Ident(s='ghi'), Comma(), Ident(s='j'), Comma(), Ident(s='k'), Comma(), Ident(s='l'), Rbrack(), Eof()] >>> list(lex("[abc = def, ghi , [j, k], l]")) [Lbrack(), Ident(s='abc'), Equal(), Ident(s='def'), Comma(), Ident(s='ghi'), Comma(), Lbrack(), Ident(s='j'), Comma(), Ident(s='k'), Rbrack(), Comma(), Ident(s='l'), Rbrack(), Eof()]
今回のコード
Python Implementation of LL(1) Lexer based loosely on Language Implementation Patterns · GitHub
次回
lexerができたので次はネストしないリストのための非常に簡単なパーサを実装する。
