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。)
最佳答案
我不认为 parse-error(t)
规则意味着难以实现。是的,它确实需要解析器与词法分析器进行通信,但除此之外,它可能被设计为使用当时的主要解析技术相对容易实现:基于 LALR(1) 的生成解析器,对纠错,例如 GNU Bison,或者确实像 GHC 使用的 Happy。
具有讽刺意味的是,至少部分由于 Haskell 在启用解析器组合库方面的成功,旧技术不像以前那样占主导地位,至少在 Haskell 社区中是这样。
LALR(1)(或 LR(1))生成的解析器具有以下特性,非常适合 parse-error(t)
规则旨在解释:
开心有专
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 也可以在组合器中很好地工作。但是您仍然需要与词法分析器进行某种交流。
关于parsing - Haskell 编译器在实践中如何实现 parse-error(t) 规则?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32344635/