如何在 Jison（或 Bison）中进行链式比较

Question

我正在开发一个用 Jison 制作的表达式解析器，它支持算术、比较等基本功能。我想允许像 1 < a < 10 和 x == y != z 这样的链式比较。我已经实现了比较多个值所需的逻辑，但我在语法上苦苦挣扎——Jison 一直将比较分组，如 (1 < a) < 10 或 x == (y != z)，我无法让它识别整个事物作为一个关系。

我的大致语法是这样的：

expressions = e EOF

e = Number
  | e + e
  | e - e
  | Relation  %prec '=='
  | ...

Relation = e RelationalOperator Relation  %prec 'CHAINED'
  | e RelationalOperator Relation         %prec 'NONCHAINED'

RelationalOperator = '==' | '!=' | ...

（抱歉，我不知道实际的 Bison 语法，我使用 JSON。Here's the entire source。）

运算符优先级大致为：NONCHAINED、==、CHAINED、+和-.

我在 e → Relation 上设置了一个动作，所以我需要那个关系来匹配整个链式比较，而不仅仅是它的一部分。我尝试了很多方法，包括调整优先级并将右递归 e RelationalOperator Relation 更改为左递归 Relation RelationalOperator e，但到目前为止没有任何效果。解析器要么只匹配可能的最小关系，要么警告我语法不明确。

如果您决定试用该程序，cloning it 和运行这些命令将帮助您入门：

git checkout develop
yarn
yarn test

Answer 1

这个问题基本上有两个相对简单的解决方案：

使用级联语法而不是优先声明。

这使得为链式比较编写语法变得相对容易，并且不会真正使二元运算符或紧绑定一元运算符的语法复杂化。

您会发现级联语法的示例随处可见，包括大多数编程语言。在这个 grammar for C expressions 中可以看到一个相当完整的例子（只看 constant_expression: 之前的语法）。

级联语法的优点之一是它们允许您将相同优先级的运算符分组到一个非终结符中，就像您尝试使用比较运算符以及链接的 C 语法使用赋值运算符一样。这不适用于优先声明，因为优先无法“看穿”单元制作；实际标记必须是具有声明优先级的规则的明显部分。

还有一个好处是，如果你对链式算子有特定的解析需求，你可以根据链式算子的规则来编写；你不必担心它会干扰其余的语法。

但是，级联语法并不能真正正确地处理一元运算符，除非一元运算符都位于优先级层次结构的顶部。这可以在 Python 中看到，它使用级联语法并且有几个优先级较低的一元运算符，例如 not 运算符，导致以下奇怪之处：
```
>>> if False == not True: print("All is well")
  File "<stdin>", line 1
    if False == not True: print("All is well")
                ^
SyntaxError: invalid syntax
```
这是语法错误，因为 == 的优先级高于 not。级联语法只允许表达式作为优先级低于表达式中任何运算符的运算符的操作数出现，这意味着表达式 not True 不能是 == 的操作数。（优先顺序允许 not a == b 被分组为 not (a == b)。）这个禁令可以说是荒谬的，因为除了 False == (not True) 之外没有其他可能的 False == not True 解释，并且优先顺序禁止唯一可能的解释这一事实使唯一可能的解释成为语法错误。优先级声明不会发生这种情况，因为优先级声明仅在 如果存在不止一种可能的解析 （即，如果确实存在歧义）时才使用。

您的语法将 not 置于优先级层次结构的顶部，尽管它实际上应该 与一元减号共享 该级别而不是在一元减号之上 [注 1 ].所以这不是使用级联语法的障碍。但是，我看到您还想实现一个 if … then … else 运算符，它在语法上是一个低优先级前缀运算符。因此，如果您希望 4 + if x then 0 else 1 在 x 为 false（而不是语法错误）时具有值 5，则级联语法会有问题。你可能不关心这个，如果你不关心，那可能就是要走的路。
坚持优先声明并将链式比较作为语义操作中的异常处理。

这将允许最简单的语法，但会使您的操作稍微复杂一些。要实现它，您需要将比较运算符实现为左关联，然后您需要能够在语义操作中区分比较（这是表达式和比较运算符的列表）来自任何其他表达式（它是一个字符串）。比较运算符的语义操作需要扩展或创建列表，具体取决于左侧操作数是列表还是字符串。任何其他运算符（包括括号分组）和比较中右侧操作数的语义操作需要检查它是否已收到列表，如果是，则将其编译成字符串。

无论您选择这两个选项中的哪一个，您都可能想要修复现有语法中的各种优先级错误，其中一些已经存在于您的上游源代码中（例如一元减号 / not上面提到的混淆）。其中包括：

求幂被配置为左结合运算符，而它几乎被普遍认为是右结合运算符。许多语言也使它的优先级高于一元减号，因为 -a<sup>2</sup> 总是被解读为 [=27 的负数=] 的平方而不是负 a 的平方（这只是 a 的平方）。

我想您将放弃三元运算符 ?:，转而使用 if … then … else 运算符。但是如果你在语法中留下 ?:，你应该使它成为右结合的，因为它在除 PHP 之外的所有语言中都是如此。（而PHP中的关联性通常被认为是设计错误。参见this summary。）

not in运算符实际上是两个token，not和in，not有很高的优先级。这就是你的语法解析它的方式，结果 4 + 3 in (7, 8) 的计算结果为真（因为它被分组为 (4 + 3) in (7, 8)），而 4 + 3 not in (7, 8) 的计算结果相当令人惊讶地为 5，一直分组为 4 + (3 not in (7, 8)).

备注

如果您使用级联优先语法，您会发现只有 - not 0 和 not - 0 中的一个是可解析的。当然，两者都可能是类型违规，但这不是语法应该关注的问题。

如何在 Jison（或 Bison）中进行链式比较

How to make a chained comparison in Jison (or Bison)

javascript

bison

context-free-grammar

jison

备注