Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1315

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

Show all headers | View raw

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 ?

I can take a crack at answering some of this. I built my own LALR1
parse generator and parser about 20 years ago.  The parser had both
Error Repair and Error Handler.  I can describe how I implemented
these.

There are two mechanisms:

Error Repair tries to fix the input token stream when a syntax error
is detected. This was popular back when compiling was much more
expensive and done as submitted batch jobs.  The desire was to not
abort a compile job or toss away source just because of some syntax
error.  Error Repair attempts to keep as much of the original input
stream and find as many errors as possible in one pass.

The basic repair mechanism tries to either Keep, Insert or Delete
input stream tokens according to their cost. The "best" repair is the
one with the minimum cost.

Error Handling is a simpler mechanism and essentially works by tossing
away tokens until a recognized state is reached.  It can be used when
Error Repair is not available or has failed.  Error Handling is
conceptually like an exception handler (this is just conceptual, it
has nothing to do with C++ or operating system exceptions).

The LALR1 parser pushes items on the stack.  If it reaches a state
where the next token cannot be consumed because there is no next state
for it (a syntax error), then the parser does the equivalent of
"throwing an exception".  It scans backwards through the parse stack
checking the state for a special terminal called ERROR. If it finds
one it rolls back the parse stack to that point, pushes the ERROR
terminal on the stack and calls the associated reduction routine as
though a match on the input terminal ERROR had been found.  That
reduction action routine is expected to do clean up.

For example

   statement
   :  assignment_statement
   |  if_statement
   |  loop_statement
   |  ERROR { action_error(); };

Say we are parsing "foo = a * b / / c;".
At the second '/' token a syntax error is detected.
The parse stack is scanned backwards until we find a state
that can shift the ERROR token. That matches a production
for "assignment" so the action_error() routine is called
which reads input token stream until it consumes a ';'.
(I'm glossing over grotty details like who cleans up
the parse stack and how is memory recovered.)
Finally the assignment production is pushed on the
parse stack and we continue as if nothing had gone wrong.

Anyway, that is the basic idea.
I found Error Repair more interesting but is much more difficult.
Most parsers seem to use Error Handling because it is much easier
to implement and recompiling is cheap.

Eric

Back to comp.compilers | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

LR(1) Parsing : Error Handling & Recovery Seima Rao <seimarao@gmail.com> - 2014-07-10 05:30 +0530
  Re: LR(1) Parsing : Error Handling & Recovery Ivan Godard <ivan@ootbcomp.com> - 2014-07-16 16:39 -0400
    Re: LR(1) Parsing : Error Handling & Recovery Evangelos Drikos <drikosev@otenet.gr> - 2014-07-17 20:15 +0300
      Re: LR(1) Parsing : Error Handling & Recovery Ivan Godard <ivan@ootbcomp.com> - 2014-07-17 13:03 -0700
        Re: LR(1) Parsing : Error Handling & Recovery Ivan Godard <ivan@ootbcomp.com> - 2014-07-17 13:57 -0700
          Re: LR(1) Parsing : Error Handling & Recovery wclodius@earthlink.net (William Clodius) - 2014-07-18 13:41 -0600
            Re: LR(1) Parsing : Error Handling & Recovery Stefan Monnier <monnier@iro.umontreal.ca> - 2014-07-18 21:09 -0400
              Re: LR(1) Parsing : Error Handling & Recovery Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-07-19 12:04 +0200
                Re: LR(1) Parsing : Error Handling & Recovery Stefan Monnier <monnier@iro.umontreal.ca> - 2014-07-20 10:28 -0400
                Re: LR(1) Parsing : Error Handling & Recovery Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2014-07-21 10:46 +0200
                Re: LR(1) Parsing : Error Handling & Recovery Stefan Monnier <monnier@iro.umontreal.ca> - 2014-08-06 21:32 -0400
            Re: LR(1) Parsing : Error Handling & Recovery arnold@skeeve.com (Aharon Robbins) - 2014-07-20 06:05 +0000
    Re: LR(1) Parsing : Error Handling & Recovery George Neuner <gneuner2@comcast.net> - 2014-07-17 18:49 -0400
      Re: LR(1) Parsing : Error Handling & Recovery wclodius@earthlink.net (William Clodius) - 2014-07-18 13:41 -0600
        Re: LR(1) Parsing : Error Handling & Recovery Hans Aberg <haberg-news@telia.com> - 2014-07-19 15:29 +0200
          Re: LR(1) Parsing : Error Handling & Recovery Evangelos Drikos <drikosev@otenet.gr> - 2014-07-20 00:40 +0300
            Re: LR(1) Parsing : Error Handling & Recovery Hans Aberg <haberg-news@telia.com> - 2014-07-20 01:38 +0200
              Re: LR(1) Parsing : Error Handling & Recovery Evangelos Drikos <drikosev@otenet.gr> - 2014-07-21 15:20 +0300
                Re: LR(1) Parsing : Error Handling & Recovery Hans Aberg <haberg-news@telia.com> - 2014-07-21 18:39 +0200
                Re: LR(1) Parsing : Error Handling & Recovery Evangelos Drikos <drikosev@otenet.gr> - 2014-08-26 13:44 +0300
                Re: LR(1) Parsing : Error Handling & Recovery Hans Aberg <haberg-news@telia.com> - 2014-08-29 11:13 +0200
                Re: split tokens; was LR(1) Parsing : Error Handling & Recovery Evangelos Drikos <drikosev@otenet.gr> - 2014-09-03 16:57 +0300
                Re: LR(1) Parsing : Error Handling & Recovery Hans Aberg <haberg-news@telia.com> - 2014-09-03 19:07 +0200
        Re: LR(1) Parsing : Error Handling & Recovery George Neuner <gneuner2@comcast.net> - 2014-07-20 01:19 -0400
          Re: LR(1) Parsing : Error Handling & Recovery wclodius@earthlink.net (William Clodius) - 2014-07-20 21:43 -0600
            Re: LR(1) Parsing : Error Handling & Recovery wclodius@earthlink.net (William Clodius) - 2014-07-21 21:44 -0600
          Re: LR(1) Parsing : Error Handling & Recovery Chris Dodd <cdodd@acm.org> - 2014-07-21 06:07 +0000
            Re: LR(1) Parsing : Error Handling & Recovery George Neuner <gneuner2@comcast.net> - 2014-07-25 21:58 -0400
              Re: LR(1) Parsing : Error Handling & Recovery Chris Dodd <cdodd@acm.org> - 2014-07-26 21:16 +0000
                Re: LR(1) Parsing : Error Handling & Recovery Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2014-07-28 14:43 +0200
                Re: LR(1) Parsing : Error Handling & Recovery Chris Dodd <cdodd@acm.org> - 2014-07-29 19:38 +0000
  Re: LR(1) Parsing : Error Handling & Recovery Eric <news@fx29.iad.highwinds-media.com> - 2014-07-16 16:40 -0400

csiph-web