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

Question

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

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

例如,考虑表达式

x *** y +++ z

在我们完成解析模块之前,我们不知道导入了哪些其他模块,因此操作符(和其他标识符)可能在范围内.我们当然不知道它们的优先级.但是解析器必须返回一些东西 ......但它应该返回

(x *** y) +++ z

或者它应该返回

x *** (y +++ z)

可怜的解析器无法知道.只有在搜索带入(+++)和(***)进入作用域的导入,从磁盘加载该文件并发现运算符优先级时,才能确定这一点.很明显,解析器本身不会完成所有I/O操作; 解析器只是将字符流转换为AST.

显然有人在某处想出了如何做到这一点.但是我无法解决这个问题......有什么提示吗？

Answer 1

在GHC trac上为解析器引用页面:

中缀运算符被解析为好像它们都是左关联的.重命名器使用固定声明来重新关联语法树.

Answer 2

AndrásKovács的答案说明了GHC的真正做法,但是有一些历史.

从Haskell 98到Haskell 2010标准实际上有一些假设的变化.在前者的BNF语法中,操作符固定性和解析以这样的方式交织在一起,理论上你可以在固定规则和表达式和缩进块结束时的规则之间进行一些非常奇怪的交互.(对于后两者,规则基本上是,"继续,直到你必须停止".)

特别是你可以重新定义一个本地运算符及其固定性,使得它的使用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的方式完成了它,并且始终拥有它们自己的理智.