sonota486

2021-06-15に更新

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

Ruby 自作言語コンパイラ parser

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

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

※ ブログに書いていたものを引っ越してきました。元の記事公開日は 2020-05-04 です。

パーサ
- https://github.com/sonota88/vm2gol-v2/blob/41/vgparser.rb
ライフゲームのコード
- https://github.com/sonota88/vm2gol-v2/blob/41/gol.vg.txt

※ 2020-05-04 時点のものです。その後の改良も加わったものが見たい場合は mainブランチを見てください。
※ パーサ以外の部分をどうやって作ったか知りたい方はこちらをどうぞ
※ 他の言語にも移植していますので Ruby わからんという方はこちらもどうぞ（2021-06-15 現在での移植先: TypeScript, Python, Dart, Java, C, Perl, C♭, PHP, Go, LibreOffice Basic, Zig, Kotlin, Pric, Crystal, Rust, Julia, Pascal）

ふつうの手書き再帰下降パーサ
- 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) {
      // ... 
    }
    (0 == 0) { // else の代わり
      // ... 
    }
  }

  // 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<del>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</del>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

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

その後の変更

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

vm2gol v2 （47）引数のパースの厳密化など

（2021-02-21 追記）いくつか機能を足してセルフホストできるようになりました。

https://github.com/sonota88/pric

参考

Parserに関するsonota88のブックマーク - はてなブックマーク

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

文法サンプル

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

2020-06-25 追記

その後の変更

参考

関連

関連記事

コメント