4 ms·

Roughly, context sensitive can be covered by monadic parsers, while applicative parsers are context free. LR(k) also corresponds to context free parsers. So, at

Roughly, context sensitive can be covered by monadic parsers, while applicative parsers are context free. LR(k) also corresponds to context free parsers. So, at least for monadic combinators they are more powerful. I also think they're fairly modular. The primitive parsers are fairly easy to write and once you have a small library (or use an existing one like Parsec) of them it is fairly easy to put them together (in haskell do notation helps too). The only other kind of parsers I have personal experience coding is recursive descent which I had more trouble trying to keep track of.

amelius 9y ago
Ok, but what about the efficiency of LR(k) parsers implemented using monads? Further, do monads warn the user when there is an ambiguity in the "grammar"?
- vorg 9y ago
  > monadic combinators are more powerful [than context free parsers] Monadic parsers can do context-sensitive things that context free parsers can't, but they can't have unordered options which context free parsers can. So really monadic parsers have different powers to context-free. > do monads warn the user when there is an ambiguity in the "grammar"? You don't have ambiguity in the grammar because monadic parsers only provide ordered options.
  - dozzie 9y ago
    > You don't have ambiguity in the grammar because monadic parsers only provide ordered options. Oh, but you do have ambiguity in the grammar, except that parser returns one of the possible parse trees deterministically and thus doesn't warn you that the input could be parsed differently. This leads to the false impression that your grammar is unambiguous.
    - marcosdumay 9y ago
      The parser implements an unambiguous grammar. But it may not be the grammar you were thinking it was. Specifically, it makes it impossible for you to even write down that ambiguous grammar you wanted.
- fusiongyro 9y ago
  > Further, do monads warn the user when there is an ambiguity in the "grammar"? I'm not aware of a parser combinator library that does this. The way you build parser combinators in Haskell doesn't exactly preclude it from being done but it wouldn't be totally trivial either. Googling for it didn't turn up much that wasn't a veiled reference to this paper: http://richard.myweb.cs.uwindsor.ca/PUBLICATIONS/PADL_08.pdf http://richard.myweb.cs.uwindsor.ca/PUBLICATIONS/PADL_08.pdf
- marcosdumay 9y ago
  If you mean big O efficiency, it doesn't make any difference if you are creating a monad, applicative, or an state machine. Complexity comes explicitly in the parser construction, so if you write a monadic parser using only LR(k) combinators, you will get an LR(k) parser. If you write some backtracking, you will get worse complexity.

amelius 9y ago

Ok, but what about the efficiency of LR(k) parsers implemented using monads? Further, do monads warn the user when there is an ambiguity in the "grammar"?

vorg 9y ago
> monadic combinators are more powerful [than context free parsers] Monadic parsers can do context-sensitive things that context free parsers can't, but they can't have unordered options which context free parsers can. So really monadic parsers have different powers to context-free. > do monads warn the user when there is an ambiguity in the "grammar"? You don't have ambiguity in the grammar because monadic parsers only provide ordered options.
- dozzie 9y ago
  > You don't have ambiguity in the grammar because monadic parsers only provide ordered options. Oh, but you do have ambiguity in the grammar, except that parser returns one of the possible parse trees deterministically and thus doesn't warn you that the input could be parsed differently. This leads to the false impression that your grammar is unambiguous.
  - marcosdumay 9y ago
    The parser implements an unambiguous grammar. But it may not be the grammar you were thinking it was. Specifically, it makes it impossible for you to even write down that ambiguous grammar you wanted.
fusiongyro 9y ago
> Further, do monads warn the user when there is an ambiguity in the "grammar"? I'm not aware of a parser combinator library that does this. The way you build parser combinators in Haskell doesn't exactly preclude it from being done but it wouldn't be totally trivial either. Googling for it didn't turn up much that wasn't a veiled reference to this paper: http://richard.myweb.cs.uwindsor.ca/PUBLICATIONS/PADL_08.pdf http://richard.myweb.cs.uwindsor.ca/PUBLICATIONS/PADL_08.pdf
marcosdumay 9y ago
If you mean big O efficiency, it doesn't make any difference if you are creating a monad, applicative, or an state machine. Complexity comes explicitly in the parser construction, so if you write a monadic parser using only LR(k) combinators, you will get an LR(k) parser. If you write some backtracking, you will get worse complexity.