LoginSignup
10
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

QualiArtsAdvent Calendar 2022

Day 18
@karamaru(からまる)inQualiArts

Goで作るインタプリタ/コンパイラ入門!

Last updated at Posted at 2022-12-17

本記事はQualiArts Advent Calendar 2022 18日目の記事です。

プログラミング言語ってどうできているんだろう？自作できたらめっちゃかっこいい！と思って出会った以下2冊の紹介です🙆‍♂️

  • Writing An Interpreter In Go
  • Writing A Compiler In Go
    • ASTから中間表現であるバイトコードを出力するコンパイラとそれを実行する仮想マシンを実装する
    • 邦訳版はないので英語を頑張って読んだ🥺　(kindle版で翻訳かければよかった)

自作言語の入門書的な立ち位置で、広義のインタプリタ・コンパイラを簡易的にGoで実装してみよう!っていう内容です。
そんなに新しい本でもないのですが、簡易的と言っても自分が作成した言語が動くのは感動するしとっても楽しかったので共有です😊

機能

先に機能の紹介です。
拡張性は無限なのですが、本書では以下機能を実装したプログラミング言語を2つの内部実装で作成することができます。(かっこいい👏)

変数拘束・四則演算

> let a = 1;
> a;
// output: 1

> a + 2;
// output: 3

> "hello" + "world!";
// output: helloworld!

関数呼び出し

> let multiple = fn(a, b){ return a * b; };
> multiple(10, 2)
// output: 20

> fn(a, b){ return a / b; }(9, 3);
// output: 3

条件分岐

> if (1 > 2) { return 1*2; } else { return 3*4; };
// output: 12

> if (1 != 2) { return 1*2; } else { return 3*4; };
// output: 2

配列・ハッシュ

> let arr = [1, 2];
> arr[0]
// output: 1
> len(arr)
// output: 2

>> let hash = {"key": "value"};
>> hash["key"];
// output: "value"

Writing An Interpreter In Go

tree-walking型インタプリタで動作するプログラミング言語をGoで自作できるようになる本。(すごい)
独自の構文を解釈し、適宜対応するGoのコードで演算するようなゴールイメージ。

仕組み

以下サイクルで文字列を評価・実行します。

ソースコード -> 字句解析(lexer) -> 構文解析(parser) -> 評価(evaluator) -> 出力

字句解析

与えられたソースコードを最小単位トークンに分解する作業です。
イメージは以下です。

lexer(雰囲気).go
type TokenType int32

type const (
	INT TokenType = iota + 1 // 数値
    PLUS                     // +
    LPAREN                   // (
    RPAREN                   // )
)

type Token sturct {
    Type TokenType
    Value interface{}
}

func main() {
    input := "1 + (2 + 3)"
    // 字句解析器でトークン化する...
    output == []*token.Token{
        {Type: INT, Value: 1},
        {Type: PLUS},
        {Type: LPAREN},
        {Type: INT, Value: 2},
        {Type: PLUS},
        {Type: INT, Value: 3},
    }
}

本書では日本語を扱わないので、基本的には入力値に対してchar毎に文字を評価してトークン化していきました。(==や>=などの複数文字表現を除く)

構文解析

字句解析で得られたトークン列をグルーピングして、意味のある表現のまとまりにする作業です。

parser(雰囲気).go
type Expression interface{}

// 数値表現
type IntegerLiteral struct {
	Value int64
}

// 中間演算子表現
type InfixExpression struct {
	Left     Expression
	Right    Expression
	Operator TokenType
}

func main() {
    input := []*Token{
        {Type: INT, Value: 1},
        {Type: PLUS},
        {Type: LPAREN},
        {Type: INT, Value: 2},
        {Type: PLUS},
        {Type: INT, Value: 3},
    }
    // 構文解析器(parser)に食わせる...
    output := []Expression{
        &InfixExpression{
            Operator: PLUS,
            Left: &IntegerLiteral{Value 1},
            Right: &InfixExpression{
                Operator: PLUS,
                Left: &IntegerLiteral{Value 2},
                Right: &IntegerLiteral{Value 3},
            },
        },
    }
}

「数値->演算子->数値」のようなトークンの並びなら、中間演算子表現って意味のまとまりにしよう!みたいな実装を中で書いています👀

この作業でバラバラだったトークンが意味のある塊(木構造)になりました👏

評価

構文解析で得られたASTをたどって評価・実行する。
本書ではリアルタイムでノードを巡って、そのノードが表現していることをオンザフライで解釈するtree-walkingインタプリタを採用している。
イメージは以下

