こんパイラ〜（挨拶）、電子の海に漂うはかなき泡沫（うたかた）、はたけやまです。
みなさん、書籍「RubyでつくるRuby」をご存知ですか？Rubyを使ってRubyのサブセット「MinRuby」のインタプリタを作ることで言語処理系作成のエッセンスを学ぼう！という本です。
- RubyでつくるRuby
今回は、この本のMinRubyを題材に、簡易なMinRubyコンパイラをRubyで作成してみようと思います。
（この記事は ESM Advent Calendar 2023 の4日目の記事になります）
Gitリポジトリ
今回作成したコンパイラのソースはこちらのgitリポジトリに置いてます。
https://github.com/thata/minrubyc-m1
言語仕様とターゲット環境
- 言語仕様
- MinRubyのサブセット
- データ型はInt（整数）のみ
- ArrayとHashは実装しない
- 関数の引数は8つまで
- （それ以外にも足りてない機能が山ほどあるよ）
- MinRubyのサブセット
- ターゲット環境
- ターゲットOS
- macOS
- ターゲットCPU
- Apple Mシリーズ（M1, M2 など）
- ターゲットOS
インテルのCPUで動かせるの？
今回作成するコンパイラはApple M1向けのコードを生成するため、インテルCPUのマシンでは動作させることができません。代わりに、今回のコンパイラをインテルCPUへ移植したものがあるのでそちらを見てみてください。
- thata/minruby_x86-64
- x86_64移植時のメモ
字句解析器と構文解析器
コンパイラに欠かすことのできない「字句解析」と「構文解析」と呼ばれる処理があります。
- 字句解析
- プログラムを「単語」や「記号」などの「トークン」と呼ばれるプログラムの最小単位に分割する処理
- 構文解析
- 文法を元にトークンを組み合わせて構文木を構築する処理
通常のコンパイラでは字句解析を行う字句解析器と構文解析を行う構文解析器を自前で実装する必要がありますが、今回作成するコンパイラでは「RubyでつくるRuby」使われているMinRubyのパーサをそのまま利用します。
MinRubyのパーサはRubyGemsとして提供されているので、事前に以下のコマンドを実行して minruby gemをインストールしておいてください。
gem install minruby
MinRubyパーサの使い方
MinRubyのパーサの使い方はこんな感じ。渡されたソースコードを構文木の形式に変換して返します。
irb(main):001:0> require 'minruby' => true irb(main):002:0> minruby_parse "10" => ["lit", 10] irb(main):003:0> minruby_parse "10 + 20" => ["+", ["lit", 10], ["lit", 20]]
MinRubyパーサが返す構文木のノードには主に以下のようなものがあります。
- リテラルノード
["lit", 10]
- 四則演算ノード（
+-*/）["+", ["lit", 10], ["lit", 20]]["-", ["lit", 10], ["lit", 20]]
- 変数代入ノード
["var_assign", "a", ["lit", 10]]
- 変数参照ノード
["var_ref", "a"]
- ステートメント（複文）ノード
["stmts", ["var_assign", "a", ["lit", 10]], ["func_call", "p", ["var_ref", "a"]]]
- 比較演算子ノード（
><>=<===!=）["==", ["lit", 1], ["lit", 1]]
- if ノード
["if", ["==", ["lit", 1], ["lit", 1]], ["stmts", ["lit", nil], ["lit", "foo"]], ["stmts", ["lit", nil], ["lit", "bar"]]]
- 関数定義ノード
["func_def", "foo", [], ["lit", 0]]
- 関数コールノード
["func_call", "p", ["lit", 10]]
コンパイラのはじめの一歩
では、コンパイラを作っていきます。まずは整数リテラルを表示するだけのコンパイラを作成します。
整数リテラルを表示するだけのコンパイラはこんな感じです。整数リテラルノードが渡されたら、リテラルの値をレジスタ x0 へ格納し、プリント関数 p を呼び出して画面へ出力します。
# minrubyc.rb require "minruby" tree = minruby_parse(ARGF.read) puts "\t.text" puts "\t.align 2" puts "\t.globl _main" puts "_main:" # lr レジスタと fp レジスタをスタックへ退避 puts "\tsub sp, sp, #16" puts "\tstp fp, lr, [sp, #0]" if tree[0] == "lit" # 整数リテラルの値を x0 レジスタへ格納 puts "\tmov x0, ##{tree[1]}" else raise "invalid AST: #{tree}" end # 終了する前に x0 レジスタの値を出力するため、p 関数を呼び出す puts "\tbl _p" # lr レジスタと fp レジスタをスタックから復元 puts "\tldp fp, lr, [sp, #0]" puts "\tadd sp, sp, #16" # 終了ステータスに 0 を返す puts "\tmov x0, #0" puts "\tret"
プリント関数 p は libminruby.c へ定義しておきます。
// libminruby.c #include <stdio.h> long p(long n) { printf("%ld\n", n); return n; }
早速コンパイルしてみましょう（コンパイル手順は後述）。4649 が出力されればOKです。
【ちょっと補足】コンパイル手順
MinRubyコンパイラのコンパイルは以下の流れで行われます。
# MinRubyのソースをコンパイルして foo.s へ出力 ruby minrubyc.rb foo.rb > foo.s # foo.s と libminruby.c をコンパイル gcc foo.s libminruby.c -o a.out # 実行 ./a.out
コンパイラへのMinRubyのソースの渡し方は、ファイルで渡しても良いし、標準入力から渡してもOKです。
四則演算の導入
整数リテラルの表示ができたので、次は四則演算を導入します。
以下が四則演算を導入したコンパイラのコードです。
右辺と左辺を評価した結果がそれぞれレジスタ x0 へ格納されるので、右辺と左辺の値を計算したのちレジスタ x0 へ格納します。
# minrubyc.rb require "minruby" def gen(tree) if tree[0] == "lit" puts "\tmov x0, ##{tree[1]}" elsif %w(+ - * /).include?(tree[0]) # 四則演算 op = tree[0] expr1 = tree[1] expr2 = tree[2] # 評価結果一時保持用のスタック領域を確保 puts "\tsub sp, sp, #16" # x0 へ格納された左辺評価結果をスタックへ積む gen(expr1) puts "\tstr x0, [sp, #0]" # x0 へ格納された右辺評価結果をスタックへ積む gen(expr2) puts "\tstr x0, [sp, #8]" # スタックへ積んだ評価結果を x1 レジスタと x0 レジスタへロード puts "\tldr x1, [sp, #8]" puts "\tldr x0, [sp, #0]" # 演算結果を x0 へ格納 case op when "+" puts "\tadd x0, x0, x1" when "-" puts "\tsub x0, x0, x1" when "*" puts "\tmul x0, x0, x1" when "/" puts "\tsdiv x0, x0, x1" else raise "invalid operator: #{op}" end # スタックを破棄 puts "\tadd sp, sp, #16" else raise "invalid AST: #{tree}" end end tree = minruby_parse(ARGF.read) puts "\t.text" puts "\t.align 2" puts "\t.globl _main" puts "_main:" # lr レジスタと fp レジスタをスタックに退避 puts "\tsub sp, sp, #16" puts "\tstp fp, lr, [sp, #0]" gen(tree) # 終了する前に x0 レジスタの値を出力するため、p 関数を呼び出す puts "\tbl _p" # lr レジスタと fp レジスタをスタックから復元 puts "\tldp fp, lr, [sp, #0]" puts "\tadd sp, sp, #16" # 終了ステータスに 0 を返す puts "\tmov w0, #10" puts "\tret"
10 + 20 をコンパイルしてみます。30 が表示されればOKです。
【ちょっと補足】レジスタの使い方のルール
64ビットARMでは x0 から x30 までの31個の整数レジスタがあります（その他、浮動小数点レジスタなどもあります）。
レジスタには利用時のルールがいろいろあります。例えば関数の引数と戻り値に関しては以下のようなルールがあります。
- 関数の引数は
x0からx7へセットする- 1番目の引数は
x0へ、2番目の引数はx1へ、みたいな感じで - （8個以上セットしたい場合のルールは割愛）
- 1番目の引数は
- 関数の戻り値は
x0へセットする
MinCamlコンパイラではこれにならって、構文木の各ノードが値を返す時はレジスタ x0 へ値をセットするようになっています。また、組み込み関数やユーザー定義関数を呼び出す時の引数はレジスタ x0 から x7 へセットし、関数の戻り値は x0 へセットするようになっています。
参考資料
ARM64: ABI 規則
https://zenn.dev/hidenori3/articles/c9053a76be641c
プリント関数 p の導入
次は、整数をプリントする p 関数を導入します。
macOSではCで定義した関数名のプリフィックスに _ がつけられてしまうため、アセンブリから p 関数を呼び出す際は bl _p のようにアンダースコアをつけて呼び出します。
diff --git a/minrubyc.rb b/minrubyc.rb index 780f97e..268a901 100644 --- a/minrubyc.rb +++ b/minrubyc.rb @@ -40,6 +40,11 @@ def gen(tree) # スタックを破棄 puts "\tadd sp, sp, #16" + elsif tree[0] == "func_call" && tree[1] == "p" + # p 関数を呼び出す + expr = tree[2] + gen(expr) + puts "\tbl _p" else raise "invalid AST: #{tree}" end @@ -57,9 +62,6 @@ puts "\tstp fp, lr, [sp, #0]" gen(tree) -# 終了する前に x0 レジスタの値を出力するため、p 関数を呼び出す -puts "\tbl _p" - # lr レジスタと fp レジスタをスタックから復元 puts "\tldp fp, lr, [sp, #0]" puts "\tadd sp, sp, #16"
p 5963 をコンパイルして 5963 が出力されればOKです。
複文（statements）の導入
次は以下のように複数のステートメントを評価できるようにします。
p 123 p 456 p 789
複文の対応は以下のとおり。stmts の中の複数のノードをぐるぐる回してコードを生成するだけでOKです。
diff --git a/minrubyc.rb b/minrubyc.rb index 268a901..b08b705 100644 --- a/minrubyc.rb +++ b/minrubyc.rb @@ -45,6 +45,10 @@ def gen(tree) expr = tree[2] gen(expr) puts "\tbl _p" + elsif tree[0] == "stmts" + tree[1..].each do |stmt| + gen(stmt) + end else raise "invalid AST: #{tree}" end
コンパイル & 実行してみます。4649 と 5963 が出力されればOKです。
変数の導入
次は変数を導入します。
変数にセットした値はスタック上に格納されるため、定義される変数の数（ var_assign の数）を数えて、その分だけスタック上に領域を確保します。
変数は宣言された順番でスタック上に並ぶので、ある変数が何番目に宣言されたかが分かれば、その変数がスタック上のどこのアドレスに格納されるのかが分かります。
var_assignが来たらスタック上の決められたアドレスへ値を格納し、var_ref が来たらスタック上の決められたアドレスから値を取得して返します。
diff --git a/minrubyc.rb b/minrubyc.rb index b08b705..2bbdefa 100644 --- a/minrubyc.rb +++ b/minrubyc.rb @@ -1,7 +1,33 @@ # minrubyc.rb require "minruby" -def gen(tree) +# tree 内に含まれる、var_assign で定義される変数名の一覧 +def var_names(tree) + if tree[0] == "var_assign" + [tree[1]] + elsif tree[0] == "stmts" + arr = [] + tree[1..].each do |statement| + arr += var_names(statement) + end + arr + else + [] + end +end + +# スタックフレーム上の変数のアドレスをフレームポインタ(fp)からのオフセットとして返す +# 例： +# ひとつ目の変数のアドレス = フレームポインタ(fp) + 16 +# ふたつ目の変数のアドレス = フレームポインタ(fp) + 24 +# ふたつ目の変数のアドレス = フレームポインタ(fp) + 32 +# ... +def var_offset(var, env) + # 変数1つにつき8バイトの領域が必要 + env.index(var) * 8 + 16 +end + +def gen(tree, env) if tree[0] == "lit" puts "\tmov x0, ##{tree[1]}" elsif %w(+ - * /).include?(tree[0]) @@ -13,11 +39,11 @@ def gen(tree) puts "\tsub sp, sp, #16" # x0 へ格納された左辺評価結果をスタックへ積む - gen(expr1) + gen(expr1, env) puts "\tstr x0, [sp, #0]" # x0 へ格納された右辺評価結果をスタックへ積む - gen(expr2) + gen(expr2, env) puts "\tstr x0, [sp, #8]" # スタックへ積んだ評価結果を x1 レジスタと x0 レジスタへロード @@ -43,32 +69,53 @@ def gen(tree) elsif tree[0] == "func_call" && tree[1] == "p" # p 関数を呼び出す expr = tree[2] - gen(expr) + gen(expr, env) puts "\tbl _p" elsif tree[0] == "stmts" tree[1..].each do |stmt| - gen(stmt) + gen(stmt, env) end + elsif tree[0] == "var_assign" + name, expr = tree[1], tree[2] + + # 評価した値をスタック上のローカル変数領域へ格納 + gen(expr, env) + puts "\tstr x0, [fp, ##{var_offset(name, env)}]" + elsif tree[0] == "var_ref" + name = tree[1] + + # ローカル変数領域からx0へ値をロード + puts "\tldr x0, [fp, ##{var_offset(name, env)}]" else raise "invalid AST: #{tree}" end end tree = minruby_parse(ARGF.read) +env = var_names(tree) +lvar_size = env.size * 8 puts "\t.text" puts "\t.align 2" puts "\t.globl _main" puts "_main:" + +# スタックフレームを確保 +# NOTE: スタックのサイズは16の倍数でなければならない +puts "\tsub sp, sp, ##{16 + (lvar_size % 16 == 0 ? lvar_size : lvar_size + 8)}" + # lr レジスタと fp レジスタをスタックに退避 -puts "\tsub sp, sp, #16" puts "\tstp fp, lr, [sp, #0]" +puts "\tmov fp, sp" -gen(tree) +gen(tree, env) # lr レジスタと fp レジスタをスタックから復元 puts "\tldp fp, lr, [sp, #0]" -puts "\tadd sp, sp, #16" + +# スタックフレームを破棄 +# NOTE: スタックのサイズは16の倍数でなければならない +puts "\tadd sp, sp, ##{16 + (lvar_size % 16 == 0 ? lvar_size : lvar_size + 8)}" # 終了ステータスに 0 を返す puts "\tmov w0, #10"
以下のコードを実行してみます。
a = 10 b = 20 c = 30 p a p b p c
いい感じに動いているようです。
比較演算子の導入
比較演算子（ == != > < >= <=）を導入します。MinCamlコンパイラには bool 型がないため、比較演算の結果が真の時は整数の 1 を、偽の時は整数の 0 を返します。
diff --git a/minrubyc.rb b/minrubyc.rb index 2bbdefa..a7bbb06 100644 --- a/minrubyc.rb +++ b/minrubyc.rb @@ -30,7 +30,7 @@ end def gen(tree, env) if tree[0] == "lit" puts "\tmov x0, ##{tree[1]}" - elsif %w(+ - * /).include?(tree[0]) + elsif %w(+ - * / == != < <= > >=).include?(tree[0]) op = tree[0] expr1 = tree[1] expr2 = tree[2] @@ -60,6 +60,24 @@ def gen(tree, env) puts "\tmul x0, x0, x1" when "/" puts "\tsdiv x0, x0, x1" + when "==" + puts "\tcmp x0, x1" + puts "\tcset x0, eq" + when "!=" + puts "\tcmp x0, x1" + puts "\tcset x0, ne" + when "<" + puts "\tcmp x0, x1" + puts "\tcset x0, lt" + when "<=" + puts "\tcmp x0, x1" + puts "\tcset x0, le" + when ">" + puts "\tcmp x0, x1" + puts "\tcset x0, gt" + when ">=" + puts "\tcmp x0, x1" + puts "\tcset x0, ge" else raise "invalid operator: #{op}" end
いい感じに動いているようです。
条件分岐の導入
次は条件分岐を導入します。いわゆる if 文です。if文の構文木はこんな感じ。条件式が真の場合はTHEN句が評価され、偽の場合はELSE句が評価されます。
irb(main):003:0> minruby_parse "if 0 == 1; p 123; else p 345; end" => ["if", ["==", ["lit", 0], ["lit", 1]], ["func_call", "p", ["lit", 123]], # THEN句 ["func_call", "p", ["lit", 345]]] # ELSE句
以下はコンパイラのコードです。
条件式を評価し、真の場合はTHEN句へ評価し、偽の場合はELSE句を評価します。
分岐先のラベル名をプログラム中で一意にするため、ラベル名に tree.object_id を付与しています。
diff --git a/minrubyc.rb b/minrubyc.rb index a7bbb06..fba72e9 100644 --- a/minrubyc.rb +++ b/minrubyc.rb @@ -11,6 +11,13 @@ def var_names(tree) arr += var_names(statement) end arr + elsif tree[0] == "if" + # if文の中の変数も参照できるよう、ifの中のブロックにも var_assign を探しに行く + arr = [] + arr += var_names(tree[2]) + if tree[3] + arr += var_names(tree[3]) + end + arr else [] end @@ -104,6 +111,24 @@ def gen(tree, env) # ローカル変数領域からx0へ値をロード puts "\tldr x0, [fp, ##{var_offset(name, env)}]" + elsif tree[0] == "if" + cond, texpr, fexpr = tree[1], tree[2], tree[3] + # 条件式を評価 + puts "\t// 条件式を評価" + gen(cond, env) + puts "\tcmp x0, #0" + + puts "\tbeq .Lelse#{tree.object_id}" + + # 真の場合はtexprを評価 + puts "\t// 真の場合" + gen(texpr, env) + puts "\tb .Lendif#{tree.object_id}" + puts ".Lelse#{tree.object_id}:" + # 偽の場合はfexprを評価 + puts "\t// 偽の場合" + gen(fexpr, env) if fexpr + puts ".Lendif#{tree.object_id}:" else raise "invalid AST: #{tree}" end @@ -126,6 +151,12 @@ puts "\tsub sp, sp, ##{16 + (lvar_size % 16 == 0 ? lvar_size : lvar_size + 8)}" puts "\tstp fp, lr, [sp, #0]" puts "\tmov fp, sp" +# ローカル変数を0で初期化 +env.each do |var| + puts "\tmov x0, #0" + puts "\tstr x0, [fp, ##{var_offset(var, env)}]" +end + gen(tree, env) # lr レジスタと fp レジスタをスタックから復元
コンパイルしてみます。 123 が出力されればOKです。
このまま勢いで while 文も導入しちゃいます。
diff --git a/minrubyc.rb b/minrubyc.rb index fba72e9..3840382 100644 --- a/minrubyc.rb +++ b/minrubyc.rb @@ -18,6 +18,9 @@ def var_names(tree) arr += var_names(tree[3]) end arr + elsif tree[0] == "while" + puts "\t// while: #{tree}" + var_names(tree[2]) else [] end @@ -129,6 +132,15 @@ def gen(tree, env) puts "\t// 偽の場合" gen(fexpr, env) if fexpr puts ".Lendif#{tree.object_id}:" + elsif tree[0] == "while" + cond, body = tree[1], tree[2] + puts ".Lwhile#{tree.object_id}:" + gen(cond, env) + puts "\tcmp x0, #0" + puts "\tbeq .Lendwhile#{tree.object_id}" + gen(body, env) + puts "\tb .Lwhile#{tree.object_id}" + puts ".Lendwhile#{tree.object_id}:" else raise "invalid AST: #{tree}" end
これもいい感じに動いているようです。
組み込み関数の呼び出し
次はlibminruby.c で定義した組み込み関数を呼び出せるようにします。 func_call が返す構文木はこんな感じ。
irb(main):001:0> minruby_parse "p my_add(10, 20)" => ["func_call", "p", ["func_call", "my_add", ["lit", 10], ["lit", 20]]]
libminruby.c へ関数 my_addを追加し、
// libminruby.c #include <stdio.h> long p(long n) { printf("%ld\n", n); return n; } // 組み込み関数テスト用 long my_add(long a, long b) { return a + b; }
コンパイラを以下のように修正します。
上述した通り、関数を呼び出す時の引数はレジスタ x0 から x7 にセットします。 func_call の引数に渡ってきたノードを評価して x0 から x7 へ順番に渡します。通常8つを超える引数を取り扱う場合はスタックを通じた引数の受け渡しを行うのですが、今回は8つを超える引数はサポートせずにエラーを返すようにしました。
diff --git a/minrubyc.rb b/minrubyc.rb index 3840382..94f1769 100644 --- a/minrubyc.rb +++ b/minrubyc.rb @@ -1,6 +1,9 @@ # minrubyc.rb require "minruby" +# 引数用レジスタの一覧 +PARAM_REGISTERS = %w(x0 x1 x2 x3 x4 x5 x6 x7) + # tree 内に含まれる、var_assign で定義される変数名の一覧 def var_names(tree) if tree[0] == "var_assign" @@ -94,11 +97,27 @@ def gen(tree, env) # スタックを破棄 puts "\tadd sp, sp, #16" - elsif tree[0] == "func_call" && tree[1] == "p" - # p 関数を呼び出す - expr = tree[2] - gen(expr, env) - puts "\tbl _p" + elsif tree[0] == "func_call" + name, *args = tree[1..] + + # 引数用のレジスタは8つしかないので、引数が8個以上の場合はエラー + raise "too many arguments (given #{args.size}, expected 8)" if args.size > 8 + + # 引数を評価してスタックへ積む + args.reverse.each do |arg| + gen(arg, env) + puts "\tsub sp, sp, #16" + puts "\tstr x0, [sp, #0]" + end + + # スタックへ詰んだ引数の値を、引数用レジスタへセット + args.each_with_index do |arg, i| + puts "\tldr #{PARAM_REGISTERS[i]}, [sp, #0]" + puts "\tadd sp, sp, #16" + end + + # 関数呼び出し + puts "\tbl _#{name}" elsif tree[0] == "stmts" tree[1..].each do |stmt| gen(stmt, env)
コンパイルして動かしてみます。いい感じに動いてそうです。
ユーザー定義関数の導入
最後に、ユーザー定義関数を導入します。以下のように、ユーザーが関数を定義し、それを呼び出せるようにします。
def hello() 860 # ハロー end p hello() #=> 860
上記のコードをパーサにかけると以下のような構文木が返ります。
irb(main):002:0> minruby_parse "def hello() 860; end; p hello()" => ["stmts", ["func_def", "hello", [], ["lit", 860]], ["func_call", "p", ["func_call", "hello"]]]
コンパイラは、func_def で定義された部分をアセンブリコードとして出力し、 func_call でそれを呼び出します。上記の構文木をアセンブリコードとして出力すると以下のようになります。ユーザー定義関数の名前が他のライブラリ関数の名前と衝突しないよう、関数名の先頭に _minruby_ というプリフィックスをつけています。例えば関数 hello はアセンブリコード上では _minruby_hello というラベルが付けられます。
.text .align 2 ;; func_def で定義されたユーザー定義関数 .globl _minruby_hello _minruby_hello: sub sp, sp, #16 stp fp, lr, [sp, #0] mov fp, sp mov x0, #860 ldp fp, lr, [sp, #0] add sp, sp, #16 ret .globl _main _main: sub sp, sp, #16 stp fp, lr, [sp, #0] mov fp, sp ;; ユーザー定義関数 hello を呼び出す bl _minruby_hello sub sp, sp, #16 str x0, [sp, #0] ldr x0, [sp, #0] add sp, sp, #16 bl _minruby_p ldp fp, lr, [sp, #0] add sp, sp, #16 mov w0, #10 ret
以下、ユーザー定義関数を実装したコンパイラのコードです。主に以下のことを行なっています。
libminrby.cの関数たちにminruby_のプリフィックスをつけた- 構文木から関数定義
func_defsを抽出する関数func_defsを追加 - 抽出した関数定義をアセンブリコードとして出力
diff --git a/libminruby.c b/libminruby.c index a581930..2ff715c 100644 --- a/libminruby.c +++ b/libminruby.c @@ -1,12 +1,12 @@ // libminruby.c #include <stdio.h> -long p(long n) { +long minruby_p(long n) { printf("%ld\n", n); return n; } // 組み込み関数テスト用 -long my_add(long a, long b) { +long minruby_my_add(long a, long b) { return a + b; } diff --git a/minrubyc.rb b/minrubyc.rb index 94f1769..6c309d8 100644 --- a/minrubyc.rb +++ b/minrubyc.rb @@ -40,6 +40,25 @@ def var_offset(var, env) env.index(var) * 8 + 16 end +# ユーザー定義関数を構文木より抽出 +def func_defs(tree) + if tree[0] == "func_def" + { + # 関数名をキーにして [関数名, 引数, 関数本体] を格納 + tree[1] => tree[1..] + } + elsif tree[0] == "stmts" + tmp_hash = {} + tree[1..].each do |stmt| + tmp_hash.merge!(func_defs(stmt)) + end + tmp_hash + else + {} + end +end + +# 構文木をアセンブリコードとして出力 def gen(tree, env) if tree[0] == "lit" puts "\tmov x0, ##{tree[1]}" @@ -97,6 +116,8 @@ def gen(tree, env) # スタックを破棄 puts "\tadd sp, sp, #16" + elsif tree[0] == "func_def" + # 関数の定義はコンパイル時にコードとして出力されるため、実行時には何も行わなくて良い elsif tree[0] == "func_call" name, *args = tree[1..] @@ -117,7 +138,7 @@ def gen(tree, env) end # 関数呼び出し - puts "\tbl _#{name}" + puts "\tbl _minruby_#{name}" elsif tree[0] == "stmts" tree[1..].each do |stmt| gen(stmt, env) @@ -165,12 +186,55 @@ def gen(tree, env) end end +# 関数定義をアセンブリコードとして出力 +def gen_func_def(func_def) + name, params, body = func_def + lenv = var_names(body) + env = params + lenv + + # 名前が衝突しないように、関数名の先頭に _minruby_ を付与 + puts "\t.globl _minruby_#{name}" + puts "_minruby_#{name}:" + + # 関数プロローグ + lvar_size = env.size * 8 + puts "\tsub sp, sp, ##{16 + (lvar_size % 16 == 0 ? lvar_size : lvar_size + 8)}" # NOTE: スタックのサイズは16の倍数でなければならない + puts "\tstp fp, lr, [sp, #0]" + puts "\tmov fp, sp" + # スタック上のパラメータ領域を初期化 + params.each_with_index do |param, i| + puts "\tstr #{PARAM_REGISTERS[i]}, [fp, ##{var_offset(param, env)}]" + end + # ローカル変数を初期化 + lenv.each do |var| + puts "\tmov x0, #0" + puts "\tstr x0, [fp, ##{var_offset(var, env)}]" + end + + gen(body, env) + + # 関数エピローグ + puts "\tldp fp, lr, [sp, #0]" + puts "\tadd sp, sp, ##{16 + (lvar_size % 16 == 0 ? lvar_size : lvar_size + 8)}" # NOTE: スタックのサイズは16の倍数でなければならない + puts "\tret" +end + tree = minruby_parse(ARGF.read) env = var_names(tree) lvar_size = env.size * 8 +# ユーザー定義関数を構文木より抽出 +func_defs = func_defs(tree) + puts "\t.text" puts "\t.align 2" + +# ユーザー定義関数をアセンブリコードとして出力 +func_defs.values.each do |func_def| + gen_func_def(func_def) +end + +# メイン関数 puts "\t.globl _main" puts "_main:"
コンパイルして動かしてみます。 860 (ハロー)が表示されればOKです。
サンプルプログラムを動かしてみる
MinCaml コンパイラはこれで完成です。最後にサンプルプログラムとして10番目のフィボナッチ数を計算する以下のプログラムを動かしてみます。
# fib.rb def fib(n) if n < 2 n else fib(n - 1) + fib(n - 2) end end p fib(10)
コンパイルして実行してみます。10番目のフィボナッチ数である 55 が表示されればOKです。
終わりに
以上、簡易なコンパイラの作り方のご紹介でした。クリスマスの夜、グラス片手に「コンパーイ（Compile）」なんていかがですか？
また、この記事を読んで「もっと言語処理系について知りたい！」となった方は以下を読んでみると良いかも。
- RubyでつくるRuby
- 低レイヤを知りたい人のためのCコンパイラ作成入門
- インタプリタの作り方（Crafting Interpreters）
- 最新コンパイラ構成技法
では、コンバイバイ〜。
