Merge remote-tracking branch 'origin/maint'

[bison.git] / src / state.h

diff --git a/src/state.h b/src/state.h
index 6b0a3de1e6711a62ebd5448a531f716f6b24beff..cfbef36d33eca8ae1b1ebb1dd7de273b5f8fc9cb 100644 (file)
--- a/src/state.h
+++ b/src/state.h
@@ -1,24 +1,22 @@
-/* Type definitions for nondeterministic finite state machine for bison,
+/* Type definitions for the finite state machine for Bison.

 
 

-   Copyright (C) 1984, 1989, 2000, 2001, 2002 Free Software
+   Copyright (C) 1984, 1989, 2000-2004, 2007, 2009-2012 Free Software

    Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
 
    Foundation, Inc.
 
    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


@@ -44,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


@@ -63,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).


@@ -94,11 +91,15 @@
 | Numbering states.  |
 `-------------------*/
 
 | Numbering states.  |
 `-------------------*/
 

-typedef short state_number;
-# define STATE_NUMBER_MAXIMUM SHRT_MAX
+typedef int state_number;
+# define STATE_NUMBER_MAXIMUM INT_MAX

 
 /* Be ready to map a state_number to an int.  */
 
 /* Be ready to map a state_number to an int.  */

-# define state_number_as_int(Tok) ((int) (Tok))
+static inline int
+state_number_as_int (state_number s)
+{
+  return s;
+}

 
 
 typedef struct state state;
 
 
 typedef struct state state;


@@ -109,7 +110,7 @@ typedef struct state state;
 
 typedef struct
 {
 
 typedef struct
 {

-  short num;
+  int num;

   state *states[1];
 } transitions;
 
   state *states[1];
 } transitions;
 


@@ -147,18 +148,18 @@ typedef struct
 
 
 /* Iterate over each transition over a token (shifts).  */
 
 
 /* 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)                                                 \
+#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))
 
 
     if (!TRANSITION_IS_DISABLED (Transitions, Iter))
 
 

-/* Return the state such SHIFTS contain a shift/goto to it on S.
+/* Return the state such SHIFTS contain a shift/goto to it on SYM.

    Abort if none found.  */
    Abort if none found.  */

-struct state *transitions_to (transitions *shifts, symbol_number s);
+struct state *transitions_to (transitions *shifts, symbol_number sym);

 
 
 /*-------.
 
 
 /*-------.


@@ -167,7 +168,7 @@ struct state *transitions_to (transitions *shifts, symbol_number s);
 
 typedef struct
 {
 
 typedef struct
 {

-  short num;
+  int num;

   symbol *symbols[1];
 } errs;
 
   symbol *symbols[1];
 } errs;
 


@@ -180,8 +181,9 @@ errs *errs_new (int num, symbol **tokens);
 
 typedef struct
 {
 
 typedef struct
 {

-  short num;
-  bitset *lookaheads;
+  int num;
+  bitset *lookahead_tokens;
+  /* Sorted ascendingly on rule number.  */

   rule *rules[1];
 } reductions;
 
   rule *rules[1];
 } reductions;
 


@@ -191,6 +193,8 @@ typedef struct
 | states.  |
 `---------*/
 
 | states.  |
 `---------*/
 

+struct state_list;
+

 struct state
 {
   state_number number;
 struct state
 {
   state_number number;


@@ -199,16 +203,23 @@ struct state
   reductions *reductions;
   errs *errs;
 
   reductions *reductions;
   errs *errs;
 

-  /* Nonzero if no lookahead is needed to decide what to do in state S.  */
+  /* 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;
 
   /* If some conflicts were solved thanks to precedence/associativity,
      a human readable description of the resolution.  */
   const char *solved_conflicts;
   char consistent;
 
   /* 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;
+  /* 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];
 };
 
   item_number items[1];
 };
 


@@ -217,7 +228,8 @@ extern state *final_state;
 
 /* Create a new state with ACCESSING_SYMBOL for those items.  */
 state *state_new (symbol_number accessing_symbol,
 
 /* Create a new state with ACCESSING_SYMBOL for those items.  */
 state *state_new (symbol_number accessing_symbol,

-                 size_t core_size, item_number *core);
+                  size_t core_size, item_number *core);
+state *state_new_isocore (state const *s);

 
 /* Set the transitions of STATE.  */
 void state_transitions_set (state *s, int num, state **trans);
 
 /* Set the transitions of STATE.  */
 void state_transitions_set (state *s, int num, state **trans);


@@ -230,9 +242,11 @@ int state_reduction_find (state *s, rule *r);
 /* Set the errs of STATE.  */
 void state_errs_set (state *s, int num, symbol **errors);
 
 /* Set the errs of STATE.  */
 void state_errs_set (state *s, int num, symbol **errors);
 

-/* Print on OUT all the lookaheads such that this STATE wants to
+/* Print on OUT all the lookahead tokens such that this STATE wants to

    reduce R.  */
    reduce R.  */

-void state_rule_lookaheads_print (state *s, rule *r, FILE *out);
+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.  */
 void state_hash_new (void);
 
 /* Create/destroy the states hash table.  */
 void state_hash_new (void);


@@ -245,9 +259,16 @@ state *state_hash_lookup (size_t core_size, item_number *core);
 /* Insert STATE in the state hash table.  */
 void state_hash_insert (state *s);
 
 /* Insert STATE in the state hash table.  */
 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.  */
 extern state **states;
 
 /* Free all the states.  */
 void states_free (void);
 /* All the states, indexed by the state number.  */
 extern state **states;
 
 /* Free all the states.  */
 void states_free (void);

+

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