X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/d0fb370f6686f29d90739486c31f060f1999842a..80dac38c5eb3b95412a6c99c9dbe976ac963c01b:/src/state.h?ds=sidebyside diff --git a/src/state.h b/src/state.h index 53f9d094..8cdf4040 100644 --- a/src/state.h +++ b/src/state.h @@ -1,137 +1,196 @@ /* Type definitions for nondeterministic finite state machine for bison, - Copyright (C) 1984, 1989 Free Software Foundation, Inc. + Copyright 1984, 1989, 2000, 2001 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, 675 Mass Ave, Cambridge, MA 02139, 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_ + + +/*---------. +| Shifts. | +`---------*/ + +typedef struct shifts +{ + short nshifts; + short shifts[1]; +} shifts; + +shifts *shifts_new PARAMS ((int n)); + + +/* What is the symbol which is shifted by SHIFTS->shifts[Shift]? Can + be a token (amongst which the error token), or non terminals in + case of gotos. */ + +#define SHIFT_SYMBOL(Shifts, Shift) \ + (state_table[Shifts->shifts[Shift]]->accessing_symbol) + +/* Is the SHIFTS->shifts[Shift] a real shift? (as opposed to gotos.) */ + +#define SHIFT_IS_SHIFT(Shifts, Shift) \ + (ISTOKEN (SHIFT_SYMBOL (Shifts, Shift))) + +/* Is the SHIFTS->shifts[Shift] a goto?. */ + +#define SHIFT_IS_GOTO(Shifts, Shift) \ + (!SHIFT_IS_SHIFT (Shifts, Shift)) + +/* Is the SHIFTS->shifts[Shift] then handling of the error token?. */ + +#define SHIFT_IS_ERROR(Shifts, Shift) \ + (SHIFT_SYMBOL (Shifts, Shift) == error_token_number) + +/* When resolving a SR conflicts, if the reduction wins, the shift is + disabled. */ + +#define SHIFT_DISABLE(Shifts, Shift) \ + (Shifts->shifts[Shift] = 0) + +#define SHIFT_IS_DISABLED(Shifts, Shift) \ + (Shifts->shifts[Shift] == 0) + + +/*-------. +| Errs. | +`-------*/ + +typedef struct errs +{ + short nerrs; + short errs[1]; +} errs; + +errs *errs_new PARAMS ((int n)); +errs *errs_dup PARAMS ((errs *src)); + + +/*-------------. +| Reductions. | +`-------------*/ + +typedef struct reductions +{ + short nreds; + short rules[1]; +} reductions; + +reductions *reductions_new PARAMS ((int n)); + + +/*----------. +| State_t. | +`----------*/ + +typedef struct state_s +{ + struct state_s *next; + struct state_s *link; + + short number; + short accessing_symbol; + shifts *shifts; + reductions *reductions; + errs *errs; + + /* Nonzero if no lookahead is needed to decide what to do in state S. */ + char consistent; + + /* Used in LALR, not LR(0). */ + /* Pseudo pointer into LA. */ + short lookaheadsp; + int nlookaheads; + + /* Its items. */ + short nitems; + short items[1]; +} state_t; + +#define STATE_ALLOC(Nitems) \ + (state_t *) xcalloc ((unsigned) (sizeof (state_t) \ + + (Nitems - 1) * sizeof (short)), 1) + +#endif /* !STATE_H_ */