Haskell编译器如何在实践中实现解析错误(t)规则？

Question

Haskell报告在布局规则中包含了一个名为" parse-error(t) "的臭名昭着的子句.此规则的目的是避免强制程序员在单行let表达式和类似情况下编写大括号.相关的句子是:

副条件解析错误(t)将被解释如下:如果到目前为止L生成的令牌与下一个令牌t一起表示Haskell语法的无效前缀,并且到目前为止生成的令牌由L后跟token"}"表示Haskell语法的有效前缀,然后parse-error(t)为true.

这会产生一种不寻常的依赖关系,其中词法分析器必然都会为解析器生成令牌,并通过插入额外的令牌来解析解析器中产生的错误.这与任何其他语言定义中的任何内容都不同,如果100%字面解释,则会严重地使实现复杂化.

不出所料,我所知道的Haskell编译器没有像编写的那样实现整个规则.例如,GHC无法解析以下表达式,根据报告,这是合法的:

let x = 42 in x == 42 == True

还有各种其他类似的奇怪案例.这篇文章列出了一些特别困难的例子.其中一些GHC正常工作,但它(从7.10.1开始)也失败了:

e = case 1 of 1 -> 1 :: Int + 1

此外,似乎GHC有一个未记录的语言扩展名称,它用词法AlternativeLayoutRule分析器中的一堆令牌上下文替换parse-error(t)子句,在大多数情况下给出类似的结果; 但是,这不是默认行为.

现实世界的Haskell编译器(特别是GHC)在lexing期间做什么来近似解析错误(t)规则？我很好奇,因为我正在尝试实现一个简单的Haskell编译器,这个规则真的让我感到沮丧.(另见相关问题.)

Answer 1

我不认为该parse-error(t)规则很难执行。是的，它确实需要解析器与词法分析器进行通信，但除此之外，它可能被设计为相对容易使用当时的主流解析技术来实现：基于 LALR(1) 的生成解析器，对以下内容有一些小的支持纠错，就像 GNU Bison，或者确实像 GHC 使用的 Happy。

具有讽刺意味的是，至少部分由于 Haskell 在启用解析器组合器库方面的成功，旧技术并不像以前那样占主导地位，至少在 Haskell 社区中是这样。

LALR(1)（或 LR(1)）生成的解析器具有以下功能，非常适合规则的解释parse-error(t)方式：

• 它永远不会后退。
• 它的表驱动决策意味着它总是“知道”给定的代币在当前位置是否合法，如果是，则如何处理它。

Happy 有一个特殊的error标记，可以用来在当前词法标记不合法时实现操作。鉴于此，GHC Happy 语法中最相关的定义是

close :: { () } 
        : vccurly               { () } -- context popped in lexer. 
        | error                 {% popContext } 

vccurly(“virtual close curly”) 是词法分析器在自行选择关闭布局级别时发送的标记。popContext是词法分析器源中定义的操作，用于从布局堆栈中删除布局级别。（顺便说一句，请注意，在此实现中，error案例不需要词法分析器发送vccurly回令牌）。

使用此功能，所有 GHC 解析器规则必须使用close非终结符来结束以 . 打开的缩进块vocurly。假设语法的其余部分是正确的，这也正确地实现了规则。

或者至少，理论是这样的。事实证明，这有时会因为 Haskell/GHC 的其他功能不太适合 LALR(1) 语法而中断。

在上面的两个示例中，第一个在 Haskell 2010 中进行了更改（因为人们意识到解析起来太尴尬），所以 GHC 在那里是正确的。但第二个 ( e = case 1 of 1 -> 1 :: Int + 1) 的发生是因为GHC 做出了不同的设计决策：

让解析器精确地解析正确的语言是很困难的。所以GHC的解析器遵循以下原则：

• 我们经常会“过度慷慨”地解析，然后过滤掉不好的情况。

GHC 有足够的扩展，Int + 1 可以解析为启用了足够多扩展的类型。另外，必须编写一个 LALR(1) 解析器来直接处理启用/禁用扩展的每种组合将非常尴尬（不确定是否可能）。因此，它只是首先解析最通用的语言，然后在检查结果所需的扩展是否已启用时失败。但到那时解析已经完成，触发规则为时已晚parse-error。（或者我是这么假设的。）

最后，我应该说，即使您不使用 (LA)LR(1) 解析器，我也不认为处理该规则有什么不可能。parse-error(t)我怀疑像 GHC 的close代币这样的东西也可以在组合器中很好地工作。但您仍然需要与词法分析器进行某种通信。