コンパイラ作成(107) 配列と単項演算子の優先順位
今回の目標
配列を実装したときに先送りしちゃった件をなんとかするよ。
// 配列 int main() { int a[10]; a[0] = 42; printf("-a[0] = %d\n", -a[0]); }
本来は-(a[0])と評価しなくちゃいけないんだけど、(-a)[0]って解釈しちゃっててコンパイルに失敗してる。
read_modify_el
優先順位を正しくするために配列の処理を先に持って行ったよ。
# 式の最後までのトークンを読み込み、変形する def read_modify_el(fkind,fstr,skind,sstr) el, kind, str = read_el fkind, fstr, skind, sstr puts to_str(el) if $opt_d # デバッグ用 el = modify_high_priority_el el, ["[]"] el = modify_el_unaryop el, ["+","-","&","*"] el = modify_el el, ["[]"] el = modify_el el, ["*","/","%"] el = modify_el el, ["+","-"] el = modify_el el, ["<",">","<=",">="] el = modify_el el, ["==","!="] el = modify_el el, ["="], :r_to_l puts to_str(el) if $opt_d # デバッグ用 return el, kind, str end
最初はmodify_elを修正しようとしたんだけど、途中で気が変わって別メソッドで処理することにしたよ。
modify_high_priority_el
これがその追加したメソッド。
# elの変形(単行演算子より優先順位が高い演算子の処理) def modify_high_priority_el(el, opl) mel = [] prev = nil loop do if el == [] then break end loop do if el == [] then break end tkn = el.shift if tkn.kind_of?(Array) || tkn.kind != TK::SYMBOL then prev = tkn break end mel << tkn end loop do if el == [] then break end if el[0].kind_of?(Array) then perror "expected operator or ';'" end if el[0].kind != TK::SYMBOL then perror "expected operator or ';'" end if opl.include? el[0].str then prev = [prev, el.shift, el.shift] else if prev != nil then mel << prev prev = nil end if el != [] then mel << el.shift end break end end end if prev != nil then mel << prev end return mel end
これで上手く行くと思うけどあんまり自信はない。
動作テスト
上手く行くかなあ。
~/myc$ myc q12.myc ~/myc$ ./q12 -a[0] = -42 ~/myc$
おお、上手く行ったみたいだ。でももうちょっと色々テストした方が良いだろうな。次回はそれだな。
コンパイラ作成(106) バグ修正
バグ
エラー処理周りのチェックをしていてバグを見つけたよ。
// 配列 int main() { double a[10], *p = a; a[0) = 42; a[1] = 55; printf("*p = %f\n", *p); }
配列の閉じ括弧が間違ってる場合。エラーにならずにコンパイル通っちゃってたよ。
read_el
# 式の最後までのトークンを読み込む # 返り値 # el : expression's token list # kind : 処理しなかったトークン(セミコロンもしくは閉じ括弧) # str : 処理しなかったトークン(セミコロンもしくは閉じ括弧) def read_el(fkind,fstr,skind,sstr) el = [] if fkind == TK::ID && sstr == "(" then # 関数呼出の処理 sel = [] sel << Token.new(fkind,fstr) sel << Token.new(skind,"()") skind, sstr = @lex.gettoken loop do if skind == TK::SYMBOL && sstr == ")" then break end fkind, fstr = skind, sstr skind, sstr = @lex.gettoken pel, skind, sstr = read_modify_el fkind, fstr, skind, sstr sel << pel if skind == TK::SYMBOL && sstr == "," then skind, sstr = @lex.gettoken elsif skind != TK::SYMBOL || sstr != ")" then perror end end el << sel if skind != TK::SYMBOL || sstr != ")" then perror end skind, sstr = @lex.gettoken elsif fstr == "(" then # 括弧の処理 fkind, fstr = skind, sstr skind, sstr = @lex.gettoken sel, skind, sstr = read_el fkind, fstr, skind, sstr el << sel skind, sstr = @lex.gettoken elsif sstr == "[" then # 配列の処理 el << Token.new(fkind,fstr) el << Token.new(skind,"[]") fkind, fstr = @lex.gettoken skind, sstr = @lex.gettoken sel, skind, sstr = read_el fkind, fstr, skind, sstr if sel.size > 1 then el << sel else el << sel[0] end if skind != TK::SYMBOL || sstr != "]" then perror "expected ']'" end skind, sstr = @lex.gettoken else el << Token.new(fkind,fstr) end loop do if skind == TK::EOF then break end if sstr == ";" then break end if sstr == ")" then break end if sstr == "]" then break end if sstr == "," then break end if sstr == "}" then break end fkind, fstr = skind, sstr skind, sstr = @lex.gettoken if fkind == TK::ID && sstr == "(" then # 関数呼出の処理 sel = [] sel << Token.new(fkind,fstr) sel << Token.new(skind,"()") skind, sstr = @lex.gettoken loop do if skind == TK::SYMBOL && sstr == ")" then break end fkind, fstr = skind, sstr skind, sstr = @lex.gettoken pel, skind, sstr = read_el fkind, fstr, skind, sstr sel << pel if skind == TK::SYMBOL && sstr == "," then skind, sstr = @lex.gettoken elsif skind != TK::SYMBOL || sstr != ")" then perror end end el << sel if skind != TK::SYMBOL || sstr != ")" then perror end skind, sstr = @lex.gettoken elsif fstr == "(" then # 括弧の処理 fkind, fstr = skind, sstr skind, sstr = @lex.gettoken sel, skind, sstr = read_el fkind, fstr, skind, sstr el << sel skind, sstr = @lex.gettoken elsif sstr == "[" then # 配列の処理 el << Token.new(fkind,fstr) el << Token.new(skind,"[]") fkind, fstr = @lex.gettoken skind, sstr = @lex.gettoken sel, skind, sstr = read_el fkind, fstr, skind, sstr if sel.size > 1 then el << sel else el << sel[0] end if skind != TK::SYMBOL || sstr != "]" then perror "expected ']'" end skind, sstr = @lex.gettoken else el << Token.new(fkind,fstr) end end return el, skind, sstr end
チェックが抜けてたよ。
動作テスト
~/myc$ myc err50.myc err50.myc:5:8 error: expected ']' ~/myc$
ちゃんとエラーになったよ。次回なにやろうかな。うーん駄目だ。もう頭が働かなくなってる。明日起きてから考えよう。
コンパイラ作成(105) 引数が配列の関数
今回の目標
コマンドライン引数を表示できるように対応するよ。
// コマンドライン int main(int argc, char *argv[]) { for(int i = 0; i < argc; i = i + 1) printf("argv[%d]=%s\n", i, argv[i]); }
関数定義の解析さえ頑張れば大丈夫かな。
function
引数の解析を修正。
# 引数の処理 kind, str = @lex.gettoken loop do if kind == TK::SYMBOL && str == ")" then break end if kind == TK::TYPE then if str == "extern" then perror "invalid 'extern'" end type = str kind, str = @lex.gettoken loop do if kind != TK::SYMBOL || str != "*" then break end type += str kind, str = @lex.gettoken end if type == "void" \ && kind == TK::SYMBOL && str == ")" \ && paratype == [] then break end var_name = str if kind != TK::ID then if type == "void" then perror "invalid type 'void'" else perror "wrong parameter name" end end kind, str = @lex.gettoken if kind == TK::SYMBOL && str == "[" then kind, str = @lex.gettoken if kind != TK::SYMBOL || str != "]" then perror end type += "*" end paratype << type print "para "+var_name+"\n" if $opt_d size = sizeof type @lvarsize += size parametersize << size if check_var var_name then perror "redefinition parameter \"" + var_name +"\"" end if type == "void" then perror "invalid type 'void'" end set_var var_name, [type,@lvarsize] else perror end if kind != TK::SYMBOL || str != ")" then kind, str = @lex.gettoken end if kind == TK::SYMBOL && str == "," then kind, str = @lex.gettoken end end
配列だったら*に変換してるよ。これで問題ないはず。
動作テスト
~/myc$ myc q11.myc ~/myc$ ./q11 abc zxc 123 argv[0]=./q11 argv[1]=abc argv[2]=zxc argv[3]=123 ~/myc$
大丈夫だね。大分配列の実装できてきたかな。次回は何やろうかな。エラー周りのテストかな。問題なければ配列の初期化に進みたいけど、結構難しいかな。
コンパイラ作成(104) ポインタを配列として扱う
今回の目標
ポインタに[]演算子を適用できるようにするよ。
// ポインタと配列演算子 int main() { char *p = "myc"; for(int i = 0; i < 3; i = i + 1) putchar(p[i]); putchar('\n'); }
配列演算子っていう呼び方で合ってるんだろうか。
codegen_els
型チェックの処理を修正。
# 型チェック if type_l == "double" && type_r == "int" then if str != "r10d" then codegen " mov r10d, #{str}" end codegen " cvtsi2sd xmm9, r10d" str = "xmm9" type_r = type_l elsif type_l == "int" && type_r == "double" then codegen " cvtsi2sd xmm8, eax" type_l = type_r end if type_l != type_r then if is_pointer_type?(type_l) && type_r == "int" then if op.str != "+" && op.str != "-" && op.str != "[]" then perror "mismatched types to binary operation" end elsif type_l == "int" && is_pointer_type?(type_r) then if op.str != "+" && op.str != "-" && op.str != "[]" then perror "mismatched types to binary operation" end elsif is_array_type?(type_l) && type_r == "int" then if op.str != "[]" then perror "mismatched types to binary operation" end elsif type_l == "int" && is_array_type?(type_r) then if op.str != "[]" then perror "mismatched types to binary operation" end else perror "mismatched types to binary operation" end elsif is_pointer_type? type_l then perror "mismatched types to binary operation" elsif type_l == "double" && op.str == "%" then perror "mismatched types to binary operation" end
ポインタ型のときも[]演算子を弾かないように修正。
if is_pointer_type?(type_l) && type_r == "int" then # ポインタ型+int型の処理 codegen_pointer_int type_l, op, ostr, str if op.str == "[]" then codegen_lval_to_rval type_l end elsif type_l == "int" && is_pointer_type?(type_r) then # int型+ポインタ型の処理 codegen_int_pointer type_r, op, ostr, str type_l = type_r if op.str == "[]" then codegen_lval_to_rval type_l end elsif is_array_type?(type_l) && type_r == "int" then # 配列+int型の処理 type_l = array_to_pointer type_l codegen_pointer_int type_l, op, ostr, str type_l = type_l[0,type_l.length-1] codegen_lval_to_rval type_l elsif type_l == "int" && is_array_type?(type_r) then # int型+配列の処理 type_r = array_to_pointer type_r codegen_int_pointer type_r, op, ostr, str type_l = type_r[0,type_r.length-1] codegen_lval_to_rval type_l else codegen " " + ostr + " #{reg}, " + str end
codegen_lval_to_rvalをコールするよう修正。
コンパイラ作成(103) int型以外のポインタの間接参照
今回の目標
前回に続きバグ修正。
// 配列 int main() { double a[10], *p = a; a[0] = 42; a[1] = 55; printf("*p = %f\n", *p); }
間接参照演算子もdouble型とかに対応できてなかったよ。
codegen_unaryop
間接参照演算子の処理のところを修正。
elsif op.str == "*" then # 間接参照演算子 type = codegen_el operand if !is_pointer_type? type then perror end type = type[0,type.length-1] codegen_lval_to_rval type =begin if is_pointer_type? type then codegen " mov rax, [rax]" else codegen " mov eax, [rax]" end =end
前回作ったメソッドを呼ぶようにしたよ。
動作テスト
~/myc$ myc q10.myc ~/myc$ ./q10 *p = 42.000000 ~/myc$
ちゃんと参照できるようになったよ。二回続けて細かな修正をしたけど、次回は何か機能追加をしたいなあ。ポインタ変数を配列として扱えるようにするかな。
コンパイラ作成(102) int型以外の配列の参照
今回の目標
色々試してたらバグが見つかったよ。
// 配列 int main() { double a[10]; a[0] = 42; a[1] = 55; printf("a[0] = %f\n", a[0]); }
配列の参照だけどint型以外の場合上手く行ってなかった。バグっていうか未サポートってところかな。
codegen_lval_to_rval
新しいメソッドを追加。
# 左辺値を右辺値に変換するコード生成 def codegen_lval_to_rval(type) if is_pointer_type? type then codegen " mov rax, [rax]" elsif type == "int" then codegen " mov eax, [rax]" elsif type == "char" then codegen " mov al, [rax]" elsif type == "double" then codegen " movsd xmm8, [rax]" else perror end end
codegen_els
配列の処理のところを修正。
if is_pointer_type?(type_l) && type_r == "int" then # ポインタ型+int型の処理 codegen_pointer_int type_l, op, ostr, str elsif type_l == "int" && is_pointer_type?(type_r) then # int型+ポインタ型の処理 codegen_int_pointer type_r, op, ostr, str type_l = type_r elsif is_array_type?(type_l) && type_r == "int" then # 配列+int型の処理 type_l = array_to_pointer type_l codegen_pointer_int type_l, op, ostr, str type_l = type_l[0,type_l.length-1] codegen_lval_to_rval type_l elsif type_l == "int" && is_array_type?(type_r) then # int型+配列の処理 type_r = array_to_pointer type_r codegen_int_pointer type_r, op, ostr, str type_l = type_r[0,type_r.length-1] codegen_lval_to_rval type_l else codegen " " + ostr + " #{reg}, " + str end
追加したメソッドを呼ぶようにしたよ。
codegen_pointer_int
ここも修正。
# ポインタ型+int型のコード生成 def codegen_pointer_int(type_l,op,ostr,str) size = sizeof type_l[0,type_l.length-1] if str == op.str then codegen " " + ostr + " rax, " + (str.to_i*size).to_s elsif str == "r10d" then codegen " movsx r10, r10d" if size == 4 then codegen " shl r10, 2" codegen " " + ostr + " rax, r10" elsif size == 8 then codegen " shl r10, 3" codegen " " + ostr + " rax, r10" else (0...size).each do codegen " " + ostr + " rax, r10" end end else codegen " mov r10d, " + str codegen " movsx r10, r10d" if size == 4 then codegen " shl r10, 2" codegen " " + ostr + " rax, r10" elsif size == 8 then codegen " shl r10, 3" codegen " " + ostr + " rax, r10" else (0...size).each do codegen " " + ostr + " rax, r10" end end end end
ここは本当にバグってたよ。size==8のとき2bitしかシフトしてなかった。
動作テスト
~/myc$ myc q9.myc ~/myc$ ./q9 a[0] = 42.000000 ~/myc$
ちゃんと動くようになったよ。次回は何にするかな。このところテストが不足してるからまずはテストか。
コンパイラ作成(101) 配列への代入
今回の目標
今回は代入だよ。
// 配列 int main() { int a[10]; a[0] = 42; printf("a[0] = %d\n", a[0]); }
まずは単純な場合から。
codegen_assign
今回、大きく書き換えたよ。
# 代入のコード生成 def codegen_assign(el) if el.size != 3 then perror end if el[2] == nil then perror "broken expression" end type_r = codegen_el [el[2]] if el[0].kind_of?(Array) then if el[0][0].str == "*" then codegen " sub rsp, 8" codegen " push rax" type_l = codegen_el [el[0][1]] if !is_pointer_type? type_l then perror end type_l = type_l[0,type_l.length-1] codegen " mov r10, rax" codegen " pop rax" codegen " add rsp, 8" str = "r10" elsif el[0][1].str == "[]" then codegen " sub rsp, 8" codegen " push rax" type_ll = codegen_el [el[0][0]] codegen " sub rsp, 8" codegen " push rax" type_lr = codegen_el [el[0][2]] codegen " mov r10, rax" codegen " pop rax" codegen " add rsp, 8" if is_array_type?(type_ll) && type_lr == "int" then # 配列+int型の処理 type_ll = array_to_pointer type_ll codegen_pointer_int type_ll, el[0][1], "add ", "r10d" type_l = type_ll[0,type_ll.length-1] elsif type_l == "int" && is_array_type?(type_r) then # int型+配列の処理 type_lr = array_to_pointer type_lr codegen_int_pointer type_lr, el[0][1], "add ", "r10d" type_l = type_lr[0,type_lr.length-1] else perror end codegen " mov r10, rax" codegen " pop rax" codegen " add rsp, 8" str = "r10" else perror end else if el[0].kind != TK::ID then perror end v = get_var el[0].str if v == nil then perror "undeclared variable \"" + el[0].str + "\"" end type_l = v[0] str = "rbp - #{v[1]}" end # 代入 if type_r == "void*" && is_pointer_type?(type_l) then type_r = type_l # 暗黙の型変換 elsif type_r == "int" && type_l == "char" then type_r = type_l # 暗黙の型変換 elsif type_r == "int" && type_l == "double" then codegen " cvtsi2sd xmm8, eax" type_r = type_l # 暗黙の型変換 elsif is_array_type? type_r then type_r = array_to_pointer type_r end if type_l != type_r then perror end if is_pointer_type? type_l then codegen " mov qword ptr [#{str}], rax" elsif type_l == "double" codegen " movsd qword ptr [#{str}], xmm8" elsif type_l == "char" codegen " mov byte ptr [#{str}], al" else codegen " mov dword ptr [#{str}], eax" end return type_l end
同じような処理を二箇所に書いてたんだけど、それだと色々修正していく上で問題になるんで、一個に纏めたよ。本題の配列への対応だけど、左辺値を求める処理を組み込んだよ。ただ、この方法で良いかは正直良く分かんないな。多次元配列とかに対応できるか不安だよ。もっと真面目に左辺値を求めるようにしないと駄目かも。この辺要検討だな。
動作テスト
~/myc$ myc q6.myc ~/myc$ ./q6 a[0] = 42 ~/myc$
大丈夫かな。そういやテストプログラムの配列の添え字、いつも0だなあ。違うのもやってみるか。
// エラトステネスの篩 int main() { int a[100]; for(int i = 0; i < 100; i = i + 1) a[i] = 1; for(int i = 2; i < 100; i = i + 1) { for(int j = i * 2; j < 100; j = j + i) { a[j] = 0; } } for(int i = 2; i < 100; i = i + 1) if( a[i] == 1 ) printf("%d ",i); printf("\n"); }
ちょろちょろっと書いたプログラムなんで効率悪いけど、配列のテストにはなるよね。
~/myc$ myc q7.myc ~/myc$ ./q7 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 ~/myc$
おお、ちゃんと素数が表示されてる。代入は参照より楽だったよ。もうちょっと苦労するかと思ったんだけどね。これで配列のサポートは大方できたかな。次回以降残ったとことエラー処理周りをやってくよ。