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.
 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.
        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.
        New test.

-       
+

 2005-10-30  Paul Eggert  <eggert@cs.ucla.edu>
 
        * bootstrap (cleanup_gnulib): New function.  Use it to clean up
 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.
 
 /* 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.
    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);
 
     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;
 
   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)
 {
 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);
 
 
   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)
 
   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)
     {
   /* 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.  */
     }
 
   /* 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);
 
      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)
     {
       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);
       /* 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 */
     }
 
   /* 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.
 
 /* 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.
    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;
 }
 
   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;
 /* 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;
 }
 
   return -1 - i;
 }
 

+static inline bool
+item_number_is_rule_number (item_number i)
+{
+  return i < 0;
+}

 
 /*--------.
 | Rules.  |
 
 /*--------.
 | 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.
 
 /* 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.
 
 
    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)
 {
 void
 state_transitions_set (state *s, int num, state **trans)
 {

-  if (s->transitions)
-    abort ();
+  assert (!s->transitions);

   s->transitions = transitions_new (num, trans);
 }
 
   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)
 {
 void
 state_reductions_set (state *s, int num, rule **reds)
 {

-  if (s->reductions)
-    abort ();
+  assert (!s->reductions);

   s->reductions = reductions_new (num, reds);
 }
 
   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.  |
 | A state hash table.  |

-`----------------------*/
+`---------------------*/

 
 /* Initial capacity of states hash table.  */
 #define HT_INITIAL_CAPACITY 257
 
 /* 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
 
 typedef size_t uintptr_t;
 #endif
 

+#include <assert.h>
+

 #include <verify.h>
 #include <xalloc.h>
 
 #include <verify.h>
 #include <xalloc.h>