Re: LR(1) Parsing : Error Handling & Recovery

On 7/9/2014 5:00 PM, Seima Rao wrote:
> How far is impressive error handling & recovery possible by LR(1)
> parsers ?
>
> What would be good references for the subject?
>
> As an aside, do the famous compilers use LR(1) parsing ?


LR1 was an experiment. The way to get apt error messages out of
one is to add error production rules. Unfortunately that process
explodes the state space, resulting in generally poor quality compilers.


As a practical matter, natural languages are pretty much LL1 (German
verbs excepted) so people are reasonably familiar to quasi-linear
parsing. A recursive descent LL1 parser can be written in less time than
a LR1 grammar for the same language can be debugged, if it ever is. For
those that really really believe in parser-generators, high-quality
generators exist for LL1 too. Nearly all languages yield to LL1
techniques (the formal proofs that a language is not LL1 are
irrelevant), often by introducing a few union-productions into the
lexer; examples have been shown here, such as DOI=1 in Fortran.


The great advantage of a recursive-descent parser is that you can do
most semantic analysis on the fly while you are at it, and can emit apt
and copious error messages at the point where the source first goes off
the rails. You can even do a decent job of recovery: for example, an
unrecognized identifier can be used to search for an approximate match
in the current dictionary (also built on the fly) to fix a typo, thereby
avoiding the cascade of irrelevant diagnostics typical of YACC parsers.


FWIW, I recall hearing that GCC switched from LR1 (LALR?) to
recursive-descent a few years back. You couldn't pay me to work on a
YACC-based front end.

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