Merge remote-tracking branch 'origin/maint'

[bison.git] / src / state.h

diff --git a/src/state.h b/src/state.h
index 78a739a8b3620e8f334c76fd4e7d025e31be0b72..cfbef36d33eca8ae1b1ebb1dd7de273b5f8fc9cb 100644 (file)
--- a/src/state.h
+++ b/src/state.h
@@ -1,22 +1,22 @@
-/* Type definitions for nondeterministic finite state machine for bison,
-   Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc.
+/* Type definitions for the finite state machine for Bison.
+
+   Copyright (C) 1984, 1989, 2000-2004, 2007, 2009-2012 Free Software
+   Foundation, Inc.

 
    This file is part of Bison, the GNU Compiler Compiler.
 
 
    This file is part of Bison, the GNU Compiler Compiler.
 

-   Bison is free software; you can redistribute it and/or modify
+   This program is free software: you can redistribute it and/or modify

    it under the terms of the GNU General Public License as published by
    it under the terms of the GNU General Public License as published by

-   the Free Software Foundation; either version 2, or (at your option)
-   any later version.
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.

 
 

-   Bison is distributed in the hope that it will be useful,
+   This program is distributed in the hope that it will be useful,

    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
 
    You should have received a copy of the GNU General Public License
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
 
    You should have received a copy of the GNU General Public License

-   along with Bison; see the file COPYING.  If not, write to
-   the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
-   Boston, MA 02111-1307, USA.  */
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */

 
 
 /* These type definitions are used to represent a nondeterministic
 
 
 /* These type definitions are used to represent a nondeterministic


@@ -42,7 +42,7 @@
    ACCESSING_SYMBOL of the core.
 
    Each core contains a vector of NITEMS items which are the indices
    ACCESSING_SYMBOL of the core.
 
    Each core contains a vector of NITEMS items which are the indices

-   in the RITEMS vector of the items that are selected in this state.
+   in the RITEM vector of the items that are selected in this state.

 
    The two types of actions are shifts/gotos (push the lookahead token
    and read another/goto to the state designated by a nterm) and
 
    The two types of actions are shifts/gotos (push the lookahead token
    and read another/goto to the state designated by a nterm) and


@@ -51,7 +51,7 @@
    lookahead token alone).  When the states are generated, these
    actions are represented in two other lists.
 
    lookahead token alone).  When the states are generated, these
    actions are represented in two other lists.
 

-   Each transition_t structure describes the possible transitions out
+   Each transition structure describes the possible transitions out

    of one state, the state whose number is in the number field.  Each
    contains a vector of numbers of the states that transitions can go
    to.  The accessing_symbol fields of those states' cores say what
    of one state, the state whose number is in the number field.  Each
    contains a vector of numbers of the states that transitions can go
    to.  The accessing_symbol fields of those states' cores say what


@@ -61,9 +61,8 @@
    deletes transitions by having them point to zero.
 
    Each reductions structure describes the possible reductions at the
    deletes transitions by having them point to zero.
 
    Each reductions structure describes the possible reductions at the

-   state whose number is in the number field.  The data is a list of
-   nreds rules, represented by their rule numbers.  first_reduction
-   points to the list of these structures.
+   state whose number is in the number field.  rules is an array of
+   num rules.  lookahead_tokens is an array of bitsets, one per rule.

 
    Conflict resolution can decide that certain tokens in certain
    states should explicitly be errors (for implementing %nonassoc).
 
    Conflict resolution can decide that certain tokens in certain
    states should explicitly be errors (for implementing %nonassoc).


@@ -82,28 +81,38 @@
 #ifndef STATE_H_
 # define STATE_H_
 
 #ifndef STATE_H_
 # define STATE_H_
 

-# include "bitsetv.h"
+# include <bitset.h>
+
+# include "gram.h"
+# include "symtab.h"

 
 
 /*-------------------.
 | Numbering states.  |
 `-------------------*/
 
 
 
 /*-------------------.
 | Numbering states.  |
 `-------------------*/
 

-typedef short state_number_t;
-# define STATE_NUMBER_MAX ((state_number_t) SHRT_MAX)
+typedef int state_number;
+# define STATE_NUMBER_MAXIMUM INT_MAX
+
+/* Be ready to map a state_number to an int.  */
+static inline int
+state_number_as_int (state_number s)
+{
+  return s;
+}
+

 
 

-/* Be ready to map a state_number_t to an int.  */
-# define state_number_as_int(Tok) ((int) (Tok))
+typedef struct state state;

 
 /*--------------.
 | Transitions.  |
 `--------------*/
 
 
 /*--------------.
 | Transitions.  |
 `--------------*/
 

