2

Is there a parser that can parse ambiguous grammars (ideally in Haskell)?

Parsec's paper (http://research.microsoft.com/en-us/um/people/daan/download/papers/parsec-paper.pdf) states the following:

"Ambiguous grammars have more than one parse tree for a sentence in the language. Only parser combinators that can return more than one value can handle ambiguous grammars. Such combinators use a list as their reply type."

But I haven't found any such parser combinators. Do they exist?

Rahul Manne
  • 1,229
  • 10
  • 20
  • 7
    Yes. Off the top of my head, the [`fullParses` function from the Earley package](https://hackage.haskell.org/package/Earley-0.11.0.1/docs/Text-Earley.html#v:fullParses) is an example of this. – Alexis King Dec 14 '16 at 22:40
  • 2
    Similar answer found here: http://stackoverflow.com/questions/35630746/can-we-define-a-non-context-free-grammar-with-antlr – mba12 Dec 14 '16 at 22:41
  • @mba12 MetaS seems to be exactly what I'm looking for, but I can't seem to find any such package. AlexisKing that answers my question, thanks! – Rahul Manne Dec 14 '16 at 22:50
  • @RahulManne Sorry, I don't know anything about MetaS. You could also write a parser in Antlr that uses custom code to handle ambiguities. That is likely more work than you are looking to do but is probably a reasonable solution. – mba12 Dec 14 '16 at 22:57
  • `ReadP` in the standard library will also do it, though it's potentially exponential in the depth of the parse multi-tree (earley is only cubic). – luqui Dec 15 '16 at 03:27
  • The [`uu-parsinglib`](https://hackage.haskell.org/package/uu-parsinglib) can also handle ambiguous grammers. See [their website](http://foswiki.cs.uu.nl/foswiki/HUT/ParserCombinators): "ambiguous grammars can be handled, provided one is prepared to indicate that a non-terminal is ambiguous". They have also a few ambiguous examples. – Renzeee Dec 15 '16 at 10:50
  • Happy(https://www.haskell.org/happy/doc/html/sec-glr.html) can deal with ambiguity. – Junyoung Clare Jang Dec 16 '16 at 13:19

0 Answers0