Parsing ambiguities


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.

-Arthur
.

Relevant Pages

  • Re: Parsing ambiguities
    ... sentences whose syntax is ambiguous but whose semantics resolve ... PLEASE PUT A RED BLOCK ON THE BLOCK IN THE BOX ... by checking each ambiguity and deleting trees that don't make semantic ... for recent dicussion on GLR parsers. ...
    (comp.lang.misc)
  • Re: Parsing ambiguities
    ... I found a paper on "limited repair" of parse trees, ... obvious way to deal with ambiguity is to generate all the (combinatorial ... A standard technique for this is to parse using a context-free parser, ... An efficient method for doing this is GLR parsing, ...
    (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)