（2週間ちょっとで）Rubyでかんたんな自作言語のコンパイラを作った

<!--

- [目次ページに戻る](https://memo88.hatenablog.com/entry/2019/05/04/234516)
- [前回からの差分をまとめて見る](https://github.com/sonota88/vm2gol-v2/compare/40...41)
-->

<!--
★ しばらくしたら表示する
- [目次ページに戻る](https://memo88.hatenablog.com/entry/2019/05/04/234516)
  / [前](https://memo88.hatenablog.com/entry/2019/12/21/144455)
  / [次](https://memo88.hatenablog.com/entry/2020/06/20/083831)
- [前回からの差分をまとめて見る](https://github.com/sonota88/vm2gol-v2/compare/40...41)

---
-->

<!--
[f:id:sonota88:20210613100132p:plain]
-->
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/234055/bfbd9fa0-7d3f-e2e3-d78a-0ac72b90d92d.png)


<!--
[RubyでオレオレVMとアセンブラとコード生成器を2週間で作ってライフゲームを動かした話](https://memo88.hatenablog.com/entry/2019/05/04/232236)
の続きです。
これを書いたときはパーサ部分（高水準言語から構文木への変換部分）を作っていなかったため仕方なく「コード生成器を作った」という表現にしていましたが、やっとパーサを書きました。
3日くらいで作れたのでさっさとやっておけばよかった。
-->

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


<!--
[RubyでオレオレVMとアセンブラとコード生成器を2週間で作ってライフゲームを動かした話](https://memo88.hatenablog.com/entry/2019/05/04/232236)
を書いたときは、高水準言語のパーサ部分まで作っていなかったので「コンパイラを作った！」と言っていいのかよく分からず、「コード生成器を作った」という若干歯切れの悪い言い方にしていましたが、パーサ部分をやっと作りました。

パーサまで揃っていなかったので「コンパイラを作った！」と言いにくかったのですが、
ここまでやったら「コンパイラを作った」と言っていいはず！
-->

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

----

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

※ パーサ以外の部分をどうやって作ったか知りたい方は[こちら](https://memo88.hatenablog.com/entry/2019/05/04/234516)をどうぞ

※ 他の言語にも移植していますので Ruby わからんという方は[こちら](https://memo88.hatenablog.com/entry/2020/08/30/132314)もどうぞ（2021-06-15 現在での移植先: TypeScript, Python, Dart, Java, C, Perl, C♭, PHP, Go, LibreOffice Basic, Zig, Kotlin, Pric, Crystal, Rust, Julia, Pascal）

[^1]: https://memo88.hatenablog.com/entry/2020/05/04/155425

---

- パーサ
  - 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ブランチ](https://github.com/sonota88/vm2gol-v2) を見てください。

---

<!--
  - 理論や理解は後回しにしてとにかく作る
  - 簡単確実な仕様にしてハードルを下げて、まずは「とにかく動く」とこまで持って行く

- ベタな文法でよい
  - 「今までにない画期的な言語を作るぞ！」みたいな野望はない
-->


- ふつうの手書き再帰下降パーサ
  - 400行ちょっと
- 難しいことはしない
  - 再帰下降パーサを実際に書くのは今回が初めてなので
  - まずはハードルを下げて「とにかく動く」ところまで持って行く
      - 下げ過ぎた気がしなくもない
  - 割とそのまま構文木にマッピングしていて、気の利いた変換とかはやってない
  - 演算子の優先順位は考慮しない
      - 明示的に括弧を書く
      - 気が向いたら後でやる（[別途履修しました](https://memo88.hatenablog.com/entry/2020/07/05/111103)）
- ベタな文法でよい / 高度な機能や独自色をなるべく入れないようにしたい
    - 初心者向け教材っぽくしておきたい気持ち
- 汎用ではない
    - ライフゲームだけコンパイルできればよい
- エラーハンドリングは適当
    - ライフゲームだけコンパイルできればよい
- ふつうの文法でふつうの再帰下降パーサなので、あまり書くことがないです……




# 文法サンプル

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

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

```javascript
// コメント

// 関数定義
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での実行までの流れ

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

----

高水準言語:

```javascript
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 に変換（実際の出力は改行が多くて冗長なので下記は手動で整形しています）

```json
[
  "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` でアセンブリコードに変換

```sh
  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` で機械語コードに変換

```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） 機械語コードのフォーマットを固定長風に変更](https://memo88.hatenablog.com/entry/2021/01/10/124904)




あとは `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: 引数のパースの厳密化など](https://memo88.hatenablog.com/entry/2020/08/23/154759)
- [step 57: 二項演算を左結合に変更](https://memo88.hatenablog.com/entry/20210407_vm2gol_v2_step57_left_assoc)
- [step 62: case 文の構文を変更 / standardrb に変更](https://memo88.hatenablog.com/entry/20210930_vm2gol_v2_62_case_when)
    - `case when ...` と書くように変更





----

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

- [素朴な自作言語Ruccolaのコンパイラをセルフホストした](https://qiita.com/sonota88/items/1e683276541cf1b87b76)




# 追加の機能など

追加の機能などについては別記事にまとめています。

https://memo88.hatenablog.com/entry/vm2gol_v2_additional_features

- 機能
  - 真偽値リテラル / break / if,else / 単項マイナス
- 代替パーサ
  - Racc / Parslet

# 参考

- [Parserに関するsonota88のブックマーク - はてなブックマーク](https://b.hatena.ne.jp/sonota88/Parser/)



# 関連

- [vm2gol-v2 移植まとめ](https://memo88.hatenablog.com/entry/2020/08/30/132314)
  - いろんな言語に移植してみています
- [四則演算と剰余のみのexprコマンドをRubyで作ってみた](https://memo88.hatenablog.com/entry/2020/07/05/111103)
  - 演算子の優先順位の考慮も必要な場合はこの方法で。
    ただ、ライフゲームを動かす分にはあんまり必要ないんですよね……。
- [リレー式論理回路シミュレータを自作して1bit CPUまで動かした](https://qiita.com/sonota88/items/a5d6d3539e0fb8040f74)
  - もっと低いレイヤーにも手を出してみました


---

- [目次ページに戻る](https://memo88.hatenablog.com/entry/2019/05/04/234516)
  / [前](https://memo88.hatenablog.com/entry/2019/12/21/144455)
  / [次](https://memo88.hatenablog.com/entry/2020/06/20/083831)