Writing An Interpreter In Go その4

その3はこちら

Parserへ識別子と演算子をASTに追加する処理をつけていく。

演算子には「左から右へ」「掛け算は足し算より先に」という優先順位があるが、C言語のコンパイラにチャレンジしたときは生成規則からパーサを書こうとして左再帰で詰んだり、スタックマシンで計算させてみたら右から処理されてしまったりとつらい記憶しかない。個人的にここは鬼門だと思っている。

2.6: 識別子

2.6: Add parser of identifier · nibral/monkey_interpreter@763c848 · GitHub

パース処理をトークンの種類をキーとするMapに登録しておいて、let / return 以外のトークンが来たらトークンに合わせた処理を呼び出す仕組み。このコミットでは識別子 (token.IDENT) のみ登録した。

イベントハンドラを登録するのに似ていて、パース対象のトークンが増えたらその分登録すればよいのでスマートっぽい。

あと、デバッグ・テストでParserがトークン列をどのように解釈したかを確認するために、各パース処理に String() を生やした。演算子ごとにカッコでくくるようにして、

1 + 2 * 3 → (1 + (2 * 3))

という感じで出力させる。ただ、GoLandだとテストでもデバッガが使えるので、ASTの中身を見るだけならこっちの方が早い気もする。

演算子の優先順位を示す定数を追加したがこの時点では使用していない。

2.6: 整数

2.6: Add parser of integer literal · nibral/monkey_interpreter@d6f0f9c · GitHub

AST上で整数を表す構造体を定義して、トークンの文字列を64ビット整数に変換する処理を書いて、token.INT の処理として登録して終わり。

一応整数に変換できなかった時のエラー処理も書いてあるが、Lexerの実装上文字列には0-9の数値のみ含まれるはずなので発動するのは64ビット整数の範囲外だったときだけ？

2.6: 前置演算子

2.6: Add parser of prefix operators · nibral/monkey_interpreter@f494a20 · GitHub

! と - の処理。前置演算子を表す構造体に Right というフィールドがあり、再帰的に式を処理するようになって「あー木構造っぽいなー」という感じが出てくる。

演算子が正しく処理されたか・ぶら下がっている数値は正しいかの両方を確認するので、実装したコードよりもテストの方が倍くらい長い。テスト駆動っぽいといえばその通りだけど、テストを書くのが面倒でついコピペしてしまう。

実装が何もない状態だとIDEの補完が効かなくてテスト書きづらいし、実装のガワだけ作ることにするといつのまにか中身まで作っててテストが後になる。この辺の解決策というか、テスト駆動するにはどこまで設計すべきなのかが知りたい。

2.6: 2項演算子

2.6: Add parser of infix operators with precedence · nibral/monkey_interpreter@b0ae349 · GitHub

==, !=, <, >, +, -, /, * の処理を一気に追加。といってもASTの構造は全部同じなのでParserに登録するところ以外は共通で使える。シュッと実装してテスト走らせるとテストが通った。

何が起きているのかさっぱりわからないが優先順位は守られている。どういうこっちゃと思って本を見ると

We are now officially able to parse infix operator expressions correctly!

Wait, what? What the hell did just happen? How does this work?

ということで、先に動くものを作ってから解説するスタイルだった。

2.7章の解説では、本では "1 + 2 + 3;" という文を例として ((1 + 2) + 3) というASTができる流れを追いかける。一番のポイントは parser/parser.go の parseExpression() にあるこの処理。

for !p.peekTokenIs(token.SEMICOLON) && precedence < p.peekPrecedence() {
    infix := p.infixParseFns[p.peekToken.Type]
    if infix == nil {
        return leftExp
    }

    p.nextToken()

    leftExp = infix(leftExp)
}

for のループ条件に演算子の優先順位が入っているのと、infix() の中から parseExpression() を再帰的に呼ぶときに演算子に合わせた優先順位を渡すことで木構造が左に深くなるか右に深くなるかが制御されるようになっている。

実は一回読んだだけだとよくわからなくて、ステップ実行したり紙に書いてみたりして何となく理解したつもり。これだけ読んでも意味不明だと思うので、ちゃんと知りたい人は本を買ってください。内容的にはここまでで半分くらい。

interpreterbook.com

www.oreilly.co.jp