1 /* Type definitions for nondeterministic finite state machine for Bison. 2 3 Copyright (C) 1984, 1989, 2000, 2001, 2002, 2003, 2004 Free 4 Software Foundation, Inc. 5 6 This file is part of Bison, the GNU Compiler Compiler. 7 8 Bison is free software; you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 2, or (at your option) 11 any later version. 12 13 Bison is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with Bison; see the file COPYING. If not, write to 20 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 21 Boston, MA 02110-1301, USA. */ 22 23 24 /* These type definitions are used to represent a nondeterministic 25 finite state machine that parses the specified grammar. This 26 information is generated by the function generate_states in the 27 file LR0. 28 29 Each state of the machine is described by a set of items -- 30 particular positions in particular rules -- that are the possible 31 places where parsing could continue when the machine is in this 32 state. These symbols at these items are the allowable inputs that 33 can follow now. 34 35 A core represents one state. States are numbered in the NUMBER 36 field. When generate_states is finished, the starting state is 37 state 0 and NSTATES is the number of states. (FIXME: This sentence 38 is no longer true: A transition to a state whose state number is 39 NSTATES indicates termination.) All the cores are chained together 40 and FIRST_STATE points to the first one (state 0). 41 42 For each state there is a particular symbol which must have been 43 the last thing accepted to reach that state. It is the 44 ACCESSING_SYMBOL of the core. 45 46 Each core contains a vector of NITEMS items which are the indices 47 in the RITEMS vector of the items that are selected in this state. 48 49 The two types of actions are shifts/gotos (push the look-ahead token 50 and read another/goto to the state designated by a nterm) and 51 reductions (combine the last n things on the stack via a rule, 52 replace them with the symbol that the rule derives, and leave the 53 look-ahead token alone). When the states are generated, these 54 actions are represented in two other lists. 55 56 Each transition structure describes the possible transitions out 57 of one state, the state whose number is in the number field. Each 58 contains a vector of numbers of the states that transitions can go 59 to. The accessing_symbol fields of those states' cores say what 60 kind of input leads to them. 61 62 A transition to state zero should be ignored: conflict resolution 63 deletes transitions by having them point to zero. 64 65 Each reductions structure describes the possible reductions at the 66 state whose number is in the number field. The data is a list of 67 nreds rules, represented by their rule numbers. first_reduction 68 points to the list of these structures. 69 70 Conflict resolution can decide that certain tokens in certain 71 states should explicitly be errors (for implementing %nonassoc). 72 For each state, the tokens that are errors for this reason are 73 recorded in an errs structure, which holds the token numbers. 74 75 There is at least one goto transition present in state zero. It 76 leads to a next-to-final state whose accessing_symbol is the 77 grammar's start symbol. The next-to-final state has one shift to 78 the final state, whose accessing_symbol is zero (end of input). 79 The final state has one shift, which goes to the termination state. 80 The reason for the extra state at the end is to placate the 81 parser's strategy of making all decisions one token ahead of its 82 actions. */ 83 84 #ifndef STATE_H_ 85 # define STATE_H_ 86 87 # include <bitset.h> 88 89 # include "gram.h" 90 # include "symtab.h" 91 92 93 /*-------------------. 94 | Numbering states. | 95 `-------------------*/ 96 97 typedef int state_number; 98 # define STATE_NUMBER_MAXIMUM INT_MAX 99 100 /* Be ready to map a state_number to an int. */ 101 static inline int 102 state_number_as_int (state_number s) 103 { 104 return s; 105 } 106 107 108 typedef struct state state; 109 110 /*--------------. 111 | Transitions. | 112 `--------------*/ 113 114 typedef struct 115 { 116 int num; 117 state *states[1]; 118 } transitions; 119 120 121 /* What is the symbol labelling the transition to 122 TRANSITIONS->states[Num]? Can be a token (amongst which the error 123 token), or non terminals in case of gotos. */ 124 125 #define TRANSITION_SYMBOL(Transitions, Num) \ 126 (Transitions->states[Num]->accessing_symbol) 127 128 /* Is the TRANSITIONS->states[Num] a shift? (as opposed to gotos). */ 129 130 #define TRANSITION_IS_SHIFT(Transitions, Num) \ 131 (ISTOKEN (TRANSITION_SYMBOL (Transitions, Num))) 132 133 /* Is the TRANSITIONS->states[Num] a goto?. */ 134 135 #define TRANSITION_IS_GOTO(Transitions, Num) \ 136 (!TRANSITION_IS_SHIFT (Transitions, Num)) 137 138 /* Is the TRANSITIONS->states[Num] labelled by the error token? */ 139 140 #define TRANSITION_IS_ERROR(Transitions, Num) \ 141 (TRANSITION_SYMBOL (Transitions, Num) == errtoken->number) 142 143 /* When resolving a SR conflicts, if the reduction wins, the shift is 144 disabled. */ 145 146 #define TRANSITION_DISABLE(Transitions, Num) \ 147 (Transitions->states[Num] = NULL) 148 149 #define TRANSITION_IS_DISABLED(Transitions, Num) \ 150 (Transitions->states[Num] == NULL) 151 152 153 /* Iterate over each transition over a token (shifts). */ 154 #define FOR_EACH_SHIFT(Transitions, Iter) \ 155 for (Iter = 0; \ 156 Iter < Transitions->num \ 157 && (TRANSITION_IS_DISABLED (Transitions, Iter) \ 158 || TRANSITION_IS_SHIFT (Transitions, Iter)); \ 159 ++Iter) \ 160 if (!TRANSITION_IS_DISABLED (Transitions, Iter)) 161 162 163 /* Return the state such SHIFTS contain a shift/goto to it on SYM. 164 Abort if none found. */ 165 struct state *transitions_to (transitions *shifts, symbol_number sym); 166 167 168 /*-------. 169 | Errs. | 170 `-------*/ 171 172 typedef struct 173 { 174 int num; 175 symbol *symbols[1]; 176 } errs; 177 178 errs *errs_new (int num, symbol **tokens); 179 180 181 /*-------------. 182 | Reductions. | 183 `-------------*/ 184 185 typedef struct 186 { 187 int num; 188 bitset *look_ahead_tokens; 189 rule *rules[1]; 190 } reductions; 191 192 193 194 /*---------. 195 | states. | 196 `---------*/ 197 198 struct state 199 { 200 state_number number; 201 symbol_number accessing_symbol; 202 transitions *transitions; 203 reductions *reductions; 204 errs *errs; 205 206 /* Nonzero if no look-ahead is needed to decide what to do in state S. */ 207 char consistent; 208 209 /* If some conflicts were solved thanks to precedence/associativity, 210 a human readable description of the resolution. */ 211 const char *solved_conflicts; 212 213 /* Its items. Must be last, since ITEMS can be arbitrarily large. 214 */ 215 size_t nitems; 216 item_number items[1]; 217 }; 218 219 extern state_number nstates; 220 extern state *final_state; 221 222 /* Create a new state with ACCESSING_SYMBOL for those items. */ 223 state *state_new (symbol_number accessing_symbol, 224 size_t core_size, item_number *core); 225 226 /* Set the transitions of STATE. */ 227 void state_transitions_set (state *s, int num, state **trans); 228 229 /* Set the reductions of STATE. */ 230 void state_reductions_set (state *s, int num, rule **reds); 231 232 int state_reduction_find (state *s, rule *r); 233 234 /* Set the errs of STATE. */ 235 void state_errs_set (state *s, int num, symbol **errors); 236 237 /* Print on OUT all the look-ahead tokens such that this STATE wants to 238 reduce R. */ 239 void state_rule_look_ahead_tokens_print (state *s, rule *r, FILE *out); 240 241 /* Create/destroy the states hash table. */ 242 void state_hash_new (void); 243 void state_hash_free (void); 244 245 /* Find the state associated to the CORE, and return it. If it does 246 not exist yet, return NULL. */ 247 state *state_hash_lookup (size_t core_size, item_number *core); 248 249 /* Insert STATE in the state hash table. */ 250 void state_hash_insert (state *s); 251 252 /* All the states, indexed by the state number. */ 253 extern state **states; 254 255 /* Free all the states. */ 256 void states_free (void); 257 #endif /* !STATE_H_ */ 258
