演算子の結合性

プログラミング言語理論では、演算子の結合性は、括弧がない場合に同じ優先順位の演算子をどのようにグループ化するかを決定する特性です。オペランドの前後に演算子があり ( など)、それらの演算子の優先順位が同じである場合、オペランドは 2 つの異なる操作 (つまり、2 つの演算子によって示される 2 つの操作) への入力として使用できます。オペランドをどの操作に適用するかの選択は、演算子の結合性によって決まります。演算子は、結合性(操作を任意にグループ化できる)、左結合性(操作を左からグループ化する)、右結合性(操作を右からグループ化する)、または非結合性(出力型が入力型と互換性がないため、操作を連鎖できない) のいずれかです。演算子の結合性と優先順位は、プログラミング言語の定義の一部です。異なるプログラミング言語では、同じ種類の演算子に対して異なる結合性と優先順位を持つ場合があります。 ^ 3 ^

式 について考えてみましょうa ~ b ~ c。演算子が~左結合性を持つ場合、この式は と解釈されます(a ~ b) ~ c。演算子が右結合性を持つ場合、式は と解釈されますa ~ (b ~ c)。演算子が非結合性の場合、式は構文エラーになるか、特別な意味を持つ可能性があります。一部の数学演算子には、本来結合性があります。たとえば、従来の数学表記法で使用される減算と除算は、本来左結合性です。対照的に、加算と乗算は、左結合性と右結合性の両方を持ちます。(例(a * b) * c = a * (b * c))。

多くのプログラミング言語のマニュアルには、演算子の優先順位と結合性の表が掲載されています。たとえば、C と C++ の表を参照してください。

ここで説明する表記上の結合性の概念は、数学的な結合性と関連していますが、異なります。数学的に結合性のある演算は、定義により、表記上の結合性を必要としません。(たとえば、加算は結合性を持つため、左結合性または右結合性である必要はありません。) ただし、数学的に結合性を持たない演算は、表記上、左結合性、右結合性、または非結合性である必要があります。(たとえば、減算は結合性を持たないため、表記上の結合性を持つ必要があります。)

結合性は、式内の演算子の優先順位が同じ場合にのみ必要です。通常+、 と は-同じ優先順位を持ちます。式 を考えてみましょう7 - 4 + 2。結果は(7 - 4) + 2 = 5または のいずれかになります。前者の結果は、 とが左結合の7 - (4 + 2) = 1場合に対応し、後者の結果は、 とが右結合の場合に対応します。 +-+-

通常の使用法を反映するため、加算、減算、乗算、除算の演算子は通常左結合ですが、 ^{[1] [2] [3]}指数演算子（存在する場合）^{[4] [より適切な情報源が必要]}一般的な取り決めはありません。代入演算子は通常右結合です。オペランドが 2 つの演算子に関連付けられたり、演算子がまったく関連付けられなかったりするのを防ぐため、同じ優先順位を持つ演算子は同じ結合性を持つ必要があります。

式 を考えてみましょう。5^4^3^2ここで は^右結合のべき乗演算子です。トークンを左から右に読み取るパーサーは、 の右結合性により^、次のように結合規則を分岐に適用します。

1. 用語5が読み上げられます。
2. 非終端 ^記号が読み取られます。ノード: " 5^"。
3. 用語4が読み取られます。ノード: " 5^4"。
4. 非終端^記号が読み取られ、右結合規則がトリガーされます。結合規則によりノードが決定されます: " 5^(4^"。
5. 用語3が読み取られます。ノード: " 5^(4^3"。
6. 非終端^記号が読み取られ、右結合規則の再適用がトリガーされます。ノード " 5^(4^(3^"。
7. 用語2が読み取られます。ノード「5^(4^(3^2」。
8. 読み取るトークンがありません。結合性を適用して解析ツリー「5^(4^(3^2))」を生成します。

これは、最上位ノード (最初の^) から始めて深さ優先で評価できます。

1. 評価者は、最初の式から 2 番目の式を経て 3 番目の式までツリーを下っていきます^。
2. ^{3 2} = 9と評価されます。結果は、2 番目の 2 番目のオペランドとして式 branch を置き換えます^。
3. 評価は解析ツリーの 1 レベル上まで続行され、4 ⁹ = 262,144 となります。ここでも、結果は最初の式の 2 番目のオペランドとして式ブランチを置き換えます^。
4. 再び、評価者はツリーをルート式まで進み、次のように評価します: 5 ²⁶²¹⁴⁴ ≈6.206 0699 × 10 ^{183 230}。最後に残った枝が崩壊し、その結果が全体の結果となり、全体的な評価が完了します。

左結合評価では、構文木 ((5^4)^3)^2と全く異なる結果 (625 ³ ) ² = 244,140,​​625 ² ≈が得られる。5.960 4645 × 10 ¹⁶ .

多くの命令型プログラミング言語では、代入演算子は右結合として定義され、代入は単なる文ではなく、式 (値に評価される) として定義されます。これにより、1 つの代入式の値を次の代入式の右オペランドとして使用して、 連鎖代入が可能になります。

Cでは、代入はの型に変換されたa = b式と同じ値に評価される式であり、のR 値をのL 値に格納するという副作用があります。^[a]したがって、式はと解釈できます。は L 値式ではないため、つまり R 値はありますが の R 値を格納する L 値を持たないため、代替式はエラーになります。 演算子の右結合性により、 などの式はと解釈できます。 babaa = (b = c)b = c; a = b;(a = b) = ca = bc=a = b = ca = (b = c)

C++では、代入はa = b式 と同じ値に評価される式でaあり、 の R 値をbの L 値に格納するという副作用がありますa。したがって、式 はa = (b = c)として解釈できますb = c; a = b;。また、代替式は、エラーを発生させる代わり(a = b) = cに として解釈できますa = b; a = c;。演算子の右結合性により、=などの式はa = b = cとして解釈できますa = (b = c)。

非結合演算子は、式の中で順番に使用された場合、動作が定義されていない演算子です。Prolog では、" "などの構造が構文エラーを構成する ため、中置演算子は非結合です:-。a :- b :- c

もう 1 つの可能性は、特定の演算子のシーケンスが結合性として表現できない別の方法で解釈される場合です。これは通常、構文的にはこれらの演算のシーケンスに特別な規則があり、意味的には動作が異なることを意味します。良い例はPythonで、Python にはそのような構造がいくつかあります。^[5]代入はステートメントであり演算ではないため、代入演算子は値を持たず、結合性がありません。連鎖代入は、代わりに代入シーケンスの文法規則を持つことで実装されa = b = c、代入シーケンスは左から右に代入されます。さらに、 のような代入と拡張代入の組み合わせは、 C では有効ですが、Python では有効ではありません。別の例は、 、、 などa = b += cの比較演算子です。 のような連鎖比較は と解釈され、または のいずれとも同等ではありません。^[6]>==<=a < b < c(a < b) and (b < c)(a < b) < ca < (b < c)

• 演算の順序（算術および代数）
• 一般的な演算子表記（プログラミング言語）
• 結合性（結合性という数学的性質）