なぜ電卓プログラムのべき乗は 2^3^2 = 512 でなければならないのか？【右結合・計算機】

プログラミングで算術式パーサー（解析器）を作る際、誰もが直面する壁があります。それが演算子の「優先順位（Precedence）」と「結合性（Associativity）」です。

「掛け算は足し算より先」というのは優先順位の話ですが、同じ優先順位の演算子が並んだとき、どちらから計算するかを決めるのが結合性です。多くの演算子は「左結合」（左から順に計算）ですが、唯一の例外とも言えるのが「べき乗（Power）」です。

今回は、なぜべき乗だけが「右結合」でなければならないのか、その数学的な理由と計算機実装における違いについて、コラムとしてまとめました。

本編パーサーの実装 : Rustで計算機を作るParserの実装

1. なぜ「べき乗」だけが右結合なのか？：数学的な必要性

右結合である理由として、一番納得できる理由は、「数学的な正確さを保つため」です。

具体例を見てみましょう。2 ^ 3 ^ 2 という式があるとします。

左結合の場合：`(2 ^ 3) ^ 2`

もしべき乗が他の演算子と同じように左結合だとすると、計算順序は以下のようになります。

\[ (2^3)^2 = 8^2 = 64 \]

右結合の場合：`2 ^ (3 ^ 2)`

しかし、数学におけるべき乗の記述 \(a^{b^c}\) は、右結合、つまり上から順に（右から）計算するのが暗黙のルールです。

\[ 2^{(3^2)} = 2^9 = 512 \]

結果が全く異なります。

もしべき乗が左結合だとすると、(2^3)^2 は指数法則により \( 2^{3 \times 2} = 2^6 \) と等しくなり、単一の指数（この場合は 3 * 2）として表現できてしまいます。これでは、わざわざ指数が別のべき乗になっている構造を表現する意味が薄れてしまいます。

「右結合にすることでしか表現できない計算順序（ネストしたべき乗）がある」というのが、べき乗を右結合にする強力な数学的動機です。

2. 計算機実装における「左」と「右」の違い

この数学的な要求を、計算機のパーサー（構文解析器）でどのように実装するかを見てみましょう。再帰降下構文解析やPratt Parsingといった手法で、演算子の結合性を扱う際、コード上のわずかな差が大きな違いを生みます。

ここでは、概念を理解するために Rust に似た疑似コードを使いますが、基本的な考え方はどの言語でも共通です。

左結合（足し算 `+` など）のイメージ

左結合の演算子は、ループを使って左から順に処理を積み上げていくイメージで実装されます。

// 疑似コード: 左から順に lhs (left hand side) を更新し続ける

fn parse_additive_expression() -> Expr {
    let mut left = parse_primary(); // まず左辺を解析 (例: 'a')

    // 次のトークンが '+' である限りループ
    while next_token_is(Token::Plus) {
        consume(Token::Plus); // '+' を消費
        let right = parse_primary(); // 次の項を解析 (例: 'b')
        
        // 現在の left と right を使って、新しい Add ノードを作り、
        // それを次のループの left とする
        left = Expr::BinaryOp(BinaryOp::Add, Box::new(left), Box::new(right));
    }
    
    // ループが終わったら、最終的な式のツリーを返す
    left
}

この実装では、式ツリーは左へ左へと成長していきます。

右結合（べき乗 `^`）のイメージ

一方、右結合の演算子は、再帰呼び出しを使って、右側の式を優先的に解析させるイメージで実装されます。

// 疑似コード: 右側を解析する際に自分自身の優先度を引き継ぐ（再帰）

fn parse_power_expression(lhs: Expr) -> Expr {
    // もし次のトークンが '^' であれば
    if next_token_is(Token::Power) {
        consume(Token::Power); // '^' を消費
        
        // 【ここが重要】
        // 右側の式を解析する際、自分自身の優先度（この場合はべき乗）を
        // 引き継いで再帰的に呼び出す。
        // これにより、右側の '^' が先に解析される。
        let rhs = parse_expression(PRECEDENCE_POWER); 
        
        // 解析した rhs を使って、Power ノードを作る
        Expr::BinaryOp(BinaryOp::Power, Box::new(lhs), Box::new(rhs))
    } else {
        // '^' がなければ、左辺をそのまま返す
        lhs
    }
}

この実装では、右側の式を先に完成させようとするため、式ツリーは右へ右へと成長していきます。