掛け算の順序

度々ネットなどで「子供が掛け算の順序を間違えたら×を食らった」などと拡散されることのあるこの「掛け算の順序問題」、根が深いらしく色々な意見がネット上にあふれていますが、コンパイラ理論（プログラミング言語の表現をコンピュータが実行可能な形式に直すプログラムをコンパイラと言います）的には部分的には合点できる点もあるというお話です。

一般的なプログラミング表現である、" val = 2 * 3 * 4" について、解説してみたいと思います。

まず、機械語と呼ばれるコンピュータの理解できる表現においては、数字を三つ持つ掛け算は（一部の例外を除いて）ありません。つまり2 * 3 * 4を一度に計算できる方法は無いのです。そこで、初めに二つを掛け合わせ、最後にもう一つを掛け合わせます。

文脈自由文法的に書くと（意図的に曖昧性がある文法にしてあります）、

 assign -> lvalue = expr
 lvalue  -> 変数名

（変数名は、具体的な規則は省略しますが正規表現で書くと
　[a-zA-Z_][0-9a-zA-Z_]* です。変数名からvalが導出できるとします）

 expr    -> expr * expr | digits ("|"はorの意味で、A|BはAかBが導出されます)
 expr    -> digits
 digits   -> digits digit | digit
 digit     -> 0|1|2|3|4|5|6|7|8|9

この表現は、左の非終端記号（文字の集まりだと思ってください）が、"->" の右の非終端記号や終端記号（具体的な文字）の列に書き換えられることを表しています。

assignがスタートの非終端記号です。assign を複数回書き換えると、val = 2 * 3 * 4を導出できることを示してみたいと思います。

順に導出してみましょう。

assign
lvalue = expr
val      = expr
val      = expr * expr
val      = digits * expr   （ここ注目！）
val      = digits * expr * expr
val      = digits * digits * expr
val      = digits * digits * digits
val      = digit * digits * digits
val      = digit * digit * digit
val      = 2 * 3 * 4               （一気に導出！）

たしかに、上記文脈自由文法から導出できました！

と、言いたいところですが、この文法は曖昧です（残念！）

具体的には

val      = digits * expr   （ここ注目！）

は、

val      = expr * digits

とも導出できます。つまり文法規則から一意な導出が決まらないのです。

掛け算が複数あるだけの表現においてはこれはさほど問題にならないのですが、

優先度の違う二項演算子（-+*/)では優先度があるため、文法が曖昧だと

導出が複数できてしまい、その結果、違う解釈ができてしまうため、計算結果が

違う導出候補が出来てしまいます。困った困った。

曖昧性のない文法を作るために、昔の人も苦心しました。その結果、

次のように書けば、曖昧性がない文法になることを発見したのです。

変更前：expr    -> expr * expr | digits ("|"はorの意味で、A|BはAかBが導出されます)

変更後： expr    -> expr * digits | digits

やってみましょう。

assign
lvalue = expr
val      = expr
val      = expr * digits
val      = expr * digits * digits
val      = digits * digits * digits
val      = digit * digits * digits
val      = digit * digit * digits
val      = digit * digit * digit
val      = 2 * 3 * 4               （一気に導出！）

たしかに、一意に導出できています。

ここで機転の利く方は、次の文法も書けるので、まだ曖昧だよと指摘するかもしれません。

変更前：expr    -> expr * expr | digits ("|"はorの意味で、A|BはAかBが導出されます)

変更後： expr    -> digits * expr | digits

右辺のdigitsとexprが逆の位置にありますね。
たしかに、この文法の場合、導出が変わってきます。やってみましょう。

assign
lvalue = expr
val      = expr
val      = digits * expr
val      = digits * digits * expr
val      = digits * digits * digits
val      = digit * digits * digits
val      = digit * digit * digits
val      = digit * digit * digit
val      = 2 * 3 * 4               （一気に導出！）

つまり導出の仕方が文法により変わり、どちらか一方の文法を採用しないといけないならば、どちらでやるか決めないといけないことがわかります。

ここで色々話をすっ飛ばして結論を言うと、

一番目の曖昧性回避の文法の方はleft associative、

二番目の曖昧性回避の文法の方はright associative、です！

left associativeは、最も左が導出の最後になる文法ルールで、

right associativeは、最も右が導出の最後になる文法ルールです。

で、結論をさらに言うと、四則演算などほとんどの二項演算子（-+*/など）はleft associative、例外として代入とべき乗だけ（=と**）は right associativeと

計算機科学の世界では決まっています。つまり曖昧な文法を避ける避け方が二つあり、

そのどちらを取るかは演算子ごとに決まっているのです。

  *   * *   *   * *   *   * *   *   * *   *   * *   *   * *   *   * *   *   * *   *   * *   *   * * 

 * *   *   * *   *   * *   *   * *   *   * *   *   * *   *   * *   *   * *   *   * *   *   * *   * 

さて本題に戻ります。掛け算の順序についてです。

掛け算は left associativeなので、

val = (2*3)*4

という導出が行われます。つまりこれを機械語風に表現すると

val1 = 2 * 3

val2 = val1 * 4

val   = val2

です。掛け算は左から順に計算していることがわかります。

僕は掛け算の順序の議論を把握しているわけではありませんが、

掛け算の順序にこだわる擁護派は、このleft associativeであることを

言いたかったのではないかと推測するわけです。

もちろん掛け算の連続であればどの順序で掛けても結果は同じです。

ただ、計算機科学的には3つの数値を一緒に掛けることはできないことから、

計算機内部では２回の計算に分けられ、それは左から順に掛け算を行っていく

のです。つまり順序は存在するわけです。

さて長くなりました。

この文書の目的は掛け算の順序派を擁護することが目的なのではなく、

掛け算の順序の存在がコンパイラ理論的にはあるよという見方の提案を

することです。

お家でお子様と一緒に式を導出しながら、掛け算の順序の存在について

議論してみるのもいいかなと思います。

では〜。

（文責kimrin）