使用链接比较运算符评估二叉表达式树

Question

我正在构建一个二进制表达式树（用于玩具脚本语言），到目前为止我的算术运算工作正常（即 4 * (5 + 6)）；现在我想添加对比较运算符的支持。使用像 0 < 1 这样的简单二进制比较很容易做到这一点，但是当我将它们链接在一起时我遇到了问题。例如，这个表达式：

0 < 1 < 2

当前生成以下二叉表达式树：

我正在使用递归将树向下遍历到叶节点，然后 return 返回值，因此 0 < 1 首先得到处理，（正确地）return 是真的。问题是下一级应该比较 True < 2，而应该比较 True && (1 < 2).

解决此问题的最佳方法是什么？我在想我可能最终不得不以不同的方式建造我的树。即

       &&
      /  \
     /    \
    <      <
   / \    / \
  0   1  1   2

但我希望有一个更 elegant/slightly-less-complicated-to-implement-in-my-bison-parser 的解决方案。

Answer 1

本质上，一系列链式比较是单个运算符，而不是一系列二元运算符。将 a < b < c 脱糖为 (a < b) && (b < c) 是不精确的，因为它计算了 b 两次。因此，如果您的 AST 允许，您可能只是将它脱糖为 n 元运算符。

如果你有可区分的联合类型，你也可以让它与一系列二元运算符一起工作。在这种情况下，一个非常简单的可区分联合就足够了。

设 T 为值为 false 或任何整数的类型。（这里，false 与任何整数不同，因此它与 0 不同。）

现在，我们定义<如下：

integer a < integer b ==> T
  if a is less than b, then b; otherwise false

T a < integer b ==> T
  if a is false, then false; otherwise a < b (as above)

任何使用链式比较的中间结果，都需要将T结果转换为布尔值；我们这样做的方式很明显：false 映射到布尔值 false，任何整数都映射到布尔值 true。

隐式转换为布尔值的结果是

a < b == c < d      # Chained comparison

与

不一样

(a < b) == (c < d)  # Comparison of two booleans

例如，这基本上是 Python 的语义。以上可以用任何可订购的类型替换整数。

为了实现链式比较，您需要在语法中正确管理括号内的比较。仅删除括号的通常的简单 AST 构造将不起作用。

使用链接比较运算符评估二叉表达式树

Evaluating a binary expression tree with chaining comparison operators

compiler-construction

tree

bison

data-structures