表达式的优先级与结合性

复习

　　表达式是程序里最常见的结构，也是语法分析里最讲究细节的地方。原因在于，1 + 2 * 3 这种写法，光看词序列，还不足以确定运算顺序。 这就要靠优先级和结合性来约定。

　　数学里我们都知道“先乘除、后加减”。1 + 2 * 3 应该算成 1 + (2 * 3) = 7，而不是 (1 + 2) * 3 = 9。

　　这种约定叫优先级（precedence）：不同运算符有不同的“级别”，级别高的先结合。

　　怎样让文法体现优先级？办法是分层。不要用一条规则把所有运算符都塞在一起，而是按优先级分成好几层：

表达式 → 项 加减
项     → 因子 乘除
因子   → 数字

　　这样，乘法在更低的“项”这一层就被结合好了，再往上才轮到加法。文法的层次，直接对应了运算的优先级。

　　当同一优先级的运算符连在一起时，还有第二个约定：结合性（associativity）。

　　看 1 - 2 - 3。它既可以算成 (1 - 2) - 3 = -4，也可以算成 1 - (2 - 3) = 2。数学约定是从左到右，也就是左结合，答案是 -4。

　　在文法里，结合性体现在递归展开的方向上：

　　这两种写法，会让语法树长成不同的形状——左结合长成往左倾斜，右结合长成往右倾斜。

　　说到底，优先级和结合性，都是在确定这棵语法树到底长什么样。树一定，运算顺序就定了：

　　所以，语法分析不只是“认出这是个表达式”，更要准确地还原它的层次。优先级分层、结合性定向，正是为了把这件事做对。而如果文法没把这些约定表达清楚，就会产生“一棵树还是另一棵树都行”的麻烦——这就是下一章的歧义。

思考题 1

　　怎样用文法分层来表达“乘法优先于加法”？

思考题 2

　　左结合和右结合，在语法树上分别表现为什么形状？

　　把加法放在“表达式”这一层、乘法放在更低的“项”这一层：表达式由项和加减构成，项由因子和乘除构成。乘法在更低层先结合，因而优先级更高，加法到上层才处理。

　　左结合（如 加减 → 加减 + 项）会让语法树向左倾斜，先结合左边的运算；右结合（如 幂 → 因子 ^ 幂）会让语法树向右倾斜，先结合右边的运算。

设计师 | 南国微雪