Re: Parsing ambiguities


On Thu, 1 Jun 2006, Ira Baxter wrote:
"Arthur J. O'Dwyer" <ajonospam@xxxxxxxxxxxxxx> wrote...
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

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).

Aha! I didn't know Bison was capable of that. ("Read the friendly
manual," I suppose...) Having read it now, I think that perhaps all
I need to do is judiciously apply "%glr-parser" and "%merge", and
then in the parser-merging function figure out which parse was the
right one.
I don't quite see how the Bison input file would look, yet, but
I'll definitely keep looking at this. It seems to be the Right Way.

-Arthur
.