程式語言導論/優先順序和結合性
程式語言的語義並非由其語法定義。但是，程式語義的某些方面完全由程式語言的語法組織方式決定。其中一個方面是運算子應用於運算元的順序。此順序通常由運算子之間的優先順序和結合性定義。直譯器或編譯器用來評估表示式的絕大多數演算法往往首先分析在表示式推導樹中更深層的運算子。例如，讓我們考慮以下來自現代程式語言的 C 程式碼片段：a = b < c ? * p + b * c : 1 << d ()。側圖顯示了此賦值的推導樹。
從這棵樹中，我們可以看到第一個星號，例如 *p 是一個一元運算子，而第二個，例如 *c 是二元運算子。我們還看到，我們將首先將變數 b 和 c 相乘，而不是將變數 p 的內容與 b 相加。這種評估順序不僅對於解釋表示式很重要，而且對於對其進行型別檢查甚至為其生成原生代碼也很重要。
優先順序：我們說運算子 op1 的優先順序高於另一個運算子 op2，如果 op1 必須在 op2 之前進行評估，無論這兩個運算子在同一個表示式中。例如，在包含這兩個運算子的算術表示式中，我們通常會先進行除法，然後再進行減法。因此，我們通常認為 4 - 4 / 2 = 2。但是，如果我們使用不同的約定，那麼我們也可以認為 4 - 4 / 2 = (4 - 4) / 2 = 0。
模糊的語法可能會影響程式語言中優先順序規則的準確含義。為了說明這一點，我們將使用以下語法，該語法識別包含數字減法和除法的表示式
<exp> ::= <exp> - <exp>
| <exp> / <exp>
| (<exp>)
| <number>
根據這種語法，表示式 4 - 4 / 2 有兩個不同的推導樹。在表示式 4 - 4 巢狀更深的那個中，我們有 4 - 4 / 2 = 0。另一方面，在 4/2 巢狀更深的樹中，我們有 4 - 4 / 2 = 2。
可以重新編寫語法以消除這種模糊性。下面我們有一個稍微不同的語法，其中除法的優先順序高於減法，這在數學中是常見的
<exp> ::= <exp> - <exp>
| <mulexp>
<mulexp> ::= <mulexp> / <mulexp>
| (<exp>)
| <number>
作為指導原則，生成規則距離起始符號越遠，其節點在推導樹中巢狀的越深。因此，由距離語法起始符號更遠的生成規則生成的運算子往往具有更高的優先順序。當然，這僅適用於我們的評估演算法從推導樹的葉子開始計算值，一直到它的根部。回到上面的例子，我們只能以一種獨特的方式構建表示式 4 - 4 / 2 的推導樹。
透過在語法中新增 mulexp 節點，我們已經使除法的優先順序高於減法。但是，我們仍然可能遇到無法明確評估解析樹的問題。這些問題與運算子的結合性有關。例如，表示式 4 - 3 - 2 可以用兩種不同的方式解釋。我們可以認為 4 - 3 - 2 = (4 - 3) - 2 = -1，或者我們可以認為 4 - 3 - 2 = 4 - (3 - 2) = 3。我們可以為該表示式構建的兩個可能的推導樹如下所示
在算術中，數學家已經採納了這樣的約定，即必須首先解決最左邊的減法。同樣，這只是一個約定：如果我們幾百年前決定減法序列應該從右到左求解，數學仍然會起作用，儘管方式略有不同。從語法的角度來看，我們可以修改語法，始終將最左邊的減法以及最左邊的除法巢狀更深。下面的語法以這種方式工作。此語法不再模稜兩可。它可以生成的任何字串都只有一個推導樹。因此，只有一種方法可以為我們的示例 4 - 3 - 2 構建解析樹。
<exp> ::= <exp> - <mulexp>
| <mulexp>
<mulexp> ::= <mulexp> / <rootexp>
| <rootexp>
<rootexp> ::= ( <exp> )
| <number>
由於減法在推導樹的左側巢狀得更深，所以我們說此運算子是左結合的。在典型的程式語言中，大多數運算子都是左結合的。但是，程式語言也具有右結合的二元運算子。一個眾所周知的例子是 C 中的賦值。賦值命令，例如 int a = 2，修改了變數 a 的狀態。但是，此命令也是一個表示式：它返回最後賦值的值。在這種情況下，賦值表示式返回的值為 2。這種語義允許程式設計師將賦值序列連結在一起，例如 int a = b = 2;。右結合運算子的另一個例子是 ML 中的列表建構函式。此運算子，我們用 :: 表示，接收一個元素和一個列表，並將該元素插入列表的開頭。例如 1::2::3::nil 等效於 1::(2::(3::nil))。它不可能不同：運算元的型別要求第一個運算子是一個元素，而第二個運算子是一個列表。如果我們以不同的方式評估它，例如 1::2::3::nil = ((1::2)::3)::nil，那麼我們將有兩個元素配對在一起，這將無法透過 ML 型別系統。