Re: Is there an error correcting parser generator out there?

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


Your prof is showing his/her prejudices a bit here. It is quite easy if
the parser uses an expicit prediction stack instead of procedural
recursive descent. You just patch the stack. Knowing where the parser
thinks it is going is a big help in doing this - that's why you can do
good error recovery in LL parsers.


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


This is, in my experience, the hardest problem for error recovery in ANY
sort of parser (try when you misspell 'procedure' in a pascal program). In
the 'if-then-else' case, an LL1 generator I wrote a couple of years ago
generated one error message and recovered correctly as soon as it hit the
'then'.


I love parser wars, too, but let's recognise that these opinions are just a
bit religious.


Andrew Dunstan
--

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