コンパイラ作成（２２） 減算除算

今回の目標

今回は減算と除算の追加。

// 四則演算
main()
{
    print((3 + 4) * 2 / (9 - 2));
}

これで加減乗除が揃うよ。

expr

今回、式の処理を大幅に変更することにした。初めはすっきりしてたルーチンが色々やってるうちにごちゃごちゃしちゃったんで、今後の機能追加を考えて一から書き直すよ。

# 式の構文解析で使う構造体
Token = Struct.new(:kind, :str) do
  def to_s
    str
  end
end

# デバッグ用出力を分かりやすくするためのルーチン
def to_str(a)
  "["+a.map{|x| if x.kind_of?(Array) then to_str(x) else x.to_s end }.join(", ")+"]"
end

式の構文解析で使う構造体とその関連のルーチン。

  # 式の構文解析
  def expr2(fkind,fstr,skind,sstr)
    el, kind, str = read_el fkind, fstr, skind, sstr
#   puts to_str(el)
    el = modify_el el, ["*","/"]
#   puts to_str(el)
    codegen_el el
    return kind, str
  end

  # 式の最後までのトークンを読み込む
  #   返り値
  #     el   : expression' 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,"()")
      el << sel
      skind, sstr = @lex.gettoken
      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
    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
      fkind, fstr = skind, sstr
      skind, sstr = @lex.gettoken
      if fkind == TK::ID && sstr == "(" then
        # 関数呼出の処理
        sel = []
        sel << Token.new(fkind,fstr)
        sel << Token.new(skind,"()")
        el << sel
        skind, sstr = @lex.gettoken
        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
      else
        el << Token.new(fkind,fstr)
      end
    end
    return el, skind, sstr
  end

  # elの変形
  #   [2, +, 3, *, 5]
  #   =>[2, +, [3, *, 5]]
  def modify_el(el, opl)
    mel = []
    tel = []
    tel << el.shift
    loop do
      if el == [] then break end
      if opl.include? el[0].str then
        tel << el.shift
        tel << el.shift
      else
        if tel.size == 1 then mel << tel[0] else mel << tel end
        tel = []
        mel << el.shift
        tel << el.shift
      end
    end
    if tel.size == 1 then mel << tel[0] else mel << tel end
    return mel
  end

  # 式のコード生成
  def codegen_el(el)
    codegen_elf el.shift
    loop do
      if el == [] then break end
      op = el.shift
      operand = el.shift
      codegen_els op, operand
    end
  end

  # 式のコード生成（二項演算の左側被演算子）
  def codegen_elf(operand)
    if operand.kind_of?(Array) then
      if operand[0].size == 2 && operand[0].kind == TK::ID && operand[1].str == "()" then
        codegen "  call " + operand[0].str
      else
        codegen_el operand
      end
    elsif operand.kind == TK::NUMBER then
      codegen "  mov  eax, " + operand.str
    end
  end

  # 式のコード生成（二項演算の右側被演算子）
  def codegen_els(op, operand)
    if op.str == "+" then
      ostr = "add "
    elsif op.str == "-" then
      ostr = "sub "
    elsif op.str == "*" then
      ostr = "mul "
    elsif op.str == "/" then
      ostr = "div "
    end
    if operand.kind_of?(Array) then
      if operand[0].size == 2 && operand[0].kind == TK::ID && operand[1].str == "()" then
        codegen "  push rax"
        codegen "  call " + operand[0].str
        codegen "  mov  ebx, eax"
        codegen "  pop  rax"
      else
        codegen "  push rax"
        codegen_el operand
        codegen "  mov  ebx, eax"
        codegen "  pop  rax"
      end
      if op.str == "*" || op.str == "/" then
        if op.str == "/" then
          codegen "  xor  edx, edx"
        end
        codegen "  " + ostr + " ebx"
      else
        codegen "  " + ostr + " eax, ebx"
      end
    elsif operand.kind == TK::NUMBER then
      if op.str == "*" || op.str == "/" then
        codegen "  mov  ebx, " + operand.str
        if op.str == "/" then
          codegen "  xor  edx, edx"
        end
        codegen "  " + ostr + " ebx"
      else
        codegen "  " + ostr + " eax, " + operand.str
      end
    end
  end

前のコードは構文解析しながらコード生成もやってたんだけど、今回はそれをやめて式のトークンを全部読み取って、構文解析して、それをもとにコード生成するようにしたよ。

動作チェック

それでは動作チェック行ってみるよ。

~/myc$ myc i16.myc
~/myc$ ./i16
2
~/myc$

えーと、計算式は(3 + 4) * 2 / (9 - 2)だったから答えは2で合ってるよね。これで四則演算ができるようになった。例によってテストが不十分だけどね。
今回、構文解析とコード生成を分離したわけだけどさ、世の中の真っ当なコンパイラはみんなそうしてるよね。mycも初めからそうすればよかったかな。コード生成まで一緒くたにやるのはやっぱり無理があったよ。でもこれは一遍やってみて分かったことだからそれなりに意味はあったのかな。
今回の変更でコンパイラのコードは586行まで増えたよ。変更前から60行ぐらい増えてるのかな。減算と除算を組み込んでだからそれほど変わってないのかな。まあ、なにはともあれ、今後演算子を増やしていきやすくなったと思うよ。さて次回は何やろうかな。演算子のサポートを増やすか、全然違うことをするか。いつも通りその時の気分で決めるか。