1 /* Type definitions for nondeterministic finite state machine for Bison. 2 3 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 Free Software 4 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 #include <config.h> 24 #include "system.h" 25 26 #include <hash.h> 27 28 #include "complain.h" 29 #include "gram.h" 30 #include "state.h" 31 32 33 /*-------------------. 34 | Shifts and Gotos. | 35 `-------------------*/ 36 37 38 /*-----------------------------------------. 39 | Create a new array of NUM shifts/gotos. | 40 `-----------------------------------------*/ 41 42 static transitions * 43 transitions_new (int num, state **the_states) 44 { 45 size_t states_size = num * sizeof *the_states; 46 transitions *res = xmalloc (offsetof (transitions, states) + states_size); 47 res->num = num; 48 memcpy (res->states, the_states, states_size); 49 return res; 50 } 51 52 53 /*-------------------------------------------------------. 54 | Return the state such that SHIFTS contain a shift/goto | 55 | to it on SYM. Abort if none found. | 56 `-------------------------------------------------------*/ 57 58 state * 59 transitions_to (transitions *shifts, symbol_number sym) 60 { 61 int j; 62 for (j = 0; ; j++) 63 { 64 assert (j < shifts->num); 65 if (TRANSITION_SYMBOL (shifts, j) == sym) 66 return shifts->states[j]; 67 } 68 } 69 70 71 /*--------------------. 72 | Error transitions. | 73 `--------------------*/ 74 75 76 /*---------------------------------. 77 | Create a new array of NUM errs. | 78 `---------------------------------*/ 79 80 errs * 81 errs_new (int num, symbol **tokens) 82 { 83 size_t symbols_size = num * sizeof *tokens; 84 errs *res = xmalloc (offsetof (errs, symbols) + symbols_size); 85 res->num = num; 86 memcpy (res->symbols, tokens, symbols_size); 87 return res; 88 } 89 90 91 92 93 /*-------------. 94 | Reductions. | 95 `-------------*/ 96 97 98 /*---------------------------------------. 99 | Create a new array of NUM reductions. | 100 `---------------------------------------*/ 101 102 static reductions * 103 reductions_new (int num, rule **reds) 104 { 105 size_t rules_size = num * sizeof *reds; 106 reductions *res = xmalloc (offsetof (reductions, rules) + rules_size); 107 res->num = num; 108 res->look_ahead_tokens = NULL; 109 memcpy (res->rules, reds, rules_size); 110 return res; 111 } 112 113 114 115 /*---------. 116 | States. | 117 `---------*/ 118 119 120 state_number nstates = 0; 121 /* FINAL_STATE is properly set by new_state when it recognizes its 122 accessing symbol: $end. */ 123 state *final_state = NULL; 124 125 126 /*------------------------------------------------------------------. 127 | Create a new state with ACCESSING_SYMBOL, for those items. Store | 128 | it in the state hash table. | 129 `------------------------------------------------------------------*/ 130 131 state * 132 state_new (symbol_number accessing_symbol, 133 size_t nitems, item_number *core) 134 { 135 state *res; 136 size_t items_size = nitems * sizeof *core; 137 138 assert (nstates < STATE_NUMBER_MAXIMUM); 139 140 res = xmalloc (offsetof (state, items) + items_size); 141 res->number = nstates++; 142 res->accessing_symbol = accessing_symbol; 143 res->transitions = NULL; 144 res->reductions = NULL; 145 res->errs = NULL; 146 res->consistent = 0; 147 res->solved_conflicts = NULL; 148 149 res->nitems = nitems; 150 memcpy (res->items, core, items_size); 151 152 state_hash_insert (res); 153 154 return res; 155 } 156 157 158 /*---------. 159 | Free S. | 160 `---------*/ 161 162 static void 163 state_free (state *s) 164 { 165 free (s->transitions); 166 free (s->reductions); 167 free (s->errs); 168 free (s); 169 } 170 171 172 /*---------------------------. 173 | Set the transitions of S. | 174 `---------------------------*/ 175 176 void 177 state_transitions_set (state *s, int num, state **trans) 178 { 179 assert (!s->transitions); 180 s->transitions = transitions_new (num, trans); 181 } 182 183 184 /*--------------------------. 185 | Set the reductions of S. | 186 `--------------------------*/ 187 188 void 189 state_reductions_set (state *s, int num, rule **reds) 190 { 191 assert (!s->reductions); 192 s->reductions = reductions_new (num, reds); 193 } 194 195 196 int 197 state_reduction_find (state *s, rule *r) 198 { 199 int i; 200 reductions *reds = s->reductions; 201 for (i = 0; i < reds->num; ++i) 202 if (reds->rules[i] == r) 203 return i; 204 return -1; 205 } 206 207 208 /*--------------------. 209 | Set the errs of S. | 210 `--------------------*/ 211 212 void 213 state_errs_set (state *s, int num, symbol **tokens) 214 { 215 assert (!s->errs); 216 s->errs = errs_new (num, tokens); 217 } 218 219 220 221 /*---------------------------------------------------. 222 | Print on OUT all the look-ahead tokens such that S | 223 | wants to reduce R. | 224 `---------------------------------------------------*/ 225 226 void 227 state_rule_look_ahead_tokens_print (state *s, rule *r, FILE *out) 228 { 229 /* Find the reduction we are handling. */ 230 reductions *reds = s->reductions; 231 int red = state_reduction_find (s, r); 232 233 /* Print them if there are. */ 234 if (reds->look_ahead_tokens && red != -1) 235 { 236 bitset_iterator biter; 237 int k; 238 char const *sep = ""; 239 fprintf (out, " ["); 240 BITSET_FOR_EACH (biter, reds->look_ahead_tokens[red], k, 0) 241 { 242 fprintf (out, "%s%s", sep, symbols[k]->tag); 243 sep = ", "; 244 } 245 fprintf (out, "]"); 246 } 247 } 248 249 250 /*---------------------. 251 | A state hash table. | 252 `---------------------*/ 253 254 /* Initial capacity of states hash table. */ 255 #define HT_INITIAL_CAPACITY 257 256 257 static struct hash_table *state_table = NULL; 258 259 /* Two states are equal if they have the same core items. */ 260 static inline bool 261 state_compare (state const *s1, state const *s2) 262 { 263 size_t i; 264 265 if (s1->nitems != s2->nitems) 266 return false; 267 268 for (i = 0; i < s1->nitems; ++i) 269 if (s1->items[i] != s2->items[i]) 270 return false; 271 272 return true; 273 } 274 275 static bool 276 state_comparator (void const *s1, void const *s2) 277 { 278 return state_compare (s1, s2); 279 } 280 281 static inline size_t 282 state_hash (state const *s, size_t tablesize) 283 { 284 /* Add up the state's item numbers to get a hash key. */ 285 size_t key = 0; 286 size_t i; 287 for (i = 0; i < s->nitems; ++i) 288 key += s->items[i]; 289 return key % tablesize; 290 } 291 292 static size_t 293 state_hasher (void const *s, size_t tablesize) 294 { 295 return state_hash (s, tablesize); 296 } 297 298 299 /*-------------------------------. 300 | Create the states hash table. | 301 `-------------------------------*/ 302 303 void 304 state_hash_new (void) 305 { 306 state_table = hash_initialize (HT_INITIAL_CAPACITY, 307 NULL, 308 state_hasher, 309 state_comparator, 310 NULL); 311 } 312 313 314 /*---------------------------------------------. 315 | Free the states hash table, not the states. | 316 `---------------------------------------------*/ 317 318 void 319 state_hash_free (void) 320 { 321 hash_free (state_table); 322 } 323 324 325 /*-----------------------------------. 326 | Insert S in the state hash table. | 327 `-----------------------------------*/ 328 329 void 330 state_hash_insert (state *s) 331 { 332 hash_insert (state_table, s); 333 } 334 335 336 /*------------------------------------------------------------------. 337 | Find the state associated to the CORE, and return it. If it does | 338 | not exist yet, return NULL. | 339 `------------------------------------------------------------------*/ 340 341 state * 342 state_hash_lookup (size_t nitems, item_number *core) 343 { 344 size_t items_size = nitems * sizeof *core; 345 state *probe = xmalloc (offsetof (state, items) + items_size); 346 state *entry; 347 348 probe->nitems = nitems; 349 memcpy (probe->items, core, items_size); 350 entry = hash_lookup (state_table, probe); 351 free (probe); 352 return entry; 353 } 354 355 /* All the decorated states, indexed by the state number. */ 356 state **states = NULL; 357 358 359 /*----------------------. 360 | Free all the states. | 361 `----------------------*/ 362 363 void 364 states_free (void) 365 { 366 state_number i; 367 for (i = 0; i < nstates; ++i) 368 state_free (states[i]); 369 free (states); 370 } 371
