编程语言导论/优先级和结合性
编程语言的语义并非由其语法定义。但是，程序语义的某些方面完全由编程语言的语法组织方式决定。其中一个方面是运算符应用于操作数的顺序。此顺序通常由运算符之间的优先级和结合性定义。解释器或编译器用来评估表达式的绝大多数算法往往首先分析在表达式推导树中更深层的运算符。例如，让我们考虑以下来自现代编程语言的 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 类型系统。