]> git.saurik.com Git - bison.git/blobdiff - src/state.h
* src/system.h: Provide default declarations for stpcpy, strndup,
[bison.git] / src / state.h
index 67b78cfce276659f6782abd5ea7467fe9badab19..f42425556490fcec2abe7f20a580e8a07a01fa65 100644 (file)
 /* Type definitions for nondeterministic finite state machine for bison,
-   Copyright (C) 1984, 1989 Free Software Foundation, Inc.
+   Copyright 1984, 1989, 2000 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
-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.
+   Bison is free software; you can redistribute it and/or modify
+   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.
 
-Bison 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.
+   Bison 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
-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.  */
+   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.  */
 
 
 /* These type definitions are used to represent a nondeterministic
-   finite state machine that parses the specified grammar.
-   This information is generated by the function generate_states
-   in the file LR0.
-
-Each state of the machine is described by a set of items --
-particular positions in particular rules -- that are the possible
-places where parsing could continue when the machine is in this state.
-These symbols at these items are the allowable inputs that can follow now.
-
-A core represents one state.  States are numbered in the number field.
-When generate_states is finished, the starting state is state 0
-and nstates is the number of states.  (A transition to a state
-whose state number is nstates indicates termination.)  All the cores
-are chained together and first_state points to the first one (state 0).
-
-For each state there is a particular symbol which must have been the
-last thing accepted to reach that state.  It is the 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.
-
-The link field is used for chaining buckets that hash states by
-their itemsets.  This is for recognizing equivalent states and
-combining them when the states are generated.
-
-The two types of transitions are shifts (push the lookahead token
-and read another) and reductions (combine the last n things on the
-stack via a rule, replace them with the symbol that the rule derives,
-and leave the lookahead token alone).  When the states are generated,
-these transitions are represented in two other lists.
-
-Each shifts structure describes the possible shift transitions out
-of one state, the state whose number is in the number field.
-The shifts structures are linked through next and first_shift points to them.
-Each contains a vector of numbers of the states that shift transitions
-can go to.  The accessing_symbol fields of those states' cores say what kind
-of input leads to them.
-
-A shift to state zero should be ignored.  Conflict resolution
-deletes shifts by changing them 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.
-
-Conflict resolution can decide that certain tokens in certain
-states should explicitly be errors (for implementing %nonassoc).
-For each state, the tokens that are errors for this reason
-are recorded in an errs structure, which has the state number
-in its number field.  The rest of the errs structure is full
-of token numbers.
-
-There is at least one shift transition present in state zero.
-It leads to a next-to-final state whose accessing_symbol is
-the grammar's start symbol.  The next-to-final state has one shift
-to the final state, whose accessing_symbol is zero (end of input).
-The final state has one shift, which goes to the termination state
-(whose number is nstates-1).
-The reason for the extra state at the end is to placate the parser's
-strategy of making all decisions one token ahead of its actions.  */
-
-
-typedef
-  struct core
-    {
-      struct core *next;
-      struct core *link;
-      short number;
-      short accessing_symbol;
-      short nitems;
-      short items[1];
-    }
-  core;
-
-
-
-typedef
-  struct shifts
-    {
-      struct shifts *next;
-      short number;
-      short nshifts;
-      short shifts[1];
-    }
-  shifts;
-
-
-
-typedef
-  struct errs
-    {
-      short nerrs;
-      short errs[1];
-    }
-  errs;
-
-
-
-typedef
-  struct reductions
-    {
-      struct reductions *next;
-      short number;
-      short nreds;
-      short rules[1];
-    }
-  reductions;
-
-
-
-extern int nstates;
-extern core *first_state;
-extern shifts *first_shift;
-extern reductions *first_reduction;
+   finite state machine that parses the specified grammar.  This
+   information is generated by the function generate_states in the
+   file LR0.
+
+   Each state of the machine is described by a set of items --
+   particular positions in particular rules -- that are the possible
+   places where parsing could continue when the machine is in this
+   state.  These symbols at these items are the allowable inputs that
+   can follow now.
+
+   A core represents one state.  States are numbered in the number
+   field.  When generate_states is finished, the starting state is
+   state 0 and nstates is the number of states.  (A transition to a
+   state whose state number is nstates indicates termination.)  All
+   the cores are chained together and first_state points to the first
+   one (state 0).
+
+   For each state there is a particular symbol which must have been
+   the last thing accepted to reach that state.  It is the
+   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.
+
+   The link field is used for chaining buckets that hash states by
+   their itemsets.  This is for recognizing equivalent states and
+   combining them when the states are generated.
+
+   The two types of transitions are shifts (push the lookahead token
+   and read another) and reductions (combine the last n things on the
+   stack via a rule, replace them with the symbol that the rule
+   derives, and leave the lookahead token alone).  When the states are
+   generated, these transitions are represented in two other lists.
+
+   Each shifts structure describes the possible shift transitions out
+   of one state, the state whose number is in the number field.  The
+   shifts structures are linked through next and first_shift points to
+   them.  Each contains a vector of numbers of the states that shift
+   transitions can go to.  The accessing_symbol fields of those
+   states' cores say what kind of input leads to them.
+
+   A shift to state zero should be ignored.  Conflict resolution
+   deletes shifts by changing them 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.
+
+   Conflict resolution can decide that certain tokens in certain
+   states should explicitly be errors (for implementing %nonassoc).
+   For each state, the tokens that are errors for this reason are
+   recorded in an errs structure, which has the state number in its
+   number field.  The rest of the errs structure is full of token
+   numbers.
+
+   There is at least one shift transition present in state zero.  It
+   leads to a next-to-final state whose accessing_symbol is the
+   grammar's start symbol.  The next-to-final state has one shift to
+   the final state, whose accessing_symbol is zero (end of input).
+   The final state has one shift, which goes to the termination state
+   (whose number is nstates-1).  The reason for the extra state at the
+   end is to placate the parser's strategy of making all decisions one
+   token ahead of its actions.  */
+
+#ifndef STATE_H_
+# define STATE_H_
+
+typedef struct core
+{
+  struct core *next;
+  struct core *link;
+  short number;
+  short accessing_symbol;
+  short nitems;
+  short items[1];
+}
+core;
+
+
+
+typedef struct shifts
+{
+  struct shifts *next;
+  short number;
+  short nshifts;
+  short shifts[1];
+}
+shifts;
+
+
+
+typedef struct errs
+{
+  short nerrs;
+  short errs[1];
+}
+errs;
+
+
+
+typedef struct reductions
+{
+  struct reductions *next;
+  short number;
+  short nreds;
+  short rules[1];
+}
+reductions;
+
+#endif /* !STATE_H_ */