TinyRubyコンパイラ/変数の代入と参照
#TinyRuby
from TinyRubyコンパイラ
次はTinyRubyへ変数を導入する。
構文木を確認
変数への代入の構文木はこんな感じ。
code:irb
rb(main):008:0> minruby_parse "a = 10; p a"
=> ["stmts", ["var_assign", "a", "lit", 10], ["func_call", "p", "var_ref", "a"]]
変数の代入
配列の0番目の要素
ノードの種類
var_assign
配列の1番目の要素
変数名
a
配列の2番目の要素
変数 a へ代入する値を求める式
変数の参照
配列の0番目の要素
ノードの種類
var_ref
配列の1番目の要素
変数名
a
ローカル変数の確保の仕方
ローカル変数は、スタック上のローカル変数領域へ格納される
ローカル変数領域のサイズは「変数の個数 * 8バイト」
「変数 a」と「変数 b」が定義された場合は、2 * 8の16バイトを確保する
ローカル変数は、ローカル変数領域の上から順に、変数名のソート順に並べる
変数名一覧は、構文木中の var_assign 集めて作成する
変数を1つだけサポート
「使える変数は1つだけ」という制限を入れると変数の実装が簡単になるので、まずは1つだけの変数をサポートする。
スタック上へ変数1つ文の領域（8バイト）を確保
var_assign が来たら、代入式右辺の評価結果をスタック上の変数領域へ格納
var_ref が来たら、スタック上の変数領域から値を取得
code:diff
diff --git a/tinyrubyc.rb b/tinyrubyc.rb
index 084a41e..0642b25 100644
--- a/tinyrubyc.rb
+++ b/tinyrubyc.rb
@@ -56,6 +56,14 @@ def gen(node)
stmts.each do |stmt|
gen(stmt)
end
+ when "var_assign"
+ # 代入式の右辺を評価
+ gen(node2)
+ # スタック上のローカル変数領域へ評価結果を格納
+ puts " mov rbp-8, rax"
+ when "var_ref"
+ # スタック上のローカル変数領域から値を取得
+ puts " mov rax, rbp-8"
else
raise "invalid AST error: #{node}"
end
@@ -70,7 +78,13 @@ puts "main:"
puts " push rbp"
puts " mov rbp, rsp"
+# ローカル変数用の領域をスタック上に確保（1つだけ）
+puts " sub rsp, 8"
+
gen(node)
+# スタック上に確保したローカル変数領域を解放（1つだけ）
+puts " add rsp, 8"
+
puts " pop rbp"
puts " ret"
出力されるアセンブリはこんな感じ。
code:sh
$ echo "a = 10; p a" | ruby tinyrubyc.rb > tmp.s
$ cat tmp.s
.intel_syntax noprefix
.globl main
main:
push rbp
mov rbp, rsp
sub rsp, 8
mov rax, 10
mov rbp-8, rax
mov rax, rbp-8
mov rdi, rax
call p
add rsp, 8
pop rbp
ret
実行してみる。
code:sh
$ echo "a = 10; p a" | ruby tinyrubyc.rb > tmp.s
$ gcc -z noexecstack tmp.s libtinyruby.c && ./a.out
10
2つ以上の変数をサポート
変数1つだけのプログラムが動くようになったので、次は2つ以上の変数をサポートする。
2つ以上の変数をサポートするために以下の修正を行う。
構文木をたどって使用される変数名一覧を取得する
スタック上へ「使用される変数の個数 * 8バイト」分の領域を確保する
var_assign で値を変数へ格納する際、それぞれの変数に応じたメモリアドレスに値を格納する
var_ref で変数から値を取得する際、それぞれの変数に応じたメモリアドレスから値を取得する
code:diff
diff --git a/test.sh b/test.sh
index 30b2444..e2cc846 100755
--- a/test.sh
+++ b/test.sh
@@ -55,7 +55,7 @@ assert() {
# assert 0 'p(0 >= 1)'
# 変数
-# assert 30 'a = 10; b = 20; p a + b'
+assert 30 'a = 10; b = 20; p a + b'
assert 10 'a = 10; p a'
# 複文
diff --git a/tinyrubyc.rb b/tinyrubyc.rb
index 0642b25..8e0737f 100644
--- a/tinyrubyc.rb
+++ b/tinyrubyc.rb
@@ -1,7 +1,32 @@
require 'minruby'
+VAR_BYTE_WIDTH = 8
+
+# 構文木内の var_assigns ノードを収集する
+def collect_var_assign_nodes(node)
+ case node0
+ when "var_assign"
+ node
+ when "stmts"
+ stmts = node1..
+ var_assigns = []
+ stmts.each do |stmt|
+ var_assigns += collect_var_assign_nodes(stmt)
+ end
+ var_assigns
+ else
+ []
+ end
+end
+
+# 構文木内の変数名一覧を取得する
+def collect_var_names(node)
+ var_assigns = collect_var_assign_nodes(node)
+ var_assigns.map { |var_assign| var_assign1 }.uniq.sort
+end
+
# 受け取った構文木からアセンブリコードを生成する
-def gen(node)
+def gen(node, env)
case node0
when "lit"
# 整数の場合
@@ -16,11 +41,11 @@ def gen(node)
puts " push r13"
# 左辺の計算結果を r12 へ格納
- gen(node1)
+ gen(node1, env)
puts " mov r12, rax"
# 右辺の計算結果を r13 へ格納
- gen(node2)
+ gen(node2, env)
puts " mov r13, rax"
# 演算結果を rax へ格納
@@ -45,7 +70,7 @@ def gen(node)
puts " pop r12"
when "func_call"
# 引数を評価して rdi レジスタにセット
- gen(node2)
+ gen(node2, env)
puts " mov rdi, rax"
# 関数を呼び出す
@@ -54,16 +79,29 @@ def gen(node)
# 文を要素として持つ配列を取得
stmts = node1..
stmts.each do |stmt|
- gen(stmt)
+ gen(stmt, env)
end
when "var_assign"
+ var_name = node1
+
+ # 変数名が見つからない場合はエラー
+ raise "undefined local variable: #{var_name}" unless env.include?(var_name)
+
# 代入式の右辺を評価
- gen(node2)
+ gen(node2, env)
+
# スタック上のローカル変数領域へ評価結果を格納
- puts " mov rbp-8, rax"
+ offset = (env.index(var_name) + 1) * VAR_BYTE_WIDTH
+ puts " mov rbp-#{offset}, rax"
when "var_ref"
+ var_name = node1
+
+ # 変数名が見つからない場合はエラー
+ raise "undefined local variable: #{var_name}" unless env.include?(var_name)
+
# スタック上のローカル変数領域から値を取得
- puts " mov rax, rbp-8"
+ offset = (env.index(var_name) + 1) * VAR_BYTE_WIDTH
+ puts " mov rax, rbp-#{offset}"
else
raise "invalid AST error: #{node}"
end
@@ -72,19 +110,22 @@ end
# 入力をパースする
node = minruby_parse(gets)
+# 変数名一覧を取得
+env = collect_var_names(node)
+
puts " .intel_syntax noprefix"
puts " .globl main"
puts "main:"
puts " push rbp"
puts " mov rbp, rsp"
-# ローカル変数用の領域をスタック上に確保（1つだけ）
-puts " sub rsp, 8"
+# ローカル変数用の領域をスタック上に確保
+puts " sub rsp, #{env.size * VAR_BYTE_WIDTH}"
-gen(node)
+gen(node, env)
-# スタック上に確保したローカル変数領域を解放（1つだけ）
-puts " add rsp, 8"
+# スタック上に確保したローカル変数領域を解放
+puts " add rsp, #{env.size * VAR_BYTE_WIDTH}"
puts " pop rbp"
puts " ret"
変数のスコープのメモ
変数のスコープは関数内に閉じているため、関数ごとにスタック上のローカル変数格納領域を確保する必要がある（現時点では関数は）
トップレベルの変数は関数内からは参照できないし、関数内の変数はトップレベルから参照できない