Re: Parsing Expression Grammar

In George's reply, I think we converged on agreement.


> However, given the original grammar above,
> I would argue that the likelihood that the action creates circularity
> is very small.
...
> Of course the tool must be conservative and issue a warning because it
> cannot know the meaning of the action.


Yes, the problem discussed is exceedingly rare. I'm mostly aware of
it, because, as a parser generator author, I see the worst cases. As
in "why did your tool complain when I did this reasonable thing?" and
(at the same time but from a different user) "why didn't your tool
complain as I shot myself in the foot?" The problem is that there are
places where the theory (especially as it meets practice) is really
opaque and one can easily write something that looks obvious, but
doesn't do what you want for reasons that aren't obvious at all.
Fortunately, such cases are generally rare as George mentioned. The
problem is as a parser generator writer, one has to balance those
concerns. Execpt in the simplest cases, one's tool is likely to
generate both false positives and false negatives--places where
problems are indicated where there are none and places where it fails
to indicate a problem which is there.


And, when George started this conversation off with a line about
context sensitive grammars, my oh-this-is-really-difficult red-lights
went off. With a little cleverness one can parse some very tricky
cases. However, when one makes a mistake in such specifications, the
tool isn't going to help you much. A tool that is too restrictive
isn't going to let you write what you need to solve the problem. A
tool that isn't restictive enough is going to let you write something
that won't work reliably. In the worst case, the tool lets you write
something that looks like it will work (and does so for some trivial
cases), but then falls down when you are using it on real live data,
perhaps after it has become mission critical, because it worked for a
while.


To bring this back around to "parsing expression grammars", that is
one of my concerns with them. The ordering of alternatives in peg's
make it real easy to write appliications that do just that, look like
they are going to work, but don't. What we don't have data on, is how
much this is a problem in "real life". Perhaps, authors don't make
the kind of mistakes that would cause peg's to be unreliable.


What I do know is that if one writes an LL(1) grammar (and not a
predicated one), then one is safe. One can use any of the major
parsing technologies and either get something that works from that
grammar or get out an error message saying there is a mistake. Well,
a non-LL tool won't tell you if you've wandered outside the safe LL
subset, so maybe you need to check your grammar against an LL tool to
be certain, but even if not you're generally in pretty nice territory.


In any case, thanks to George for the wonderful exchange. I think in
trying to explain what I meant, I made even my own understanding
better.


-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

Return to the comp.compilers page.
Search the comp.compilers archives again.