OLD | NEW |
(Empty) | |
| 1 /* Type definitions for nondeterministic finite state machine for Bison. |
| 2 |
| 3 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 Free Software |
| 4 Foundation, Inc. |
| 5 |
| 6 This file is part of Bison, the GNU Compiler Compiler. |
| 7 |
| 8 This program 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 3 of the License, or |
| 11 (at your option) any later version. |
| 12 |
| 13 This program 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 this program. If not, see <http://www.gnu.org/licenses/>. */ |
| 20 |
| 21 #include <config.h> |
| 22 #include "system.h" |
| 23 |
| 24 #include <hash.h> |
| 25 |
| 26 #include "complain.h" |
| 27 #include "gram.h" |
| 28 #include "state.h" |
| 29 #include "print-xml.h" |
| 30 |
| 31 |
| 32 /*-------------------. |
| 33 | Shifts and Gotos. | |
| 34 `-------------------*/ |
| 35 |
| 36 |
| 37 /*-----------------------------------------. |
| 38 | Create a new array of NUM shifts/gotos. | |
| 39 `-----------------------------------------*/ |
| 40 |
| 41 static transitions * |
| 42 transitions_new (int num, state **the_states) |
| 43 { |
| 44 size_t states_size = num * sizeof *the_states; |
| 45 transitions *res = xmalloc (offsetof (transitions, states) + states_size); |
| 46 res->num = num; |
| 47 memcpy (res->states, the_states, states_size); |
| 48 return res; |
| 49 } |
| 50 |
| 51 |
| 52 /*-------------------------------------------------------. |
| 53 | Return the state such that SHIFTS contain a shift/goto | |
| 54 | to it on SYM. Abort if none found. | |
| 55 `-------------------------------------------------------*/ |
| 56 |
| 57 state * |
| 58 transitions_to (transitions *shifts, symbol_number sym) |
| 59 { |
| 60 int j; |
| 61 for (j = 0; ; j++) |
| 62 { |
| 63 aver (j < shifts->num); |
| 64 if (TRANSITION_SYMBOL (shifts, j) == sym) |
| 65 return shifts->states[j]; |
| 66 } |
| 67 } |
| 68 |
| 69 |
| 70 /*--------------------. |
| 71 | Error transitions. | |
| 72 `--------------------*/ |
| 73 |
| 74 |
| 75 /*---------------------------------. |
| 76 | Create a new array of NUM errs. | |
| 77 `---------------------------------*/ |
| 78 |
| 79 errs * |
| 80 errs_new (int num, symbol **tokens) |
| 81 { |
| 82 size_t symbols_size = num * sizeof *tokens; |
| 83 errs *res = xmalloc (offsetof (errs, symbols) + symbols_size); |
| 84 res->num = num; |
| 85 memcpy (res->symbols, tokens, symbols_size); |
| 86 return res; |
| 87 } |
| 88 |
| 89 |
| 90 |
| 91 |
| 92 /*-------------. |
| 93 | Reductions. | |
| 94 `-------------*/ |
| 95 |
| 96 |
| 97 /*---------------------------------------. |
| 98 | Create a new array of NUM reductions. | |
| 99 `---------------------------------------*/ |
| 100 |
| 101 static reductions * |
| 102 reductions_new (int num, rule **reds) |
| 103 { |
| 104 size_t rules_size = num * sizeof *reds; |
| 105 reductions *res = xmalloc (offsetof (reductions, rules) + rules_size); |
| 106 res->num = num; |
| 107 res->lookahead_tokens = NULL; |
| 108 memcpy (res->rules, reds, rules_size); |
| 109 return res; |
| 110 } |
| 111 |
| 112 |
| 113 |
| 114 /*---------. |
| 115 | States. | |
| 116 `---------*/ |
| 117 |
| 118 |
| 119 state_number nstates = 0; |
| 120 /* FINAL_STATE is properly set by new_state when it recognizes its |
| 121 accessing symbol: $end. */ |
| 122 state *final_state = NULL; |
| 123 |
| 124 |
| 125 /*------------------------------------------------------------------. |
| 126 | Create a new state with ACCESSING_SYMBOL, for those items. Store | |
| 127 | it in the state hash table. | |
| 128 `------------------------------------------------------------------*/ |
| 129 |
| 130 state * |
| 131 state_new (symbol_number accessing_symbol, |
| 132 size_t nitems, item_number *core) |
| 133 { |
| 134 state *res; |
| 135 size_t items_size = nitems * sizeof *core; |
| 136 |
| 137 aver (nstates < STATE_NUMBER_MAXIMUM); |
| 138 |
| 139 res = xmalloc (offsetof (state, items) + items_size); |
| 140 res->number = nstates++; |
| 141 res->accessing_symbol = accessing_symbol; |
| 142 res->transitions = NULL; |
| 143 res->reductions = NULL; |
| 144 res->errs = NULL; |
| 145 res->consistent = 0; |
| 146 res->solved_conflicts = NULL; |
| 147 res->solved_conflicts_xml = 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 aver (!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 aver (!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 aver (!s->errs); |
| 216 s->errs = errs_new (num, tokens); |
| 217 } |
| 218 |
| 219 |
| 220 |
| 221 /*--------------------------------------------------. |
| 222 | Print on OUT all the lookahead tokens such that S | |
| 223 | wants to reduce R. | |
| 224 `--------------------------------------------------*/ |
| 225 |
| 226 void |
| 227 state_rule_lookahead_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->lookahead_tokens && red != -1) |
| 235 { |
| 236 bitset_iterator biter; |
| 237 int k; |
| 238 char const *sep = ""; |
| 239 fprintf (out, " ["); |
| 240 BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0) |
| 241 { |
| 242 fprintf (out, "%s%s", sep, symbols[k]->tag); |
| 243 sep = ", "; |
| 244 } |
| 245 fprintf (out, "]"); |
| 246 } |
| 247 } |
| 248 |
| 249 void |
| 250 state_rule_lookahead_tokens_print_xml (state *s, rule *r, |
| 251 FILE *out, int level) |
| 252 { |
| 253 /* Find the reduction we are handling. */ |
| 254 reductions *reds = s->reductions; |
| 255 int red = state_reduction_find (s, r); |
| 256 |
| 257 /* Print them if there are. */ |
| 258 if (reds->lookahead_tokens && red != -1) |
| 259 { |
| 260 bitset_iterator biter; |
| 261 int k; |
| 262 xml_puts (out, level, "<lookaheads>"); |
| 263 BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0) |
| 264 { |
| 265 xml_printf (out, level + 1, "<symbol>%s</symbol>", |
| 266 xml_escape (symbols[k]->tag)); |
| 267 } |
| 268 xml_puts (out, level, "</lookaheads>"); |
| 269 } |
| 270 } |
| 271 |
| 272 |
| 273 /*---------------------. |
| 274 | A state hash table. | |
| 275 `---------------------*/ |
| 276 |
| 277 /* Initial capacity of states hash table. */ |
| 278 #define HT_INITIAL_CAPACITY 257 |
| 279 |
| 280 static struct hash_table *state_table = NULL; |
| 281 |
| 282 /* Two states are equal if they have the same core items. */ |
| 283 static inline bool |
| 284 state_compare (state const *s1, state const *s2) |
| 285 { |
| 286 size_t i; |
| 287 |
| 288 if (s1->nitems != s2->nitems) |
| 289 return false; |
| 290 |
| 291 for (i = 0; i < s1->nitems; ++i) |
| 292 if (s1->items[i] != s2->items[i]) |
| 293 return false; |
| 294 |
| 295 return true; |
| 296 } |
| 297 |
| 298 static bool |
| 299 state_comparator (void const *s1, void const *s2) |
| 300 { |
| 301 return state_compare (s1, s2); |
| 302 } |
| 303 |
| 304 static inline size_t |
| 305 state_hash (state const *s, size_t tablesize) |
| 306 { |
| 307 /* Add up the state's item numbers to get a hash key. */ |
| 308 size_t key = 0; |
| 309 size_t i; |
| 310 for (i = 0; i < s->nitems; ++i) |
| 311 key += s->items[i]; |
| 312 return key % tablesize; |
| 313 } |
| 314 |
| 315 static size_t |
| 316 state_hasher (void const *s, size_t tablesize) |
| 317 { |
| 318 return state_hash (s, tablesize); |
| 319 } |
| 320 |
| 321 |
| 322 /*-------------------------------. |
| 323 | Create the states hash table. | |
| 324 `-------------------------------*/ |
| 325 |
| 326 void |
| 327 state_hash_new (void) |
| 328 { |
| 329 state_table = hash_initialize (HT_INITIAL_CAPACITY, |
| 330 NULL, |
| 331 state_hasher, |
| 332 state_comparator, |
| 333 NULL); |
| 334 } |
| 335 |
| 336 |
| 337 /*---------------------------------------------. |
| 338 | Free the states hash table, not the states. | |
| 339 `---------------------------------------------*/ |
| 340 |
| 341 void |
| 342 state_hash_free (void) |
| 343 { |
| 344 hash_free (state_table); |
| 345 } |
| 346 |
| 347 |
| 348 /*-----------------------------------. |
| 349 | Insert S in the state hash table. | |
| 350 `-----------------------------------*/ |
| 351 |
| 352 void |
| 353 state_hash_insert (state *s) |
| 354 { |
| 355 hash_insert (state_table, s); |
| 356 } |
| 357 |
| 358 |
| 359 /*------------------------------------------------------------------. |
| 360 | Find the state associated to the CORE, and return it. If it does | |
| 361 | not exist yet, return NULL. | |
| 362 `------------------------------------------------------------------*/ |
| 363 |
| 364 state * |
| 365 state_hash_lookup (size_t nitems, item_number *core) |
| 366 { |
| 367 size_t items_size = nitems * sizeof *core; |
| 368 state *probe = xmalloc (offsetof (state, items) + items_size); |
| 369 state *entry; |
| 370 |
| 371 probe->nitems = nitems; |
| 372 memcpy (probe->items, core, items_size); |
| 373 entry = hash_lookup (state_table, probe); |
| 374 free (probe); |
| 375 return entry; |
| 376 } |
| 377 |
| 378 |
| 379 /*--------------------------------------------------------. |
| 380 | Record S and all states reachable from S in REACHABLE. | |
| 381 `--------------------------------------------------------*/ |
| 382 |
| 383 static void |
| 384 state_record_reachable_states (state *s, bitset reachable) |
| 385 { |
| 386 if (bitset_test (reachable, s->number)) |
| 387 return; |
| 388 bitset_set (reachable, s->number); |
| 389 { |
| 390 int i; |
| 391 for (i = 0; i < s->transitions->num; ++i) |
| 392 if (!TRANSITION_IS_DISABLED (s->transitions, i)) |
| 393 state_record_reachable_states (s->transitions->states[i], reachable); |
| 394 } |
| 395 } |
| 396 |
| 397 void |
| 398 state_remove_unreachable_states (state_number old_to_new[]) |
| 399 { |
| 400 state_number nstates_reachable = 0; |
| 401 bitset reachable = bitset_create (nstates, BITSET_FIXED); |
| 402 state_record_reachable_states (states[0], reachable); |
| 403 { |
| 404 state_number i; |
| 405 for (i = 0; i < nstates; ++i) |
| 406 { |
| 407 if (bitset_test (reachable, states[i]->number)) |
| 408 { |
| 409 states[nstates_reachable] = states[i]; |
| 410 states[nstates_reachable]->number = nstates_reachable; |
| 411 old_to_new[i] = nstates_reachable++; |
| 412 } |
| 413 else |
| 414 { |
| 415 state_free (states[i]); |
| 416 old_to_new[i] = nstates; |
| 417 } |
| 418 } |
| 419 } |
| 420 nstates = nstates_reachable; |
| 421 bitset_free (reachable); |
| 422 } |
| 423 |
| 424 /* All the decorated states, indexed by the state number. */ |
| 425 state **states = NULL; |
| 426 |
| 427 |
| 428 /*----------------------. |
| 429 | Free all the states. | |
| 430 `----------------------*/ |
| 431 |
| 432 void |
| 433 states_free (void) |
| 434 { |
| 435 state_number i; |
| 436 for (i = 0; i < nstates; ++i) |
| 437 state_free (states[i]); |
| 438 free (states); |
| 439 } |
OLD | NEW |