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