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