vm2gol v2 製作メモ(16) 簡単なコード生成



条件分岐とループができて、 サブルーチンの呼び出しができて、引数が渡せて、 結果を返せて、ローカル変数が使えるようになった!!!  ので、これくらい揃えばもうなんでもできるんじゃね!?!?  みたいな気分になりました。

というわけでここからコード生成に突入しようと思います。

つまり!  コンパイラ(の一部)!  です!!

( ただし、ここまでで VM は完成という訳ではないので、 VM も必要に応じて修正していきます。 )


まずは空の main 関数呼び出しから始めましょうか。

C言語で書くとこんな感じ(雰囲気で適当に書いてます)。

void main(){
  // 何もしない
}

まじめにパースすると面倒なので、 またまたこんなオレオレフォーマットを使うことにしました。 これをコード生成の入力とします。 JSON なので、 JSON.parse すれば構文木がゲットできます。

// 16_empty_main.vgt.json

["func"
  ,"main" // 関数名
  ,[] // 引数
  ,[] // 関数本体
]

これがアセンブリコードになったときどうなってほしいか?

こうなってほしい!

  call main
  exit

label main
  push bp
  cp sp bp

  # 関数の処理本体

  cp bp sp
  pop bp
  ret

このようなアセンブリコードに変換するプログラム(=コード生成器) を作っていきましょう。

入力ファイルの拡張子は、 元のプログラムが C言語相当なつもりなので 最初は .vgc.json としていましたが、 構文木をそのまま書いているようなものなので、 Tree の "t" を取って .vgt.json としました。

この形式のコードのことを「vgtコード」と呼ぶことにします。

コード生成器は vgcg.rb というファイル名にしました。 "cg" は code generator の略。

次のようなコマンドでコード生成を行って アセンブリコードのファイルに出力する想定です。

ruby vgcg.rb foo.vgt.json > foo.vga.txt

さて、まず大枠を作ってみました。 出力するアセンブリコードをハードコーディングしておいて、 最初はこんなとこから始めるといいんじゃないでしょうか?

# vgcg.rb

# aline: assembly line

require 'json'

def codegen(tree)
  alines = []

  alines << "  call main"
  alines << "  exit"

  alines << ""
  alines << "label main"
  alines << "  push bp"
  alines << "  cp sp bp"

  alines << ""
  alines << "  # 関数の処理本体"

  alines << ""
  alines << "  cp bp sp"
  alines << "  pop bp"
  alines << "  ret"

  alines
end

# vgtコード読み込み
src = File.read(ARGV[0])

# 構文木に変換
tree = JSON.parse(src)

# コード生成(アセンブリコードに変換)
alines = codegen(tree)

# アセンブリコードを出力
alines.each {|aline|
  puts aline
}

大枠としてはこうで、あとは codegen() をそれっぽくしていけばよさそうです。

aline は assembly line の略。 アセンブリコードの1行に対応する文字列ということにします。

(2021-05-28 追記) 簡素化のため ステップ 53 で 配列 alines に貯めていくのやめてその都度 print する方式に変更しました。


codegen() に渡されている tree はこんな内容です (見た目は元の JSON と同じですが、こっちは Ruby の配列です)。

[
  "func",
  "main",
  [],
  []
]

入力の内容そのままですね。

ただの配列なので、関数名が欲しければ tree[1] 、 関数の本体部分が欲しければ tree[3] で取り出せます。

こうやって取り出したものでハードコーディングしたところを置き換えていきます。 関数本体はまだ空なので出力としては変化なしですね。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -7,16 +7,22 @@ require 'json'
 def codegen(tree)
   alines = []
 
+  fn_name = tree[1]
+  body = tree[3]
+
   alines << "  call main"
   alines << "  exit"
 
   alines << ""
-  alines << "label main"
+  alines << "label #{fn_name}"
   alines << "  push bp"
   alines << "  cp sp bp"
 
   alines << ""
   alines << "  # 関数の処理本体"
+  body.each {|stmt|
+    alines << "  # TODO"
+  }
 
   alines << ""
   alines << "  cp bp sp"

「関数 main をエントリポイントにする」 と決めたので、一番最初の call main の部分は 置き換えずに決め打ちのままにしています。

動かしてみます。

$ ruby vgcg.rb 16_empty_main.vgt.json 
  call main
  exit

label main
  push bp
  cp sp bp

  # 関数の処理本体

  cp bp sp
  pop bp
  ret

特に問題なし。


run.sh を修正しましょう。 アセンブルの前にコード生成のステップを追加します。

--- a/run.sh
+++ b/run.sh
@@ -3,8 +3,10 @@
 set -o errexit
 
 file="$1"
-bname=$(basename $file .vga.txt)
+bname=$(basename $file .vgt.json)
+asmfile=tmp/${bname}.vga.txt
 exefile=tmp/${bname}.vge.yaml
 
-ruby vgasm.rb $file > $exefile
+ruby vgcg.rb $file > $asmfile
+ruby vgasm.rb $asmfile > $exefile
 ruby vgvm.rb $exefile

動かします!

$ ./run.sh 16_empty_main.vgt.json 

(略)

================================
reg_a(0) reg_b(0) reg_c(0) zf(0)
---- memory (main) ----
      00   ["call", 5]
pc => 02   ["exit"]
      03 ["label", "main"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["cp", "bp", "sp"]
      13   ["pop", "bp"]
      15   ["ret"]
---- memory (stack) ----
         41 0
         42 0
         43 0
         44 0
         45 0
         46 0
         47 49
         48 2
sp bp => 49 0

exit

動きました!

今回はここまで。 コード生成の初回なのでまあこんなものでしょう。