Rubyで素朴な自作言語のコンパイラを作った

Ruby vm2gol-v2

RubyでオレオレVMとアセンブラとコード生成器を2週間で作ってライフゲームを動かした話 の続きです。 このときスコープ外にしていたフロントエンド部分（高水準言語から構文木への変換部分）をやっと書きました。 3日くらいでできたのでさっさとやっておけばよかった。

パーサまで揃っていなかったため仕方なく「コード生成器を作った」という表現にしていましたが、 ここまでやったら「コンパイラを作った」と言っていいはず！

  • ふつうの手書き再帰下降パーサ
    • 400行ちょっと
  • 難しいことはしない
    • 再帰下降パーサを実際に書くのは今回が初めてなので
    • まずはハードルを下げて「とにかく動く」とこまで持って行く
      • 下げ過ぎた気がしなくもない
    • 構文木を割とそのままマッピングしていて、気の利いた変換とかはやってない
    • 式の優先順位は考慮しない
      • 明示的に括弧を書く
      • 気が向いたら後でやる
  • 汎用ではない
  • ベタな文法でよい
    • 「今までにない画期的な言語を作るぞ！」みたいな野望はない
  • エラーハンドリングは適当
  • ふつうの文法でふつうの再帰下降パーサなので、あまり書くことがないです……

文法サンプル

見ての通り、特にひねりのない感じです。 パッと見では JavaScript に近いでしょうか。

set, call, call_set は明示的に書きます。

// コメント

// 関数定義
func add(a, b) {
  // return（返り値は省略可）
  return a + b;
}

// main 関数は必須
func main() {
  // ローカル変数宣言
  var a;

  // ローカル変数宣言＋初期化
  var b = 1;

  // ローカル変数への代入
  set a = 2;

  // 関数呼び出し
  call add(1, 2);

  // 関数呼び出して返り値をローカル変数に代入
  call_set c = add(1, 2);

  // while
  while (a != 10) {
    // ...
  }

  // case
  case {
    (a == 1) {
      // ...
    }
    (a == 2) {
      // ... 
    }
    // ...
  }

  // VMコメント
  _cmt("...");
}

コンパイルからVMでの実行までの流れ

足し算をする関数を呼び出すだけのサンプルで 高水準言語から機械語までの変換の流れを具体的に見てみます。

高水準言語:

func add(a, b) {
  var result = a + b;
  return result;
}

func main() {
  var result;
  call_set result = add(1, 2);
}

↓ ruby vgparser.rb add.vg.txt > add.vgt.json で AST に変換 （実際の出力は改行が多くて冗長なので下記は手動で整形しています）

[
  "stmts",
  [
    "func", "add", ["a", "b"],
    [
      ["var", "result", ["+", "a", "b"]],
      ["return", "result"]
    ]
  ],
  [
    "func", "main", [],
    [
      ["var", "result"],
      ["call_set", "result", ["add", 1, 2]]
    ]
  ]
]

↓ ruby vgcg.rb add.vgt.json > add.vga.txt でアセンブリコードに変換

  call main
  exit

label add
  push bp
  cp sp bp

  # 関数の処理本体
  sub_sp 1
  push [bp+2]
  push [bp+3]
  pop reg_b
  pop reg_a
  add_ab
  cp reg_a [bp-1]
  cp [bp-1] reg_a

  cp bp sp
  pop bp
  ret

label main
  push bp
  cp sp bp

  # 関数の処理本体
  sub_sp 1
  push 2
  push 1
  _cmt call_set~~add
  call add
  add_sp 2
  cp reg_a [bp-1]

  cp bp sp
  pop bp
  ret

↓ ruby vgasm.rb add.vga.txt > add.vge.yaml で機械語コードに変換

---
- call
- 35
- exit
- label
- add
- push
- bp
- cp
- sp
- bp
- sub_sp
- 1
- push
- "[bp+2]"
- push
- "[bp+3]"
- pop
- reg_b
- pop
- reg_a
- add_ab
- cp
- reg_a
- "[bp-1]"
- cp
- "[bp-1]"
- reg_a
- cp
- bp
- sp
- pop
- bp
- ret
- label
- main
- push
- bp
- cp
- sp
- bp
- sub_sp
- 1
- push
- 2
- push
- 1
- _cmt
- call_set~~add
- call
- 5
- add_sp
- 2
- cp
- reg_a
- "[bp-1]"
- cp
- bp
- sp
- pop
- bp
- ret

（2021-01-11 追記）
この機械語コードのフォーマットは1命令1行となるようにその後変更しました: vm2gol v2 （51） 機械語コードのフォーマットを固定長風に変更
（追記ここまで）

あとは STEP= ruby vgvm.rb add.vge.yaml とすると VM で1命令ずつステップ実行できます。

また、これまでと同様に run.sh を使って ./run.sh gol.vg.txt のように実行すると   パース → コード生成 → アセンブル → VMで実行   がまとめて実行できます。

2020-06-25 追記

節目っぽいのでこの時点での行数を数えてみました。 空行やコメントだけの行も含めた単純な行数です。

   14 common.rb
   63 vgasm.rb
  474 vgcg.rb
  433 vgparser.rb
  491 vgvm.rb
 1475 合計

思ったより少ない。2,000行超えてるかなと思ってましたが。

gol.vg.txt と、コンパイル・アセンブルで生成される AST・アセンブリコード・機械語コードも行数を見てみます。

  208 gol.vg.txt
  874 tmp/gol.vgt.json
  693 tmp/gol.vga.txt
 1299 tmp/gol.vge.yaml

フーン、という感じですね（気の利いた感想が出てこなかった）。

2021-02-21 追記

いくつか機能を足してセルフホストできるようになりました。

https://github.com/sonota88/vm2gol-v2/tree/v3_wip/selfhost

その後の変更

けっこういいかげんなところがあるので、後から修正しています。

参考

関連