LispKit Lisp処理系の実装 １：パーサ
前回書いたとおりまずはパーサを実装する。
最近散々パーサ実装について書いてきてなんだが、Lispなのでかなりの手抜きパーサ。
字句解析
まずはトークンの定義：
from dataclasses import dataclass @dataclass class Lparen: pass @dataclass class Rparen: pass @dataclass class Dot: pass @dataclass class Alpha: s : str @dataclass class Num: n : int
Quoteをトークンとして扱って、例えば(QUOTE (1 2 3))の代わりに'(1 2 3)と書けるようにしようかとも考えたのだが、タネ本の方ではそういう実装になっていなかったので今回は省略。
字句解析は本当に手抜き：
def lex(s): s = s.replace("(", " ( ").replace(")", " ) ").replace(".", " . ") for token in s.split(): match token: case "(": yield t.Lparen() case ")": yield t.Rparen() case ".": yield t.Dot() case _ if all((c in string.ascii_letters) for c in token): yield t.Alpha(token) case _ if all((c in string.digits) for c in token): yield t.Num(int(token)) case _: raise ValueError(f"Unable to lex {token}")
Pythonの文字列処理のs.replace(...)で().の文字の周りに空白を入れてからs.split()を呼んで、それをパターンマッチで適当なトークンクラスに変換している。
構文解析
ASTのノードの定義：
from dataclasses import dataclass @dataclass class Alpha: s : str @dataclass class Num: n : int @dataclass class Cons: car : any cdr : any
トークンとASTでAlphaとNumがかぶっているのが嫌だが、うまく差別化できる名前が思いつかない。見ての通り、三種類の要素しかないAST。
パーサは非常に簡単ながら再帰下降パーサになっている：
def parse(s): tokens = list(lex(s))[::-1] return parse_exp(tokens) def parse_exp(tokens): match tokens.pop(): case t.Lparen(): return parse_list(tokens) case t.Num(n): return a.Num(n) case t.Alpha(s): return a.Alpha(s) case token: raise ValueError(f"Unexpected token {token} at start of expression") def parse_list(tokens): items = [] tail = a.Alpha("NIL") while tokens[-1] not in (t.Dot(), t.Rparen()): items.append(parse_exp(tokens)) if tokens[-1] == t.Dot(): tokens.pop() tail = parse_exp(tokens) if tokens[-1] != t.Rparen(): raise ValueError(f"Unexpected token {tokens[-1]} found at end of dotted list") tokens.pop() for item in reversed(items): tail = a.Cons(item, tail) return tail
lexerの返すトークンを全部逆順にリストに入れて、相互再帰関数でpopして消費しながら回していく、というのは結構よく使う小技。
例えばこんな問題でもほぼ同じ手法が使えた：
Pythonなら
— zehnpaard (@zehnpaard) May 14, 2021
def get_node(items):
n=items.pop()
c=get_children(items, n["level"])
if c:
n["children"]=c
return n
def get_children(items, level):
c=[]
while items and items[-1]["level"]>level:
c.append(get_node(items))
return c
ns=get_children(items[::-1], 0) https://t.co/lg5MNZItp0
全トークンがメモリに乗るのが微妙だが、それ以外では無限に先読み可能なスタックとして便利に使える。
あとはparse_expで左カッコに遭遇したらparse_listを呼び出し、その中でリストの要素の数だけparse_expが呼び出される、という相互再帰構造。
使ってみる
前回同様、ユニットテストを掲載する。
まずはlexer：
def test_lexer(): assert list(p.lex("()")) == [t.Lparen(), t.Rparen()] assert list(p.lex("(abc)")) == [t.Lparen(), t.Alpha("abc"), t.Rparen()] assert list(p.lex("( abc) ")) == [t.Lparen(), t.Alpha("abc"), t.Rparen()] assert list(p.lex("(abc 2)")) == [t.Lparen(), t.Alpha("abc"), t.Num(2), t.Rparen()] assert list(p.lex("(abc 2 . ghi )")) == [t.Lparen(), t.Alpha("abc"), t.Num(2), t.Dot(), t.Alpha("ghi"), t.Rparen()] assert list(p.lex("(()()(")) == [t.Lparen(), t.Lparen(), t.Rparen(), t.Lparen(), t.Rparen(), t.Lparen()]
parser：
def test_parser(): assert p.parse("()") == a.Alpha("NIL") assert p.parse("(abc)") == a.Cons(a.Alpha("abc"), a.Alpha("NIL")) assert p.parse("(abc 2 . ghi )") == a.Cons(a.Alpha("abc"), a.Cons(a.Num(2), a.Alpha("ghi"))) assert p.parse("(abc 2 . (ghi) )") == a.Cons(a.Alpha("abc"), a.Cons(a.Num(2), a.Cons(a.Alpha("ghi"), a.Alpha("NIL"))))
