Re: Error recovery and LR(1)/LALR(1)

"Gordon V Cormack" <>
20 Jun 2002 21:44:29 -0400

          From comp.compilers

Related articles
Error recovery and LR(1)/LALR(1) (Heng Yuan) (2002-06-17)
Re: Error recovery and LR(1)/LALR(1) (Gordon V Cormack) (2002-06-20)
Re: Error recovery and LR(1)/LALR(1) (2002-06-20)
Error recovery and LR(1)/LALR(1) (Chris F Clark) (2002-06-20)
Re: Error recovery and LR(1)/LALR(1) (=?Windows-1252?Q?S=F6nke_Kannapinn?=) (2002-06-28)
| List of all articles for this month |

From: "Gordon V Cormack" <>
Newsgroups: comp.compilers
Date: 20 Jun 2002 21:44:29 -0400
Organization: University of Waterloo
References: 02-06-055
Keywords: parse, LALR
Posted-Date: 20 Jun 2002 21:44:29 EDT

Heng Yuan <> wrote:
>I am in the process of writing an LR(1)/LALR(1) parser generator called
>YooParse, which will be used with YooLex, a C++ lexer generator. While I
>successfully generated the LR(1)/LALR(1) DFA states, I encountered
>problems dealing with error states. This is a long post.
>Situation 1:
>For example, a DFA state contains the following LR(1) items
> A -> alpha X . , lookahead = 'a'
> B -> beta X . gamma , lookahead = 'b'
>My question is really what to do if the lookahead is neither 'a'
>or 'b'? Should A be reduced?

Minor nit: If this is a valid LR state, alpha == beta.

In a full LR(1) parse you would not reduce A. With LALR, SLR, or with
certain types of table compression, you may reduce A but, as you have
observed, error reporting and recovery are impaired.

My opinion is that, in this day and age, you should be building a
parse tree anyway. If you build a parse tree, it is easy enough to
"unparse" a bit so that you can do some sort of local edit to
resume the parse.

If you don't want to unparse, you can, without too much overhead, put
"anticipation" into your reduction strategy ... follow the chain of
reductions that you are planning to do and don't do any of them unless
they will lead to a valid shift. This can be done with a simple loop
that examines the states that will be uncovered after each reduction.
The loop continues until either a shift or an error action is
encountered. This will slow your parse, but not much - presumably the
stack operations and/or semantic actions overwhelm the cost of this
simple loop).
Gordon V. Cormack CS Dept, University of Waterloo, Canada N2L 3G1

Post a followup to this message

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