应用解析比monadic解析有什么好处？

Question

似乎已经达成共识,你应该使用Parsec作为应用而不是monad.应用解析比monadic解析有什么好处？

monadic解析了吗？

Answer 1

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

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

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

您可能认为拥有一些额外的灵活性不会伤害,但实际上它可以.它阻止我们在不运行它的情况下对解析器进行有用的静态分析.例如,假设我们想知道解析器是否可以匹配空字符串,以及匹配中可能的第一个字符是什么.我们想要功能

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

但是,使用monadic解析器,我们不知道第二部分的语法是什么,而不知道输入.

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

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

但这有什么意义呢？我们可以使用这些额外的静态知识吗？那么,我们可以例如使用它通过下一个字符进行比较的,以避免在LL(1)解析回溯first集合中的每个可替换的.我们还可以通过检查first两个备选方案的集合是否重叠来静态地确定这是否是模糊的.

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

然而,通常应用性和一元分析之间的选择已经被你使用的解析库的作者提出.当像Parsec这样的库公开两个接口时,选择使用哪个接口纯粹是一种风格.在某些情况下,应用代码比monadic代码更容易阅读,有时候反过来也是如此.

@HeinrichApfelmus你不能这样回答`empty`.或者你*可以*,但它就像回答[http://en.wikipedia.org/wiki/Halting_problem]"让我们运行程序,看看它是否停止". (6认同)
等待!直到今天我才有同样的想法,当我想到`empty`测试也可以应用于monadic解析器.原因是我们可以通过在空字符串上应用解析器`x`来获得名为`???`的值.更一般地说,您可以将空字符串提供给解析器,看看会发生什么.同样,第一个字符集可以至少以函数形式获得`first :: Parser a - >(Char - > Bool)`.当然,将后者转换为"Set Char"会导致字符的枚举效率低下,这就是应用函子具有优势的地方. (5认同)
@hammar:如果我们在空x`中运行`let x = pure f**y**x该怎么办？如果`empty y`是'False`,那么计算就不会终止......只是指出,它不是那么简单. (3认同)

Answer 2

如果解析器纯粹是应用程序,则可以在运行之前分析其结构并"优化"它.如果解析器是monadic,它基本上是图灵完备程序,并且执行几乎任何有趣的分析都等同于解决暂停问题(即,不可能).

哦,是的,这也有风格差异......

@PiDelport它完全与图灵完整性有关.`>> =`接受左侧解析器的结果并将其传递给右侧的解析器,从而使得生成的解析器无法进行静态分析,因为现在解析器本身已完成.`<*>`和`<$>`不检查参数,所以虽然解析器本身的输出是图灵完成的,因为你可以把任何东西放在`<$>`的左边,解析方面本身就受限制了并且可以静态分析. (3认同)

Answer 3

我可以看到更喜欢应用解析器而不是monadic解析器的主要原因与在任何上下文中优选应用代码而不是monadic代码的主要原因相同:功能较弱,应用程序使用起来更简单.

这是一个更通用的工程格言的实例:使用最简单的工具来完成工作.当小车可以使用时,不要使用叉车.不要使用台锯切出优惠券.当代码IO纯粹时,不要编写代码.把事情简单化.

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

不,"使用最简单的工具"似乎是一个很好的经验法则,但实际上并非如此.例如,我们使用计算机来书写字母,但是与一把剪刀相比,计算机与纸张相似. (3认同)
你是对的.最好这样说,"正确的工具是最有效的工具,同时最简单的复杂工具." 我的描述中缺少的是关于效率的部分:您需要一种功能强大的工具,不仅可以完成工作,还可以使工作尽可能简单.但与此同时,你不希望一个有很多花边和口哨的工具不适用于手头的任务,因为这些工具很可能增加操作它的复杂性而没有任何好处. (3认同)