RubyやJavaScriptなどのインタプリタの仕組みをざっと理解する

#この記事を書こうと思ったワケ
『Go言語でつくるインタプリタ』という、GoでRubyやJavaScriptなどのインタプリタを作ってみるという内容を会社の研修として取り組み一段落したので、その復習として記事を書いた。

#結論
私たちがソースコードを書いて、コンピュータに処理を実行させようという時、プログラミング言語の内部で起こっていることは、プログラミング言語が、書かれたソースコードを入力として受け取り、言語仕様（ルール）に沿って字句を解釈し、それを何らかのデータ構造として解析した後、予め決められた評価基準に沿って評価器がデータを評価してユーザーに出力結果を返している。

※インタプリタに絞って、話を進めさせていただきます。CやGoなどのコンパイラ言語はまた少し変わります。

#字句解析

• 文字列で書かれたソースコードは、そのままではプログラミング言語は解釈できない
• そこで人間がプログラミング言語が扱いやすいように、ソースコードを（文字列の）トークン列として変換する必要がある
• つまり、ソースコードを入力として受け取り、トークン列を出力するのが字句解析器

###イメージ

// トークン列を登録しておく
const (
	ILLEGAL = "ILLEGAL"
	EOF     = "EOF"

	// 識別子とリテラル
	IDENT = "IDENT" // add, foobar, x, y, ...
	INT   = "INT"   // 1343456

	// 演算子
	ASSIGN   = "="
	PLUS     = "+"
	MINUS    = "-"
	BANG     = "!"
	ASTERISK = "*"
	SLASH    = "/"

	LT = "<"
	GT = ">"

	EQ     = "=="
	NOT_EQ = "!="

	// デリミタ（複数の要素を並べて記述する際に、要素の区切りを表す記号や特殊な文字（の並び））
	COMMA     = ","
	SEMICOLON = ";"

	LPAREN = "("
	RPAREN = ")"
	LBRACE = "{"
	RBRACE = "}"

	// 識別子ではなく言語の一部であるキーワード（予約語）
	FUNCTION = "FUNCTION"
	LET      = "LET"
	TRUE     = "TRUE"
	FALSE    = "FALSE"
	IF       = "IF"
	ELSE     = "ELSE"
	RETURN   = "RETURN"
)

###テストケースの例

func TestNextToken(t *testing.T) {
	 input := `=+(){},;`
	 tests := []struct {
		 expectedType token.TokenType
		 expectedLiteral string
}{
	 {token.ASSIGN, "="},
	 {token.PLUS, "+"},
	 {token.LPAREN, "("},
	 {token.RPAREN, ")"},
	 {token.LBRACE, "{"},
	 {token.RBRACE, "}"},
	 {token.COMMA, ","},
	 {token.SEMICOLON, ";"},
	 {token.EOF, ""},
 }

#構文解析（Parser）

• ある入力を、その入力に対応しているデータ構造に変換するのが構文解析
• 具体的には、Lexerで変換されたトークン列を上から順番に、1個1個「これは、こういう意味のある構文だ！」と解析した後、AST（抽象構文木）を構築する

###テストの例

parser_test.go

// そのトークンが、人間が意図する意味の構文になっているか、トークンごとにテスト
// 今回の例は、「Let」というトークンが、「Let文としての意味を解釈できているか」をテスト
func TestLetStatements(t *testing.T) {
	tests := []struct {
		input              string
		expectedIdentifier string
		expectedValue      interface{}
	}{
		{"let x = 5;", "x", 5},
		{"let y = true;", "y", true},
		{"let foobar = y;", "foobar", "y"},
	}

	for _, tt := range tests {
		l := lexer.New(tt.input)
		p := New(l)
		program := p.ParseProgram()
		checkParserErrors(t, p)

		if len(program.Statements) != 1 {
			t.Fatalf("program.Statements does not contain 1 statements. got=%d",
				len(program.Statements))
		}

		stmt := program.Statements[0]
		if !testLetStatement(t, stmt, tt.expectedIdentifier) {
			return
		}

		val := stmt.(*ast.LetStatement).Value
		if !testLiteralExpression(t, val, tt.expectedValue) {
			return
		}
	}
}

ASTについて少し補足

• 例えば、let文で解釈して欲しいことは、与えられた変数名を値に束縛させること
• AST（データ構造）に変換するには、(1)予約後としてのlet（のトークン）(2)変数の名前(3)変数束縛され値を生成する式(Expression)が必要

ast.go

type LetStatement struct {
	Token token.Token // 'let' トークン（token.LETタイプのこと）
	Name  *Identifier // 識別子名のポインタ
	Value Expression
	// 値を生成する式（Expression）
	//　関数リテラルや関数の実行結果の可能性もあるので
	// 型がinterfaceのExpressionにしておく
}

func (ls *LetStatement) statementNode() {}

// LetStatementのトークン（LET）のポインタをセット
func (ls *LetStatement) TokenLiteral() string { return ls.Token.Literal }
func (ls *LetStatement) String() string {
	var out bytes.Buffer // Bufferを用意

	out.WriteString(ls.TokenLiteral() + " ")
	out.WriteString(ls.Name.String())
	out.WriteString(" = ")

	if ls.Value != nil {
		out.WriteString(ls.Value.String())
	}

	out.WriteString(";")

	return out.String()
}

#評価器（Evaluator）

• 先ほどのParserで、トークン列をASTのツリー状のデータ構造を構築した
• ASTというデータの構造ができたものの、それを人間が解釈できる値に還元（評価）させないといけない
• 還元（評価）の仕方は様々あるが、Rubyのバージョン1.8以下では「tree-walkingインタプリタ」という評価器を使っていて、具体的には、構築したASTを順番に辿りながら順次実行していた

※バージョン1.9から仮想マシンのアーキテクチャに移行し現在ではRubyインタプリタはソースコードを構文解析し、ASTを構築し、それからASTをバイトコードにコンパイルし、それが仮想マシン上で実行される形になった

###let文のテスト

evaluator_test.go

func TestLetStatements(t *testing.T) {
	tests := []struct {
		input    string
		expected int64
	}{
		{"let a = 5; a;", 5},
		{"let a = 5 * 5; a;", 25},
		{"let a = 5; let b = a; b;", 5},
		{"let a = 5; let b = a; let c = a + b + 5; c;", 15},
	}
        // INT型のオブジェクトとして評価されたかチェック
	for _, tt := range tests {
		testIntegerObject(t, testEval(tt.input), tt.expected)
	}
}

#その他
本当は書籍での学習を通じてインタプリタがどうやって「変数束縛」「環境」「関数呼び出し」「配列」「ハッシュ」などを実現させているのか理解したのだが、今回の記事の趣旨とは外れてしまうので、別の機会にでもアウトプットしようと思う。

#参考
Go言語でつくるインタプリタ
インタプリタ言語とコンパイラ言語
コーディングを支える技術――成り立ちから学ぶプログラミング作法