歧义文法

复习

　　前面说 1 - 2 - 3 必须约定结合性。如果不约定，会发生什么？答案是：文法变成歧义的（ambiguous）。

　　歧义文法，指的是这样一类文法：存在某个输入串，它可以被推导出不止一棵语法树。

　　回到 1 - 2 - 3。如果文法写成：

表达式 → 表达式 - 表达式
表达式 → 数字

　　那么 1 - 2 - 3 既可以被推成 (1 - 2) - 3 的树，也可以被推成 1 - (2 - 3) 的树。两棵都“合法”，但含义不同、结果也不同。

　　对编译器来说，歧义是件麻烦事，因为它不知道该听哪一棵树。

　　语法树决定了语义：(1-2)-3 得 -4，1-(2-3) 得 2，完完全全是两个程序。如果编译器“随便选一棵”，那么同一段代码在不同编译器上可能算出不同结果，这显然不能接受。一个合格的文法，不该让人和机器都无所适从。

　　顺带一提，还有个有名的歧义例子叫“悬空 else”：if A if B S1 else S2 里，那个 else 到底配哪个 if？不同配法会产生不同的语法树。

　　消除歧义，通常有两种思路：

　　前面讲优先级与结合性，本质上就是在消除表达式的歧义。可见这两个话题是紧密相连的。

　　一句话总结：好的文法，应当让每个合法输入都只有唯一一棵语法树。 这也是设计程序语言时，必须认真对待的一环。

思考题 1

　　为什么歧义文法对编译器是危险的？

思考题 2

　　消除歧义，常见有哪些办法？

　　因为歧义意味着同一段代码可以对应多棵语法树，而不同语法树往往语义不同、结果不同。编译器若无法唯一确定该用哪棵树，就可能产生与预期不符甚至跨平台不一致的行为。

　　常见办法有两种：一是改写文法，把它变换成无歧义的等价形式，例如给表达式分层来体现优先级和结合性；二是补充文法之外的约定（如优先级、结合性规则），让分析器按约定做出唯一选择。

设计师 | 南国微雪