FYI: lalr1.cc infloops in error recovery

[Akim Demaille]

Index: ChangeLog
from  Akim Demaille  <address@hidden>

        Have lalr1.cc catch with Paul Eggert's patch to fix the infinite
        error recovery loops.  This patch is based on
        <http://mail.gnu.org/archive/html/bison-patches/2003-06/msg00000.html>.
        Also, augment the similarity between lalr1.cc and yacc.c.
        Note: the locations of error recovery rules are not correct yet.

        * data/lalr1.cc: Comment changes to augment the similarity between
        lalr1.cc and yacc.c.
        (YYERROR): Goto to yyerrorlab, not yyerrlab1.
        (yyerrlab1): Remove, but where it used to be (now the bottom part of
        yyerrlab), when hitting EOF, pop the whole stack here instead of
        merely falling thru the default error handling mechanism.
        (yyerrorlab): New label, with the old contents of YYERROR,
        plus the following change: pop the stack of rhs corresponding
        to the production that invoked YYERROR.  That is how Yacc
        behaves (required by POSIX).
        * tests/calc.at (AT_CHECK_CALC_LALR1_CC): No longer expected to
        fail.

Index: data/lalr1.cc
===================================================================
RCS file: /cvsroot/bison/bison/data/lalr1.cc,v
retrieving revision 1.36
diff -u -u -r1.36 lalr1.cc
--- data/lalr1.cc 7 Jul 2003 03:46:28 -0000 1.36
+++ data/lalr1.cc 25 Aug 2003 08:05:26 -0000
@@ -328,7 +328,7 @@
 
 #define YYACCEPT       goto yyacceptlab
 #define YYABORT                goto yyabortlab
-#define YYERROR                goto yyerrlab1
+#define YYERROR                goto yyerrorlab
 
 
 int
@@ -395,6 +395,8 @@
 #endif
     }
 
+  /* If the proper action on seeing token YYTOKEN is to reduce or to
+     detect an error, take that action.  */
   n_ += ilooka_;
   if (n_ < 0 || last_ < n_ || check_[n_] != ilooka_)
     goto yydefault;
@@ -439,16 +441,26 @@
   state_ = n_;
   goto yynewstate;
 
-  /* Default action.  */
+/*-----------------------------------------------------------.
+| yydefault -- do the default action for the current state.  |
+`-----------------------------------------------------------*/
  yydefault:
   n_ = defact_[state_];
   if (n_ == 0)
     goto yyerrlab;
   goto yyreduce;
 
-  /* Reduce.  */
+/*-----------------------------.
+| yyreduce -- Do a reduction.  |
+`-----------------------------*/
  yyreduce:
   len_ = r2_[n_];
+  /* If LEN_ is nonzero, implement the default value of the action:
+     `$$ = $1'.  Otherwise, use the top of the stack.
+
+     Otherwise, the following line sets YYVAL to garbage.
+     This behavior is undocumented and Bison
+     users should not rely upon it.  */
   if (len_)
     {
       yyval = semantic_stack_[len_ - 1];
@@ -517,7 +529,9 @@
     state_ = defgoto_[n_ - ntokens_];
   goto yynewstate;
 
-  /* Report and recover from errors.  This is very incomplete.  */
+/*------------------------------------.
+| yyerrlab -- here on detecting error |
+`------------------------------------*/
  yyerrlab:
   /* If not already recovering from an error, report this error.  */
   if (!errstatus)
@@ -558,32 +572,61 @@
        message = "syntax error";
       error_ ();
     }
-  goto yyerrlab1;
-
 
-  /*----------------------------------------------------.
-  | yyerrlab1 -- error raised explicitly by an action.  |
-  `----------------------------------------------------*/
- yyerrlab1:
   if (errstatus == 3)
     {
       /* If just tried and failed to reuse lookahead token after an
         error, discard it.  */
 
       /* Return failure if at end of input.  */
-      if (looka_ == eof_)
-       goto yyabortlab;
+      if (looka_ <= eof_)
+        {
+          /* If at end of input, pop the error token,
+            then the rest of the stack, then return failure.  */
+         if (looka_ == eof_)
+            for (;;)
+              {
+                 state_stack_.pop ();
+                 semantic_stack_.pop ();
+                 location_stack_.pop ();
+                if (state_stack_.height () == 1)
+                  YYABORT;
+//              YYDSYMPRINTF ("Error: popping", yystos[*yyssp], yyvsp, yylsp);
+// FIXME: yydestruct (yystos[*yyssp], yyvsp]b4_location_if([, yylsp])[);
+              }
+        }
+      else
+        {
 #if YYDEBUG
-      YYCDEBUG << "Discarding token " << looka_
-              << " (" << name_[ilooka_] << ")." << std::endl;
+           YYCDEBUG << "Discarding token " << looka_
+                   << " (" << name_[ilooka_] << ")." << std::endl;
+//       yydestruct (yytoken, &yylval]b4_location_if([, &yylloc])[);
 #endif
-      looka_ = empty_;
+           looka_ = empty_;
+        }
     }
 
   /* Else will try to reuse lookahead token after shifting the error
      token.  */
+  goto yyerrlab1;
+
+
+/*---------------------------------------------------.
+| yyerrorlab -- error raised explicitly by YYERROR.  |
+`---------------------------------------------------*/
+yyerrorlab:
+
+  state_stack_.pop (len_);
+  semantic_stack_.pop (len_);
+  location_stack_.pop (len_);
+  state_ = state_stack_[0];
+  goto yyerrlab1;
 
-  errstatus = 3;
+/*-------------------------------------------------------------.
+| yyerrlab1 -- common code for both syntax error and YYERROR.  |
+`-------------------------------------------------------------*/
+yyerrlab1:
+  errstatus = 3;       /* Each real token shifted decrements this.  */
 
   for (;;)
     {
@@ -601,7 +644,7 @@
 
       /* Pop the current state because it cannot handle the error token.  */
       if (state_stack_.height () == 1)
-       goto yyabortlab;
+       YYABORT;
 
 #if YYDEBUG
       if (debug_)
@@ -625,9 +668,10 @@
        }
 #endif
 
-      state_ = (state_stack_.pop (), state_stack_[0]);
+      state_stack_.pop ();
       semantic_stack_.pop ();
-      location_stack_.pop ();;
+      location_stack_.pop ();
+      state_ = state_stack_[0];
 
 #if YYDEBUG
       if (debug_)
Index: tests/calc.at
===================================================================
RCS file: /cvsroot/bison/bison/tests/calc.at,v
retrieving revision 1.58
diff -u -u -r1.58 calc.at
--- tests/calc.at 16 Jun 2003 18:42:49 -0000 1.58
+++ tests/calc.at 25 Aug 2003 08:05:26 -0000
@@ -611,7 +611,7 @@
 # Start a testing chunk which compiles `calc' grammar with
 # the C++ skeleton, and performs several tests over the parser.
 m4_define([AT_CHECK_CALC_LALR1_CC],
-[AT_CHECK_CALC([%skeleton "lalr1.cc"] $@, [expected to fail])])
+[AT_CHECK_CALC([%skeleton "lalr1.cc"] $@)])
 
 # AT_CHECK_CALC_LALR1_CC()