使用用户定义的运算符优先级进行解析

Question

好的，所以这里有一个问题：鉴于 Haskell 允许您定义具有任意运算符优先级的新运算符...如何实际解析 Haskell 源代码？

在解析源代码之前，您无法知道设置了哪些运算符优先级。但是在知道正确的运算符优先级之前，您无法解析源代码。那么...嗯，怎么样？

例如，考虑表达式

x *** y +++ z

在我们完成对模块的解析之前，我们不知道导入了哪些其他模块，因此不知道范围内可能有哪些运算符（和其他标识符）。我们当然还不知道它们的优先顺序。但是解析器必须 return 一些东西 ... 但是它应该 return

(x *** y) +++ z

还是应该return

x *** (y +++ z)

可怜的解析器无从知晓。这只能在您找到将 (+++) 和 (***) 带入作用域的导入、从磁盘加载该文件并发现运算符优先级后才能确定。显然解析器本身不会做所有这些 I/O；解析器只是将字符流转换为 AST。

很明显，某个地方的某个人已经想出了如何做到这一点。但我无法解决...有什么提示吗？

Answer 1

为解析器引用 page on GHC trac：

Infix operators are parsed as if they were all left-associative. The renamer uses the fixity declarations to re-associate the syntax tree.

Answer 2

András Kovács 的回答说明了 GHC 中真正做了什么，但这有一些历史。

从 Haskell 98 到 Haskell 2010 标准实际上有一些假设性的变化。在前者的 BNF 语法中，运算符固定性和解析以这样一种方式交织在一起，理论上你可以在固定性规则与 when 表达式和缩进块的规则之间有一些非常奇怪的交互结尾。（对于后两者，规则本质上是 "keep on going until you have to stop"。）

特别是您可以重新定义一个本地运算符及其固定性，以便它的使用完全属于重新定义的内部 where 块......当它不属于时。所以你得到了一个解析器悖论。我找不到任何旧示例，但这可能是一个：

let (+) = (Prelude.+)
    infix 9 + -- make the inner + high precedence and non-associative
in 2 + 3 + 4
--       ^ this + cannot parse here as the inner operator, which means
--         the let ... in ... expression should end automatically first,
--         but then it's the standard +, and its fixity says it should parse
--         as part of the inner expression...

在 Haskell 2010 年，他们正式更改了操作符固定性，以便在正确解析后的单独阶段确定。

那么为什么这是一个假设的变化？因为所有的编译器编写者都已经按照 Haskell 2010 年的方式做到了，而且为了他们自己的理智，他们总是这样做。

Answer 3

总结目前的评论，看来可能性是这样的：

Return 一个解析树，其中任何中缀运算符都保留为某种 "list" 结构，然后在知道优先级后重新排列。
假装你知道运算符的优先级，然后在事后重新排列解析树。
首先执行仅读取导入和固定声明的解析，加载导入，然后使用已知优先级执行完整解析。

使用用户定义的运算符优先级进行解析

Parsing with user-defined operator precedence

syntax

parsing

haskell