Re: Reductions during Bison error handling

[Akim Demaille]

| Actually, there are couple of experiments that might be interesting
| (although I have a sneaking suspicion that papers have already been
| written about them):
| 
| 1. What would be the effect on table size and error-recovery behavior
|    if Bison were always to use 'error' as the default reduction (so
|    that yydefact could be eliminated entirely and 
|    yypact[yystate] == YYFLAG only for accepting state).
| 
| 2. What would be the effect on table size and error-recovery behavior
|    if Bison were to use default reductions only for consistent LALR
|    states (in current Bison terms, only use the default when
|    yypact[yystate] == YYFLAG) and make 'error' the default everywhere
|    else.
| 
| The intent (besides a slight simplification of the parser) is to cause
| Bison to detect parsing errors as soon as the offending token was
| consulted (without performing any reductions first). 
| 
| The side-effect of each of these would presumably be to increase the
| size of yytable, et al.  Furthermore, option (1) would have an
| additional side-effect on behavior, namely that a lookahead token
| would have to be present (i.e., to have been read by yylex) in ALL
| states.  Currently, if you write
| 
|       prog : expr ';'  { ACTION($1); }
|            | prog expr ';' { ACTION($2); }
|              ;
| 
|       expr : blah blah blah ... 
|              ;
| 
| (and "blah blah blah" never ends in a semicolon) then ACTION will be
| called before yylex is called to read beyond the semicolon.  This
| makes a difference with interactive input from a console, of course.  
| 
| The intent of the experiment is to determine whether the cost of these
| side-effects is significant, given the (I think desirable) earlier
| detection of errors).

Indeed, these would be interesting experiments.  I don't think the
impact on the table sizes would be really that bad: since the
inception of all these algorithms, memory has become cheap.  Unless
the behavior shows an exponential explosion, which I doubt about, it
should be afordable.  Actually, there are even true LR(1) parser
generators out there, which is certainly much more costly.

Also, somewhere else in the thread, you mentioned the decreasing
interest for better error recovery schemes.  That is really true, but
I have a couple of observations/questions:

1. Corbett's PhD is very interesting, but I was not convinced by the
implementation cost: it seems to be very demanding on the grammar's
writer, as it seems to require a significant amount of hand-written
code to tweak the parse stack.  It is my understanding that Bison
(used to) provides some help in *detecting* the error, and some of the
required pieces to implement the recovery, but nothing high-level to
implement the recovery itself.

That maybe too much demanding today, as, as noted, the compilation
cycle is now much shorter, and grammar maintainability is now
certainly ranted as more important.

2. GNAT is indeed quite impressive in this regard, but Robert Dewar
did state a couple of time that he meant to demonstrate, with GNAT,
that hand written recursive descent can be a nice framework for high
level error recovery/correction.  IOW, it's hand written, and I'm not
sure Bison's audience aims at that level of correction perfection.

3. Paul E. and I have discussed a couple of times about implementing
more pleasing error recovery (for the grammar author), using the
Burke-Fisher algorithm.  SML Yacc uses it.  None of us had the time to
address this issue yet, and I'm currently considering giving this as
a student project.