Re: Parsing ambiguities


On Thu, 1 Jun 2006, Robbert Haarman wrote:
On Thu, Jun 01, 2006 at 12:45:32AM -0400, Arthur J. O'Dwyer wrote:

Is there any (free and/or published) parser generator that can deal
with ambiguous grammars like this one by generating multiple parse trees?

There's a paper on parser combinators in Haskell that describes a very
elegant way to generate parsers that can deal with ambiguity. Indeed, it
generates (lazily, because it's Haskell) all possible parsings of the
input, discarding any that fail at higher levels. It would be
conceptually simple to build your interpreter on top of that.

Googling "Haskell parser combinator" turns up only Parsec, a parser
combinator library for Haskell that I hope wasn't what you were referring
to.
(Parsec has a <|> symbol that means the same as | in Yacc, but with
the added constraint that it won't ever do backtracking if it fails to
get an exact match. You need to add the keyword "try" in order to get
normal behavior. The documentation spends a long time explaining how
to match the C keyword "return" without barfing on "read" or "returns".
IMNSHO, this is extremely silly.)

This blog entry
http://chneukirchen.org/blog/archive/2005/10/the-rightyear-parsing-library.html
claims flatly that "you need to ensure you don't have left-recursion in
your grammar, because that borks parser combinators in general." Is
that true?

A little more searching got things like
D. S. Swierstra & P. Azero Alcocer,
"Fast, Error Correcting Parser Combinators: A Short Tutorial"
http://www.cs.uu.nl/groups/ST/Software/UU_Parsing/Sofsem99.pdf
which looks more relevant, if less prepackaged. Is this the sort of
thing you're talking about?

I've made an implementation of the same parser combinators in Scheme. I
can send it to you if you're interested.

(1) I'm currently working in C. (2) If I wanted to switch languages,
apparently Ruby and Haskell, among others, include Parsec-like things
in their standard distros. (3) If yours is "the same" as Parsec (no way
to do backtracking automatically), I don't see how I could use it
effectively, as explained above.
However, objection (3) cancels out objection (2): if Haskell and Ruby
only contain Parsec-like parsers, then switching to one of them wouldn't
help me any more than switching to Scheme!
So you could upload the code somewhere, or e-mail it to me, and I
might take a look. (Examples of usage is a must! :) More info on these
parser combinators and how they're applicable to ambiguity would be
really nice, though.

My current code is here:
http://www.contrib.andrew.cmu.edu/~ajo/disseminate/shrdlu/
It's definitely nothing special to look at, but hopefully it'll
give you some idea of the particular things I'm having trouble with.
(For example, prepositional phrases just plain aren't in the grammar
right now, because I don't know how to handle the "ON THE BLOCK IN THE
BOX" ambiguity.)

-Arthur
.

Relevant Pages

  • Re: BNF notation needed
    ... The parser uses a grammar that relies on the category associated with ... do not fit the natural categories required by the parser and its ... deal well with context sensitive grammars. ... In automatic parsers the ambiguity is normally not ...
    (comp.lang.fortran)
  • Re: Parsing fully context-free grammars
    ... This is one of the problems with GLR parsers. ... then you get a parser that is ambiguous also. ... This problem can be resolved at the grammar level and avoid the ... The problem is the ambiguity in the grammar, ...
    (comp.compilers)
  • Re: Is pyparsing really a recursive descent parser?
    ... The important part is what it recurses through... ... of that grammar meant. ... ambiguity doesn't have to do with recognizing the language. ... PyParsing is parser. ...
    (comp.lang.python)
  • Re: Is pyparsing really a recursive descent parser?
    ... There are an enormous variety of parsing tools, ... For instance, the Earley parser ... Okay, in some contexts, an ambiguous grammar may be considered ... over the other through the context of the parse results? ...
    (comp.lang.python)
  • Re: ANTLR Target for Ruby
    ... is to figure out where backtracking might be needed and do it efficiently ... a large overhead over using a hand-crafted parser. ... If you also provided a sweet metagrammar (I find your earlier Grammar ... The real work is in the "engine" that does parser ...
    (comp.lang.ruby)