evaluator(雰囲気).go
func main() {
    input := []Expression{
        &InfixExpression{
            Operator: PLUS,
            Left: &IntegerLiteral{Value 1},
            Right: &InfixExpression{
                Operator: PLUS,
                Left: &IntegerLiteral{Value 2},
                Right: &IntegerLiteral{Value 3},
            },
        },
    }
    // 評価器(evaluator)に食わせる...
        // 値や構文を共通のinterfaceで扱えるようにして、`swith hoge.(type)`で各表現を処理する
            // IntegerLiteral -> 数値型のObjectを返却する
            // InfixExpression -> 右辺を評価してから左辺を評価して中間演算子で演算する...みたいな
    output := 6

ここまできて計算式の結果を求めることができます🎉
他にも上記で紹介した機能を実装するのですが今回は割愛します。

次はWriting A Compiler In Goでバイトコード・VMの概念を取り入れていきます。

Writing A Compiler In Go

上記インタプリタでtree-walkingインタプリタでASTをたどりながら評価していた部分を、ASTを直接評価するのではなく、中間表現であるバイトコードを出力(コンパイル)してから、それをスタック(Last In First Out）データ構造であるVMで実行するまでを体験できます。 (かっこいい)

interpreter: -> 構文解析 -> 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　評価 -> 出力
compiler:    -> 構文解析 -> 中間表現のバイトコード出力 -> VMで実行 -> 出力

仕組み

Compiler

足し算を例に取ると以下のイメージです。
VMのスタックに対してどのように操作してほしいか、構文成績器から受け取ったASTから中間表現であるバイトコードに変換し、表現します。

compiler(雰囲気).go
type Opcode byte

const (
	OpConstant Opcode = iota + 1 // 定数のN番目をstackに積んでねって命令
    OpAdd                        // stackの上から1番目の値と上から2番目の値を足して、結果をstackの上に積んでねって命令
    OpPop　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　// stackのtopの値をpopしてねって命令
)

func main() {
    input := "1 + 2"
    // コンパイル
        // 数値型なら、OpConstantって命令+値の格納場所(本書では値の命名順)を追加
        // 中間演算子型なら、左辺/右辺の順にコンパイル↑。最後に演算子の命令を追加
    output := `
OpConstant 0　 // 定数0番目(=1)をstackにロードしてね
OpConstant 1 // 定数1番目(=1)をstackにロードしてね 
OpAdd　       // stackの上から1番目と2番目の値を足してね
OpPop        // stackの一番上の値を消してね(式が終了しているため)
`
// actual: [1 0 0 1 0 1 2 3]
}

本書では定数は最大2byteで表現できる個数分しか格納できないような記述をするので、定数命令には3byte分の幅があります。(オペコード1byteと、定数が何個目かを示すオペランド2byte分)

定数を2つ定義して、それらを足し算するような命令を生成することができましたね。

VM

上記コンパイルで生成されたバイトコードを受け取り、 stackへ操作を行います。

1 + 2を例に取るとイメージは以下。

※　演算結果を値を変数に詰めたりしていないので計算結果は即座にpopされる

vm(雰囲気).go
type VM struct {
    stack     []Object // IF
}

func main() {
    input := []byte{1, 0, 0, 1, 0, 1, 2, 3} // [OpConstant 0, OpConstant 1, OpAdd, OpPop]
    // VMで命令実行
        // OpConstant: 定数をstackにpushする
        // OpAdd: stackから2つpopして足し算をし、結果をpushする
        // OpPop: stackから1つpopする
    fmt.Println(<最後にpopしたobject>) // -> 3
}

こんな感じでコンパイル->VM実行まで行うことができました👏

前述したtree-walking方式でASTノードを巡るインタプリタよりも、こちらのバイトコード->VM実行の方が命令が少なく拘束に動作するそうです👀(フィボナッチ数列で3倍のベンチマークが載っていました)

面白かったポイント　/ JUMP命令

条件分岐if-elseを記載する際、条件の真偽によって、特定の命令をVMが読み飛ばすJUMNP処理を挟むのが面白かった。

例えば以下の例だと

if (2 > 1) { 10 } else { 20 }; 30;

バイトコードは以下になる。

code.OpConstant 0       // 1~3byte    数値: 2
code.OpConstant 1       // 4~6byte    数値: 1
code.OpGreaterThan      // 7byte
code.OpJumpNotTruthy 17 // 8~10byte   条件がfalseの時、17byte目まで命令をスキップする (code.OpConstant, 3~)
code.OpConstant 2       // 11~13byte  数値: 10
code.OpJump, 20         // 14~16byte  条件がtrueの時、20byte目の命令までスキップする (code.OpPop~)
code.OpConstant, 3      // 17~19byte  数値: 20
code.OpPop              // 20byte
code.OpConstant, 4      // 22~24byte  数値: 30
code.OpPop

VM実行時、条件式の真偽によって柔軟に命令を選択できるのは賢いと思いました🙆‍♂️

※ code.OpConstant,code.OpJumpNotTruthy, code.OpJumpの命令は合計3byteの幅がある。(opcode 1byte + (何個目の定数か/どのbyteの命令にjumpするか) 2byte)

まとめ

本書では他にもクロージャをどう実現するのか、変数のスコープをどう表現するのかなど面白い箇所がたくさんあるので、ぜひ手にとって読んでみてください😊

関連ブログです。
-> 自作言語をwasm変換するコンパイラをrustで作った

10
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
10
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?