[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
FYI: Fix the computation of YYFINAL
From: |
Akim Demaille |
Subject: |
FYI: Fix the computation of YYFINAL |
Date: |
Thu, 03 Nov 2005 16:22:59 +0100 |
User-agent: |
Gnus/5.110004 (No Gnus v0.4) Emacs/21.4 (gnu/linux) |
I introduced the following bug years ago, and it was "harmless" until
we (i.e., I, again...) allowed the user to use $end in her grammar. I
opened a can of worms without realizing it.
At least one issue is addressed here.
Index: ChangeLog
from Akim Demaille <address@hidden>
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.
Index: src/LR0.c
===================================================================
RCS file: /cvsroot/bison/bison/src/LR0.c,v
retrieving revision 1.93
diff -u -u -r1.93 LR0.c
--- src/LR0.c 14 May 2005 06:49:47 -0000 1.93
+++ src/LR0.c 3 Nov 2005 15:20:53 -0000
@@ -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 @@
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 @@
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 @@
/* 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 @@
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 @@
/* 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 */
Index: src/gram.h
===================================================================
RCS file: /cvsroot/bison/bison/src/gram.h,v
retrieving revision 1.57
diff -u -u -r1.57 gram.h
--- src/gram.h 14 May 2005 06:49:47 -0000 1.57
+++ src/gram.h 3 Nov 2005 15:20:53 -0000
@@ -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 @@
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 @@
return -1 - i;
}
+static inline bool
+item_number_is_rule_number (item_number i)
+{
+ return i < 0;
+}
/*--------.
| Rules. |
Index: src/state.c
===================================================================
RCS file: /cvsroot/bison/bison/src/state.c,v
retrieving revision 1.36
diff -u -u -r1.36 state.c
--- src/state.c 5 Oct 2005 06:39:08 -0000 1.36
+++ src/state.c 3 Nov 2005 15:20:53 -0000
@@ -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 @@
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 @@
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 @@
}
-/*----------------------.
+/*---------------------.
| A state hash table. |
-`----------------------*/
+`---------------------*/
/* Initial capacity of states hash table. */
#define HT_INITIAL_CAPACITY 257
Index: src/system.h
===================================================================
RCS file: /cvsroot/bison/bison/src/system.h,v
retrieving revision 1.71
diff -u -u -r1.71 system.h
--- src/system.h 13 Oct 2005 10:13:24 -0000 1.71
+++ src/system.h 3 Nov 2005 15:20:53 -0000
@@ -52,6 +52,8 @@
typedef size_t uintptr_t;
#endif
+#include <assert.h>
+
#include <verify.h>
#include <xalloc.h>
Index: tests/sets.at
===================================================================
RCS file: /cvsroot/bison/bison/tests/sets.at,v
retrieving revision 1.19
diff -u -u -r1.19 sets.at
--- tests/sets.at 24 Jul 2005 07:24:22 -0000 1.19
+++ tests/sets.at 3 Nov 2005 15:20:53 -0000
@@ -252,3 +252,51 @@
]])
AT_CLEANUP
+
+
+
+
+## -------- ##
+## Accept. ##
+## -------- ##
+
+# In some weird cases Bison could compute an incorrect final state
+# number. This happens only if the $end token is used in the user
+# grammar, which is a very suspicious accidental feature introduce
+# as a side effect of allowing the user to name $end using
+# `%token END 0 "end of file"'.
+
+AT_SETUP([Accept])
+
+AT_DATA([input.y],
+[[%token END 0
+%%
+input:
+ 'a'
+| '(' input ')'
+| '(' error END
+;
+]])
+
+AT_CHECK([[bison -v -o input.c input.y]])
+
+# Get the final state in the parser.
+AT_CHECK([sed -n 's/.*define YYFINAL *\([0-9][0-9]\)*/final state \1/p'
input.c],
+ 0, [stdout])
+mv stdout expout
+
+# Get the final state in the report, from the "accept" action..
+AT_CHECK([sed -n '
+ /^state \(.*\)/{
+ s//final state \1/
+ x
+ }
+ / accept/{
+ x
+ p
+ q
+ }
+ ' input.output],
+ 0, [expout])
+
+AT_CLEANUP
- FYI: Fix the computation of YYFINAL,
Akim Demaille <=