search
LoginSignup
10
Help us understand the problem. What are the problem?

posted at

updated at

(初心者が2週間ちょっとで)Rubyでかんたんな自作言語のコンパイラを作った

image.png

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

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

その後の変更


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

追加の機能など

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

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

参考

関連


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

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
What you can do with signing up
10
Help us understand the problem. What are the problem?