]>
Commit | Line | Data |
---|---|---|
ec14f0c8 | 1 | /* Type definitions for nondeterministic finite state machine for Bison. |
03b9e273 | 2 | |
f805dfcb JD |
3 | Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2009 Free |
4 | Software Foundation, Inc. | |
5e893e1c AD |
5 | |
6 | This file is part of Bison, the GNU Compiler Compiler. | |
7 | ||
f16b0819 | 8 | This program is free software: you can redistribute it and/or modify |
5e893e1c | 9 | it under the terms of the GNU General Public License as published by |
f16b0819 PE |
10 | the Free Software Foundation, either version 3 of the License, or |
11 | (at your option) any later version. | |
5e893e1c | 12 | |
f16b0819 | 13 | This program is distributed in the hope that it will be useful, |
5e893e1c AD |
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 | |
f16b0819 | 19 | along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
5e893e1c | 20 | |
2cec9080 | 21 | #include <config.h> |
5e893e1c | 22 | #include "system.h" |
17ee7397 PE |
23 | |
24 | #include <hash.h> | |
25 | ||
df0e7316 | 26 | #include "complain.h" |
62a3e4f0 | 27 | #include "gram.h" |
5e893e1c | 28 | #include "state.h" |
41d7a5f2 | 29 | #include "print-xml.h" |
5e893e1c | 30 | |
df0e7316 AD |
31 | |
32 | /*-------------------. | |
33 | | Shifts and Gotos. | | |
34 | `-------------------*/ | |
35 | ||
36 | ||
03b9e273 PE |
37 | /*-----------------------------------------. |
38 | | Create a new array of NUM shifts/gotos. | | |
39 | `-----------------------------------------*/ | |
2cec70b9 | 40 | |
17ee7397 PE |
41 | static transitions * |
42 | transitions_new (int num, state **the_states) | |
5e893e1c | 43 | { |
03b9e273 PE |
44 | size_t states_size = num * sizeof *the_states; |
45 | transitions *res = xmalloc (offsetof (transitions, states) + states_size); | |
ccaf65bc | 46 | res->num = num; |
03b9e273 | 47 | memcpy (res->states, the_states, states_size); |
5e893e1c AD |
48 | return res; |
49 | } | |
2cec70b9 AD |
50 | |
51 | ||
a737b216 PE |
52 | /*-------------------------------------------------------. |
53 | | Return the state such that SHIFTS contain a shift/goto | | |
54 | | to it on SYM. Abort if none found. | | |
55 | `-------------------------------------------------------*/ | |
24c7d800 | 56 | |
17ee7397 | 57 | state * |
a737b216 | 58 | transitions_to (transitions *shifts, symbol_number sym) |
24c7d800 AD |
59 | { |
60 | int j; | |
c21493b8 PE |
61 | for (j = 0; ; j++) |
62 | { | |
4f82b42a | 63 | aver (j < shifts->num); |
c21493b8 PE |
64 | if (TRANSITION_SYMBOL (shifts, j) == sym) |
65 | return shifts->states[j]; | |
66 | } | |
24c7d800 | 67 | } |
df0e7316 AD |
68 | |
69 | ||
70 | /*--------------------. | |
71 | | Error transitions. | | |
72 | `--------------------*/ | |
73 | ||
74 | ||
03b9e273 PE |
75 | /*---------------------------------. |
76 | | Create a new array of NUM errs. | | |
77 | `---------------------------------*/ | |
2cec70b9 | 78 | |
17ee7397 PE |
79 | errs * |
80 | errs_new (int num, symbol **tokens) | |
2cec70b9 | 81 | { |
03b9e273 PE |
82 | size_t symbols_size = num * sizeof *tokens; |
83 | errs *res = xmalloc (offsetof (errs, symbols) + symbols_size); | |
8b752b00 | 84 | res->num = num; |
03b9e273 | 85 | memcpy (res->symbols, tokens, symbols_size); |
2cec70b9 AD |
86 | return res; |
87 | } | |
80dac38c | 88 | |
df0e7316 AD |
89 | |
90 | ||
91 | ||
92 | /*-------------. | |
93 | | Reductions. | | |
94 | `-------------*/ | |
95 | ||
96 | ||
03b9e273 PE |
97 | /*---------------------------------------. |
98 | | Create a new array of NUM reductions. | | |
99 | `---------------------------------------*/ | |
80dac38c | 100 | |
17ee7397 PE |
101 | static reductions * |
102 | reductions_new (int num, rule **reds) | |
80dac38c | 103 | { |
03b9e273 PE |
104 | size_t rules_size = num * sizeof *reds; |
105 | reductions *res = xmalloc (offsetof (reductions, rules) + rules_size); | |
8b752b00 | 106 | res->num = num; |
742e4900 | 107 | res->lookahead_tokens = NULL; |
03b9e273 | 108 | memcpy (res->rules, reds, rules_size); |
80dac38c AD |
109 | return res; |
110 | } | |
10e5b8bd AD |
111 | |
112 | ||
df0e7316 AD |
113 | |
114 | /*---------. | |
115 | | States. | | |
116 | `---------*/ | |
117 | ||
118 | ||
17ee7397 | 119 | state_number nstates = 0; |
df0e7316 | 120 | /* FINAL_STATE is properly set by new_state when it recognizes its |
88bce5a2 | 121 | accessing symbol: $end. */ |
17ee7397 | 122 | state *final_state = NULL; |
df0e7316 | 123 | |
c7ca99d4 | 124 | |
8b752b00 AD |
125 | /*------------------------------------------------------------------. |
126 | | Create a new state with ACCESSING_SYMBOL, for those items. Store | | |
127 | | it in the state hash table. | | |
128 | `------------------------------------------------------------------*/ | |
df0e7316 | 129 | |
17ee7397 PE |
130 | state * |
131 | state_new (symbol_number accessing_symbol, | |
03b9e273 | 132 | size_t nitems, item_number *core) |
df0e7316 | 133 | { |
17ee7397 | 134 | state *res; |
03b9e273 | 135 | size_t items_size = nitems * sizeof *core; |
df0e7316 | 136 | |
4f82b42a | 137 | aver (nstates < STATE_NUMBER_MAXIMUM); |
df0e7316 | 138 | |
03b9e273 PE |
139 | res = xmalloc (offsetof (state, items) + items_size); |
140 | res->number = nstates++; | |
df0e7316 | 141 | res->accessing_symbol = accessing_symbol; |
03b9e273 PE |
142 | res->transitions = NULL; |
143 | res->reductions = NULL; | |
144 | res->errs = NULL; | |
f805dfcb | 145 | res->state_list = NULL; |
03b9e273 | 146 | res->consistent = 0; |
df0e7316 | 147 | res->solved_conflicts = NULL; |
41d7a5f2 | 148 | res->solved_conflicts_xml = NULL; |
df0e7316 | 149 | |
03b9e273 PE |
150 | res->nitems = nitems; |
151 | memcpy (res->items, core, items_size); | |
df0e7316 | 152 | |
8b752b00 AD |
153 | state_hash_insert (res); |
154 | ||
df0e7316 AD |
155 | return res; |
156 | } | |
157 | ||
f805dfcb JD |
158 | state * |
159 | state_new_isocore (state const *s) | |
160 | { | |
161 | state *res; | |
162 | size_t items_size = s->nitems * sizeof *s->items; | |
163 | ||
164 | aver (nstates < STATE_NUMBER_MAXIMUM); | |
165 | ||
166 | res = xmalloc (offsetof (state, items) + items_size); | |
167 | res->number = nstates++; | |
168 | res->accessing_symbol = s->accessing_symbol; | |
169 | res->transitions = | |
170 | transitions_new (s->transitions->num, s->transitions->states); | |
171 | res->reductions = reductions_new (s->reductions->num, s->reductions->rules); | |
172 | res->errs = NULL; | |
173 | res->state_list = NULL; | |
174 | res->consistent = s->consistent; | |
175 | res->solved_conflicts = NULL; | |
176 | res->solved_conflicts_xml = NULL; | |
177 | ||
178 | res->nitems = s->nitems; | |
179 | memcpy (res->items, s->items, items_size); | |
180 | ||
181 | return res; | |
182 | } | |
183 | ||
df0e7316 | 184 | |
17ee7397 PE |
185 | /*---------. |
186 | | Free S. | | |
187 | `---------*/ | |
8b752b00 AD |
188 | |
189 | static void | |
17ee7397 | 190 | state_free (state *s) |
8b752b00 | 191 | { |
17ee7397 PE |
192 | free (s->transitions); |
193 | free (s->reductions); | |
194 | free (s->errs); | |
195 | free (s); | |
8b752b00 AD |
196 | } |
197 | ||
198 | ||
17ee7397 PE |
199 | /*---------------------------. |
200 | | Set the transitions of S. | | |
201 | `---------------------------*/ | |
32e1e0a4 AD |
202 | |
203 | void | |
17ee7397 | 204 | state_transitions_set (state *s, int num, state **trans) |
32e1e0a4 | 205 | { |
4f82b42a | 206 | aver (!s->transitions); |
17ee7397 | 207 | s->transitions = transitions_new (num, trans); |
32e1e0a4 AD |
208 | } |
209 | ||
210 | ||
17ee7397 PE |
211 | /*--------------------------. |
212 | | Set the reductions of S. | | |
213 | `--------------------------*/ | |
8a731ca8 AD |
214 | |
215 | void | |
17ee7397 | 216 | state_reductions_set (state *s, int num, rule **reds) |
8a731ca8 | 217 | { |
4f82b42a | 218 | aver (!s->reductions); |
17ee7397 | 219 | s->reductions = reductions_new (num, reds); |
8b752b00 AD |
220 | } |
221 | ||
222 | ||
cd08e51e | 223 | int |
17ee7397 | 224 | state_reduction_find (state *s, rule *r) |
cd08e51e AD |
225 | { |
226 | int i; | |
17ee7397 | 227 | reductions *reds = s->reductions; |
cd08e51e | 228 | for (i = 0; i < reds->num; ++i) |
17ee7397 | 229 | if (reds->rules[i] == r) |
cd08e51e AD |
230 | return i; |
231 | return -1; | |
232 | } | |
233 | ||
234 | ||
17ee7397 PE |
235 | /*--------------------. |
236 | | Set the errs of S. | | |
237 | `--------------------*/ | |
8b752b00 AD |
238 | |
239 | void | |
17ee7397 | 240 | state_errs_set (state *s, int num, symbol **tokens) |
8b752b00 | 241 | { |
4f82b42a | 242 | aver (!s->errs); |
17ee7397 | 243 | s->errs = errs_new (num, tokens); |
8a731ca8 AD |
244 | } |
245 | ||
246 | ||
32e1e0a4 | 247 | |
742e4900 JD |
248 | /*--------------------------------------------------. |
249 | | Print on OUT all the lookahead tokens such that S | | |
250 | | wants to reduce R. | | |
251 | `--------------------------------------------------*/ | |
10e5b8bd AD |
252 | |
253 | void | |
742e4900 | 254 | state_rule_lookahead_tokens_print (state *s, rule *r, FILE *out) |
10e5b8bd | 255 | { |
cd08e51e | 256 | /* Find the reduction we are handling. */ |
17ee7397 PE |
257 | reductions *reds = s->reductions; |
258 | int red = state_reduction_find (s, r); | |
10e5b8bd AD |
259 | |
260 | /* Print them if there are. */ | |
742e4900 | 261 | if (reds->lookahead_tokens && red != -1) |
10e5b8bd | 262 | { |
cd08e51e AD |
263 | bitset_iterator biter; |
264 | int k; | |
d0829076 | 265 | char const *sep = ""; |
2f4f028d | 266 | fprintf (out, " ["); |
742e4900 | 267 | BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0) |
d0829076 PE |
268 | { |
269 | fprintf (out, "%s%s", sep, symbols[k]->tag); | |
270 | sep = ", "; | |
271 | } | |
2f4f028d | 272 | fprintf (out, "]"); |
10e5b8bd AD |
273 | } |
274 | } | |
c7ca99d4 | 275 | |
41d7a5f2 PE |
276 | void |
277 | state_rule_lookahead_tokens_print_xml (state *s, rule *r, | |
278 | FILE *out, int level) | |
279 | { | |
280 | /* Find the reduction we are handling. */ | |
281 | reductions *reds = s->reductions; | |
282 | int red = state_reduction_find (s, r); | |
283 | ||
284 | /* Print them if there are. */ | |
285 | if (reds->lookahead_tokens && red != -1) | |
286 | { | |
287 | bitset_iterator biter; | |
288 | int k; | |
41d7a5f2 PE |
289 | xml_puts (out, level, "<lookaheads>"); |
290 | BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0) | |
291 | { | |
408476bc | 292 | xml_printf (out, level + 1, "<symbol>%s</symbol>", |
41d7a5f2 PE |
293 | xml_escape (symbols[k]->tag)); |
294 | } | |
295 | xml_puts (out, level, "</lookaheads>"); | |
296 | } | |
297 | } | |
298 | ||
c7ca99d4 | 299 | |
36b5e963 | 300 | /*---------------------. |
c7ca99d4 | 301 | | A state hash table. | |
36b5e963 | 302 | `---------------------*/ |
c7ca99d4 AD |
303 | |
304 | /* Initial capacity of states hash table. */ | |
305 | #define HT_INITIAL_CAPACITY 257 | |
306 | ||
307 | static struct hash_table *state_table = NULL; | |
308 | ||
309 | /* Two states are equal if they have the same core items. */ | |
03b9e273 | 310 | static inline bool |
17ee7397 | 311 | state_compare (state const *s1, state const *s2) |
c7ca99d4 | 312 | { |
f6fbd3da | 313 | size_t i; |
c7ca99d4 AD |
314 | |
315 | if (s1->nitems != s2->nitems) | |
8307162d | 316 | return false; |
c7ca99d4 AD |
317 | |
318 | for (i = 0; i < s1->nitems; ++i) | |
319 | if (s1->items[i] != s2->items[i]) | |
8307162d | 320 | return false; |
c7ca99d4 | 321 | |
8307162d | 322 | return true; |
c7ca99d4 AD |
323 | } |
324 | ||
03b9e273 PE |
325 | static bool |
326 | state_comparator (void const *s1, void const *s2) | |
327 | { | |
328 | return state_compare (s1, s2); | |
329 | } | |
330 | ||
233a88ad PE |
331 | static inline size_t |
332 | state_hash (state const *s, size_t tablesize) | |
c7ca99d4 AD |
333 | { |
334 | /* Add up the state's item numbers to get a hash key. */ | |
233a88ad | 335 | size_t key = 0; |
f6fbd3da | 336 | size_t i; |
17ee7397 PE |
337 | for (i = 0; i < s->nitems; ++i) |
338 | key += s->items[i]; | |
c7ca99d4 AD |
339 | return key % tablesize; |
340 | } | |
341 | ||
233a88ad PE |
342 | static size_t |
343 | state_hasher (void const *s, size_t tablesize) | |
03b9e273 PE |
344 | { |
345 | return state_hash (s, tablesize); | |
346 | } | |
347 | ||
c7ca99d4 AD |
348 | |
349 | /*-------------------------------. | |
350 | | Create the states hash table. | | |
351 | `-------------------------------*/ | |
352 | ||
353 | void | |
354 | state_hash_new (void) | |
355 | { | |
356 | state_table = hash_initialize (HT_INITIAL_CAPACITY, | |
357 | NULL, | |
03b9e273 PE |
358 | state_hasher, |
359 | state_comparator, | |
360 | NULL); | |
c7ca99d4 AD |
361 | } |
362 | ||
363 | ||
364 | /*---------------------------------------------. | |
365 | | Free the states hash table, not the states. | | |
366 | `---------------------------------------------*/ | |
367 | ||
368 | void | |
369 | state_hash_free (void) | |
370 | { | |
371 | hash_free (state_table); | |
372 | } | |
373 | ||
374 | ||
17ee7397 PE |
375 | /*-----------------------------------. |
376 | | Insert S in the state hash table. | | |
377 | `-----------------------------------*/ | |
c7ca99d4 AD |
378 | |
379 | void | |
17ee7397 | 380 | state_hash_insert (state *s) |
c7ca99d4 | 381 | { |
75c7a52a AD |
382 | if (!hash_insert (state_table, s)) |
383 | xalloc_die (); | |
c7ca99d4 AD |
384 | } |
385 | ||
386 | ||
387 | /*------------------------------------------------------------------. | |
388 | | Find the state associated to the CORE, and return it. If it does | | |
389 | | not exist yet, return NULL. | | |
390 | `------------------------------------------------------------------*/ | |
391 | ||
17ee7397 | 392 | state * |
03b9e273 | 393 | state_hash_lookup (size_t nitems, item_number *core) |
c7ca99d4 | 394 | { |
03b9e273 PE |
395 | size_t items_size = nitems * sizeof *core; |
396 | state *probe = xmalloc (offsetof (state, items) + items_size); | |
17ee7397 | 397 | state *entry; |
c7ca99d4 | 398 | |
03b9e273 PE |
399 | probe->nitems = nitems; |
400 | memcpy (probe->items, core, items_size); | |
c7ca99d4 AD |
401 | entry = hash_lookup (state_table, probe); |
402 | free (probe); | |
403 | return entry; | |
404 | } | |
405 | ||
5967f0cf | 406 | |
14462c2b JD |
407 | /*--------------------------------------------------------. |
408 | | Record S and all states reachable from S in REACHABLE. | | |
409 | `--------------------------------------------------------*/ | |
5967f0cf JD |
410 | |
411 | static void | |
14462c2b | 412 | state_record_reachable_states (state *s, bitset reachable) |
5967f0cf | 413 | { |
14462c2b | 414 | if (bitset_test (reachable, s->number)) |
5967f0cf | 415 | return; |
14462c2b JD |
416 | bitset_set (reachable, s->number); |
417 | { | |
418 | int i; | |
419 | for (i = 0; i < s->transitions->num; ++i) | |
420 | if (!TRANSITION_IS_DISABLED (s->transitions, i)) | |
421 | state_record_reachable_states (s->transitions->states[i], reachable); | |
422 | } | |
5967f0cf JD |
423 | } |
424 | ||
425 | void | |
426 | state_remove_unreachable_states (state_number old_to_new[]) | |
427 | { | |
428 | state_number nstates_reachable = 0; | |
14462c2b JD |
429 | bitset reachable = bitset_create (nstates, BITSET_FIXED); |
430 | state_record_reachable_states (states[0], reachable); | |
431 | { | |
432 | state_number i; | |
433 | for (i = 0; i < nstates; ++i) | |
434 | { | |
435 | if (bitset_test (reachable, states[i]->number)) | |
436 | { | |
437 | states[nstates_reachable] = states[i]; | |
438 | states[nstates_reachable]->number = nstates_reachable; | |
439 | old_to_new[i] = nstates_reachable++; | |
440 | } | |
441 | else | |
442 | { | |
443 | state_free (states[i]); | |
444 | old_to_new[i] = nstates; | |
445 | } | |
446 | } | |
447 | } | |
5967f0cf | 448 | nstates = nstates_reachable; |
14462c2b | 449 | bitset_free (reachable); |
5967f0cf JD |
450 | } |
451 | ||
c7ca99d4 | 452 | /* All the decorated states, indexed by the state number. */ |
17ee7397 | 453 | state **states = NULL; |
c7ca99d4 AD |
454 | |
455 | ||
456 | /*----------------------. | |
457 | | Free all the states. | | |
458 | `----------------------*/ | |
459 | ||
460 | void | |
461 | states_free (void) | |
462 | { | |
17ee7397 | 463 | state_number i; |
c7ca99d4 | 464 | for (i = 0; i < nstates; ++i) |
8b752b00 AD |
465 | state_free (states[i]); |
466 | free (states); | |
c7ca99d4 | 467 | } |