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

Ivan Godard <ivan@ootbcomp.com>
Wed, 16 Jul 2014 16:39:09 -0400 (EDT)

          From comp.compilers

Related articles
LR(1) Parsing : Error Handling & Recovery seimarao@gmail.com (Seima Rao) (2014-07-10)
Re: LR(1) Parsing : Error Handling & Recovery ivan@ootbcomp.com (Ivan Godard) (2014-07-16)
Re: LR(1) Parsing : Error Handling & Recovery news@fx29.iad.highwinds-media.com (Eric) (2014-07-16)
Re: LR(1) Parsing : Error Handling & Recovery drikosev@otenet.gr (Evangelos Drikos) (2014-07-17)
Re: LR(1) Parsing : Error Handling & Recovery ivan@ootbcomp.com (Ivan Godard) (2014-07-17)
Re: LR(1) Parsing : Error Handling & Recovery ivan@ootbcomp.com (Ivan Godard) (2014-07-17)
Re: LR(1) Parsing : Error Handling & Recovery gneuner2@comcast.net (George Neuner) (2014-07-17)
Re: LR(1) Parsing : Error Handling & Recovery wclodius@earthlink.net (2014-07-18)
[24 later articles]
| List of all articles for this month |

From: Ivan Godard <ivan@ootbcomp.com>
Newsgroups: comp.compilers
Date: Wed, 16 Jul 2014 16:39:09 -0400 (EDT)
Organization: A noiseless patient Spider
References: 14-07-023
Keywords: parse, errors
Posted-Date: 16 Jul 2014 16:39:09 EDT

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.


Post a followup to this message

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