Commit | Line | Data |
---|---|---|
ec14f0c8 | 1 | /* Type definitions for nondeterministic finite state machine for Bison. |
03b9e273 | 2 | |
75ad86ee | 3 | Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 Free Software |
c21493b8 | 4 | 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; | |
145 | res->consistent = 0; | |
df0e7316 | 146 | res->solved_conflicts = NULL; |
41d7a5f2 | 147 | res->solved_conflicts_xml = NULL; |
df0e7316 | 148 | |
03b9e273 PE |
149 | res->nitems = nitems; |
150 | memcpy (res->items, core, items_size); | |
df0e7316 | 151 | |
8b752b00 AD |
152 | state_hash_insert (res); |
153 | ||
df0e7316 AD |
154 | return res; |
155 | } | |
156 | ||
157 | ||
17ee7397 PE |
158 | /*---------. |
159 | | Free S. | | |
160 | `---------*/ | |
8b752b00 AD |
161 | |
162 | static void | |
17ee7397 | 163 | state_free (state *s) |
8b752b00 | 164 | { |
17ee7397 PE |
165 | free (s->transitions); |
166 | free (s->reductions); | |
167 | free (s->errs); | |
168 | free (s); | |
8b752b00 AD |
169 | } |
170 | ||
171 | ||
17ee7397 PE |
172 | /*---------------------------. |
173 | | Set the transitions of S. | | |
174 | `---------------------------*/ | |
32e1e0a4 AD |
175 | |
176 | void | |
17ee7397 | 177 | state_transitions_set (state *s, int num, state **trans) |
32e1e0a4 | 178 | { |
4f82b42a | 179 | aver (!s->transitions); |
17ee7397 | 180 | s->transitions = transitions_new (num, trans); |
32e1e0a4 AD |
181 | } |
182 | ||
183 | ||
17ee7397 PE |
184 | /*--------------------------. |
185 | | Set the reductions of S. | | |
186 | `--------------------------*/ | |
8a731ca8 AD |
187 | |
188 | void | |
17ee7397 | 189 | state_reductions_set (state *s, int num, rule **reds) |
8a731ca8 | 190 | { |
4f82b42a | 191 | aver (!s->reductions); |
17ee7397 | 192 | s->reductions = reductions_new (num, reds); |
8b752b00 AD |
193 | } |
194 | ||
195 | ||
cd08e51e | 196 | int |
17ee7397 | 197 | state_reduction_find (state *s, rule *r) |
cd08e51e AD |
198 | { |
199 | int i; | |
17ee7397 | 200 | reductions *reds = s->reductions; |
cd08e51e | 201 | for (i = 0; i < reds->num; ++i) |
17ee7397 | 202 | if (reds->rules[i] == r) |
cd08e51e AD |
203 | return i; |
204 | return -1; | |
205 | } | |
206 | ||
207 | ||
17ee7397 PE |
208 | /*--------------------. |
209 | | Set the errs of S. | | |
210 | `--------------------*/ | |
8b752b00 AD |
211 | |
212 | void | |
17ee7397 | 213 | state_errs_set (state *s, int num, symbol **tokens) |
8b752b00 | 214 | { |
4f82b42a | 215 | aver (!s->errs); |
17ee7397 | 216 | s->errs = errs_new (num, tokens); |
8a731ca8 AD |
217 | } |
218 | ||
219 | ||
32e1e0a4 | 220 | |
742e4900 JD |
221 | /*--------------------------------------------------. |
222 | | Print on OUT all the lookahead tokens such that S | | |
223 | | wants to reduce R. | | |
224 | `--------------------------------------------------*/ | |
10e5b8bd AD |
225 | |
226 | void | |
742e4900 | 227 | state_rule_lookahead_tokens_print (state *s, rule *r, FILE *out) |
10e5b8bd | 228 | { |
cd08e51e | 229 | /* Find the reduction we are handling. */ |
17ee7397 PE |
230 | reductions *reds = s->reductions; |
231 | int red = state_reduction_find (s, r); | |
10e5b8bd AD |
232 | |
233 | /* Print them if there are. */ | |
742e4900 | 234 | if (reds->lookahead_tokens && red != -1) |
10e5b8bd | 235 | { |
cd08e51e AD |
236 | bitset_iterator biter; |
237 | int k; | |
d0829076 | 238 | char const *sep = ""; |
2f4f028d | 239 | fprintf (out, " ["); |
742e4900 | 240 | BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0) |
d0829076 PE |
241 | { |
242 | fprintf (out, "%s%s", sep, symbols[k]->tag); | |
243 | sep = ", "; | |
244 | } | |
2f4f028d | 245 | fprintf (out, "]"); |
10e5b8bd AD |
246 | } |
247 | } | |
c7ca99d4 | 248 | |
41d7a5f2 PE |
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; | |
41d7a5f2 PE |
262 | xml_puts (out, level, "<lookaheads>"); |
263 | BITSET_FOR_EACH (biter, reds->lookahead_tokens[red], k, 0) | |
264 | { | |
408476bc | 265 | xml_printf (out, level + 1, "<symbol>%s</symbol>", |
41d7a5f2 PE |
266 | xml_escape (symbols[k]->tag)); |
267 | } | |
268 | xml_puts (out, level, "</lookaheads>"); | |
269 | } | |
270 | } | |
271 | ||
c7ca99d4 | 272 | |
36b5e963 | 273 | /*---------------------. |
c7ca99d4 | 274 | | A state hash table. | |
36b5e963 | 275 | `---------------------*/ |
c7ca99d4 AD |
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. */ | |
03b9e273 | 283 | static inline bool |
17ee7397 | 284 | state_compare (state const *s1, state const *s2) |
c7ca99d4 | 285 | { |
f6fbd3da | 286 | size_t i; |
c7ca99d4 AD |
287 | |
288 | if (s1->nitems != s2->nitems) | |
8307162d | 289 | return false; |
c7ca99d4 AD |
290 | |
291 | for (i = 0; i < s1->nitems; ++i) | |
292 | if (s1->items[i] != s2->items[i]) | |
8307162d | 293 | return false; |
c7ca99d4 | 294 | |
8307162d | 295 | return true; |
c7ca99d4 AD |
296 | } |
297 | ||
03b9e273 PE |
298 | static bool |
299 | state_comparator (void const *s1, void const *s2) | |
300 | { | |
301 | return state_compare (s1, s2); | |
302 | } | |
303 | ||
233a88ad PE |
304 | static inline size_t |
305 | state_hash (state const *s, size_t tablesize) | |
c7ca99d4 AD |
306 | { |
307 | /* Add up the state's item numbers to get a hash key. */ | |
233a88ad | 308 | size_t key = 0; |
f6fbd3da | 309 | size_t i; |
17ee7397 PE |
310 | for (i = 0; i < s->nitems; ++i) |
311 | key += s->items[i]; | |
c7ca99d4 AD |
312 | return key % tablesize; |
313 | } | |
314 | ||
233a88ad PE |
315 | static size_t |
316 | state_hasher (void const *s, size_t tablesize) | |
03b9e273 PE |
317 | { |
318 | return state_hash (s, tablesize); | |
319 | } | |
320 | ||
c7ca99d4 AD |
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, | |
03b9e273 PE |
331 | state_hasher, |
332 | state_comparator, | |
333 | NULL); | |
c7ca99d4 AD |
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 | ||
17ee7397 PE |
348 | /*-----------------------------------. |
349 | | Insert S in the state hash table. | | |
350 | `-----------------------------------*/ | |
c7ca99d4 AD |
351 | |
352 | void | |
17ee7397 | 353 | state_hash_insert (state *s) |
c7ca99d4 | 354 | { |
17ee7397 | 355 | hash_insert (state_table, s); |
c7ca99d4 AD |
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 | ||
17ee7397 | 364 | state * |
03b9e273 | 365 | state_hash_lookup (size_t nitems, item_number *core) |
c7ca99d4 | 366 | { |
03b9e273 PE |
367 | size_t items_size = nitems * sizeof *core; |
368 | state *probe = xmalloc (offsetof (state, items) + items_size); | |
17ee7397 | 369 | state *entry; |
c7ca99d4 | 370 | |
03b9e273 PE |
371 | probe->nitems = nitems; |
372 | memcpy (probe->items, core, items_size); | |
c7ca99d4 AD |
373 | entry = hash_lookup (state_table, probe); |
374 | free (probe); | |
375 | return entry; | |
376 | } | |
377 | ||
5967f0cf | 378 | |
14462c2b JD |
379 | /*--------------------------------------------------------. |
380 | | Record S and all states reachable from S in REACHABLE. | | |
381 | `--------------------------------------------------------*/ | |
5967f0cf JD |
382 | |
383 | static void | |
14462c2b | 384 | state_record_reachable_states (state *s, bitset reachable) |
5967f0cf | 385 | { |
14462c2b | 386 | if (bitset_test (reachable, s->number)) |
5967f0cf | 387 | return; |
14462c2b JD |
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 | } | |
5967f0cf JD |
395 | } |
396 | ||
397 | void | |
398 | state_remove_unreachable_states (state_number old_to_new[]) | |
399 | { | |
400 | state_number nstates_reachable = 0; | |
14462c2b JD |
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 | } | |
5967f0cf | 420 | nstates = nstates_reachable; |
14462c2b | 421 | bitset_free (reachable); |
5967f0cf JD |
422 | } |
423 | ||
c7ca99d4 | 424 | /* All the decorated states, indexed by the state number. */ |
17ee7397 | 425 | state **states = NULL; |
c7ca99d4 AD |
426 | |
427 | ||
428 | /*----------------------. | |
429 | | Free all the states. | | |
430 | `----------------------*/ | |
431 | ||
432 | void | |
433 | states_free (void) | |
434 | { | |
17ee7397 | 435 | state_number i; |
c7ca99d4 | 436 | for (i = 0; i < nstates; ++i) |
8b752b00 AD |
437 | state_free (states[i]); |
438 | free (states); | |
c7ca99d4 | 439 | } |