1 /* Output the generated parsing program for Bison.
2
3 Copyright (C) 1984, 1986, 1989, 1992, 2000-2006, 2009-2015, 2018-2021
4 Free Software 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 <https://www.gnu.org/licenses/>. */
20
21 #include <config.h>
22 #include "system.h"
23
24 #include <bitset.h>
25 #include <bitsetv.h>
26
27 #include "complain.h"
28 #include "conflicts.h"
29 #include "files.h"
30 #include "getargs.h"
31 #include "gram.h"
32 #include "lalr.h"
33 #include "muscle-tab.h"
34 #include "reader.h"
35 #include "symtab.h"
36 #include "tables.h"
37
38 /* Several tables are indexed both by state and nonterminal numbers.
39 We call such an index a 'vector'; i.e., a vector is either a state
40 or a nonterminal number.
41
42 Of course vector_number_t ought to be wide enough to contain
43 state_number and symbol_number. */
44 typedef int vector_number;
45
46 #if 0 /* Not currently used. */
47 static inline vector_number
48 state_number_to_vector_number (state_number s)
49 {
50 return s;
51 }
52 #endif
53
54 static inline vector_number
55 symbol_number_to_vector_number (symbol_number sym)
56 {
57 return state_number_as_int (nstates) + sym - ntokens;
58 }
59
60 int nvectors;
61
62
63 /* FROMS and TOS are indexed by vector_number.
64
65 If VECTOR is a nonterminal, (FROMS[VECTOR], TOS[VECTOR]) form an
66 array of state numbers of the non defaulted GOTO on VECTOR.
67
68 If VECTOR is a state, TOS[VECTOR] is the array of actions to do on
69 the (array of) symbols FROMS[VECTOR].
70
71 In both cases, TALLY[VECTOR] is the size of the arrays
72 FROMS[VECTOR], TOS[VECTOR]; and WIDTH[VECTOR] =
73 (FROMS[VECTOR][SIZE] - FROMS[VECTOR][0] + 1) where SIZE =
74 TALLY[VECTOR].
75
76 FROMS therefore contains symbol_number and action_number,
77 TOS state_number and action_number,
78 TALLY sizes,
79 WIDTH differences of FROMS.
80
81 Let base_number be the type of FROMS, TOS, and WIDTH. */
82 #define BASE_MAXIMUM INT_MAX
83 #define BASE_MINIMUM INT_MIN
84
85 static base_number **froms;
86 static base_number **tos;
87 static int **conflict_tos;
88 static size_t *tally;
89 static base_number *width;
90
91
92 /* For a given state, N = ACTROW[SYMBOL]:
93
94 If N = 0, stands for 'run the default action'.
95 If N = MIN, stands for 'raise a syntax error'.
96 If N > 0, stands for 'shift SYMBOL and go to n'.
97 If N < 0, stands for 'reduce -N'. */
98 typedef int action_number;
99 #define ACTION_NUMBER_MINIMUM INT_MIN
100
101 static action_number *actrow;
102
103 /* FROMS and TOS are reordered to be compressed. ORDER[VECTOR] is the
104 new vector number of VECTOR. We skip 'empty' vectors (i.e.,
105 TALLY[VECTOR] = 0), and call these 'entries'. */
106 static vector_number *order;
107 static int nentries;
108
109 base_number *base = NULL;
110 /* A distinguished value of BASE, negative infinite. During the
111 computation equals to BASE_MINIMUM, later mapped to BASE_NINF to
112 keep parser tables small. */
113 base_number base_ninf = 0;
114
115 /* Bitset representing an integer set in the range
116 POS_SET_OFFSET..(POS_SET_OFFSET + SIZE). POS_SET_OFFSET is
117 nonpositive. */
118 static bitset pos_set = NULL;
119 /* The integer denoted by bitno 0 in pos_set. */
120 static int pos_set_base = 0;
121
122 static int *conflrow;
123 int *conflict_table;
124 int *conflict_list;
125 int conflict_list_cnt;
126 static int conflict_list_free;
127
128 /* TABLE_SIZE is the allocated size of both TABLE and CHECK. We start
129 with more or less the original hard-coded value (which was
130 SHRT_MAX). */
131 static int table_size = 32768;
132 base_number *table;
133 base_number *check;
134 /* The value used in TABLE to denote explicit syntax errors
135 (%nonassoc), a negative infinite. First defaults to ACTION_NUMBER_MINIMUM,
136 but in order to keep small tables, renumbered as TABLE_ERROR, which
137 is the smallest (non error) value minus 1. */
138 base_number table_ninf = 0;
139 static int lowzero;
140 int high;
141
142 state_number *yydefgoto;
143 rule_number *yydefact;
144
145
146 /*----------.
147 | pos_set. |
148 `----------*/
149
150 #if 0
151 static void
152 pos_set_dump (void)
153 {
154 fprintf (stderr, "pos_set (%ld, %d) =", bitset_size (pos_set), pos_set_base);
155 bitset_iterator biter;
156 int i;
157 BITSET_FOR_EACH (biter, pos_set, i, 0)
158 fprintf (stderr, " %d", i + pos_set_base);
159 putc ('\n', stderr);
160 }
161 #endif
162
163
164 /* The size and base of POS_SET are not known, we need to be able to
165 move the base farther "on the left", and grow "on the right".
166
167 It would be nice to be able to predict the base accurately, but it
168 seems difficult (-nstates seems to work most of the time, except
169 when there are useless tokens).
170
171 FIXME: The current approach is correct, but with poor performances.
172 Bitsets need to support 'assign' and 'shift'. And instead of
173 extending POS_SET just for the out-of-range new values, we need
174 something like doubling the size.
175 */
176
177 static void
178 pos_set_set (int pos)
179 {
180 int bitno = pos - pos_set_base;
181 if (bitno < 0)
182 {
183 // Need more room on the left.
184 // DELTA is positive. Run 'pos_set >> delta'.
185 const int delta = pos_set_base - pos;
186 const int old_size = bitset_size (pos_set);
187 const int new_size = old_size + delta;
188 bitset_resize (pos_set, new_size);
189 // Right-shift all the bits by DELTA. Be sure to reset the new
190 // bits on the left.
191 //
192 // FIXME: add bitset_assign, and bitset_shift?
193 for (int i = new_size - 1; 0 <= i ; --i)
194 if (delta <= i && bitset_test (pos_set, i - delta))
195 bitset_set (pos_set, i);
196 else
197 bitset_reset (pos_set, i);
198 pos_set_base = pos;
199 bitno = 0;
200 }
201 else if (bitset_size (pos_set) <= bitno)
202 // Need more room on the right.
203 bitset_resize (pos_set, bitno + 1);
204 bitset_set (pos_set, bitno);
205 }
206
207 static bool
208 pos_set_test (int pos)
209 {
210 const int bitno = pos - pos_set_base;
211 return bitset_test (pos_set, bitno);
212 }
213
214
215 /*-------------------------------------------------------------------.
216 | If TABLE, CONFLICT_TABLE, and CHECK are too small to be addressed |
217 | at DESIRED, grow them. TABLE[DESIRED] can be used, so the desired |
218 | size is at least DESIRED + 1. |
219 `-------------------------------------------------------------------*/
220
221 static void
222 table_grow (int desired)
223 {
224 int old_size = table_size;
225
226 while (table_size <= desired)
227 table_size *= 2;
228
229 if (trace_flag & trace_resource)
230 fprintf (stderr, "growing tables from %d to %d\n",
231 old_size, table_size);
232
233 table = xnrealloc (table, table_size, sizeof *table);
234 memset (table + old_size, 0,
235 sizeof *table * (table_size - old_size));
236
237 conflict_table = xnrealloc (conflict_table, table_size,
238 sizeof *conflict_table);
239 memset (conflict_table + old_size, 0,
240 sizeof *conflict_table * (table_size - old_size));
241
242 check = xnrealloc (check, table_size, sizeof *check);
243 for (int i = old_size; i < table_size; ++i)
244 check[i] = -1;
245 }
246
247
248
249
250 /*-------------------------------------------------------------------.
251 | For GLR parsers, for each conflicted token in S, as indicated |
252 | by non-zero entries in CONFLROW, create a list of possible |
253 | reductions that are alternatives to the shift or reduction |
254 | currently recorded for that token in S. Store the alternative |
255 | reductions followed by a 0 in CONFLICT_LIST, updating |
256 | CONFLICT_LIST_CNT, and storing an index to the start of the list |
257 | back into CONFLROW. |
258 `-------------------------------------------------------------------*/
259
260 static void
261 conflict_row (state *s)
262 {
263 if (!nondeterministic_parser)
264 return;
265
266 const reductions *reds = s->reductions;
267 for (state_number j = 0; j < ntokens; j += 1)
268 if (conflrow[j])
269 {
270 conflrow[j] = conflict_list_cnt;
271
272 /* Find all reductions for token J, and record all that do not
273 match ACTROW[J]. */
274 for (int i = 0; i < reds->num; i += 1)
275 if (bitset_test (reds->lookaheads[i], j)
276 && (actrow[j]
277 != rule_number_as_item_number (reds->rules[i]->number)))
278 {
279 aver (0 < conflict_list_free);
280 conflict_list[conflict_list_cnt] = reds->rules[i]->number + 1;
281 conflict_list_cnt += 1;
282 conflict_list_free -= 1;
283 }
284
285 /* Leave a 0 at the end. */
286 aver (0 < conflict_list_free);
287 conflict_list[conflict_list_cnt] = 0;
288 conflict_list_cnt += 1;
289 conflict_list_free -= 1;
290 }
291 }
292
293
294 /*------------------------------------------------------------------.
295 | Decide what to do for each type of token if seen as the |
296 | lookahead in specified state. The value returned is used as the |
297 | default action (yydefact) for the state. In addition, ACTROW is |
298 | filled with what to do for each kind of token, index by symbol |
299 | number, with zero meaning do the default action. The value |
300 | ACTION_NUMBER_MINIMUM, a very negative number, means this |
301 | situation is an error. The parser recognizes this value |
302 | specially. |
303 | |
304 | This is where conflicts are resolved. The loop over lookahead |
305 | rules considered lower-numbered rules last, and the last rule |
306 | considered that likes a token gets to handle it. |
307 | |
308 | For GLR parsers, also sets CONFLROW[SYM] to an index into |
309 | CONFLICT_LIST iff there is an unresolved conflict (s/r or r/r) |
310 | with symbol SYM. The default reduction is not used for a symbol |
311 | that has any such conflicts. |
312 `------------------------------------------------------------------*/
313
314 static rule *
315 action_row (state *s)
316 {
317 for (state_number i = 0; i < ntokens; i++)
318 actrow[i] = conflrow[i] = 0;
319
320 reductions *reds = s->reductions;
321 bool conflicted = false;
322 if (reds->lookaheads)
323 /* loop over all the rules available here which require
324 lookahead (in reverse order to give precedence to the first
325 rule) */
326 for (int i = reds->num - 1; 0 <= i; --i)
327 /* and find each token which the rule finds acceptable
328 to come next */
329 {
330 bitset_iterator biter;
331 int j;
332 BITSET_FOR_EACH (biter, reds->lookaheads[i], j, 0)
333 {
334 /* and record this rule as the rule to use if that
335 token follows. */
336 if (actrow[j] != 0)
337 {
338 conflicted = true;
339 conflrow[j] = 1;
340 }
341 actrow[j] = rule_number_as_item_number (reds->rules[i]->number);
342 }
343 }
344
345 /* Now see which tokens are allowed for shifts in this state. For
346 them, record the shift as the thing to do. So shift is preferred
347 to reduce. */
348 transitions *trans = s->transitions;
349 /* Set to nonzero to inhibit having any default reduction. */
350 bool nodefault = false;
351 {
352 int i;
353 FOR_EACH_SHIFT (trans, i)
354 {
355 symbol_number sym = TRANSITION_SYMBOL (trans, i);
356 state *shift_state = trans->states[i];
357
358 if (actrow[sym] != 0)
359 {
360 conflicted = true;
361 conflrow[sym] = 1;
362 }
363 actrow[sym] = state_number_as_int (shift_state->number);
364
365 /* Do not use any default reduction if there is a shift for
366 error */
367 if (sym == errtoken->content->number)
368 nodefault = true;
369 }
370 }
371
372 /* See which tokens are an explicit error in this state (due to
373 %nonassoc). For them, record ACTION_NUMBER_MINIMUM as the
374 action. */
375 errs *errp = s->errs;
376 for (int i = 0; i < errp->num; i++)
377 {
378 symbol *sym = errp->symbols[i];
379 actrow[sym->content->number] = ACTION_NUMBER_MINIMUM;
380 }
381
382 /* Turn off default reductions where requested by the user. See
383 state_lookaheads_count in lalr.c to understand when states are
384 labeled as consistent. */
385 {
386 char *default_reductions =
387 muscle_percent_define_get ("lr.default-reduction");
388 if (STRNEQ (default_reductions, "most") && !s->consistent)
389 nodefault = true;
390 free (default_reductions);
391 }
392
393 /* Now find the most common reduction and make it the default action
394 for this state. */
395 rule *default_reduction = NULL;
396 if (reds->num >= 1 && !nodefault)
397 {
398 if (s->consistent)
399 default_reduction = reds->rules[0];
400 else
401 {
402 int max = 0;
403 for (int i = 0; i < reds->num; i++)
404 {
405 int count = 0;
406 rule *r = reds->rules[i];
407 for (symbol_number j = 0; j < ntokens; j++)
408 if (actrow[j] == rule_number_as_item_number (r->number))
409 count++;
410
411 if (count > max)
412 {
413 max = count;
414 default_reduction = r;
415 }
416 }
417
418 /* GLR parsers need space for conflict lists, so we can't
419 default conflicted entries. For non-conflicted entries
420 or as long as we are not building a GLR parser,
421 actions that match the default are replaced with zero,
422 which means "use the default". */
423
424 if (0 < max)
425 for (symbol_number j = 0; j < ntokens; j++)
426 if (actrow[j]
427 == rule_number_as_item_number (default_reduction->number)
428 && ! (nondeterministic_parser && conflrow[j]))
429 actrow[j] = 0;
430 }
431 }
432
433 /* If have no default reduction, the default is an error.
434 So replace any action which says "error" with "use default". */
435
436 if (!default_reduction)
437 for (symbol_number i = 0; i < ntokens; i++)
438 if (actrow[i] == ACTION_NUMBER_MINIMUM)
439 actrow[i] = 0;
440
441 if (conflicted)
442 conflict_row (s);
443
444 return default_reduction;
445 }
446
447
448 /*----------------------------------------.
449 | Set FROMS, TOS, TALLY and WIDTH for S. |
450 `----------------------------------------*/
451
452 static void
453 save_row (state_number s)
454 {
455 /* Number of non default actions in S. */
456 size_t count = 0;
457 for (symbol_number i = 0; i < ntokens; i++)
458 if (actrow[i] != 0)
459 count++;
460
461 if (count)
462 {
463 /* Allocate non defaulted actions. */
464 base_number *sp1 = froms[s] = xnmalloc (count, sizeof *sp1);
465 base_number *sp2 = tos[s] = xnmalloc (count, sizeof *sp2);
466 int *sp3 = conflict_tos[s] =
467 nondeterministic_parser ? xnmalloc (count, sizeof *sp3) : NULL;
468
469 /* Store non defaulted actions. */
470 for (symbol_number i = 0; i < ntokens; i++)
471 if (actrow[i] != 0)
472 {
473 *sp1++ = i;
474 *sp2++ = actrow[i];
475 if (nondeterministic_parser)
476 *sp3++ = conflrow[i];
477 }
478
479 tally[s] = count;
480 width[s] = sp1[-1] - froms[s][0] + 1;
481 }
482 }
483
484
485 /*------------------------------------------------------------------.
486 | Figure out the actions for the specified state, indexed by |
487 | lookahead token kind. |
488 | |
489 | The YYDEFACT table is output now. The detailed info is saved for |
490 | putting into YYTABLE later. |
491 `------------------------------------------------------------------*/
492
493 static void
494 token_actions (void)
495 {
496 int nconflict = nondeterministic_parser ? conflicts_total_count () : 0;
497
498 yydefact = xnmalloc (nstates, sizeof *yydefact);
499
500 actrow = xnmalloc (ntokens, sizeof *actrow);
501 conflrow = xnmalloc (ntokens, sizeof *conflrow);
502
503 conflict_list = xnmalloc (1 + 2 * nconflict, sizeof *conflict_list);
504 conflict_list_free = 2 * nconflict;
505 conflict_list_cnt = 1;
506
507 /* Find the rules which are reduced. */
508 if (!nondeterministic_parser)
509 for (rule_number r = 0; r < nrules; ++r)
510 rules[r].useful = false;
511
512 for (state_number i = 0; i < nstates; ++i)
513 {
514 rule *default_reduction = action_row (states[i]);
515 yydefact[i] = default_reduction ? default_reduction->number + 1 : 0;
516 save_row (i);
517
518 /* Now that the parser was computed, we can find which rules are
519 really reduced, and which are not because of SR or RR
520 conflicts. */
521 if (!nondeterministic_parser)
522 {
523 for (symbol_number j = 0; j < ntokens; ++j)
524 if (actrow[j] < 0 && actrow[j] != ACTION_NUMBER_MINIMUM)
525 rules[item_number_as_rule_number (actrow[j])].useful = true;
526 if (yydefact[i])
527 rules[yydefact[i] - 1].useful = true;
528 }
529 }
530 free (actrow);
531 free (conflrow);
532 }
533
534
535 /*------------------------------------------------------------------.
536 | Compute FROMS[VECTOR], TOS[VECTOR], TALLY[VECTOR], WIDTH[VECTOR], |
537 | i.e., the information related to non defaulted GOTO on the nterm |
538 | SYM. |
539 | |
540 | DEFAULT_STATE is the principal destination on SYM, i.e., the |
541 | default GOTO destination on SYM. |
542 `------------------------------------------------------------------*/
543
544 static void
545 save_column (symbol_number sym, state_number default_state)
546 {
547 const goto_number begin = goto_map[sym - ntokens];
548 const goto_number end = goto_map[sym - ntokens + 1];
549
550 /* Number of non default GOTO. */
551 size_t count = 0;
552 for (goto_number i = begin; i < end; i++)
553 if (to_state[i] != default_state)
554 count++;
555
556 if (count)
557 {
558 /* Allocate room for non defaulted gotos. */
559 vector_number symno = symbol_number_to_vector_number (sym);
560 base_number *sp1 = froms[symno] = xnmalloc (count, sizeof *sp1);
561 base_number *sp2 = tos[symno] = xnmalloc (count, sizeof *sp2);
562
563 /* Store the state numbers of the non defaulted gotos. */
564 for (goto_number i = begin; i < end; i++)
565 if (to_state[i] != default_state)
566 {
567 *sp1++ = from_state[i];
568 *sp2++ = to_state[i];
569 }
570
571 tally[symno] = count;
572 width[symno] = sp1[-1] - froms[symno][0] + 1;
573 }
574 }
575
576
577 /*----------------------------------------------------------------.
578 | The default state for SYM: the state which is 'the' most common |
579 | GOTO destination on SYM (an nterm). |
580 `----------------------------------------------------------------*/
581
582 static state_number
583 default_goto (symbol_number sym, size_t state_count[])
584 {
585 const goto_number begin = goto_map[sym - ntokens];
586 const goto_number end = goto_map[sym - ntokens + 1];
587
588 /* In the case this symbol is never reduced to ($accept), use state
589 0. We used to use -1, but as a result the yydefgoto table must
590 be signed, which (1) might trigger compiler warnings when storing
591 a value from yydefgoto into a state number (nonnegative), and (2)
592 wastes bits which might result in using a int16 where a uint8
593 suffices. */
594 state_number res = 0;
595
596 if (begin != end)
597 {
598 for (state_number s = 0; s < nstates; s++)
599 state_count[s] = 0;
600
601 for (goto_number i = begin; i < end; i++)
602 state_count[to_state[i]]++;
603
604 size_t max = 0;
605 for (state_number s = 0; s < nstates; s++)
606 if (max < state_count[s])
607 {
608 max = state_count[s];
609 res = s;
610 }
611 }
612 return res;
613 }
614
615
616 /*-------------------------------------------------------------------.
617 | Figure out what to do after reducing with each rule, depending on |
618 | the saved state from before the beginning of parsing the data that |
619 | matched this rule. |
620 | |
621 | The YYDEFGOTO table is output now. The detailed info is saved for |
622 | putting into YYTABLE later. |
623 `-------------------------------------------------------------------*/
624
625 static void
626 goto_actions (void)
627 {
628 size_t *state_count = xnmalloc (nstates, sizeof *state_count);
629 yydefgoto = xnmalloc (nnterms, sizeof *yydefgoto);
630
631 /* For a given nterm I, STATE_COUNT[S] is the number of times there
632 is a GOTO to S on I. */
633 for (symbol_number i = ntokens; i < nsyms; ++i)
634 {
635 state_number default_state = default_goto (i, state_count);
636 save_column (i, default_state);
637 yydefgoto[i - ntokens] = default_state;
638 }
639 free (state_count);
640 }
641
642
643 /*------------------------------------------------------------------.
644 | Compute ORDER, a reordering of vectors, in order to decide how to |
645 | pack the actions and gotos information into yytable. |
646 `------------------------------------------------------------------*/
647
648 static void
649 sort_actions (void)
650 {
651 nentries = 0;
652
653 for (int i = 0; i < nvectors; i++)
654 if (0 < tally[i])
655 {
656 const size_t t = tally[i];
657 const int w = width[i];
658 int j = nentries - 1;
659
660 while (0 <= j && width[order[j]] < w)
661 j--;
662
663 while (0 <= j && width[order[j]] == w && tally[order[j]] < t)
664 j--;
665
666 for (int k = nentries - 1; k > j; k--)
667 order[k + 1] = order[k];
668
669 order[j + 1] = i;
670 nentries++;
671 }
672 }
673
674
675 /* If VECTOR is a state whose actions (reflected by FROMS, TOS, TALLY
676 and WIDTH of VECTOR) are common to a previous state, return this
677 state number.
678
679 In any other case, return -1. */
680
681 static state_number
682 matching_state (vector_number vector)
683 {
684 vector_number i = order[vector];
685 /* If VECTOR is a nterm, return -1. */
686 if (i < nstates)
687 {
688 size_t t = tally[i];
689 int w = width[i];
690
691 /* If VECTOR has GLR conflicts, return -1 */
692 if (conflict_tos[i] != NULL)
693 for (int j = 0; j < t; j += 1)
694 if (conflict_tos[i][j] != 0)
695 return -1;
696
697 for (int prev = vector - 1; 0 <= prev; prev--)
698 {
699 vector_number j = order[prev];
700 /* Given how ORDER was computed, if the WIDTH or TALLY is
701 different, there cannot be a matching state. */
702 if (width[j] != w || tally[j] != t)
703 return -1;
704 else
705 {
706 bool match = true;
707 for (int k = 0; match && k < t; k++)
708 if (tos[j][k] != tos[i][k]
709 || froms[j][k] != froms[i][k]
710 || (conflict_tos[j] != NULL && conflict_tos[j][k] != 0))
711 match = false;
712 if (match)
713 return j;
714 }
715 }
716 }
717 return -1;
718 }
719
720
721 static base_number
722 pack_vector (vector_number vector)
723 {
724 vector_number i = order[vector];
725 size_t t = tally[i];
726 base_number *from = froms[i];
727 base_number *to = tos[i];
728 int *conflict_to = conflict_tos[i];
729
730 aver (t != 0);
731
732 for (base_number res = lowzero - from[0]; ; res++)
733 {
734 bool ok = true;
735 aver (res < table_size);
736 {
737 for (int k = 0; ok && k < t; k++)
738 {
739 int loc = res + state_number_as_int (from[k]);
740 if (table_size <= loc)
741 table_grow (loc);
742
743 if (table[loc] != 0)
744 ok = false;
745 }
746
747 if (ok && pos_set_test (res))
748 ok = false;
749 }
750
751 if (ok)
752 {
753 int loc PACIFY_CC (= -1);
754 for (int k = 0; k < t; k++)
755 {
756 loc = res + state_number_as_int (from[k]);
757 table[loc] = to[k];
758 if (nondeterministic_parser && conflict_to != NULL)
759 conflict_table[loc] = conflict_to[k];
760 check[loc] = from[k];
761 }
762
763 while (table[lowzero] != 0)
764 lowzero++;
765
766 if (high < loc)
767 high = loc;
768
769 aver (BASE_MINIMUM <= res && res <= BASE_MAXIMUM);
770 return res;
771 }
772 }
773 }
774
775
776 /*-------------------------------------------------------------.
777 | Remap the negative infinite in TAB from NINF to the greatest |
778 | possible smallest value. Return it. |
779 | |
780 | In most case this allows us to use shorts instead of ints in |
781 | parsers. |
782 `-------------------------------------------------------------*/
783
784 static base_number
785 table_ninf_remap (base_number tab[], int size, base_number ninf)
786 {
787 base_number res = 0;
788
789 for (int i = 0; i < size; i++)
790 if (tab[i] < res && tab[i] != ninf)
791 res = tab[i];
792
793 --res;
794
795 for (int i = 0; i < size; i++)
796 if (tab[i] == ninf)
797 tab[i] = res;
798
799 return res;
800 }
801
802 static void
803 pack_table (void)
804 {
805 base = xnmalloc (nvectors, sizeof *base);
806 pos_set = bitset_create (table_size + nstates, BITSET_FRUGAL);
807 pos_set_base = -nstates;
808 table = xcalloc (table_size, sizeof *table);
809 conflict_table = xcalloc (table_size, sizeof *conflict_table);
810 check = xnmalloc (table_size, sizeof *check);
811
812 lowzero = 0;
813 high = 0;
814
815 for (int i = 0; i < nvectors; i++)
816 base[i] = BASE_MINIMUM;
817
818 for (int i = 0; i < table_size; i++)
819 check[i] = -1;
820
821 for (int i = 0; i < nentries; i++)
822 {
823 state_number s = matching_state (i);
824 base_number place;
825
826 if (s < 0)
827 /* A new set of state actions, or a nonterminal. */
828 place = pack_vector (i);
829 else
830 /* Action of I were already coded for S. */
831 place = base[s];
832
833 pos_set_set (place);
834 base[order[i]] = place;
835 }
836
837 /* Use the greatest possible negative infinites. */
838 base_ninf = table_ninf_remap (base, nvectors, BASE_MINIMUM);
839 table_ninf = table_ninf_remap (table, high + 1, ACTION_NUMBER_MINIMUM);
840
841 bitset_free (pos_set);
842 }
843
844
845
846 /*-----------------------------------------------------------------.
847 | Compute and output yydefact, yydefgoto, yypact, yypgoto, yytable |
848 | and yycheck. |
849 `-----------------------------------------------------------------*/
850
851 void
852 tables_generate (void)
853 {
854 /* This is a poor way to make sure the sizes are properly
855 correlated. In particular the signedness is not taken into
856 account. But it's not useless. */
857 verify (sizeof nstates <= sizeof nvectors);
858 verify (sizeof nnterms <= sizeof nvectors);
859
860 nvectors = state_number_as_int (nstates) + nnterms;
861
862 froms = xcalloc (nvectors, sizeof *froms);
863 tos = xcalloc (nvectors, sizeof *tos);
864 conflict_tos = xcalloc (nvectors, sizeof *conflict_tos);
865 tally = xcalloc (nvectors, sizeof *tally);
866 width = xnmalloc (nvectors, sizeof *width);
867
868 token_actions ();
869
870 goto_actions ();
871 free (goto_map);
872 free (from_state);
873 free (to_state);
874
875 order = xcalloc (nvectors, sizeof *order);
876 sort_actions ();
877 pack_table ();
878 free (order);
879
880 free (tally);
881 free (width);
882
883 for (int i = 0; i < nvectors; i++)
884 {
885 free (froms[i]);
886 free (tos[i]);
887 free (conflict_tos[i]);
888 }
889
890 free (froms);
891 free (tos);
892 free (conflict_tos);
893 }
894
895
896 /*-------------------------.
897 | Free the parser tables. |
898 `-------------------------*/
899
900 void
901 tables_free (void)
902 {
903 free (base);
904 free (conflict_table);
905 free (conflict_list);
906 free (table);
907 free (check);
908 free (yydefgoto);
909 free (yydefact);
910 }