二項演算が右結合になっていたのを左結合に変えます。

例として 1 + 2 + 3 で見てみます。

変更前は

[:+,
  1,
  [:+, 2, 3]]

となるようにパースされていて、最終的に機械語になって実行されるときには

2 + 3
1 + {2 + 3 の結果}

という順番で実行されるようになっていました。

今回の変更により

[:+,
  [:+, 1, 2],
  3]

となるようにパースされ、

1 + 2
{1 + 2 の結果} + 3

という順番で実行されるようになります。

なぜ変更するかという話で言えば、 v3 を作っているときに右結合なのを忘れていて少しハマったのがきっかけです。コードを書いている側としては、無意識のうちに他の一般的な言語と同じで左結合だろうと思っていたわけですね。自分で作ったのに。

すごく困るというわけではないですし、「ライフゲームがコンパイルできればよい」という観点で言えば正直どっちでも大差ありません。

どっちでもいいのですが、実装を大きく変えなければいけないわけでもないので、だったらより良い（一般的で直感に反していない、自然な）形に変えておこう、という程度の動機です。

意図的に右結合にしていたということもなかったと思いますし、変えてしまっていいでしょう。

修正後の状態。

def binary_op?(t)
  ["+", "*", "==", "!="].include?(t.value)
end

def _parse_expr_factor
  t = peek()

  if t.type == :sym
    consume "("
    expr = parse_expr()
    consume ")"
    expr

  elsif t.type == :int || t.type == :ident
    $pos += 1

    case t.type
    when :int
      t.value.to_i
    else
      t.value
    end

  else
    raise ParseError
  end
end

def parse_expr
  expr = _parse_expr_factor()

  while binary_op?(peek())
    op =
      case peek().value
      when "+"  then "+"
      when "*"  then "*"
      when "==" then "eq"
      when "!=" then "neq"
      else
        raise ParseError, "must not happen"
      end
    $pos += 1

    expr_r = _parse_expr_factor()
    expr = [op.to_sym, expr, expr_r]
  end

  expr
end

二項演算子があったら
二項演算子とその次の項をパースする
繰り返す

という処理になりました。関数の引数や case 文の when 句のパースと似たパターンですね。

その他の修正

ラベルが見つからない場合はエラーにする (vgasm.rb)
- 存在しない関数を呼び出すようなコードを書いた場合、原因が分かりにくいエラーが VM での実行時に発生するようになっていて困ったので、アセンブルの段階でエラーにしてしまうことに
VMコメントの整理
rename: codegen_〜 => gen_〜 (vgcg.rb)
- メソッド名を短くしました。 gen_〜 でも分かるからいいかなと。

2021-10-05 追記

式の結合と優先順位については、現時点で

左結合
演算子の優先順位なし（括弧で明示）

という方式になっていますが、たまたま VTL という言語についての記事を読んでいて「おお、同じだ」と思いました。

VTL(Very Tiny Language)の作成

VTLでは，演算子の間に優先順位は存在せず，左から順番に演算が行われます．演算の順序を変えたい場合は括弧"()"をつけます．例えば，"2+3*4"の結果は"20"となり，"2+(3*4)"の結果は"14"となります．

vm2gol の方は「ライフゲームをコンパイルするという目的に対して重要度の低い部分を排してできるだけ簡素にしたい」という動機により優先順位なしになっているわけですが、VTL の方はリソースの制約が背景にあっての選択のようです。

目次ページに戻る / 前 / 次

memo486

vm2gol v2 （57）二項演算を左結合に変更

その他の修正

2021-10-05 追記