In some (weird) cases, the final state number is incorrect.

Reported by Alexandre Duret-Lutz.
* src/LR0.c (state_list_append): Remove the computation of
final_state.
(save_reductions): Do it here.
(get_state): Alpha conversion.
(generate_states): Use a for loop.
* src/gram.h (item_number_is_rule_number)
(item_number_is_symbol_number): New.
* src/state.c: Use assert.
* src/system.h: Include assert.h.
* tests/sets.at (Accept): New.

diff --git a/ChangeLog b/ChangeLog
index d4a25f1687445cfe60f8b930f67bc670250c3e56..2b829bacdebe25a1f6057575d9a8127f9cf855db 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,14 +1,29 @@
+2005-11-03  Akim Demaille  <akim@epita.fr>
+
+       In some (weird) cases, the final state number is incorrect.
+       Reported by Alexandre Duret-Lutz.
+       * src/LR0.c (state_list_append): Remove the computation of
+       final_state.
+       (save_reductions): Do it here.
+       (get_state): Alpha conversion.
+       (generate_states): Use a for loop.
+       * src/gram.h (item_number_is_rule_number)
+       (item_number_is_symbol_number): New.
+       * src/state.c: Use assert.
+       * src/system.h: Include assert.h.
+       * tests/sets.at (Accept): New.
+
 2005-10-30  Paul Hilfinger  <hilfingr@tully.CS.Berkeley.EDU>
 
        * data/glr.c (yyfill): Adjust comment.
-       (yyresolveAction): Initialize default location properly 
+       (yyresolveAction): Initialize default location properly
        for empty right-hand sides.
        (yydoAction): Ditto.
        Add comment explaining apparently dead code.
-       * tests/glr-regression.at 
-       (Incorrectly initialized location for empty right-hand side in GLR): 
+       * tests/glr-regression.at
+       (Incorrectly initialized location for empty right-hand side in GLR):
        New test.
-       
+
 2005-10-30  Paul Eggert  <eggert@cs.ucla.edu>
 
        * bootstrap (cleanup_gnulib): New function.  Use it to clean up

diff --git a/src/LR0.c b/src/LR0.c
index 43030fc5ba739c0a1a52724d5f9d7e7f53e80a72..2cba955a3d77b4fe77f0f5f7fce140e101939154 100644 (file)
--- a/src/LR0.c
+++ b/src/LR0.c
@@ -1,6 +1,6 @@
 /* Generate the nondeterministic finite state machine for Bison.
 
-   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2004 Free
+   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2004, 2005 Free
    Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
@@ -66,11 +66,6 @@ state_list_append (symbol_number sym, size_t core_size, item_number *core)
     fprintf (stderr, "state_list_append (state = %d, symbol = %d (%s))\n",
             nstates, sym, symbols[sym]->tag);
 
-  /* If this is the endtoken, and this is not the initial state, then
-     this is the final state.  */
-  if (sym == 0 && first_state)
-    final_state = s;
-
   node->next = NULL;
   node->state = s;
 
@@ -213,20 +208,20 @@ new_itemsets (state *s)
 static state *
 get_state (symbol_number sym, size_t core_size, item_number *core)
 {
-  state *sp;
+  state *s;
 
   if (trace_flag & trace_automaton)
     fprintf (stderr, "Entering get_state, symbol = %d (%s)\n",
             sym, symbols[sym]->tag);
 
-  sp = state_hash_lookup (core_size, core);
-  if (!sp)
-    sp = state_list_append (sym, core_size, core);
+  s = state_hash_lookup (core_size, core);
+  if (!s)
+    s = state_list_append (sym, core_size, core);
 
   if (trace_flag & trace_automaton)
-    fprintf (stderr, "Exiting get_state => %d\n", sp->number);
+    fprintf (stderr, "Exiting get_state => %d\n", s->number);
 
-  return sp;
+  return s;
 }
 
 /*---------------------------------------------------------------.
@@ -278,9 +273,18 @@ save_reductions (state *s)
   /* Find and count the active items that represent ends of rules. */
   for (i = 0; i < nritemset; ++i)
     {
-      int item = ritem[itemset[i]];
-      if (item < 0)
-       redset[count++] = &rules[item_number_as_rule_number (item)];
+      item_number item = ritem[itemset[i]];
+      if (item_number_is_rule_number (item))
+       {
+         rule_number r = item_number_as_rule_number (item);
+         redset[count++] = &rules[r];
+         if (r == 0)
+           {
+             /* This is "reduce 0", i.e., accept. */
+             assert (!final_state);
+             final_state = s;
+           }
+       }
     }
 
   /* Make a reductions structure and copy the data into it.  */
