应用性parsing与单体parsing有什么好处?

似乎有一个共识,你应该使用Parsec作为应用而不是monad。 应用性parsing与单体parsing有什么好处?

  • 样式
  • 性能
  • 抽象化

monadicparsing出来了吗?

monadic和applicativeparsing的主要区别在于如何处理顺序组合。 在应用parsing器的情况下,我们使用(<*>) ,而对于monad,我们使用(>>=)

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

一元方法更加灵活,因为它允许第二部分的语法依赖于第一部分的语法,但在实践中我们很less需要这种额外的灵活性。

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

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

通过使用parsing器,我们可以轻松回答这个问题。 (我在这里作弊了一点,假设我们在我们的候选parsing器“languages”中有一个对应于(<*>)(>>=)的数据构造函数。

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

然而,对于一个monadicparsing器,我们不知道第二部分的语法是不知道input的。

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

通过允许更多,我们能够推理得更less。 这与dynamic和静态types系统的select类似。

但是这是什么意思呢? 我们可以使用这些额外的静态知识呢? 那么,我们可以使用它来避免LL(1)parsing中的回溯,通过比较下一个字符与每个备选的first集合。 我们还可以通过检查两个替代scheme的first组是否重叠来静态确定这是否是模棱两可的。

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

但是,通常情况下,应用程序和单点parsing之间的select已经由您正在使用的parsing库的作者做出。 当像Parsec这样的库暴露这两个接口时,select使用哪一个纯粹是一种风格。 在某些情况下,应用程序代码比单向代码更容易阅读,有时反过来也是如此。

如果一个parsing器是纯粹的应用程序,可以分析其结构,并在运行之前对它进行“优化”。 如果一个parsing器是一元的,那么它基本上就是一个图灵完整的程序,对它进行几乎任何有趣的分析都相当于解决停止问题(即不可能)。

哦,是的,还有一个风格的差异…

我认为主要的原因是偏好应用分析器而不是单向分析器,这与在任何上下文中优先使用应用代码而不是单向代码的主要原因相同:function不够强大,应用程序使用更简单。

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

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

Parsec使用Applicative的好处只是风格。 Monad具有更强大的优势 – 您可以实现上下文相关的parsing器。

Doaitse Swierstra的UUparsing更有效率,如果只适用。

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

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

但是没有办法写

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

所以是的,这基本上是一个风格问题 我想如果你使用returnap ,那么使用pure<*>应该没有性能损失 因为Applicative是一个比Monad小得多的接口,所以这意味着<*>有时可以比ap更高的优化。 (但是,通过巧妙的GHC重写规则,无论如何,通常可以实现相同的优化。)

monadicparsing出来了吗?

由于Monad是应用程序的子集,因此我会得出结论,应用程序parsing是monadicparsing的一个子集。