LL/LR error correction

johnm@po.EECS.Berkeley.EDU (John D. Mitchell) writes:
>... It is generally the case that LR generators are much harder to get good
>error recovery out of. LL generators tend to make this a good bit easier...


Warren Stevens <wgstevens@undergrad.math.uwaterloo.ca> writes:
> Well, my compiler prof went to great lengths to tell us this was hogwash.
> His argument: once a LL parser has choosen a path, it's doomed to go along
> that path, regardless of what it may find along the way. It would be
> possible to back up a few steps, but that's not easy.


The parser exception handling that I mentioned in a recent comp.compilers
article explains how it's possible to "unwind" the stack to trigger
error reporting and recovery where you want.


> On the other hand, in LR parsing, the parser has a choice of a number of
> rules that it can reduce, and so can make a better guess as to the type of
> error the programmer has written and the best strategy to fix it. Errors
> such as a missing 'if' in a if-then-else clause in Pascal are hard to fix
> with a LL parser, because you get so far along in the parsing before you
> realise what's happened, while in a LR parser, it's not nearly as hard,
> because you can pick the rule you think the programmer meant and use it
> instead of another, incorrect, rule.


I'm going to have to agree that a table-driven parser's run time state is
easier to modify in this respect--you can insert the 'if' and then restart
the parser in a different state. An RD parser has to modify the program
stack, which is not easy to do. On the other hand, you have to write code
by hand to examine the table-driven stack looking for a good way to
resynchronize anyway. Metaware's compilers do this I'm told.


No parsing technique is a "silver bullet". LR grammars are easier to write
than LL grammars, but LL is more flexible with respect to semantic actions
and can be more easily debugged. To gain parsing strength while maintaining
semantic flexibility, predicated-LL(k) parsers were invented. But, table
driven parsers (LL,LR) have some advantages over RD parsers and vice versa.
The argument goes on and on and on...


Jon Mauney jon@mauney.com writes:
> 2) LL(1) is not equivalent to recursive descent. LL parsers can
> (and should) be table-driven.


I must disagree; see below.


> Recursive descent takes the very
> simple predictions of upcoming context, and encodes it into
> the procedure call stack, which again requires code and/or
> auxiliary data to extract.


Parser exception handling makes this easier.


Table driven LL(1) is smaller and has decent potential for error recovery.
However, predicated-LL(1) is harder to implement using a table rather than
RD (not as nice either--you can't define local variables etc...). Even more
importantly, predicated-LL(k) for k>1 is not possible using standard
table-driven techniques for "homogeneous" automata because of exponential
space requirements. You need heterogeneous automata for that (i.e., where
each state can be totally different--almost as if you had a different
interpreter for each state).


If you're totally bored some Saturday, take a look at my thesis at
everest.ee.umn.edu in pub/pccts/parr.phd.thesis.ps.gz. I guarantee you'll
be sorry you did ;)


Regards,
Terence of the North
--

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