From 36b5e963e6a0d2992831ab8635963e75ac36671e Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Wed, 9 Nov 2005 15:48:05 +0000 Subject: [PATCH] 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. --- ChangeLog | 23 +++++++++++++++++++---- src/LR0.c | 43 +++++++++++++++++++++---------------------- src/gram.h | 13 ++++++++++++- src/state.c | 12 +++++------- src/system.h | 2 ++ 5 files changed, 59 insertions(+), 34 deletions(-) diff --git a/ChangeLog b/ChangeLog index d4a25f16..2b829bac 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,14 +1,29 @@ +2005-11-03 Akim Demaille + + 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 * 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 * bootstrap (cleanup_gnulib): New function. Use it to clean up diff --git a/src/LR0.c b/src/LR0.c index 43030fc5..2cba955a 100644 --- 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 a5dfc1e9..b8f316a0 100644 --- 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 89d0c870..e78db69b 100644 --- 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 9b874b95..369218cd 100644 --- a/src/system.h +++ b/src/system.h @@ -52,6 +52,8 @@ typedef size_t uintptr_t; #endif +#include + #include #include -- 2.45.2