-typedef struct transtion_s
+typedef struct

 {
 {

-  short num;
-  state_number_t states[1];
-} transitions_t;
+  int num;
+  state *states[1];
+} transitions;

 
 
 /* What is the symbol labelling the transition to
 
 
 /* What is the symbol labelling the transition to


@@ -111,7 +120,7 @@ typedef struct transtion_s
    token), or non terminals in case of gotos.  */
 
 #define TRANSITION_SYMBOL(Transitions, Num) \
    token), or non terminals in case of gotos.  */
 
 #define TRANSITION_SYMBOL(Transitions, Num) \

-  (states[Transitions->states[Num]]->accessing_symbol)
+  (Transitions->states[Num]->accessing_symbol)

 
 /* Is the TRANSITIONS->states[Num] a shift? (as opposed to gotos).  */
 
 
 /* Is the TRANSITIONS->states[Num] a shift? (as opposed to gotos).  */
 


@@ -132,117 +141,134 @@ typedef struct transtion_s
    disabled.  */
 
 #define TRANSITION_DISABLE(Transitions, Num) \
    disabled.  */
 
 #define TRANSITION_DISABLE(Transitions, Num) \

-  (Transitions->states[Num] = 0)
+  (Transitions->states[Num] = NULL)

 
 #define TRANSITION_IS_DISABLED(Transitions, Num) \
 
 #define TRANSITION_IS_DISABLED(Transitions, Num) \

-  (Transitions->states[Num] == 0)
+  (Transitions->states[Num] == NULL)
+
+
+/* Iterate over each transition over a token (shifts).  */
+#define FOR_EACH_SHIFT(Transitions, Iter)                       \
+  for (Iter = 0;                                                \
+       Iter < Transitions->num                                  \
+         && (TRANSITION_IS_DISABLED (Transitions, Iter)         \
+             || TRANSITION_IS_SHIFT (Transitions, Iter));       \
+       ++Iter)                                                  \
+    if (!TRANSITION_IS_DISABLED (Transitions, Iter))
+

 
 

-/* Return the state such these TRANSITIONS contain a shift/goto to it on
-   SYMBOL.  Aborts if none found.  */
-struct state_s;
-struct state_s *transitions_to PARAMS ((transitions_t *state,
-                                       symbol_number_t s));
+/* Return the state such SHIFTS contain a shift/goto to it on SYM.
+   Abort if none found.  */
+struct state *transitions_to (transitions *shifts, symbol_number sym);

 
 
 /*-------.
 | Errs.  |
 `-------*/
 
 
 
 /*-------.
 | Errs.  |
 `-------*/
 

-typedef struct errs_s
+typedef struct

 {
 {

-  short num;
-  symbol_number_t symbols[1];
-} errs_t;
+  int num;
+  symbol *symbols[1];
+} errs;

 
 

-errs_t *errs_new PARAMS ((int num, symbol_number_t *tokens));
+errs *errs_new (int num, symbol **tokens);

 
 
 /*-------------.
 | Reductions.  |
 `-------------*/
 
 
 
 /*-------------.
 | Reductions.  |
 `-------------*/
 

-typedef struct reductions_s
+typedef struct

 {
 {

-  short num;
-  rule_number_t rules[1];
-} reductions_t;
+  int num;
+  bitset *lookahead_tokens;
+  /* Sorted ascendingly on rule number.  */
+  rule *rules[1];
+} reductions;

 
 
 
 
 
 

-/*----------.
-| State_t.  |
-`----------*/
+/*---------.
+| states.  |
+`---------*/

 
 

