Re: Why LL(1) Parsers do not support left recursion?

Hans-Peter (Dodi) wrote:
> > My point is that table driven parsers are unreadable, due to the lost
> > relationship between the parser code and the implemented language or
> > grammar. Do there exist LR parsers or parser generators at all, which
> > preserve the relationship between the parser code and the grammar?


"Arthur J. O'Dwyer" <ajonospam@andrew.cmu.edu> writes:
> Again, you seem to confuse human-centered subjective terms like
> "preserve the relationship" with measurable terms. Obviously there is
> /some/ kind of special relationship between a yacc-generated parser
> and its target language --- something that makes it parse C and not
> Java or pig Latin. You're complaining that the relationship isn't
> close enough to the surface for humans to see --- but why is that
> important?
> After all, the point of table-driven parsers is that humans never
> /need/ to see the generated code. It "just works."


Arthur, if that were only true!!! When it is true, life is wonderful.
When it isn't true, because your parser generator has given you a
conflict message and one needs to understand why your grammar is
incorrect and what you should do about it, life is painful. In that
case, one really does need to be able to read the tables and
understand them. For many it seems, that task is akin to visiting the
dentist. For that reason alone, I don't think recursive descent will
ever die (and nor should it, at least not in the machine generated
version).


Note, this in fact gives me mixed feelings (because I've worked hard
to make Yacc++ accept a wide class of grammars, wider than traditional
LALR(1)). In general, the more powerful the parsing method, the more
difficult it is to fix problems when the parser is misbehaving. (I'm
reminded of a quote where Mr. Scott (of Star Trek) is standing with 4
ball-bearings in hand looking at an incapacitated starship with
trans-warp drive, saying roughly, "the more complicated the plumbing,
the easier it is to break".) My feeling is that when GLR parsers
break, they are harder to fix than simple LR ones, just as LR ones are
harder to fix than LL ones. Moreover, I'm more certain that it is
harder to "know" that a GLR parser is broken than an LR one, atleast
if by broken one means unanticipated ambiguity, because the whole
point of GLR parsing is to allow certain ambiguities, and I think that
it would be hard to prove that one has only allowed the specific
allowed ambiguities.


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