1 /* Type definitions for nondeterministic finite state machine for Bison.
3 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 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/>. */
29 #include "print-xml.h"
32 /*-------------------.
34 `-------------------*/
37 /*-----------------------------------------.
38 | Create a new array of NUM shifts/gotos. |
39 `-----------------------------------------*/
42 transitions_new (int num
, state
**the_states
)
44 size_t states_size
= num
* sizeof *the_states
;
45 transitions
*res
= xmalloc (offsetof (transitions
, states
) + states_size
);
47 memcpy (res
->states
, the_states
, states_size
);
52 /*-------------------------------------------------------.
53 | Return the state such that SHIFTS contain a shift/goto |
54 | to it on SYM. Abort if none found. |
55 `-------------------------------------------------------*/
58 transitions_to (transitions
*shifts
, symbol_number sym
)
63 aver (j
< shifts
->num
);
64 if (TRANSITION_SYMBOL (shifts
, j
) == sym
)
65 return shifts
->states
[j
];
70 /*--------------------.
71 | Error transitions. |
72 `--------------------*/
75 /*---------------------------------.
76 | Create a new array of NUM errs. |
77 `---------------------------------*/
80 errs_new (int num
, symbol
**tokens
)
82 size_t symbols_size
= num
* sizeof *tokens
;
83 errs
*res
= xmalloc (offsetof (errs
, symbols
) + symbols_size
);
85 memcpy (res
->symbols
, tokens
, symbols_size
);
97 /*---------------------------------------.
98 | Create a new array of NUM reductions. |
99 `---------------------------------------*/
102 reductions_new (int num
, rule
**reds
)
104 size_t rules_size
= num
* sizeof *reds
;
105 reductions
*res
= xmalloc (offsetof (reductions
, rules
) + rules_size
);
107 res
->lookahead_tokens
= NULL
;
108 memcpy (res
->rules
, reds
, rules_size
);
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
;
125 /*------------------------------------------------------------------.
126 | Create a new state with ACCESSING_SYMBOL, for those items. Store |
127 | it in the state hash table. |
128 `------------------------------------------------------------------*/
131 state_new (symbol_number accessing_symbol
,
132 size_t nitems
, item_number
*core
)
135 size_t items_size
= nitems
* sizeof *core
;
137 aver (nstates
< STATE_NUMBER_MAXIMUM
);
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
;
146 res
->solved_conflicts
= NULL
;
147 res
->solved_conflicts_xml
= NULL
;
149 res
->nitems
= nitems
;
150 memcpy (res
->items
, core
, items_size
);
152 state_hash_insert (res
);
163 state_free (state
*s
)
165 free (s
->transitions
);
166 free (s
->reductions
);
172 /*---------------------------.
173 | Set the transitions of S. |
174 `---------------------------*/
177 state_transitions_set (state
*s
, int num
, state
**trans
)
179 aver (!s
->transitions
);
180 s
->transitions
= transitions_new (num
, trans
);
184 /*--------------------------.
185 | Set the reductions of S. |
186 `--------------------------*/
189 state_reductions_set (state
*s
, int num
, rule
**reds
)
191 aver (!s
->reductions
);
192 s
->reductions
= reductions_new (num
, reds
);
197 state_reduction_find (state
*s
, rule
*r
)
200 reductions
*reds
= s
->reductions
;
201 for (i
= 0; i
< reds
->num
; ++i
)
202 if (reds
->rules
[i
] == r
)
208 /*--------------------.
209 | Set the errs of S. |
210 `--------------------*/
213 state_errs_set (state
*s
, int num
, symbol
**tokens
)
216 s
->errs
= errs_new (num
, tokens
);
221 /*--------------------------------------------------.
222 | Print on OUT all the lookahead tokens such that S |
223 | wants to reduce R. |
224 `--------------------------------------------------*/
227 state_rule_lookahead_tokens_print (state
*s
, rule
*r
, FILE *out
)
229 /* Find the reduction we are handling. */
230 reductions
*reds
= s
->reductions
;
231 int red
= state_reduction_find (s
, r
);
233 /* Print them if there are. */
234 if (reds
->lookahead_tokens
&& red
!= -1)
236 bitset_iterator biter
;
238 char const *sep
= "";
240 BITSET_FOR_EACH (biter
, reds
->lookahead_tokens
[red
], k
, 0)
242 fprintf (out
, "%s%s", sep
, symbols
[k
]->tag
);
250 state_rule_lookahead_tokens_print_xml (state
*s
, rule
*r
,
251 FILE *out
, int level
)
253 /* Find the reduction we are handling. */
254 reductions
*reds
= s
->reductions
;
255 int red
= state_reduction_find (s
, r
);
257 /* Print them if there are. */
258 if (reds
->lookahead_tokens
&& red
!= -1)
260 bitset_iterator biter
;
262 xml_puts (out
, level
, "<lookaheads>");
263 BITSET_FOR_EACH (biter
, reds
->lookahead_tokens
[red
], k
, 0)
265 xml_printf (out
, level
+ 1, "<symbol class=\"%s\">%s</symbol>",
266 symbol_class_get_string (symbols
[k
]),
267 xml_escape (symbols
[k
]->tag
));
269 xml_puts (out
, level
, "</lookaheads>");
274 /*---------------------.
275 | A state hash table. |
276 `---------------------*/
278 /* Initial capacity of states hash table. */
279 #define HT_INITIAL_CAPACITY 257
281 static struct hash_table
*state_table
= NULL
;
283 /* Two states are equal if they have the same core items. */
285 state_compare (state
const *s1
, state
const *s2
)
289 if (s1
->nitems
!= s2
->nitems
)
292 for (i
= 0; i
< s1
->nitems
; ++i
)
293 if (s1
->items
[i
] != s2
->items
[i
])
300 state_comparator (void const *s1
, void const *s2
)
302 return state_compare (s1
, s2
);
306 state_hash (state
const *s
, size_t tablesize
)
308 /* Add up the state's item numbers to get a hash key. */
311 for (i
= 0; i
< s
->nitems
; ++i
)
313 return key
% tablesize
;
317 state_hasher (void const *s
, size_t tablesize
)
319 return state_hash (s
, tablesize
);
323 /*-------------------------------.
324 | Create the states hash table. |
325 `-------------------------------*/
328 state_hash_new (void)
330 state_table
= hash_initialize (HT_INITIAL_CAPACITY
,
338 /*---------------------------------------------.
339 | Free the states hash table, not the states. |
340 `---------------------------------------------*/
343 state_hash_free (void)
345 hash_free (state_table
);
349 /*-----------------------------------.
350 | Insert S in the state hash table. |
351 `-----------------------------------*/
354 state_hash_insert (state
*s
)
356 hash_insert (state_table
, s
);
360 /*------------------------------------------------------------------.
361 | Find the state associated to the CORE, and return it. If it does |
362 | not exist yet, return NULL. |
363 `------------------------------------------------------------------*/
366 state_hash_lookup (size_t nitems
, item_number
*core
)
368 size_t items_size
= nitems
* sizeof *core
;
369 state
*probe
= xmalloc (offsetof (state
, items
) + items_size
);
372 probe
->nitems
= nitems
;
373 memcpy (probe
->items
, core
, items_size
);
374 entry
= hash_lookup (state_table
, probe
);
380 /*--------------------------------------------------------.
381 | Record S and all states reachable from S in REACHABLE. |
382 `--------------------------------------------------------*/
385 state_record_reachable_states (state
*s
, bitset reachable
)
387 if (bitset_test (reachable
, s
->number
))
389 bitset_set (reachable
, s
->number
);
392 for (i
= 0; i
< s
->transitions
->num
; ++i
)
393 if (!TRANSITION_IS_DISABLED (s
->transitions
, i
))
394 state_record_reachable_states (s
->transitions
->states
[i
], reachable
);
399 state_remove_unreachable_states (state_number old_to_new
[])
401 state_number nstates_reachable
= 0;
402 bitset reachable
= bitset_create (nstates
, BITSET_FIXED
);
403 state_record_reachable_states (states
[0], reachable
);
406 for (i
= 0; i
< nstates
; ++i
)
408 if (bitset_test (reachable
, states
[i
]->number
))
410 states
[nstates_reachable
] = states
[i
];
411 states
[nstates_reachable
]->number
= nstates_reachable
;
412 old_to_new
[i
] = nstates_reachable
++;
416 state_free (states
[i
]);
417 old_to_new
[i
] = nstates
;
421 nstates
= nstates_reachable
;
422 bitset_free (reachable
);
425 /* All the decorated states, indexed by the state number. */
426 state
**states
= NULL
;
429 /*----------------------.
430 | Free all the states. |
431 `----------------------*/
437 for (i
= 0; i
< nstates
; ++i
)
438 state_free (states
[i
]);