应用性分析相对于monadic分析有什么好处？ [英] What are the benefits of applicative parsing over monadic parsing?

问题描述

似乎有一个共识，你应该使用Parsec作为应用而不是单子。

抽象

单分析是否解析出来？

解决方案

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

 （*）:: Parser（a  - > b） - >解析器a  - >解析器b 
（>> =）::解析器a  - > （a→Parser b）→>解析器b 
  

一元方法更灵活，因为它允许第二部分的语法依赖于我们很少需要这种额外的灵活性。

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

  empty :: Parser a  - > Bool 
 first :: Parser a  - >设置Char 
  

通过应用解析器，我们可以轻松回答这个问题。假设我们有一个对应于（<>）和（>> = ）



  empty（f * x）在我们的候选解析器languages中） ）=空f&&空x 
先（f *> x）|空的f =第一个f'union`首先x 
 |否则=首先f 
  

但是，对于monadic解析器，我们不知道第二个语法部分不知道输入。

 空（x>> = f）=空x&&空（f ???）
先（x>> = f）|首先空x =第一个x`union`（f ???）
 |否则=首先x 
  

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

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

另一个例如，它可用于错误恢复，如论文确定性，错误 - 修正Combinator Parsers by S. Doaitse Swierstra和Luc Duponcheel。

然而，通常情况下，应用程序和单点解析之间的选择已经由作者您正在使用的解析库。当像Parsec这样的库暴露这两个接口时，选择使用哪一个纯粹是一种风格。在某些情况下，应用程序代码比单代码代码更容易阅读，有时也是相反。

There seems to be a consensus that you should use Parsec as an applicative rather than a monad. What are the benefits of applicative parsing over monadic parsing?

• style
• performance
• abstraction

Is monadic parsing out?

解决方案

The main difference between monadic and applicative parsing is in how sequential composition is handled. In the case of an applicative parser, we use (<*>), whereas with a monad we use (>>=).

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

The monadic approach is more flexible, because it allows the grammar of the second part to depend on the result from the first one, but we rarely need this extra flexibility in practice.

You might think that having some extra flexibility can't hurt, but in reality it can. It prevents us from doing useful static analysis on a parser without running it. For example, let's say we want to know whether a parser can match the empty string or not, and what the possible first characters can be in a match. We want functions

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

With an applicative parser, we can easily answer this question. (I'm cheating a little here. Imagine we have a data constructors corresponding to (<*>) and (>>=) in our candidate parser "languages").

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

However, with a monadic parser we don't know what the grammar of the second part is without knowing the input.

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

By allowing more, we're able to reason less. This is similar to the choice between dynamic and static type systems.

But what is the point of this? What might we use this extra static knowledge for? Well, we can for example use it to avoid backtracking in LL(1) parsing by comparing the next character to the first set of each alternative. We can also determine statically whether this would be ambiguous by checking if the first sets of two alternatives overlap.

Another example is that it can be used for error recovery, as shown in the paper Deterministic, Error-Correcting Combinator Parsers by S. Doaitse Swierstra and Luc Duponcheel.

Usually, however, the choice between applicative and monadic parsing has already been made by the authors of the parsing library you're using. When a library such as Parsec exposes both interfaces, the choice of which one to use is purely a stylistic one. In some cases applicative code is easier to read than monadic code and sometimes it's the other way round.

这篇关于应用性分析相对于monadic分析有什么好处？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！