-typedef struct state_s
-{
-  state_number_t number;
-  symbol_number_t accessing_symbol;
-  transitions_t     *transitions;
-  reductions_t *reductions;
-  errs_t       *errs;
+struct state_list;

 
 

-  /* Nonzero if no lookahead is needed to decide what to do in state S.  */
+struct state
+{
+  state_number number;
+  symbol_number accessing_symbol;
+  transitions *transitions;
+  reductions *reductions;
+  errs *errs;
+
+  /* When an includer (such as ielr.c) needs to store states in a list, the
+     includer can define struct state_list as the list node structure and can
+     store in this member a reference to the node containing each state.  */
+  struct state_list *state_list;
+
+  /* If non-zero, then no lookahead sets on reduce actions are needed to
+     decide what to do in state S.  */

   char consistent;
 
   char consistent;
 

-  /* Used in LALR, not LR(0).
-
-     When a state is not consistent (there is an S/R or R/R conflict),
-     lookaheads are needed to enable the reductions.  NLOOKAHEADS is
-     the number of lookahead guarded reductions of the
-     LOOKAHEADS_RULE.  For each rule LOOKAHEADS_RULE[R], LOOKAHEADS[R]
-     is the bitset of the lookaheads enabling this reduction.  */
-  int nlookaheads;
-  bitsetv lookaheads;
-  rule_t **lookaheads_rule;
-

   /* If some conflicts were solved thanks to precedence/associativity,
      a human readable description of the resolution.  */
   const char *solved_conflicts;
   /* If some conflicts were solved thanks to precedence/associativity,
      a human readable description of the resolution.  */
   const char *solved_conflicts;

+  const char *solved_conflicts_xml;

 
 

-  /* Its items.  Must be last, since ITEMS can be arbitrarily large.
-     */
-  unsigned short nitems;
-  item_number_t items[1];
-} state_t;
+  /* Its items.  Must be last, since ITEMS can be arbitrarily large.  Sorted
+     ascendingly on item index in RITEM, which is sorted on rule number.  */
+  size_t nitems;
+  item_number items[1];
+};

 
 

-extern state_number_t nstates;
-extern state_t *final_state;
+extern state_number nstates;
+extern state *final_state;

 
 /* Create a new state with ACCESSING_SYMBOL for those items.  */
 
 /* Create a new state with ACCESSING_SYMBOL for those items.  */

-state_t *state_new PARAMS ((symbol_number_t accessing_symbol,
-                           size_t core_size, item_number_t *core));
+state *state_new (symbol_number accessing_symbol,
+                  size_t core_size, item_number *core);
+state *state_new_isocore (state const *s);

 
 /* Set the transitions of STATE.  */
 
 /* Set the transitions of STATE.  */

-void state_transitions_set PARAMS ((state_t *state,
-                                   int num, state_number_t *transitions));
+void state_transitions_set (state *s, int num, state **trans);

 
 /* Set the reductions of STATE.  */
 
 /* Set the reductions of STATE.  */

-void state_reductions_set PARAMS ((state_t *state,
-                                  int num, rule_number_t *reductions));
+void state_reductions_set (state *s, int num, rule **reds);
+
+int state_reduction_find (state *s, rule *r);

 
 /* Set the errs of STATE.  */
 
 /* Set the errs of STATE.  */

-void state_errs_set PARAMS ((state_t *state,
-                            int num, symbol_number_t *errs));
+void state_errs_set (state *s, int num, symbol **errors);

 
 

-/* Print on OUT all the lookaheads such that this STATE wants to
-   reduce this RULE.  */
-void state_rule_lookaheads_print PARAMS ((state_t *state, rule_t *rule,
-                                         FILE *out));
+/* Print on OUT all the lookahead tokens such that this STATE wants to
+   reduce R.  */
+void state_rule_lookahead_tokens_print (state *s, rule *r, FILE *out);
+void state_rule_lookahead_tokens_print_xml (state *s, rule *r,
+                                            FILE *out, int level);

 
 /* Create/destroy the states hash table.  */
 
 /* Create/destroy the states hash table.  */

-void state_hash_new PARAMS ((void));
-void state_hash_free PARAMS ((void));
+void state_hash_new (void);
+void state_hash_free (void);

 
 /* Find the state associated to the CORE, and return it.  If it does
    not exist yet, return NULL.  */
 
 /* Find the state associated to the CORE, and return it.  If it does
    not exist yet, return NULL.  */

-state_t *state_hash_lookup PARAMS ((size_t core_size, item_number_t *core));
+state *state_hash_lookup (size_t core_size, item_number *core);

 
 /* Insert STATE in the state hash table.  */
 
 /* Insert STATE in the state hash table.  */

-void state_hash_insert PARAMS ((state_t *state));
+void state_hash_insert (state *s);
+
+/* Remove unreachable states, renumber remaining states, update NSTATES, and
+   write to OLD_TO_NEW a mapping of old state numbers to new state numbers such
+   that the old value of NSTATES is written as the new state number for removed
+   states.  The size of OLD_TO_NEW must be the old value of NSTATES.  */
+void state_remove_unreachable_states (state_number old_to_new[]);

 
 /* All the states, indexed by the state number.  */
 
 /* All the states, indexed by the state number.  */

-extern state_t **states;
+extern state **states;

 
 /* Free all the states.  */
 
 /* Free all the states.  */

-void states_free PARAMS ((void));
+void states_free (void);
+

 #endif /* !STATE_H_ */
 #endif /* !STATE_H_ */