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

Heng Yuan <heng@Ag.arizona.edu> 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
gvcormack@uwaterloo.ca http://cormack.uwaterloo.ca/cormack

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