John Hughes 的确定性 LL(1) 使用 Arrow 和错误进行解析

Question

我想根据 John Hughes 的论文Generalizing Monads to Arrows编写一个解析器。在通读并尝试重新实现他的代码时，我意识到有些事情不太合理。在一节中，他根据 Swierstra 和 Duponchel 的论文Deterministic, error-correcting combinator parsers using Arrows展示了一个解析器实现。他描述的解析器类型是这样的：

data StaticParser ch = SP Bool [ch]
data DynamicParser ch a b = DP (a, [ch]) -> (b, [ch])
data Parser ch a b = P (StaticParser ch) (DynamicParser ch a b)

组合运算符看起来像这样：

(.) :: Parser ch b c -> Parser ch a b -> Parser ch a c
  P (SP e2 st2) (DP f2) . P (SP e1 st1) (DP f1) =
  P (SP (e1 && e2) (st1 `union` if e1 then st2 else []))
    (DP $ f2 . f1)

问题在于解析器的组合q . p“忘记了q”的起始符号。我想到的一种可能的解释是 Hughes 期望我们所有的DynamicParsers 都是完整的，这样符号解析器的类型签名将是symbol :: ch -> Parser ch a (Maybe ch)而不是 symbol :: ch -> Parser ch a ch。这仍然看起来很尴尬，因为我们必须复制信息，将起始符号信息放在StaticParser和 中DynamicParser。另一个问题是，几乎所有解析器都有可能抛出异常，这意味着我们将不得不在内部花费大量时间Maybe或Either创建本质上是“单子不构成问题”的内容。这可以通过重写DynamicParser自身来处理故障或作为Arrow 转换器来解决，但这与论文相差甚远。这些问题都没有在论文中得到解决，而且解析器被呈现为好像它显然有效，所以我觉得我必须遗漏一些基本的东西。如果有人能抓住我错过的东西，那将是非常有帮助的。

Answer 1

我认为 Swierstra 和 Duponcheel 描述的确定性解析器与传统解析器有点不同：它们根本不处理失败，只处理选择。

另请参阅invokeDetS&D 论文中的函数：

invokeDet :: Symbol s => DetPar s a -> Input s -> a
invokeDet (_, p) inp = case p inp [] of (a, _) -> a

这个函数明确地假设它总是能够找到有效的解析。

使用 Hughes 描述的箭头版本的解析器，您可以编写如下示例：

main = do
  let p = symbol 'a' >>> (symbol 'b' <+> symbol 'c')
  print $ invokeDet p "ab"
  print $ invokeDet p "ac"

这将打印预期的内容：

'b'
'c'

但是，如果您编写“失败”解析：

main = do
  let p = symbol 'a' >>> (symbol 'b' <+> symbol 'c')
  print $ invokeDet p "ad"

它仍然会打印：

'c'

为了使这种行为更加明智，Swierstra 和 Duponcheel 还引入了纠错功能。如果我们假设输入中的'c'错误字符d已被纠正为 a，则输出是预期的。c这需要一个额外的机制，该机制可能太复杂而无法包含在休斯的论文中。

我已在这里上传了用于获取这些结果的实现：https ://gist.github.com/noughtmare/eced4441332784cc8212e9c0adb68b35

有关相同风格的更实用解析器的更多信息（但不再是确定性的，也不再限于 LL(1)），我真的很喜欢Swierstra 的“组合器解析：简短教程” 。第 9.3 节的有趣摘录：

这里的一个微妙点是如何处理单子解析器的问题。正如我们在[13]中所描述的，静态分析与一元计算并不一致，因为在这种情况下，我们根据迄今为止生成的输入动态构建新的解析：静态分析的整体思想是它是静态的。这一观察结果促使 John Hughes 提出了处理此类情况的箭头 [7]。直到最近我们才意识到，尽管我们的论点总体上仍然成立，但它们并不适用于 LL(1) 分析的情况。如果我们想要计算可以被以下形式的解析器识别为第一个符号的符号p >>= q，那么如果左侧可以识别空字符串，那么我们只对右侧的起始符号感兴趣；好消息是，在这种情况下，我们静态地知道将作为见证人返回什么值，并且可以将该值传递给 q，并静态地分析此调用的结果。不幸的是，我们必须采取特殊的预防措施，以防左侧运算符在其中一个空推导中包含对 pErrors 的调用，因为从那时起，可以静态确定此替代方案的见证就不再正确了。

Swierstra 的完整解析器实现可以在包中找到uu-parsinglib，尽管我不知道其中实现了多少扩展。