RubyでオレオレVMとアセンブラとコード生成器を2週間で作ってライフゲームを動かした話の続きです。このときスコープ外にしていたフロントエンド部分（高水準言語から構文木への変換部分）をやっと書きました。3日くらいでできたのでさっさとやっておけばよかった。
これまではパーサまで揃っていなかったため仕方なく「コード生成器を作った」という表現にしていましたが、ここまでやったら「コンパイラを作った」と言っていいはず！
※ ブログに書いていたもの1を引っ越してきました。元の記事公開日は 2020-05-04 です。
※ パーサ以外の部分をどうやって作ったか知りたい方はこちらをどうぞ
※ 他の言語にも移植していますので Ruby わからんという方はこちらもどうぞ（2021-06-15 現在での移植先: TypeScript, Python, Dart, Java, C, Perl, C♭, PHP, Go, LibreOffice Basic, Zig, Kotlin, Pric, Crystal, Rust, Julia, Pascal）
- パーサ
- ライフゲームのコード
※ 2020-05-04 時点のものです。その後の改良も加わったものが見たい場合は mainブランチ を見てください。
- ふつうの手書き再帰下降パーサ
- 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 (a != 10) {
// ...
}
// 条件分岐
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~~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行超えてるかなと思ってました。VM・アセンブラを除いたコンパイラ部分だけだと 1,000行以内に納まっています。
gol.vg.txt と、コンパイル・アセンブルで生成される AST・アセンブリコード・機械語コードも行数を見てみます。
208 gol.vg.txt
874 tmp/gol.vgt.json
693 tmp/gol.vga.txt
1299 tmp/gol.vge.yaml
フーン、という感じですね（気の利いた感想が出てこなかった）。
その後の変更
- step 47: 引数のパースの厳密化など
- step 57: 二項演算を左結合に変更
-
step 62: case 文の構文を変更 / standardrb に変更
-
case when ...と書くように変更
-
（2021-02-21 追記）いくつか機能を足してセルフホストできるようになりました。
追加の機能など
追加の機能などについては別記事にまとめています。
- 機能
- 真偽値リテラル / break / if,else / 単項マイナス
- 代替パーサ
- Racc / Parslet
参考
関連
-
vm2gol-v2 移植まとめ
- いろんな言語に移植してみています
-
四則演算と剰余のみのexprコマンドをRubyで作ってみた
- 演算子の優先順位の考慮も必要な場合はこの方法で。
ただ、ライフゲームを動かす分にはあんまり必要ないんですよね……。
- 演算子の優先順位の考慮も必要な場合はこの方法で。
-
リレー式論理回路シミュレータを自作して1bit CPUまで動かした
- もっと低いレイヤーにも手を出してみました