@@ -338,9 +342,8 @@ generate_states (void)
      item of this initial rule.  */
   state_list_append (0, 1, &initial_core);
 
-  list = first_state;
-
-  while (list)
+  /* States are queued when they are created; process them all.  */
+  for (list = first_state; list; list = list->next)
     {
       state *s = list->state;
       if (trace_flag & trace_automaton)
@@ -362,10 +365,6 @@ generate_states (void)
       /* Create the shifts structures for the shifts to those states,
         now that the state numbers transitioning to are known.  */
       state_transitions_set (s, nshifts, shiftset);
-
-      /* states are queued when they are created; process them all.
-        */
-      list = list->next;
     }
 
   /* discard various storage */

diff --git a/src/gram.h b/src/gram.h
index a5dfc1e93ba4fa40f5786650d6f41943f300be3c..b8f316a03945546fa2c6c63267bef98c7e08517d 100644 (file)
--- a/src/gram.h
+++ b/src/gram.h
@@ -1,6 +1,6 @@
 /* Data definitions for internal representation of Bison's input.
 
-   Copyright (C) 1984, 1986, 1989, 1992, 2001, 2002, 2003, 2004
+   Copyright (C) 1984, 1986, 1989, 1992, 2001, 2002, 2003, 2004, 2005
    Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
@@ -138,6 +138,12 @@ item_number_as_symbol_number (item_number i)
   return i;
 }
 
+static inline bool
+item_number_is_symbol_number (item_number i)
+{
+  return i >= 0;
+}
+
 /* Rule numbers.  */
 typedef int rule_number;
 extern rule_number nrules;
@@ -154,6 +160,11 @@ item_number_as_rule_number (item_number i)
   return -1 - i;
 }
 
+static inline bool
+item_number_is_rule_number (item_number i)
+{
+  return i < 0;
+}
 
 /*--------.
 | Rules.  |

diff --git a/src/state.c b/src/state.c
index 89d0c870b532937dbaaede68d3518655fb69a147..e78db69bd41545bed1b796d0b20076c48bfa9de6 100644 (file)
--- a/src/state.c
+++ b/src/state.c
@@ -1,6 +1,6 @@
 /* Type definitions for nondeterministic finite state machine for Bison.
 
-   Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
+   Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
 
@@ -174,8 +174,7 @@ state_free (state *s)
 void
 state_transitions_set (state *s, int num, state **trans)
 {
-  if (s->transitions)
-    abort ();
+  assert (!s->transitions);
   s->transitions = transitions_new (num, trans);
 }
 
@@ -187,8 +186,7 @@ state_transitions_set (state *s, int num, state **trans)
 void
 state_reductions_set (state *s, int num, rule **reds)
 {
-  if (s->reductions)
-    abort ();
+  assert (!s->reductions);
   s->reductions = reductions_new (num, reds);
 }
 
@@ -248,9 +246,9 @@ state_rule_look_ahead_tokens_print (state *s, rule *r, FILE *out)
 }
 
 
-/*----------------------.
+/*---------------------.
 | A state hash table.  |
-`----------------------*/
+`---------------------*/
 
 /* Initial capacity of states hash table.  */
 #define HT_INITIAL_CAPACITY 257

diff --git a/src/system.h b/src/system.h
index 9b874b9595c97fb6a944a2af4a1d887712cc0256..369218cd0b82f7af5aef92710615067d7dcd8cc4 100644 (file)
--- a/src/system.h
+++ b/src/system.h
@@ -52,6 +52,8 @@
 typedef size_t uintptr_t;
 #endif
 
+#include <assert.h>
+
 #include <verify.h>
 #include <xalloc.h>