适用性分析相对于monadic解析有什么好处？

Question

似乎有一种共识，你应该使用Parsec作为应用而不是单子。应用性分析相对于monadic分析有什么好处？

• 风格
• 性能
• 抽象

是一元解析出来？

Answer 1

monadic和applicative分析之间的主要区别在于如何处理顺序组合。在应用解析器的情况下，我们使用(<*>)，而对于monad，我们使用(>>=)。

(<*>) :: Parser (a -> b) -> Parser a -> Parser b 
(>>=) :: Parser a -> (a -> Parser b) -> Parser b 

的单子方法更为灵活，因为它允许第二部分的语法依赖于结果从第一个，但我们很少需要在实践中，这种额外的灵活性。

你可能会认为，有一些额外的灵活性，不能伤害，但在现实中就可以了。它阻止我们在分析器上执行有用的静态分析而不运行它。例如，假设我们想知道解析器是否可以匹配空字符串，以及匹配中可能的第一个字符是什么。我们想要的功能

empty :: Parser a -> Bool 
first :: Parser a -> Set Char 

通过应用解析器，我们可以轻松回答这个问题。 （我在这里作弊一点。试想一下，我们有相应(<*>)和(>>=)在我们的候选人分析器“语言”数据构造）。

empty (f <*> x) = empty f && empty x 
first (f <*> x) | empty f = first f `union` first x 
       | otherwise = first f 

然而，有一元解析器，我们不知道是什么，第二部分的语法是不知道的输入。

empty (x >>= f) = empty x && empty (f ???) 
first (x >>= f) | empty x = first x `union` first (f ???) 
       | otherwise = first x 

通过允许更多，我们能够推理得更少。这类似于动态和静态类型系统之间的选择。

但这个又是什么意义呢？我们可以使用这些额外的静态知识来做什么？那么，我们可以通过比较下一个字符与每个备选方案的first集来避免LL（1）解析中的回溯。我们还可以通过检查两个备选方案的first组是否重叠来静态确定这是否会不明确。

另一个例子是它可以用于错误恢复，如S.Doaitse Swierstra和Luc Duponcheel在论文Deterministic, Error-Correcting Combinator Parsers中所示。

但通常，应用性和一元分析之间的选择已经被你使用的解析库的作者提出。当像Parsec这样的库暴露这两个接口时，选择使用哪一个纯粹是一种风格。在某些情况下，应用程序代码比单向代码更易于阅读，有时反过来也是如此。

Answer 2

随着Parsec的使用Applicative的好处只是风格。 Monad的优势在于它更强大 - 您可以实现上下文相关的解析器。

如果仅适用，Doaitse Swierstra的UU解析更高效。

Answer 3

Monads严格地比应用程序更有特色的抽象。你可以写

instance (Monad m) => Applicative m where 
    pure = return 
    (<*>) = ap 

但是没有办法写

instance (Applicative a) => Monad a where 
    return = pure 
    (>>=) = ??? 

所以，是的，它本质上是风格的问题。我想如果你使用return和ap，那么应该有没有性能损失而不是使用pure和<*>。由于Applicative是一个比Monad小得多的接口，这意味着<*>有时可以比ap更高度优化。 （但是，通过巧妙的GHC重写规则，无论如何，通常都可以实现相同的优化。）

是否是monadic解析？

由于Monads是应用程序的一个子集，因此我会得出结论，应用程序解析是monadic解析的一个子集。

Answer 4

我认为主观原因应用解析器优于一元解析器的主要原因与在任何上下文中优先使用应用代码而不是一次性代码的主要原因相同：功能较弱，应用程序更易于使用。

这是一个更一般的工程格言的实例：使用最简单的工具完成工作。小推车可以使用时不要使用叉车。不要使用台锯切割优惠券。当它可能是纯粹的时候，不要在IO中编写代码。把事情简单化。

但有时候，你需要额外的力量Monad。这一点的确切迹象是，当您需要根据迄今为止计算的内容来更改计算过程时。在解析术语中，这意味着根据迄今为止解析的内容确定如何解析接下来的内容;换句话说，你可以用这种方式构造上下文敏感的语法。

Answer 5

如果解析器是纯粹的应用性，它可以分析它的结构和运行它之前的“优化”了。如果一个解析器是monadic，它基本上是一个图灵完整的程序，对它进行几乎任何有趣的分析都相当于解决暂停问题（即不可能）。

哦，是的，有一个风格相差太大......