1 /* Type definitions for the finite state machine for Bison.
3 Copyright (C) 2001-2007, 2009-2015, 2018-2020 Free Software
6 This file is part of Bison, the GNU Compiler Compiler.
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.
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.
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/>. */
32 #include "print-xml.h"
35 /*-------------------.
37 `-------------------*/
40 /*-----------------------------------------.
41 | Create a new array of NUM shifts/gotos. |
42 `-----------------------------------------*/
45 transitions_new (int num
, state
**dst
)
47 size_t states_size
= num
* sizeof *dst
;
48 transitions
*res
= xmalloc (offsetof (transitions
, states
) + states_size
);
50 memcpy (res
->states
, dst
, states_size
);
56 transitions_to (state
*s
, symbol_number sym
)
58 transitions
*trans
= s
->transitions
;
59 for (int i
= 0; i
< trans
->num
; ++i
)
60 if (TRANSITION_SYMBOL (trans
, i
) == sym
)
61 return trans
->states
[i
];
66 /*--------------------.
67 | Error transitions. |
68 `--------------------*/
71 /*---------------------------------.
72 | Create a new array of NUM errs. |
73 `---------------------------------*/
76 errs_new (int num
, symbol
**tokens
)
78 size_t symbols_size
= num
* sizeof *tokens
;
79 errs
*res
= xmalloc (offsetof (errs
, symbols
) + symbols_size
);
82 memcpy (res
->symbols
, tokens
, symbols_size
);
94 /*---------------------------------------.
95 | Create a new array of NUM reductions. |
96 `---------------------------------------*/
99 reductions_new (int num
, rule
**reds
)
101 size_t rules_size
= num
* sizeof *reds
;
102 reductions
*res
= xmalloc (offsetof (reductions
, rules
) + rules_size
);
104 res
->lookaheads
= NULL
;
105 memcpy (res
->rules
, reds
, rules_size
);
116 state_number nstates
= 0;
117 /* FINAL_STATE is properly set by new_state when it recognizes its
118 accessing symbol: $end. */
119 state
*final_state
= NULL
;
122 /*------------------------------------------------------------------.
123 | Create a new state with ACCESSING_SYMBOL, for those items. Store |
124 | it in the state hash table. |
125 `------------------------------------------------------------------*/
128 state_new (symbol_number accessing_symbol
,
129 size_t nitems
, item_index
*core
)
131 aver (nstates
< STATE_NUMBER_MAXIMUM
);
133 size_t items_size
= nitems
* sizeof *core
;
134 state
*res
= xmalloc (offsetof (state
, items
) + items_size
);
135 res
->number
= nstates
++;
136 res
->accessing_symbol
= accessing_symbol
;
137 res
->transitions
= NULL
;
138 res
->reductions
= NULL
;
140 res
->state_list
= NULL
;
141 res
->consistent
= false;
142 res
->solved_conflicts
= NULL
;
143 res
->solved_conflicts_xml
= NULL
;
145 res
->nitems
= nitems
;
146 memcpy (res
->items
, core
, items_size
);
148 state_hash_insert (res
);
154 state_new_isocore (state
const *s
)
156 aver (nstates
< STATE_NUMBER_MAXIMUM
);
158 size_t items_size
= s
->nitems
* sizeof *s
->items
;
159 state
*res
= xmalloc (offsetof (state
, items
) + items_size
);
160 res
->number
= nstates
++;
161 res
->accessing_symbol
= s
->accessing_symbol
;
163 transitions_new (s
->transitions
->num
, s
->transitions
->states
);
164 res
->reductions
= reductions_new (s
->reductions
->num
, s
->reductions
->rules
);
166 res
->state_list
= NULL
;
167 res
->consistent
= s
->consistent
;
168 res
->solved_conflicts
= NULL
;
169 res
->solved_conflicts_xml
= NULL
;
171 res
->nitems
= s
->nitems
;
172 memcpy (res
->items
, s
->items
, items_size
);
183 state_free (state
*s
)
185 free (s
->transitions
);
186 free (s
->reductions
);
193 state_transitions_print (const state
*s
, FILE *out
)
195 const transitions
*trans
= s
->transitions
;
196 fprintf (out
, "transitions of %d (%d):\n",
197 s
->number
, trans
->num
);
198 for (int i
= 0; i
< trans
->num
; ++i
)
199 fprintf (out
, " %d: (%d, %s, %d)\n",
202 symbols
[s
->transitions
->states
[i
]->accessing_symbol
]->tag
,
203 s
->transitions
->states
[i
]->number
);
207 /*---------------------------.
208 | Set the transitions of S. |
209 `---------------------------*/
212 state_transitions_set (state
*s
, int num
, state
**dst
)
214 aver (!s
->transitions
);
215 s
->transitions
= transitions_new (num
, dst
);
216 if (trace_flag
& trace_automaton
)
217 state_transitions_print (s
, stderr
);
221 /*--------------------------.
222 | Set the reductions of S. |
223 `--------------------------*/
226 state_reductions_set (state
*s
, int num
, rule
**reds
)
228 aver (!s
->reductions
);
229 s
->reductions
= reductions_new (num
, reds
);
234 state_reduction_find (state
const *s
, rule
const *r
)
236 reductions
*reds
= s
->reductions
;
237 for (int i
= 0; i
< reds
->num
; ++i
)
238 if (reds
->rules
[i
] == r
)
244 /*--------------------.
245 | Set the errs of S. |
246 `--------------------*/
249 state_errs_set (state
*s
, int num
, symbol
**tokens
)
252 s
->errs
= errs_new (num
, tokens
);
257 /*--------------------------------------------------.
258 | Print on OUT all the lookahead tokens such that S |
259 | wants to reduce R. |
260 `--------------------------------------------------*/
263 state_rule_lookaheads_print (state
const *s
, rule
const *r
, FILE *out
)
265 /* Find the reduction we are handling. */
266 reductions
*reds
= s
->reductions
;
267 int red
= state_reduction_find (s
, r
);
269 /* Print them if there are. */
270 if (reds
->lookaheads
&& red
!= -1)
272 bitset_iterator biter
;
274 char const *sep
= "";
276 BITSET_FOR_EACH (biter
, reds
->lookaheads
[red
], k
, 0)
278 fprintf (out
, "%s%s", sep
, symbols
[k
]->tag
);
286 state_rule_lookaheads_print_xml (state
const *s
, rule
const *r
,
287 FILE *out
, int level
)
289 /* Find the reduction we are handling. */
290 reductions
*reds
= s
->reductions
;
291 int red
= state_reduction_find (s
, r
);
293 /* Print them if there are. */
294 if (reds
->lookaheads
&& red
!= -1)
296 bitset_iterator biter
;
298 xml_puts (out
, level
, "<lookaheads>");
299 BITSET_FOR_EACH (biter
, reds
->lookaheads
[red
], k
, 0)
301 xml_printf (out
, level
+ 1, "<symbol>%s</symbol>",
302 xml_escape (symbols
[k
]->tag
));
304 xml_puts (out
, level
, "</lookaheads>");
309 /*---------------------.
310 | A state hash table. |
311 `---------------------*/
313 /* Initial capacity of states hash table. */
314 #define HT_INITIAL_CAPACITY 257
316 static struct hash_table
*state_table
= NULL
;
318 /* Two states are equal if they have the same core items. */
320 state_compare (state
const *s1
, state
const *s2
)
322 if (s1
->nitems
!= s2
->nitems
)
325 for (size_t i
= 0; i
< s1
->nitems
; ++i
)
326 if (s1
->items
[i
] != s2
->items
[i
])
333 state_comparator (void const *s1
, void const *s2
)
335 return state_compare (s1
, s2
);
339 state_hash (state
const *s
, size_t tablesize
)
341 /* Add up the state's item numbers to get a hash key. */
343 for (size_t i
= 0; i
< s
->nitems
; ++i
)
345 return key
% tablesize
;
349 state_hasher (void const *s
, size_t tablesize
)
351 return state_hash (s
, tablesize
);
355 /*-------------------------------.
356 | Create the states hash table. |
357 `-------------------------------*/
360 state_hash_new (void)
362 state_table
= hash_xinitialize (HT_INITIAL_CAPACITY
,
370 /*---------------------------------------------.
371 | Free the states hash table, not the states. |
372 `---------------------------------------------*/
375 state_hash_free (void)
377 hash_free (state_table
);
381 /*-----------------------------------.
382 | Insert S in the state hash table. |
383 `-----------------------------------*/
386 state_hash_insert (state
*s
)
388 hash_xinsert (state_table
, s
);
392 /*------------------------------------------------------------------.
393 | Find the state associated to the CORE, and return it. If it does |
394 | not exist yet, return NULL. |
395 `------------------------------------------------------------------*/
398 state_hash_lookup (size_t nitems
, const item_index
*core
)
400 size_t items_size
= nitems
* sizeof *core
;
401 state
*probe
= xmalloc (offsetof (state
, items
) + items_size
);
402 probe
->nitems
= nitems
;
403 memcpy (probe
->items
, core
, items_size
);
404 state
*entry
= hash_lookup (state_table
, probe
);
410 /*--------------------------------------------------------.
411 | Record S and all states reachable from S in REACHABLE. |
412 `--------------------------------------------------------*/
415 state_record_reachable_states (state
*s
, bitset reachable
)
417 if (bitset_test (reachable
, s
->number
))
419 bitset_set (reachable
, s
->number
);
420 for (int i
= 0; i
< s
->transitions
->num
; ++i
)
421 if (!TRANSITION_IS_DISABLED (s
->transitions
, i
))
422 state_record_reachable_states (s
->transitions
->states
[i
], reachable
);
426 state_remove_unreachable_states (state_number old_to_new
[])
428 state_number nstates_reachable
= 0;
429 bitset reachable
= bitset_create (nstates
, BITSET_FIXED
);
430 state_record_reachable_states (states
[0], reachable
);
431 for (state_number i
= 0; i
< nstates
; ++i
)
433 if (bitset_test (reachable
, states
[i
]->number
))
435 states
[nstates_reachable
] = states
[i
];
436 states
[nstates_reachable
]->number
= nstates_reachable
;
437 old_to_new
[i
] = nstates_reachable
++;
441 state_free (states
[i
]);
442 old_to_new
[i
] = nstates
;
445 nstates
= nstates_reachable
;
446 bitset_free (reachable
);
449 /* All the decorated states, indexed by the state number. */
450 state
**states
= NULL
;
453 /*----------------------.
454 | Free all the states. |
455 `----------------------*/
461 for (state_number i
= 0; i
< nstates
; ++i
)
462 state_free (states
[i
]);