Re: Parsing ambiguities

"Arthur J. O'Dwyer" <ajonospam@xxxxxxxxxxxxxx> wrote in message
news:Pine.LNX.4.60-041.0606010031070.5237@xxxxxxxxxxxxxxxxxxxxxxxx

Recently I've been playing around with a "blocks world" AI of my
own construction --- think SHRDLU but far, far dumber --- and so it
occurs to me to ask the following idle question, which is probably
better suited to comp.ai, but since parsers are on-topic here...

Does anyone have any experience or advice for dealing with
sentences whose syntax is ambiguous but whose semantics resolve
the ambiguity? For example,

PLEASE PUT A RED BLOCK ON THE BLOCK IN THE BOX

could mean "Look on the [previously mentioned] block, find a red block
there, and put it in the box"; or it could mean "Look for a red block
and put it on the only block in the box."
The syntax is ambiguous, but by looking at the positions of the blocks,
we can deduce that one of the possible parses is nonsense, and therefore
use the other one.

I found a paper on "limited repair" of parse trees, where the idea
was to cut-and-paste prepositional phrases on a single parse tree until
things felt right, but that seems really icky. It seems to me that the
obvious way to deal with ambiguity is to generate all the (combinatorial
explosion) parse trees for the sentence in the first place.
Is there any (free and/or published) parser generator that can deal
with ambiguous grammars like this one by generating multiple parse trees?

Or am I not seeing some other way of dealing with the problem? SHRDLU
dealt with it expertly, but I haven't found out how, yet. (I don't even
know whether SHRDLU used "parse trees" as I understand them or not,
actually.)

Any advice appreciated.

A standard technique for this is to parse using a context-free parser,
producing all the parsing combinations, and then filter them post-parsing,
by checking each ambiguity and deleting trees that don't make semantic
sense.
An efficient method for doing this is GLR parsing, in which sub-trees
under ambiguity nodes are shared. Check out comp.compilers
for recent dicussion on GLR parsers. We use them to parse
real computer langauges, because ambiguities are a lot more common
than you'd expect (and C++ is ambiguity hell, but our GLR
parser handles this with aplomb).


--
Ira Baxter, CTO
www.semanticdesigns.com


.

Relevant Pages

  • Parsing ambiguities
    ... but since parsers are on-topic here... ... PLEASE PUT A RED BLOCK ON THE BLOCK IN THE BOX ... I found a paper on "limited repair" of parse trees, ... obvious way to deal with ambiguity is to generate all the (combinatorial ...
    (comp.lang.misc)
  • Re: Why LL(1) Parsers do not support left recursion?
    ... #>>> Only poorly designed programming languages are ambiguous. ... Because it is trivial to avoid this kind ambiguity, ... it's possible to create many different "parse trees" ...
    (comp.compilers)
  • Re: Parsing ambiguities
    ... elegant way to generate parsers that can deal with ambiguity. ... Error Correcting Parser Combinators: ... If yours is "the same" as Parsec (no way ... prepositional phrases just plain aren't in the grammar ...
    (comp.lang.misc)
  • 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: parsing a subtype_indication
    ... What I'd like to know is, when the parser has seen: ... build a number of abstract parse trees, then resolve each, using ... symbol table info, to a concrete interpretation, then ...
    (comp.lang.vhdl)