]>
Commit | Line | Data |
---|---|---|
1 | /* Output the generated parsing program for bison, | |
2 | Copyright 1984, 1986, 1989, 1992, 2000, 2001 Free Software Foundation, Inc. | |
3 | ||
4 | This file is part of Bison, the GNU Compiler Compiler. | |
5 | ||
6 | Bison is free software; you can redistribute it and/or modify it | |
7 | under the terms of the GNU General Public License as published by | |
8 | the Free Software Foundation; either version 2, or (at your option) | |
9 | any later version. | |
10 | ||
11 | Bison is distributed in the hope that it will be useful, but | |
12 | WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
17 | along with Bison; see the file COPYING. If not, write to the Free | |
18 | Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA | |
19 | 02111-1307, USA. */ | |
20 | ||
21 | ||
22 | /* The parser tables consist of these tables. | |
23 | Starred ones needed only for the semantic parser. | |
24 | Double starred are output only if switches are set. | |
25 | ||
26 | yytranslate = vector mapping yylex's token numbers into bison's token | |
27 | numbers. | |
28 | ||
29 | ** yytname = vector of string-names indexed by bison token number | |
30 | ||
31 | ** yytoknum = vector of yylex token numbers corresponding to entries | |
32 | in yytname | |
33 | ||
34 | yyrline = vector of line-numbers of all rules. For yydebug printouts. | |
35 | ||
36 | yyrhs = vector of items of all rules. | |
37 | This is exactly what ritems contains. For yydebug and for semantic | |
38 | parser. | |
39 | ||
40 | yyprhs[r] = index in yyrhs of first item for rule r. | |
41 | ||
42 | yyr1[r] = symbol number of symbol that rule r derives. | |
43 | ||
44 | yyr2[r] = number of symbols composing right hand side of rule r. | |
45 | ||
46 | * yystos[s] = the symbol number of the symbol that leads to state s. | |
47 | ||
48 | yydefact[s] = default rule to reduce with in state s, | |
49 | when yytable doesn't specify something else to do. | |
50 | Zero means the default is an error. | |
51 | ||
52 | yydefgoto[i] = default state to go to after a reduction of a rule that | |
53 | generates variable ntokens + i, except when yytable | |
54 | specifies something else to do. | |
55 | ||
56 | yypact[s] = index in yytable of the portion describing state s. | |
57 | The lookahead token's type is used to index that portion | |
58 | to find out what to do. | |
59 | ||
60 | If the value in yytable is positive, | |
61 | we shift the token and go to that state. | |
62 | ||
63 | If the value is negative, it is minus a rule number to reduce by. | |
64 | ||
65 | If the value is zero, the default action from yydefact[s] is used. | |
66 | ||
67 | yypgoto[i] = the index in yytable of the portion describing | |
68 | what to do after reducing a rule that derives variable i + ntokens. | |
69 | This portion is indexed by the parser state number, s, | |
70 | as of before the text for this nonterminal was read. | |
71 | The value from yytable is the state to go to if | |
72 | the corresponding value in yycheck is s. | |
73 | ||
74 | yytable = a vector filled with portions for different uses, | |
75 | found via yypact and yypgoto. | |
76 | ||
77 | yycheck = a vector indexed in parallel with yytable. | |
78 | It indicates, in a roundabout way, the bounds of the | |
79 | portion you are trying to examine. | |
80 | ||
81 | Suppose that the portion of yytable starts at index p | |
82 | and the index to be examined within the portion is i. | |
83 | Then if yycheck[p+i] != i, i is outside the bounds | |
84 | of what is actually allocated, and the default | |
85 | (from yydefact or yydefgoto) should be used. | |
86 | Otherwise, yytable[p+i] should be used. | |
87 | ||
88 | YYFINAL = the state number of the termination state. | |
89 | YYFLAG = most negative short int. Used to flag ?? | |
90 | YYNTBASE = ntokens. | |
91 | */ | |
92 | ||
93 | #include "system.h" | |
94 | #include "obstack.h" | |
95 | #include "quotearg.h" | |
96 | #include "getargs.h" | |
97 | #include "xalloc.h" | |
98 | #include "files.h" | |
99 | #include "gram.h" | |
100 | #include "LR0.h" | |
101 | #include "complain.h" | |
102 | #include "output.h" | |
103 | #include "lalr.h" | |
104 | #include "reader.h" | |
105 | #include "conflicts.h" | |
106 | #include "macrotab.h" | |
107 | ||
108 | extern void berror PARAMS((const char *)); | |
109 | ||
110 | static int nvectors; | |
111 | static int nentries; | |
112 | static short **froms; | |
113 | static short **tos; | |
114 | static short *tally; | |
115 | static short *width; | |
116 | static short *actrow; | |
117 | static short *state_count; | |
118 | static short *order; | |
119 | static short *base; | |
120 | static short *pos; | |
121 | static short *table; | |
122 | static short *check; | |
123 | static int lowzero; | |
124 | static int high; | |
125 | ||
126 | struct obstack macro_obstack; | |
127 | struct obstack output_obstack; | |
128 | ||
129 | /* FIXME. */ | |
130 | ||
131 | static inline void | |
132 | output_table_data (struct obstack* oout, | |
133 | short* table, | |
134 | short first, | |
135 | short begin, | |
136 | short end) | |
137 | { | |
138 | int i; | |
139 | int j = 1; | |
140 | ||
141 | obstack_fgrow1 (oout, "%6d", first); | |
142 | for (i = begin; i < end; ++i) | |
143 | { | |
144 | obstack_1grow (oout, ','); | |
145 | if (j >= 10) | |
146 | { | |
147 | obstack_sgrow (oout, "\n "); | |
148 | j = 1; | |
149 | } | |
150 | else | |
151 | ++j; | |
152 | obstack_fgrow1 (oout, "%6d", table[i]); | |
153 | } | |
154 | obstack_1grow (oout, 0); | |
155 | } | |
156 | ||
157 | ||
158 | static void | |
159 | output_token_translations (void) | |
160 | { | |
161 | output_table_data (&output_obstack, token_translations, | |
162 | 0, 1, max_user_token_number + 1); | |
163 | macro_insert ("translate", obstack_finish (&output_obstack)); | |
164 | } | |
165 | ||
166 | ||
167 | static void | |
168 | output_gram (void) | |
169 | { | |
170 | output_table_data (&output_obstack, rrhs, | |
171 | 0, 1, nrules + 1); | |
172 | macro_insert ("prhs", obstack_finish (&output_obstack)); | |
173 | ||
174 | { | |
175 | size_t yyrhs_size = 1; | |
176 | short *yyrhs, *sp; | |
177 | int i; | |
178 | ||
179 | for (sp = ritem + 1; *sp; sp++) | |
180 | ++yyrhs_size; | |
181 | yyrhs = XMALLOC (short, yyrhs_size); | |
182 | ||
183 | for (sp = ritem + 1, i = 1; *sp; ++sp, ++i) | |
184 | yyrhs[i] = *sp > 0 ? *sp : 0; | |
185 | ||
186 | output_table_data (&output_obstack, yyrhs, | |
187 | ritem[0], 1, yyrhs_size); | |
188 | macro_insert ("rhs", obstack_finish (&output_obstack)); | |
189 | ||
190 | XFREE (yyrhs); | |
191 | } | |
192 | ||
193 | /* if (!semantic_parser && !no_parser_flag) | |
194 | obstack_sgrow (&table_obstack, "\n#endif\n"); */ | |
195 | } | |
196 | ||
197 | ||
198 | static void | |
199 | output_stos (void) | |
200 | { | |
201 | output_table_data (&output_obstack, accessing_symbol, | |
202 | 0, 1, nstates); | |
203 | macro_insert ("stos", obstack_finish (&output_obstack)); | |
204 | } | |
205 | ||
206 | ||
207 | static void | |
208 | output_rule_data (void) | |
209 | { | |
210 | int i; | |
211 | int j; | |
212 | short *short_tab = NULL; | |
213 | ||
214 | output_table_data (&output_obstack, rline, | |
215 | 0, 1, nrules + 1); | |
216 | macro_insert ("rline", obstack_finish (&output_obstack)); | |
217 | ||
218 | j = 0; | |
219 | for (i = 0; i < nsyms; i++) | |
220 | /* this used to be i<=nsyms, but that output a final "" symbol | |
221 | almost by accident */ | |
222 | { | |
223 | /* Width of the next token, including the two quotes, the coma | |
224 | and the space. */ | |
225 | int strsize = 4; | |
226 | char *p; | |
227 | ||
228 | for (p = tags[i]; p && *p; p++) | |
229 | if (*p == '"' || *p == '\\' || *p == '\n' || *p == '\t' | |
230 | || *p == '\b') | |
231 | strsize += 2; | |
232 | else if (*p < 040 || *p >= 0177) | |
233 | strsize += 4; | |
234 | else | |
235 | strsize++; | |
236 | ||
237 | if (j + strsize > 75) | |
238 | { | |
239 | obstack_sgrow (&output_obstack, "\n "); | |
240 | j = 2; | |
241 | } | |
242 | ||
243 | obstack_1grow (&output_obstack, '\"'); | |
244 | for (p = tags[i]; p && *p; p++) | |
245 | { | |
246 | if (*p == '"' || *p == '\\') | |
247 | obstack_fgrow1 (&output_obstack, "\\%c", *p); | |
248 | else if (*p == '\n') | |
249 | obstack_sgrow (&output_obstack, "\\n"); | |
250 | else if (*p == '\t') | |
251 | obstack_sgrow (&output_obstack, "\\t"); | |
252 | else if (*p == '\b') | |
253 | obstack_sgrow (&output_obstack, "\\b"); | |
254 | else if (*p < 040 || *p >= 0177) | |
255 | obstack_fgrow1 (&output_obstack, "\\%03o", *p); | |
256 | else | |
257 | obstack_1grow (&output_obstack, *p); | |
258 | } | |
259 | ||
260 | obstack_sgrow (&output_obstack, "\", "); | |
261 | j += strsize; | |
262 | } | |
263 | /* add a NULL entry to list of tokens */ | |
264 | obstack_sgrow (&output_obstack, "NULL"); | |
265 | ||
266 | /* Finish table and store. */ | |
267 | obstack_1grow (&output_obstack, 0); | |
268 | macro_insert ("tname", obstack_finish (&output_obstack)); | |
269 | ||
270 | /* Output YYTOKNUM. */ | |
271 | output_table_data (&output_obstack, user_toknums, | |
272 | 0, 1, ntokens + 1); | |
273 | macro_insert ("toknum", obstack_finish (&output_obstack)); | |
274 | ||
275 | /* Output YYR1. */ | |
276 | output_table_data (&output_obstack, rlhs, | |
277 | 0, 1, nrules + 1); | |
278 | macro_insert ("r1", obstack_finish (&output_obstack)); | |
279 | XFREE (rlhs + 1); | |
280 | ||
281 | /* Output YYR2. */ | |
282 | short_tab = XMALLOC (short, nrules + 1); | |
283 | for (i = 1; i < nrules; i++) | |
284 | short_tab[i] = rrhs[i + 1] - rrhs[i] - 1; | |
285 | short_tab[nrules] = nitems - rrhs[nrules] - 1; | |
286 | output_table_data (&output_obstack, short_tab, | |
287 | 0, 1, nrules + 1); | |
288 | macro_insert ("r2", obstack_finish (&output_obstack)); | |
289 | XFREE (short_tab); | |
290 | ||
291 | XFREE (rrhs + 1); | |
292 | } | |
293 | ||
294 | /*------------------------------------------------------------------. | |
295 | | Decide what to do for each type of token if seen as the lookahead | | |
296 | | token 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 | | MINSHORT, a very negative number, means this situation is an | | |
301 | | error. The parser recognizes this value specially. | | |
302 | | | | |
303 | | This is where conflicts are resolved. The loop over lookahead | | |
304 | | rules considered lower-numbered rules last, and the last rule | | |
305 | | considered that likes a token gets to handle it. | | |
306 | `------------------------------------------------------------------*/ | |
307 | ||
308 | static int | |
309 | action_row (int state) | |
310 | { | |
311 | int i; | |
312 | int j; | |
313 | int k; | |
314 | int m = 0; | |
315 | int n = 0; | |
316 | int count; | |
317 | int default_rule; | |
318 | int nreds; | |
319 | int max; | |
320 | int rule; | |
321 | int shift_state; | |
322 | int symbol; | |
323 | unsigned mask; | |
324 | unsigned *wordp; | |
325 | reductions *redp; | |
326 | shifts *shiftp; | |
327 | errs *errp; | |
328 | int nodefault = 0; /* set nonzero to inhibit having any default reduction */ | |
329 | ||
330 | for (i = 0; i < ntokens; i++) | |
331 | actrow[i] = 0; | |
332 | ||
333 | default_rule = 0; | |
334 | nreds = 0; | |
335 | redp = reduction_table[state]; | |
336 | ||
337 | if (redp) | |
338 | { | |
339 | nreds = redp->nreds; | |
340 | ||
341 | if (nreds >= 1) | |
342 | { | |
343 | /* loop over all the rules available here which require | |
344 | lookahead */ | |
345 | m = lookaheads[state]; | |
346 | n = lookaheads[state + 1]; | |
347 | ||
348 | for (i = n - 1; i >= m; i--) | |
349 | { | |
350 | rule = -LAruleno[i]; | |
351 | wordp = LA + i * tokensetsize; | |
352 | mask = 1; | |
353 | ||
354 | /* and find each token which the rule finds acceptable | |
355 | to come next */ | |
356 | for (j = 0; j < ntokens; j++) | |
357 | { | |
358 | /* and record this rule as the rule to use if that | |
359 | token follows. */ | |
360 | if (mask & *wordp) | |
361 | actrow[j] = rule; | |
362 | ||
363 | mask <<= 1; | |
364 | if (mask == 0) | |
365 | { | |
366 | mask = 1; | |
367 | wordp++; | |
368 | } | |
369 | } | |
370 | } | |
371 | } | |
372 | } | |
373 | ||
374 | shiftp = shift_table[state]; | |
375 | ||
376 | /* Now see which tokens are allowed for shifts in this state. For | |
377 | them, record the shift as the thing to do. So shift is preferred | |
378 | to reduce. */ | |
379 | ||
380 | if (shiftp) | |
381 | { | |
382 | k = shiftp->nshifts; | |
383 | ||
384 | for (i = 0; i < k; i++) | |
385 | { | |
386 | shift_state = shiftp->shifts[i]; | |
387 | if (!shift_state) | |
388 | continue; | |
389 | ||
390 | symbol = accessing_symbol[shift_state]; | |
391 | ||
392 | if (ISVAR (symbol)) | |
393 | break; | |
394 | ||
395 | actrow[symbol] = shift_state; | |
396 | ||
397 | /* Do not use any default reduction if there is a shift for | |
398 | error */ | |
399 | if (symbol == error_token_number) | |
400 | nodefault = 1; | |
401 | } | |
402 | } | |
403 | ||
404 | errp = err_table[state]; | |
405 | ||
406 | /* See which tokens are an explicit error in this state (due to | |
407 | %nonassoc). For them, record MINSHORT as the action. */ | |
408 | ||
409 | if (errp) | |
410 | { | |
411 | k = errp->nerrs; | |
412 | ||
413 | for (i = 0; i < k; i++) | |
414 | { | |
415 | symbol = errp->errs[i]; | |
416 | actrow[symbol] = MINSHORT; | |
417 | } | |
418 | } | |
419 | ||
420 | /* Now find the most common reduction and make it the default action | |
421 | for this state. */ | |
422 | ||
423 | if (nreds >= 1 && !nodefault) | |
424 | { | |
425 | if (consistent[state]) | |
426 | default_rule = redp->rules[0]; | |
427 | else | |
428 | { | |
429 | max = 0; | |
430 | for (i = m; i < n; i++) | |
431 | { | |
432 | count = 0; | |
433 | rule = -LAruleno[i]; | |
434 | ||
435 | for (j = 0; j < ntokens; j++) | |
436 | { | |
437 | if (actrow[j] == rule) | |
438 | count++; | |
439 | } | |
440 | ||
441 | if (count > max) | |
442 | { | |
443 | max = count; | |
444 | default_rule = rule; | |
445 | } | |
446 | } | |
447 | ||
448 | /* actions which match the default are replaced with zero, | |
449 | which means "use the default" */ | |
450 | ||
451 | if (max > 0) | |
452 | { | |
453 | for (j = 0; j < ntokens; j++) | |
454 | { | |
455 | if (actrow[j] == default_rule) | |
456 | actrow[j] = 0; | |
457 | } | |
458 | ||
459 | default_rule = -default_rule; | |
460 | } | |
461 | } | |
462 | } | |
463 | ||
464 | /* If have no default rule, the default is an error. | |
465 | So replace any action which says "error" with "use default". */ | |
466 | ||
467 | if (default_rule == 0) | |
468 | for (j = 0; j < ntokens; j++) | |
469 | { | |
470 | if (actrow[j] == MINSHORT) | |
471 | actrow[j] = 0; | |
472 | } | |
473 | ||
474 | return default_rule; | |
475 | } | |
476 | ||
477 | ||
478 | static void | |
479 | save_row (int state) | |
480 | { | |
481 | int i; | |
482 | int count; | |
483 | short *sp; | |
484 | short *sp1; | |
485 | short *sp2; | |
486 | ||
487 | count = 0; | |
488 | for (i = 0; i < ntokens; i++) | |
489 | { | |
490 | if (actrow[i] != 0) | |
491 | count++; | |
492 | } | |
493 | ||
494 | if (count == 0) | |
495 | return; | |
496 | ||
497 | froms[state] = sp1 = sp = XCALLOC (short, count); | |
498 | tos[state] = sp2 = XCALLOC (short, count); | |
499 | ||
500 | for (i = 0; i < ntokens; i++) | |
501 | { | |
502 | if (actrow[i] != 0) | |
503 | { | |
504 | *sp1++ = i; | |
505 | *sp2++ = actrow[i]; | |
506 | } | |
507 | } | |
508 | ||
509 | tally[state] = count; | |
510 | width[state] = sp1[-1] - sp[0] + 1; | |
511 | } | |
512 | ||
513 | ||
514 | /*------------------------------------------------------------------. | |
515 | | Figure out the actions for the specified state, indexed by | | |
516 | | lookahead token type. | | |
517 | | | | |
518 | | The YYDEFACT table is output now. The detailed info is saved for | | |
519 | | putting into YYTABLE later. | | |
520 | `------------------------------------------------------------------*/ | |
521 | ||
522 | static void | |
523 | token_actions (void) | |
524 | { | |
525 | int i; | |
526 | short *yydefact = XCALLOC (short, nstates); | |
527 | ||
528 | actrow = XCALLOC (short, ntokens); | |
529 | for (i = 0; i < nstates; ++i) | |
530 | { | |
531 | yydefact[i] = action_row (i); | |
532 | save_row (i); | |
533 | } | |
534 | ||
535 | output_table_data (&output_obstack, yydefact, | |
536 | yydefact[0], 1, nstates); | |
537 | macro_insert ("defact", obstack_finish (&output_obstack)); | |
538 | ||
539 | XFREE (actrow); | |
540 | XFREE (yydefact); | |
541 | } | |
542 | ||
543 | ||
544 | static void | |
545 | free_shifts (void) | |
546 | { | |
547 | shifts *sp, *sptmp; /* JF derefrenced freed ptr */ | |
548 | ||
549 | XFREE (shift_table); | |
550 | ||
551 | for (sp = first_shift; sp; sp = sptmp) | |
552 | { | |
553 | sptmp = sp->next; | |
554 | XFREE (sp); | |
555 | } | |
556 | } | |
557 | ||
558 | ||
559 | static void | |
560 | free_reductions (void) | |
561 | { | |
562 | reductions *rp, *rptmp; /* JF fixed freed ptr */ | |
563 | ||
564 | XFREE (reduction_table); | |
565 | ||
566 | for (rp = first_reduction; rp; rp = rptmp) | |
567 | { | |
568 | rptmp = rp->next; | |
569 | XFREE (rp); | |
570 | } | |
571 | } | |
572 | ||
573 | ||
574 | ||
575 | static void | |
576 | save_column (int symbol, int default_state) | |
577 | { | |
578 | int i; | |
579 | short *sp; | |
580 | short *sp1; | |
581 | short *sp2; | |
582 | int count; | |
583 | int symno; | |
584 | ||
585 | short begin = goto_map[symbol]; | |
586 | short end = goto_map[symbol + 1]; | |
587 | ||
588 | count = 0; | |
589 | for (i = begin; i < end; i++) | |
590 | { | |
591 | if (to_state[i] != default_state) | |
592 | count++; | |
593 | } | |
594 | ||
595 | if (count == 0) | |
596 | return; | |
597 | ||
598 | symno = symbol - ntokens + nstates; | |
599 | ||
600 | froms[symno] = sp1 = sp = XCALLOC (short, count); | |
601 | tos[symno] = sp2 = XCALLOC (short, count); | |
602 | ||
603 | for (i = begin; i < end; i++) | |
604 | { | |
605 | if (to_state[i] != default_state) | |
606 | { | |
607 | *sp1++ = from_state[i]; | |
608 | *sp2++ = to_state[i]; | |
609 | } | |
610 | } | |
611 | ||
612 | tally[symno] = count; | |
613 | width[symno] = sp1[-1] - sp[0] + 1; | |
614 | } | |
615 | ||
616 | static int | |
617 | default_goto (int symbol) | |
618 | { | |
619 | int i; | |
620 | int m; | |
621 | int n; | |
622 | int default_state; | |
623 | int max; | |
624 | ||
625 | m = goto_map[symbol]; | |
626 | n = goto_map[symbol + 1]; | |
627 | ||
628 | if (m == n) | |
629 | return -1; | |
630 | ||
631 | for (i = 0; i < nstates; i++) | |
632 | state_count[i] = 0; | |
633 | ||
634 | for (i = m; i < n; i++) | |
635 | state_count[to_state[i]]++; | |
636 | ||
637 | max = 0; | |
638 | default_state = -1; | |
639 | ||
640 | for (i = 0; i < nstates; i++) | |
641 | { | |
642 | if (state_count[i] > max) | |
643 | { | |
644 | max = state_count[i]; | |
645 | default_state = i; | |
646 | } | |
647 | } | |
648 | ||
649 | return default_state; | |
650 | } | |
651 | ||
652 | ||
653 | /*-------------------------------------------------------------------. | |
654 | | Figure out what to do after reducing with each rule, depending on | | |
655 | | the saved state from before the beginning of parsing the data that | | |
656 | | matched this rule. | | |
657 | | | | |
658 | | The YYDEFGOTO table is output now. The detailed info is saved for | | |
659 | | putting into YYTABLE later. | | |
660 | `-------------------------------------------------------------------*/ | |
661 | ||
662 | static void | |
663 | goto_actions (void) | |
664 | { | |
665 | int i; | |
666 | short *yydefgoto = XMALLOC (short, nsyms - ntokens); | |
667 | ||
668 | state_count = XCALLOC (short, nstates); | |
669 | for (i = ntokens; i < nsyms; ++i) | |
670 | { | |
671 | int default_state = default_goto (i); | |
672 | save_column (i, default_state); | |
673 | yydefgoto[i - ntokens] = default_state; | |
674 | } | |
675 | ||
676 | output_table_data (&output_obstack, yydefgoto, | |
677 | yydefgoto[0], 1, nsyms - ntokens); | |
678 | macro_insert ("defgoto", obstack_finish (&output_obstack)); | |
679 | ||
680 | XFREE (state_count); | |
681 | XFREE (yydefgoto); | |
682 | } | |
683 | ||
684 | ||
685 | /* The next few functions decide how to pack the actions and gotos | |
686 | information into yytable. */ | |
687 | ||
688 | static void | |
689 | sort_actions (void) | |
690 | { | |
691 | int i; | |
692 | int j; | |
693 | int k; | |
694 | int t; | |
695 | int w; | |
696 | ||
697 | order = XCALLOC (short, nvectors); | |
698 | nentries = 0; | |
699 | ||
700 | for (i = 0; i < nvectors; i++) | |
701 | { | |
702 | if (tally[i] > 0) | |
703 | { | |
704 | t = tally[i]; | |
705 | w = width[i]; | |
706 | j = nentries - 1; | |
707 | ||
708 | while (j >= 0 && (width[order[j]] < w)) | |
709 | j--; | |
710 | ||
711 | while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t)) | |
712 | j--; | |
713 | ||
714 | for (k = nentries - 1; k > j; k--) | |
715 | order[k + 1] = order[k]; | |
716 | ||
717 | order[j + 1] = i; | |
718 | nentries++; | |
719 | } | |
720 | } | |
721 | } | |
722 | ||
723 | ||
724 | static int | |
725 | matching_state (int vector) | |
726 | { | |
727 | int i; | |
728 | int j; | |
729 | int k; | |
730 | int t; | |
731 | int w; | |
732 | int match; | |
733 | int prev; | |
734 | ||
735 | i = order[vector]; | |
736 | if (i >= nstates) | |
737 | return -1; | |
738 | ||
739 | t = tally[i]; | |
740 | w = width[i]; | |
741 | ||
742 | for (prev = vector - 1; prev >= 0; prev--) | |
743 | { | |
744 | j = order[prev]; | |
745 | if (width[j] != w || tally[j] != t) | |
746 | return -1; | |
747 | ||
748 | match = 1; | |
749 | for (k = 0; match && k < t; k++) | |
750 | { | |
751 | if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k]) | |
752 | match = 0; | |
753 | } | |
754 | ||
755 | if (match) | |
756 | return j; | |
757 | } | |
758 | ||
759 | return -1; | |
760 | } | |
761 | ||
762 | ||
763 | static int | |
764 | pack_vector (int vector) | |
765 | { | |
766 | int i; | |
767 | int j; | |
768 | int k; | |
769 | int t; | |
770 | int loc = 0; | |
771 | int ok; | |
772 | short *from; | |
773 | short *to; | |
774 | ||
775 | i = order[vector]; | |
776 | t = tally[i]; | |
777 | ||
778 | assert (t); | |
779 | ||
780 | from = froms[i]; | |
781 | to = tos[i]; | |
782 | ||
783 | for (j = lowzero - from[0]; j < MAXTABLE; j++) | |
784 | { | |
785 | ok = 1; | |
786 | ||
787 | for (k = 0; ok && k < t; k++) | |
788 | { | |
789 | loc = j + from[k]; | |
790 | if (loc > MAXTABLE) | |
791 | fatal (_("maximum table size (%d) exceeded"), MAXTABLE); | |
792 | ||
793 | if (table[loc] != 0) | |
794 | ok = 0; | |
795 | } | |
796 | ||
797 | for (k = 0; ok && k < vector; k++) | |
798 | { | |
799 | if (pos[k] == j) | |
800 | ok = 0; | |
801 | } | |
802 | ||
803 | if (ok) | |
804 | { | |
805 | for (k = 0; k < t; k++) | |
806 | { | |
807 | loc = j + from[k]; | |
808 | table[loc] = to[k]; | |
809 | check[loc] = from[k]; | |
810 | } | |
811 | ||
812 | while (table[lowzero] != 0) | |
813 | lowzero++; | |
814 | ||
815 | if (loc > high) | |
816 | high = loc; | |
817 | ||
818 | return j; | |
819 | } | |
820 | } | |
821 | ||
822 | berror ("pack_vector"); | |
823 | return 0; /* JF keep lint happy */ | |
824 | } | |
825 | ||
826 | ||
827 | static void | |
828 | pack_table (void) | |
829 | { | |
830 | int i; | |
831 | int place; | |
832 | int state; | |
833 | ||
834 | base = XCALLOC (short, nvectors); | |
835 | pos = XCALLOC (short, nentries); | |
836 | table = XCALLOC (short, MAXTABLE); | |
837 | check = XCALLOC (short, MAXTABLE); | |
838 | ||
839 | lowzero = 0; | |
840 | high = 0; | |
841 | ||
842 | for (i = 0; i < nvectors; i++) | |
843 | base[i] = MINSHORT; | |
844 | ||
845 | for (i = 0; i < MAXTABLE; i++) | |
846 | check[i] = -1; | |
847 | ||
848 | for (i = 0; i < nentries; i++) | |
849 | { | |
850 | state = matching_state (i); | |
851 | ||
852 | if (state < 0) | |
853 | place = pack_vector (i); | |
854 | else | |
855 | place = base[state]; | |
856 | ||
857 | pos[i] = place; | |
858 | base[order[i]] = place; | |
859 | } | |
860 | ||
861 | for (i = 0; i < nvectors; i++) | |
862 | { | |
863 | if (froms[i]) | |
864 | XFREE (froms[i]); | |
865 | if (tos[i]) | |
866 | XFREE (tos[i]); | |
867 | } | |
868 | ||
869 | XFREE (froms); | |
870 | XFREE (tos); | |
871 | XFREE (pos); | |
872 | } | |
873 | ||
874 | /* the following functions output yytable, yycheck | |
875 | and the vectors whose elements index the portion starts */ | |
876 | ||
877 | static void | |
878 | output_base (void) | |
879 | { | |
880 | /* Output pact. */ | |
881 | output_table_data (&output_obstack, base, | |
882 | base[0], 1, nstates); | |
883 | macro_insert ("pact", obstack_finish (&output_obstack)); | |
884 | ||
885 | /* Output pgoto. */ | |
886 | output_table_data (&output_obstack, base, | |
887 | base[nstates], nstates + 1, nvectors); | |
888 | macro_insert ("pgoto", obstack_finish (&output_obstack)); | |
889 | ||
890 | XFREE (base); | |
891 | } | |
892 | ||
893 | ||
894 | static void | |
895 | output_table (void) | |
896 | { | |
897 | output_table_data (&output_obstack, table, | |
898 | table[0], 1, high + 1); | |
899 | macro_insert ("table", obstack_finish (&output_obstack)); | |
900 | XFREE (table); | |
901 | } | |
902 | ||
903 | ||
904 | static void | |
905 | output_check (void) | |
906 | { | |
907 | output_table_data (&output_obstack, check, | |
908 | check[0], 1, high + 1); | |
909 | macro_insert ("check", obstack_finish (&output_obstack)); | |
910 | XFREE (check); | |
911 | } | |
912 | ||
913 | /* compute and output yydefact, yydefgoto, yypact, yypgoto, yytable | |
914 | and yycheck. */ | |
915 | ||
916 | static void | |
917 | output_actions (void) | |
918 | { | |
919 | nvectors = nstates + nvars; | |
920 | ||
921 | froms = XCALLOC (short *, nvectors); | |
922 | tos = XCALLOC (short *, nvectors); | |
923 | tally = XCALLOC (short, nvectors); | |
924 | width = XCALLOC (short, nvectors); | |
925 | ||
926 | token_actions (); | |
927 | free_shifts (); | |
928 | free_reductions (); | |
929 | XFREE (lookaheads); | |
930 | XFREE (LA); | |
931 | XFREE (LAruleno); | |
932 | XFREE (accessing_symbol); | |
933 | ||
934 | goto_actions (); | |
935 | XFREE (goto_map + ntokens); | |
936 | XFREE (from_state); | |
937 | XFREE (to_state); | |
938 | ||
939 | sort_actions (); | |
940 | pack_table (); | |
941 | /* FIXME: See if this is useful. */ | |
942 | /* obstack_1grow (&table_obstack, '\n'); */ | |
943 | output_base (); | |
944 | output_table (); | |
945 | /* FIXME: See if this is useful. */ | |
946 | /* obstack_1grow (&table_obstack, '\n'); */ | |
947 | output_check (); | |
948 | } | |
949 | ||
950 | /*------------------------------------------. | |
951 | | Copy the parser code into TABLE_OBSTACK. | | |
952 | `------------------------------------------*/ | |
953 | ||
954 | static void | |
955 | output_parser (void) | |
956 | { | |
957 | int c; | |
958 | FILE *fskel; | |
959 | size_t line; | |
960 | int actions_dumped = 0; | |
961 | ||
962 | /* Loop over lines in the standard parser file. */ | |
963 | if (!skeleton) | |
964 | { | |
965 | if (semantic_parser) | |
966 | skeleton = skeleton_find ("BISON_HAIRY", BISON_HAIRY); | |
967 | else | |
968 | skeleton = skeleton_find ("BISON_SIMPLE", BISON_SIMPLE); | |
969 | } | |
970 | fskel = xfopen (skeleton, "r"); | |
971 | ||
972 | /* New output code. */ | |
973 | line = 1; | |
974 | c = getc (fskel); | |
975 | while (c != EOF) | |
976 | { | |
977 | if (c != '%') | |
978 | { | |
979 | if (c == '\n') | |
980 | ++line; | |
981 | obstack_1grow (&table_obstack, c); | |
982 | c = getc (fskel); | |
983 | } | |
984 | else if ((c = getc (fskel)) == '%') | |
985 | { | |
986 | /* Read the macro. */ | |
987 | char* macro_key = 0; | |
988 | char* macro_value = 0; | |
989 | while (isalnum (c = getc (fskel)) || c == '_') | |
990 | obstack_1grow (¯o_obstack, c); | |
991 | obstack_1grow (¯o_obstack, 0); | |
992 | ||
993 | /* Output the right value, or see if it's something special. */ | |
994 | macro_key = obstack_finish (¯o_obstack); | |
995 | macro_value = macro_find (macro_key); | |
996 | if (macro_value) | |
997 | obstack_sgrow (&table_obstack, macro_value); | |
998 | else if (!strcmp (macro_key, "line")) | |
999 | obstack_fgrow1 (&table_obstack, "%d", line + 1); | |
1000 | else if (!strcmp (macro_key, "action")) | |
1001 | { | |
1002 | size_t size = obstack_object_size (&action_obstack); | |
1003 | obstack_grow (&table_obstack, | |
1004 | obstack_finish (&action_obstack), size); | |
1005 | } | |
1006 | else | |
1007 | { | |
1008 | obstack_sgrow (&table_obstack, "%%"); | |
1009 | obstack_sgrow (&table_obstack, macro_key); | |
1010 | } | |
1011 | } | |
1012 | } | |
1013 | ||
1014 | /* End. */ | |
1015 | xfclose (fskel); | |
1016 | } | |
1017 | ||
1018 | static void | |
1019 | output_program (void) | |
1020 | { | |
1021 | int c; | |
1022 | ||
1023 | while ((c = getc (finput)) != EOF) | |
1024 | obstack_1grow (&table_obstack, c); | |
1025 | } | |
1026 | ||
1027 | ||
1028 | static void | |
1029 | free_itemsets (void) | |
1030 | { | |
1031 | core *cp, *cptmp; | |
1032 | ||
1033 | XFREE (state_table); | |
1034 | ||
1035 | for (cp = first_state; cp; cp = cptmp) | |
1036 | { | |
1037 | cptmp = cp->next; | |
1038 | XFREE (cp); | |
1039 | } | |
1040 | } | |
1041 | ||
1042 | /* FIXME. */ | |
1043 | ||
1044 | #define MACRO_INSERT_INT(Key, Value) \ | |
1045 | { \ | |
1046 | obstack_fgrow1 (¯o_obstack, "%d", Value); \ | |
1047 | obstack_1grow (¯o_obstack, 0); \ | |
1048 | macro_insert (Key, obstack_finish (¯o_obstack)); \ | |
1049 | } | |
1050 | ||
1051 | #define MACRO_INSERT_STRING(Key, Value) \ | |
1052 | { \ | |
1053 | obstack_sgrow (¯o_obstack, Value); \ | |
1054 | obstack_1grow (¯o_obstack, 0); \ | |
1055 | macro_insert (Key, obstack_finish (¯o_obstack)); \ | |
1056 | } | |
1057 | ||
1058 | #define MACRO_INSERT_PREFIX(Key, Value) \ | |
1059 | { \ | |
1060 | obstack_fgrow2 (¯o_obstack, "%s%s", spec_name_prefix, Value); \ | |
1061 | obstack_1grow (¯o_obstack, 0); \ | |
1062 | macro_insert (Key, obstack_finish (¯o_obstack)); \ | |
1063 | } | |
1064 | ||
1065 | static void | |
1066 | prepare (void) | |
1067 | { | |
1068 | MACRO_INSERT_INT ("last", high); | |
1069 | MACRO_INSERT_INT ("flag", MINSHORT); | |
1070 | MACRO_INSERT_INT ("pure", pure_parser); | |
1071 | MACRO_INSERT_INT ("nsym", nsyms); | |
1072 | MACRO_INSERT_INT ("debug", debug_flag); | |
1073 | MACRO_INSERT_INT ("final", final_state); | |
1074 | MACRO_INSERT_INT ("maxtok", max_user_token_number); | |
1075 | MACRO_INSERT_INT ("ntbase", ntokens); | |
1076 | MACRO_INSERT_INT ("verbose", 0); | |
1077 | ||
1078 | MACRO_INSERT_STRING ("filename", infile); | |
1079 | ||
1080 | MACRO_INSERT_INT ("nnts", nvars); | |
1081 | MACRO_INSERT_INT ("nrules", nrules); | |
1082 | MACRO_INSERT_INT ("nstates", nstates); | |
1083 | MACRO_INSERT_INT ("ntokens", ntokens); | |
1084 | ||
1085 | if (spec_name_prefix) | |
1086 | { | |
1087 | MACRO_INSERT_PREFIX ("yylex", "lex"); | |
1088 | MACRO_INSERT_PREFIX ("yychar", "char"); | |
1089 | MACRO_INSERT_PREFIX ("yylval", "lval"); | |
1090 | MACRO_INSERT_PREFIX ("yydebug", "debug"); | |
1091 | MACRO_INSERT_PREFIX ("yyerror", "error"); | |
1092 | MACRO_INSERT_PREFIX ("yynerrs", "nerrs"); | |
1093 | MACRO_INSERT_PREFIX ("yyparse", "parse"); | |
1094 | } | |
1095 | } | |
1096 | ||
1097 | /*----------------------------------------------------------. | |
1098 | | Output the parsing tables and the parser code to ftable. | | |
1099 | `----------------------------------------------------------*/ | |
1100 | ||
1101 | void | |
1102 | output (void) | |
1103 | { | |
1104 | obstack_init (¯o_obstack); | |
1105 | obstack_init (&output_obstack); | |
1106 | ||
1107 | #if 0 | |
1108 | /* If using a simple parser the definition of YYSTYPE are put into | |
1109 | TABLE_OBSTACK. */ | |
1110 | if (!semantic_parser) | |
1111 | { | |
1112 | size_t size = obstack_object_size (&attrs_obstack); | |
1113 | obstack_grow (&table_obstack, obstack_finish (&attrs_obstack), size); | |
1114 | } | |
1115 | #endif | |
1116 | ||
1117 | /* reader_output_yylsp (&table_obstack); */ | |
1118 | free_itemsets (); | |
1119 | ||
1120 | output_token_translations (); | |
1121 | output_gram (); | |
1122 | ||
1123 | XFREE (ritem); | |
1124 | if (semantic_parser) | |
1125 | output_stos (); | |
1126 | output_rule_data (); | |
1127 | output_actions (); | |
1128 | ||
1129 | /* if (!no_parser_flag) */ | |
1130 | prepare (); | |
1131 | output_parser (); | |
1132 | output_program (); | |
1133 | ||
1134 | obstack_free (¯o_obstack, 0); | |
1135 | obstack_free (&output_obstack, 0); | |
1136 | } |