在Menhir/Ocamlyacc中为运算符指定动态优先级和优先顺序

Question

我正在尝试解析一种语言，其中运算符具有动态属性（优先级和结合性），使用类似于Ocamlyacc的Menhir解析器。在词法分析阶段，所有运算符都填充一个OP:string标记（因此"+"变成了(OP "+")等）。

运算符属性在解析时确定，并填充一个表格，将运算符及其属性关联起来。鉴于此表格，我如何指示Menhir根据该表格的数据动态更改解析运算符的规则优先级？

谢谢， CharlieP.

- CharlieP

Answer 1

很抱歉我会以"你做错了"的方式回答。我有三个反对意见，希望能有建设性的提出来，按照相关性递减的顺序：

1. Menhir并不适用于动态语法更新；如果您坚持在解析时更改语法，则应使用提供此功能的工具，例如GLR解析器Dypgen。Dypgen手册提到了可能以受限制的方式动态更新操作符优先级（似乎可以添加新操作符和相应的优先级，但不能更改现有的优先级），这可能与您的需求匹配或不匹配。请参阅Dypgen手册(PDF)第6.6节，第42页。

2. 动态更新CFG语法不是处理用户定义运算符优先级的最佳方法。Agda具有非常通用的用户定义混合运算符，他们的解决方案大致如下：使用CFG解析器解析静态已知的语法结构，但对可能使用复杂优先级和结合性的表达式，只需将其解析成标记列表即可。例如，let x = if foo then x + y * z else bar将解析为类似于Let(x, If(foo, Expr(x, +, y, *, z), bar)的东西。稍后的专业传递可以收集所需信息，将这些Expr节点后解析成其特定的结构。对于什么适用于解析器生成器的内容（已知静态丰富的CFG），请使用后处理传递来处理复杂的、不明确定义的动态内容。Agda的开发者在该主题上有一些文献资料，例如Parsing Mixfix Operators，Danielsson和Norell，2009年。

从设计的角度来看，我强烈建议将词法分析和语法分析分为几个不同的阶段，每个阶段都定义清晰，并且只使用前一个结构中收集到的信息，而不是试图动态地更改自己的行为。这样做会得到更简单、更稳健的结果。

在我看来，动态或用户定义的优先级和优先顺序有点邪恶。OCaml有一个不同的系统，其中操作符优先级是由它们的前几个字符（例如，@、@@和@+都是右结合的）确定的。对于选择中缀运算符的人来说可能有点受限制，但对于代码的读者来说，他们只需要学习一组语法规则，而不必动态适应任何新的代码片段，使他们的生活更加舒适。如果您想允许插入具有完全不同语法的野生、外部代码片段，引用机制（例如 camlp4 <:foo< ... >>）比调整操作符层级的关联性和优先级更加稳健，也更容易解析。

话虽如此，不同的项目有不同的需求，如果您坚持要在某些我不知道的应用程序中使用动态更改运算符优先级和关联性，我完全理解。只需记住这并不是唯一的方法，有时一致性和简单性比绝对灵活性更好。

- gasche