parsing - Haskell 编译器在实践中如何实现 parse-error(t) 规则？

Question

Haskell 报告在布局规则中包含一个有点臭名昭著的条款，称为“parse-error(t)”。这条规则的目的是避免强制程序员在单行中写大括号let。表达式和类似的情况。相关语句是:

The side condition parse-error(t) is to be interpreted as follows: if the tokens generated so far by L together with the next token t represent an invalid prefix of the Haskell grammar, and the tokens generated so far by L followed by the token “}” represent a valid prefix of the Haskell grammar, then parse-error(t) is true.

这会创建一个不寻常的依赖关系，其中词法分析器必须为解析器生成标记，并通过插入额外的标记供解析器使用来响应解析器中产生的错误。这与您在任何其他语言定义中发现的几乎所有内容都不同，并且如果它被 100% 逐字解释，那么实现会严重复杂化。

不出所料，据我所知，没有任何 Haskell 编译器实现了所写的整个规则。例如， GHC fails to parse the following expression ，根据报告是合法的:

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

还有很多其他类似的奇怪案例。 This post列出了一些特别困难的例子。其中一些 GHC 可以正常工作，但它也(从 7.10.1 开始)在这个上失败:

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

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

真实世界的 Haskell 编译器(尤其包括 GHC)如何在词法分析过程中逼近 parse-error(t) 规则？ 我很好奇，因为我正在尝试实现一个简单的 Haskell 编译器，而这条规则真的让我很困惑。 (另见 this related question。)

Answer 1

我不认为 parse-error(t)规则意味着难以实现。是的，它确实需要解析器与词法分析器进行通信，但除此之外，它可能被设计为使用当时的主要解析技术相对容易实现:基于 LALR(1) 的生成解析器，对纠错，例如 GNU Bison，或者确实像 GHC 使用的 Happy。
具有讽刺意味的是，至少部分由于 Haskell 在启用解析器组合库方面的成功，旧技术不像以前那样占主导地位，至少在 Haskell 社区中是这样。
LALR(1)(或 LR(1))生成的解析器具有以下特性，非常适合 parse-error(t)规则旨在解释:

它从不回头。

它的表驱动决策意味着它总是“知道”给定 token 在当前位置是否合法，如果是，如何处理它。

开心有专 error当前词法标记不合法时可用于实现 Action 的标记。鉴于此， most relevant definition在 GHC 的快乐语法中是

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

vccurly ("virtual close curly") 是词法分析器在自行选择关闭布局级别时发送的标记。 popContext是 an action defined in the lexer source从布局堆栈中删除布局级别。 (注意顺便说一句，在这个实现中， error 的情况不需要词法分析器发送回 vccurly token )。
使用它，所有 GHC 解析器规则必须使用 close作为他们结束缩进 block 的非终结符，用 vocurly 打开.假设其余的语法是正确的，这也正确地实现了规则。
或者至少，这是理论。事实证明，这有时会因为 Haskell/GHC 的其他功能不适合 LALR(1) 语法而中断。
在上面的两个示例中，第一个在 Haskell 2010 中进行了更改(因为人们意识到它太难解析了)，所以 GHC 在那里是正确的。但是第二个( e = case 1 of 1 -> 1 :: Int + 1 )发生是因为 different design decision GHC 使:

Making a parser parse precisely the right language is hard. So GHC's parser follows the following principle:

• We often parse "over-generously", and filter out the bad cases later.

GHC 有足够的扩展名 Int + 1可以解析为启用了足够多的类型。此外，必须编写一个 LALR(1) 解析器来直接处理启用/禁用扩展的每种组合将非常尴尬(甚至不确定是否可能)。所以它只是首先解析最通用的语言，然后在检查结果所需的扩展是否启用时失败。但是到那时解析已经完成，触发 parse-error 为时已晚规则。 (或者我假设。)
最后，我应该说，我认为处理 parse-error(t) 没有什么不可能的。即使您没有使用 (LA)LR(1) 解析器，也要遵守规则。我怀疑像 GHC 的 close token 也可以在组合器中很好地工作。但是您仍然需要与词法分析器进行某种交流。