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

Question

我试图理解解析器组合器中的 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] 中。我不明白的是它如何跟踪每次运行之间的结果。应用组合是上下文无关的，不应该记住两者之间的状态。对吗？

非常感谢!

Answer 1

让我们分解一下；

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

基本上是指<​​/p>

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

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

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

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

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

• fmap非常简单:它需要一个函数 a -> b , 一个解析器 Parser s a并返回 Parser s b .这使我们能够在不实际运行解析器的情况下显式操作解析器的结果。
• <*>与 fmap 完全一样有点不同的是函数本身是解析的结果。在(主观上)最理智的实现中:
  • 运行返回函数的左侧解析器(消耗输入)
  • 运行返回参数的右侧解析器(在剩余输入上)
  • 将以上内容组合成一个解析器，该解析器返回应用于上述参数的函数

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

• 首先我们解析一些类型为a的对象使用解析器 p .
• 然后，在解析上下文中，我们应用函数 (:) :: 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在那之后没有这个属性。因此，我们强制它至少解析一件事(“解析一个然后解析任何数字”)。