无法理解解析器组合器中的 'pMany' 和 'pMany1'

Can not understand 'pMany' and 'pMany1' in the parser combinator

我正在尝试了解解析器组合器中的 pMany 和 pMany1 函数

newtype Parser s t = P([s] -> [(t, [s])])
pMany, pMany1 :: Parser s a → Parser s [a] 
pMany p =(:) <$> p <*> pMany p `opt` [] 
pMany1 p = (:) <$> p <*> pMany p

据我了解,pMany 运行 尽可能多地调用解析器并将最终结果收集在 [a] 中。我不明白的是它如何跟踪每个 运行 之间的结果。应用组合是上下文无关的,不应该记住两者之间的状态。对吗?

非常感谢!

让我们分解一下;

pMany p = (:) <$> p <*> pMany p `opt` [] 

基本就是

pMany p = (fmap (:) p <*> pMany p) `opt` [] 

这个表达式由两部分组成:

  • 解析fmap (:) p <*> pMany p
  • 如果以上失败,结果为空列表也没关系

这里的想法是尝试解析“一个元素并尝试解析更多”或者如果上一步没有成功则“不解析任何东西”。我假设第二部分是可以理解的,让我们关注第一部分。

我们在这里需要了解 fmap<*> 是如何工作的:

  • fmap 非常简单:它需要一个函数 a -> b、一个解析器 Parser s a 和 returns Parser s b。这允许我们显式地操作解析器的结果而实际上 运行 它。
  • <*>fmap 的工作原理完全相同,只是函数本身是解析的结果。在(主观上)最理智的实施中:
    • 运行returns一个函数
    • 的左侧解析器(消耗输入)
    • 运行returns参数
    • 的右侧解析器(在剩余输入上)
    • 将上述组合成一个解析器,returns 函数应用于提到的参数

那么在这个神秘的 fmap (:) p <*> pMany p 中发生了什么:

  • 首先我们使用解析器 p.
  • 解析一些 a 类型的对象
  • 然后,在解析上下文中,我们对其应用函数 (:) :: a -> [a] -> [a]。所以如果我们已经解析了,比方说,一个 int 2137,我们现在有 (:) 2137\rest -> 2137:rest 相同。此时我们有了 Parser s ([a] -> [a]).
  • 类型的解析器
  • 下一步是解析 <*> 运算符的右侧,它是对 pMany 的递归调用。我们可以将其理解为“使用相同的算法进行”。实际上,我们解析了其余的元素。这会产生(根据 pMany 的类型)Parser s [a].
  • 最后,我们将前一个结果应用到最后一个结果上,得到一个将左侧元素(用 p 解析)附加到后面的元素(用 pMany p 解析)的解析器。从 <*> 的类型我们可以推断出结果类型将是预期的 Parser s [a]

此代码在语义上等同于

pMany p = (do
    someElem <- p
    restElems <- pMany p
    return (someElem : restElems)
  ) `opt` []

pMany1 做同样的事情,但是如果它不能解析第一个元素就会失败。请注意,它在没有此 属性 的那个之后调用 pMany。结果我们强制它至少解析一件事(“解析一个然后解析任何数字”)。