「Go言語で作るインタプリタ」を読んだ。親切な内容の本ではあるけどやっぱりインタプリタを作る。ってテーマ自体が難しく、読むのに苦戦したので内容書きながら整理してみる。
O'Reilly Japan - Go言語でつくるインタプリタ
ざっくり全体の流れ
- プログラムを標準入力に渡す
- 入力したプログラムを字句解析器(lexer)でトークンに分割する
- 分割したトークンから抽象構文木(ast)をつくる
- 抽象構文器を評価(eval)して結果を出力する
もう少し噛み砕いてみる
プログラムを構成するパッケージ
repl
「Read(読み込み)、Eval(評価)、Print(出力)、Loop(繰り返し)」の略。main関数からまず呼ばれるところ
token
ソースコードを分解して意味ごとにまとめたようなもの。「let a = 5」だったら「let」は変数宣言のletというキーワードで「a」は識別子で「=」はイコール分で「5」は整数。といった風に空白区切りで文字列を作ってそれぞれに意味を持たせる
lexer
字句解析器。ソースコードを受け取ってソースコードを表現するトークンを返す
parser
構文解析器。構文解析器とは入力データを受け取ってデータ構造を返すもの。今回の場合はプログラムを受け取って木構造のastを返却する。
ast
replで受け取った文字列を木構造にする。例えば「1 + 2」だったら「＋」の左下に「1」がぶら下がっていて右下に「2」がぶら下がっているようなイメージ。ほとんどのコンパイラやインタプリタの内部表現がこのデータ構造らしい。
まず木構造っていうのはこういうの👇（wikipedia）
ja.wikipedia.org
evaluator
astを評価する。つまりここでastのデータ構造を元にプログラムとしての実行結果を導き出す
object
evalの評価結果。この本ではeval構造体中の評価関数に使われるinterfaceとして実装される
その他用語整理
プログラム中に出てくる英単語の意味を忘れがちで混乱したので書き出して整理
Node
astで出力した木構造の要素。式（Statement）か文（Expression）のどちらかで構成される。式は値を生成し、文はしない。
Identifier
識別子のこと。識別子は式の１種でもある
prefix
5 + 5の＋とか、5 * 5の*みたいな中置演算子
infix
-5の-とか!foobarの!みたいな前置演算子
enviroment
変数に値を保存するために使う環境と呼ばれるもの。
プログラム内では文字列とobjectを関連付けるハッシュマップとして実装されていて、objectパッケージの中に定義されている構造体でlet文を評価する際に更新される。
上記の用語を踏まえてプログラムの流れを追ってみる
- 標準入力を受け取る
- 入力した文字列を使ってlexer構造体を初期化する
- 初期化したlexer構造体を元にparser構造体を初期化する。
- parse構造体のParseProgramに標準入力を読み込ませる
- parse構造体の初期化メソッド（New）の中でlexer構造体のnextToken関数を呼び出してtoken構造体を初期化していく
- ParseProgram内でparseStatement関数を呼び出しastの構造体を作成する。
- parseStatement関数内で呼び出されるastを作成する。parseStatement関数はトークンのタイプをcase文で判定してlet式、return式、それ以外のいずれかが呼ばれる
- ParseProgramを実行するとastの配列が返却される
- 返却されたast（抽象構文木）の構造体をEvalメソッドで評価していく
- Evalメソッドの中ではnodeの種別によって実行プログラムが分岐する。nodeの種別がLetstatementの場合はenviromentを更新して変数の値を保持する
- evalでの評価が終わったら結果を標準出力に書き出して実行終了
よくわからないところ掘り下げてみる
抽象構文木の構造について
最終的にEvalメソッドに抽象構文木（ast構造体）を渡して結果を受け取るところでこのプログラムの処理は完結するんだけど、該当のプログラムを読むと以下のように書かれている
program := p.ParseProgram()
if len(p.Errors()) != 0 {
printParserErrors(out, p.Errors())
continue
}
evaluated := evaluator.Eval(program, env)
if evaluated != nil {
io.WriteString(out, evaluated.Inspect())
io.WriteString(out, "\n")
}
parsePrigramメソッドでast構造体(program)を作ってEvalメソッドに渡している。
Evalメソッドはastとenviromentを受け取ってオブジェクトを返す
func Eval(node ast.Node, env *object.Environment) object.Object
で、そのastの構造は例えば以下のようになっている（この本の内容に含まれているastのテストコードから抜粋）
これはlet myVar = anotherVar;という文字列を
program := &Program{
Statements: []Statement{
&LetStatement{
Token: token.Token{Type: token.LET, Literal: "let"},
Name: &Identifier{
Token: token.Token{Type: token.IDENT, Literal: "myVar"},
Value: "myVar",
},
Value: &Identifier{
Token: token.Token{Type: token.IDENT, Literal: "anotherVar"},
Value: "anotherVar",
},
},
},
}
つまり頂点にStatements（式を複数保持する配列）があってその下にその式の種別が定義されている。式は種別ごとに異なった値を保持する構造体。上記の場合はlet式の構造体でトークンと変数名、変数の値を定義している。
Statementsというnodeが頂点にあり、そのNodeがLetStatementというnodeを持っていてそのLetStatementがToken、Name、Valueというnodeを持っている。という感じ。
enviromentについて
例えば以下のように入力を評価していく場合、前回の受付で更新した変数の状態を参照するのに必要となる。この場合、変数「a」、「b」、「c」、「d」それぞれの名前に何が保存されているかenviromentに記録される
let a = 5;
let b = a > 3;
let c = a * 99;
if (b) { 10 } else { 1 };
let d = if (c > a) { 99 } else { 100 };
d * c * a
enviromentがないと複数回入力した場合に以前の変数の格納結果を参照できない。
その他
計算の際のトークンの優先度はどう決める？
例えば1 + 2 * 2という式だと2 * 2を先に計算してから1を足す必要がある。これをどうするのか？
→優先度を定義した連想配列をparser構造体の中に定義していてそれを参照してEvalメソッドが適切な順序で評価できるようにastを出力する。
var precedences = map[token.TokenType]int{
token.EQ: EQUALS,
token.NOT_EQ: EQUALS,
token.LT: LESSGREATER,
token.GT: LESSGREATER,
token.PLUS: SUM,
token.MINUS: SUM,
token.SLASH: PRODUCT,
token.ASTERISK: PRODUCT,
token.LPAREN: CALL,
token.LBRACKET: INDEX,
}
それぞれの意味はtoken構造体に定義されている
const (
ILLEGAL = "ILLEGAL"
EOF = "EOF"
// Identifiers + literals
IDENT = "IDENT" // add, foobar, x, y, ...
INT = "INT" // 1343456
STRING = "STRING" // "foobar"
// Operators
ASSIGN = "="
PLUS = "+"
MINUS = "-"
BANG = "!"
ASTERISK = "*"
SLASH = "/"
LT = "<"
GT = ">"
EQ = "=="
NOT_EQ = "!="
// Delimiters
COMMA = ","
SEMICOLON = ";"
COLON = ":"
LPAREN = "("
RPAREN = ")"
LBRACE = "{"
RBRACE = "}"
LBRACKET = "["
RBRACKET = "]"
// Keywords
FUNCTION = "FUNCTION"
LET = "LET"
TRUE = "TRUE"
FALSE = "FALSE"
IF = "IF"
ELSE = "ELSE"
RETURN = "RETURN"
)
precedencesは下に行くほど優先度が高い。抽象構文木の中で優先度が高いものを評価の上位に割り当てることでEVal関数が適切な順序で処理できる。
Evalメソッドでやってること
Evalメソッドの中ではNodeのタイプごとに対応する関数を作ってそれぞれnodeを評価している。この１つ１つの分岐の中身を実装していく必要がある。
func Eval(node ast.Node, env *object.Environment) object.Object {
switch node := node.(type) {
// Statements
case *ast.Program:
return evalProgram(node, env)
case *ast.BlockStatement:
return evalBlockStatement(node, env)
case *ast.ExpressionStatement:
return Eval(node.Expression, env)
流石に１つ１つこの記事に書くのは辛いので割愛するが、例えば中置演算子の式計算は以下のような感じ。
func evalIntegerInfixExpression(
operator string,
left, right object.Object,
) object.Object {
leftVal := left.(*object.Integer).Value
rightVal := right.(*object.Integer).Value
switch operator {
case "+":
return &object.Integer{Value: leftVal + rightVal}
case "-":
return &object.Integer{Value: leftVal - rightVal}
case "*":
return &object.Integer{Value: leftVal * rightVal}
case "/":
return &object.Integer{Value: leftVal / rightVal}
case "<":
return nativeBoolToBooleanObject(leftVal < rightVal)
case ">":
return nativeBoolToBooleanObject(leftVal > rightVal)
case "==":
return nativeBoolToBooleanObject(leftVal == rightVal)
case "!=":
return nativeBoolToBooleanObject(leftVal != rightVal)
default:
return newError("unknown operator: %s %s %s",
left.Type(), operator, right.Type())
}
}
左下と右下の値を引数に渡して演算していく。こういった評価関数を「式」と「文」のそれぞれの種別ごとに用意する必要がある。
以上
