]> git.saurik.com Git - bison.git/blame - src/output.c
* configure.in: Check the protos of strchr ans strspn.
[bison.git] / src / output.c
CommitLineData
c3e23647 1/* Output the generated parsing program for bison,
fabd3b43 2 Copyright 1984, 1986, 1989, 1992, 2000, 2001 Free Software Foundation, Inc.
c3e23647 3
9ee3c97b 4 This file is part of Bison, the GNU Compiler Compiler.
c3e23647 5
9ee3c97b
AD
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.
c3e23647 10
9ee3c97b
AD
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.
c3e23647 15
9ee3c97b
AD
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. */
c3e23647
RS
20
21
6c89f1c1
AD
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.
c3e23647 25
6c89f1c1
AD
26 yytranslate = vector mapping yylex's token numbers into bison's token
27 numbers.
c3e23647 28
6c89f1c1 29 ** yytname = vector of string-names indexed by bison token number
c3e23647 30
6c89f1c1
AD
31 ** yytoknum = vector of yylex token numbers corresponding to entries
32 in yytname
c3e23647 33
6c89f1c1 34 yyrline = vector of line-numbers of all rules. For yydebug printouts.
c3e23647 35
6c89f1c1
AD
36 yyrhs = vector of items of all rules.
37 This is exactly what ritems contains. For yydebug and for semantic
38 parser.
c3e23647 39
6c89f1c1 40 yyprhs[r] = index in yyrhs of first item for rule r.
c3e23647 41
6c89f1c1 42 yyr1[r] = symbol number of symbol that rule r derives.
c3e23647 43
6c89f1c1 44 yyr2[r] = number of symbols composing right hand side of rule r.
c3e23647 45
6c89f1c1 46 * yystos[s] = the symbol number of the symbol that leads to state s.
e372befa 47
6c89f1c1
AD
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.
c3e23647 51
6c89f1c1
AD
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.
c3e23647 55
6c89f1c1
AD
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.
c3e23647 59
6c89f1c1
AD
60 If the value in yytable is positive,
61 we shift the token and go to that state.
c3e23647 62
6c89f1c1 63 If the value is negative, it is minus a rule number to reduce by.
c3e23647 64
6c89f1c1 65 If the value is zero, the default action from yydefact[s] is used.
c3e23647 66
6c89f1c1
AD
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.
c3e23647 73
6c89f1c1
AD
74 yytable = a vector filled with portions for different uses,
75 found via yypact and yypgoto.
c3e23647 76
6c89f1c1
AD
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.
c3e23647 80
6c89f1c1
AD
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.
c3e23647 87
6c89f1c1
AD
88 YYFINAL = the state number of the termination state.
89 YYFLAG = most negative short int. Used to flag ??
90 YYNTBASE = ntokens.
c3e23647
RS
91*/
92
c3e23647 93#include "system.h"
14d3eb9b 94#include "quotearg.h"
ceed8467 95#include "getargs.h"
c3e23647
RS
96#include "files.h"
97#include "gram.h"
b2ca4022 98#include "LR0.h"
a0f6b076 99#include "complain.h"
6c89f1c1 100#include "output.h"
720d742f 101#include "lalr.h"
a70083a3 102#include "reader.h"
0619caf0 103#include "conflicts.h"
11d82f03 104#include "muscle_tab.h"
c3e23647 105
d019d655 106
c3e23647
RS
107static int nvectors;
108static int nentries;
342b8b6e
AD
109static short **froms = NULL;
110static short **tos = NULL;
111static short *tally = NULL;
112static short *width = NULL;
113static short *actrow = NULL;
114static short *state_count = NULL;
115static short *order = NULL;
116static short *base = NULL;
117static short *pos = NULL;
118static short *table = NULL;
119static short *check = NULL;
c3e23647
RS
120static int lowzero;
121static int high;
122
11d82f03 123struct obstack muscle_obstack;
f87685c3 124static struct obstack format_obstack;
c3e23647 125
c7925b99
MA
126int error_verbose = 0;
127
f0440388
MA
128/* Returns the number of lines of S. */
129static size_t
130get_lines_number (const char *s)
131{
132 size_t lines = 0;
1fa14068 133
f0440388
MA
134 size_t i;
135 for (i = 0; s[i]; ++i)
d0b0fefa
AD
136 if (s[i] == '\n')
137 ++lines;
1fa14068 138
f0440388
MA
139 return lines;
140}
141
142
26f609ff 143/* FIXME. */
c3e23647 144
d019d655 145static inline void
342b8b6e
AD
146output_table_data (struct obstack *oout,
147 short *table_data,
148 short first,
1fa14068
AD
149 int begin,
150 int end)
d019d655 151{
26f609ff
RA
152 int i;
153 int j = 1;
342b8b6e 154
26f609ff
RA
155 obstack_fgrow1 (oout, "%6d", first);
156 for (i = begin; i < end; ++i)
d019d655 157 {
896fe5c1 158 obstack_1grow (oout, ',');
d019d655
AD
159 if (j >= 10)
160 {
ff4423cc 161 obstack_sgrow (oout, "\n ");
d019d655
AD
162 j = 1;
163 }
164 else
26f609ff 165 ++j;
8f451ef7 166 obstack_fgrow1 (oout, "%6d", table_data[i]);
c3e23647 167 }
26f609ff 168 obstack_1grow (oout, 0);
c3e23647
RS
169}
170
171
4a120d45 172static void
d2729d44 173output_token_translations (void)
c3e23647 174{
f87685c3 175 output_table_data (&format_obstack, token_translations,
26f609ff 176 0, 1, max_user_token_number + 1);
f87685c3 177 muscle_insert ("translate", obstack_finish (&format_obstack));
342b8b6e 178 XFREE (token_translations);
c3e23647
RS
179}
180
181
4a120d45 182static void
d2729d44 183output_gram (void)
c3e23647 184{
b2ed6e58
AD
185 {
186 int i;
187 short *values = XCALLOC (short, nrules + 1);
188 for (i = 0; i < nrules + 1; ++i)
189 values[i] = rule_table[i].rhs;
f87685c3 190 output_table_data (&format_obstack, values,
b2ed6e58
AD
191 0, 1, nrules + 1);
192 XFREE (values);
193 }
194
f87685c3 195 muscle_insert ("prhs", obstack_finish (&format_obstack));
342b8b6e 196
1e9798d5
AD
197 {
198 size_t yyrhs_size = 1;
199 short *yyrhs, *sp;
200 int i;
c3e23647 201
1e9798d5
AD
202 for (sp = ritem + 1; *sp; sp++)
203 ++yyrhs_size;
204 yyrhs = XMALLOC (short, yyrhs_size);
c3e23647 205
1e9798d5
AD
206 for (sp = ritem + 1, i = 1; *sp; ++sp, ++i)
207 yyrhs[i] = *sp > 0 ? *sp : 0;
c3e23647 208
f87685c3 209 output_table_data (&format_obstack, yyrhs,
26f609ff 210 ritem[0], 1, yyrhs_size);
f87685c3 211 muscle_insert ("rhs", obstack_finish (&format_obstack));
26f609ff 212
1e9798d5
AD
213 XFREE (yyrhs);
214 }
796d61fb 215
4ec8e00f
MA
216#if 0
217 if (!semantic_parser)
218 obstack_sgrow (&table_obstack, "\n#endif\n");
219#endif
c3e23647
RS
220}
221
222
4a120d45 223static void
d2729d44 224output_stos (void)
c3e23647 225{
9703cc49
AD
226 int i;
227 short *values = (short *) alloca (sizeof (short) * nstates);
228 for (i = 0; i < nstates; ++i)
f693ad14 229 values[i] = state_table[i]->accessing_symbol;
f87685c3 230 output_table_data (&format_obstack, values,
26f609ff 231 0, 1, nstates);
f87685c3 232 muscle_insert ("stos", obstack_finish (&format_obstack));
c3e23647
RS
233}
234
235
4a120d45 236static void
d2729d44 237output_rule_data (void)
c3e23647 238{
6c89f1c1
AD
239 int i;
240 int j;
1e9798d5 241 short *short_tab = NULL;
c3e23647 242
e41dc700
AD
243 {
244 short *values = XCALLOC (short, nrules + 1);
245 for (i = 0; i < nrules + 1; ++i)
246 values[i] = rule_table[i].line;
f87685c3 247 output_table_data (&format_obstack, values,
e41dc700 248 0, 1, nrules + 1);
f87685c3 249 muscle_insert ("rline", obstack_finish (&format_obstack));
e41dc700
AD
250 XFREE (values);
251 }
252
c3e23647 253
1e9798d5
AD
254 j = 0;
255 for (i = 0; i < nsyms; i++)
c3e23647 256 {
92790e5b
AD
257 /* Be sure not to use twice the same quotearg slot. */
258 const char *cp =
259 quotearg_n_style (1, c_quoting_style,
260 quotearg_style (escape_quoting_style, tags[i]));
1e9798d5
AD
261 /* Width of the next token, including the two quotes, the coma
262 and the space. */
92790e5b 263 int strsize = strlen (cp) + 2;
1e9798d5
AD
264
265 if (j + strsize > 75)
c3e23647 266 {
f87685c3 267 obstack_sgrow (&format_obstack, "\n ");
1e9798d5 268 j = 2;
c3e23647
RS
269 }
270
f87685c3
AD
271 obstack_sgrow (&format_obstack, cp);
272 obstack_sgrow (&format_obstack, ", ");
1e9798d5 273 j += strsize;
c3e23647 274 }
9ee3c97b 275 /* add a NULL entry to list of tokens */
f87685c3 276 obstack_sgrow (&format_obstack, "NULL");
c3e23647 277
26f609ff 278 /* Finish table and store. */
f87685c3
AD
279 obstack_1grow (&format_obstack, 0);
280 muscle_insert ("tname", obstack_finish (&format_obstack));
e372befa 281
9ee3c97b 282 /* Output YYTOKNUM. */
f87685c3 283 output_table_data (&format_obstack, user_toknums,
26f609ff 284 0, 1, ntokens + 1);
f87685c3 285 muscle_insert ("toknum", obstack_finish (&format_obstack));
e372befa 286
9ee3c97b 287 /* Output YYR1. */
b2ed6e58
AD
288 {
289 short *values = XCALLOC (short, nrules + 1);
290 for (i = 0; i < nrules + 1; ++i)
291 values[i] = rule_table[i].lhs;
f87685c3 292 output_table_data (&format_obstack, values,
b2ed6e58 293 0, 1, nrules + 1);
f87685c3 294 muscle_insert ("r1", obstack_finish (&format_obstack));
b2ed6e58
AD
295 XFREE (values);
296 }
d019d655 297
9ee3c97b 298 /* Output YYR2. */
1e9798d5 299 short_tab = XMALLOC (short, nrules + 1);
c3e23647 300 for (i = 1; i < nrules; i++)
b2ed6e58
AD
301 short_tab[i] = rule_table[i + 1].rhs - rule_table[i].rhs - 1;
302 short_tab[nrules] = nitems - rule_table[nrules].rhs - 1;
f87685c3 303 output_table_data (&format_obstack, short_tab,
26f609ff 304 0, 1, nrules + 1);
f87685c3 305 muscle_insert ("r2", obstack_finish (&format_obstack));
1e9798d5 306 XFREE (short_tab);
c3e23647
RS
307}
308
6c89f1c1
AD
309/*------------------------------------------------------------------.
310| Decide what to do for each type of token if seen as the lookahead |
311| token in specified state. The value returned is used as the |
312| default action (yydefact) for the state. In addition, actrow is |
313| filled with what to do for each kind of token, index by symbol |
314| number, with zero meaning do the default action. The value |
315| MINSHORT, a very negative number, means this situation is an |
316| error. The parser recognizes this value specially. |
317| |
318| This is where conflicts are resolved. The loop over lookahead |
319| rules considered lower-numbered rules last, and the last rule |
320| considered that likes a token gets to handle it. |
321`------------------------------------------------------------------*/
c3e23647 322
4a120d45 323static int
f9507c28 324action_row (state_t *state)
c3e23647 325{
6c89f1c1 326 int i;
837491d8 327 int default_rule = 0;
f9507c28 328 reductions *redp = state->reductions;
f9507c28
AD
329 shifts *shiftp = state->shifts;
330 errs *errp = state->errs;
837491d8
AD
331 /* set nonzero to inhibit having any default reduction */
332 int nodefault = 0;
c3e23647
RS
333
334 for (i = 0; i < ntokens; i++)
335 actrow[i] = 0;
336
80dac38c 337 if (redp->nreds >= 1)
c3e23647 338 {
837491d8
AD
339 int j;
340 /* loop over all the rules available here which require
341 lookahead */
f9507c28 342 for (i = state->nlookaheads - 1; i >= 0; --i)
837491d8
AD
343 /* and find each token which the rule finds acceptable
344 to come next */
345 for (j = 0; j < ntokens; j++)
346 /* and record this rule as the rule to use if that
347 token follows. */
f9507c28
AD
348 if (BITISSET (LA (state->lookaheadsp + i), j))
349 actrow[j] = -LAruleno[state->lookaheadsp + i];
c3e23647
RS
350 }
351
36281465
AD
352 /* Now see which tokens are allowed for shifts in this state. For
353 them, record the shift as the thing to do. So shift is preferred
354 to reduce. */
d954473d 355 for (i = 0; i < shiftp->nshifts; i++)
c3e23647 356 {
837491d8
AD
357 int symbol;
358 int shift_state = shiftp->shifts[i];
d954473d
AD
359 if (!shift_state)
360 continue;
c3e23647 361
f693ad14 362 symbol = state_table[shift_state]->accessing_symbol;
c3e23647 363
d954473d
AD
364 if (ISVAR (symbol))
365 break;
c3e23647 366
d954473d 367 actrow[symbol] = shift_state;
c3e23647 368
d954473d
AD
369 /* Do not use any default reduction if there is a shift for
370 error */
371 if (symbol == error_token_number)
372 nodefault = 1;
c3e23647
RS
373 }
374
36281465
AD
375 /* See which tokens are an explicit error in this state (due to
376 %nonassoc). For them, record MINSHORT as the action. */
2cec70b9
AD
377 for (i = 0; i < errp->nerrs; i++)
378 {
379 int symbol = errp->errs[i];
380 actrow[symbol] = MINSHORT;
381 }
c3e23647 382
36281465
AD
383 /* Now find the most common reduction and make it the default action
384 for this state. */
c3e23647 385
80dac38c 386 if (redp->nreds >= 1 && !nodefault)
c3e23647 387 {
f9507c28 388 if (state->consistent)
c3e23647
RS
389 default_rule = redp->rules[0];
390 else
391 {
7a5350ba 392 int max = 0;
f9507c28 393 for (i = 0; i < state->nlookaheads; i++)
c3e23647 394 {
7a5350ba 395 int count = 0;
f9507c28 396 int rule = -LAruleno[state->lookaheadsp + i];
837491d8 397 int j;
9ee3c97b 398
c3e23647 399 for (j = 0; j < ntokens; j++)
837491d8
AD
400 if (actrow[j] == rule)
401 count++;
9ee3c97b 402
c3e23647
RS
403 if (count > max)
404 {
405 max = count;
406 default_rule = rule;
407 }
408 }
9ee3c97b 409
c3e23647
RS
410 /* actions which match the default are replaced with zero,
411 which means "use the default" */
9ee3c97b 412
c3e23647
RS
413 if (max > 0)
414 {
837491d8 415 int j;
c3e23647 416 for (j = 0; j < ntokens; j++)
837491d8
AD
417 if (actrow[j] == default_rule)
418 actrow[j] = 0;
9ee3c97b 419
ceed8467 420 default_rule = -default_rule;
c3e23647
RS
421 }
422 }
423 }
424
425 /* If have no default rule, the default is an error.
426 So replace any action which says "error" with "use default". */
427
428 if (default_rule == 0)
837491d8
AD
429 for (i = 0; i < ntokens; i++)
430 if (actrow[i] == MINSHORT)
431 actrow[i] = 0;
c3e23647 432
36281465 433 return default_rule;
c3e23647
RS
434}
435
436
4a120d45 437static void
d2729d44 438save_row (int state)
c3e23647 439{
6c89f1c1
AD
440 int i;
441 int count;
442 short *sp;
443 short *sp1;
444 short *sp2;
c3e23647
RS
445
446 count = 0;
447 for (i = 0; i < ntokens; i++)
796d61fb
AD
448 if (actrow[i] != 0)
449 count++;
c3e23647
RS
450
451 if (count == 0)
452 return;
453
d7913476
AD
454 froms[state] = sp1 = sp = XCALLOC (short, count);
455 tos[state] = sp2 = XCALLOC (short, count);
c3e23647
RS
456
457 for (i = 0; i < ntokens; i++)
796d61fb
AD
458 if (actrow[i] != 0)
459 {
460 *sp1++ = i;
461 *sp2++ = actrow[i];
462 }
c3e23647
RS
463
464 tally[state] = count;
465 width[state] = sp1[-1] - sp[0] + 1;
466}
467
468
6c89f1c1
AD
469/*------------------------------------------------------------------.
470| Figure out the actions for the specified state, indexed by |
471| lookahead token type. |
472| |
f2acea59
AD
473| The YYDEFACT table is output now. The detailed info is saved for |
474| putting into YYTABLE later. |
6c89f1c1 475`------------------------------------------------------------------*/
c3e23647 476
4a120d45 477static void
6c89f1c1 478token_actions (void)
c3e23647 479{
6c89f1c1 480 int i;
d7913476 481 short *yydefact = XCALLOC (short, nstates);
c3e23647 482
d7913476 483 actrow = XCALLOC (short, ntokens);
f2acea59 484 for (i = 0; i < nstates; ++i)
c3e23647 485 {
f9507c28 486 yydefact[i] = action_row (state_table[i]);
6c89f1c1 487 save_row (i);
c3e23647 488 }
bbb5bcc6 489
f87685c3 490 output_table_data (&format_obstack, yydefact,
26f609ff 491 yydefact[0], 1, nstates);
f87685c3 492 muscle_insert ("defact", obstack_finish (&format_obstack));
342b8b6e 493
26f609ff 494 XFREE (actrow);
d7913476 495 XFREE (yydefact);
c3e23647
RS
496}
497
498
3f96f4dc
AD
499/*-----------------------------.
500| Output the actions to OOUT. |
501`-----------------------------*/
502
503static void
f0440388 504actions_output (FILE *out, size_t *line)
3f96f4dc
AD
505{
506 int rule;
507 for (rule = 1; rule < nrules + 1; ++rule)
508 if (rule_table[rule].action)
509 {
ea52d706 510 fprintf (out, " case %d:\n", rule);
3f96f4dc
AD
511
512 if (!no_lines_flag)
ea52d706
AD
513 fprintf (out, muscle_find ("linef"),
514 rule_table[rule].action_line,
515 quotearg_style (c_quoting_style,
516 muscle_find ("filename")));
3f96f4dc
AD
517 /* As a Bison extension, add the ending semicolon. Since some
518 Yacc don't do that, help people using bison as a Yacc
519 finding their missing semicolons. */
ea52d706
AD
520 fprintf (out, "{ %s%s }\n break;\n\n",
521 rule_table[rule].action,
522 yacc_flag ? ";" : "");
f0440388 523
fbc8ecb7
MA
524 /* We always output 4 '\n' per action. */
525 *line += 4;
526 /* Plus one if !no_lines_flag. */
527 if (!no_lines_flag)
528 ++*line;
f0440388
MA
529 /* Get the number of lines written by the user. */
530 *line += get_lines_number (rule_table[rule].action);
3f96f4dc
AD
531 }
532}
533
534
f499b062
AD
535/*----------------------------.
536| Output the guards to OOUT. |
537`----------------------------*/
538
539static void
540guards_output (FILE *out, size_t *line)
541{
542 int rule;
543 for (rule = 1; rule < nrules + 1; ++rule)
544 if (rule_table[rule].action)
545 {
546 fprintf (out, " case %d:\n", rule);
547
548 if (!no_lines_flag)
549 fprintf (out, muscle_find ("linef"),
550 rule_table[rule].guard_line,
551 quotearg_style (c_quoting_style,
552 muscle_find ("filename")));
553 fprintf (out, "{ %s; }\n break;\n\n",
554 rule_table[rule].guard);
555
556 /* We always output 4 '\n' per action. */
557 *line += 4;
558 /* Plus one if !no_lines_flag. */
559 if (!no_lines_flag)
560 ++*line;
561 /* Get the number of lines written by the user. */
562 *line += get_lines_number (rule_table[rule].guard);
563 }
564}
565
566
4a120d45 567static void
d2729d44 568save_column (int symbol, int default_state)
c3e23647 569{
6c89f1c1 570 int i;
6c89f1c1
AD
571 short *sp;
572 short *sp1;
573 short *sp2;
574 int count;
837491d8 575 int symno = symbol - ntokens + nstates;
c3e23647 576
43591cec
AD
577 short begin = goto_map[symbol];
578 short end = goto_map[symbol + 1];
c3e23647
RS
579
580 count = 0;
43591cec 581 for (i = begin; i < end; i++)
796d61fb
AD
582 if (to_state[i] != default_state)
583 count++;
c3e23647
RS
584
585 if (count == 0)
586 return;
587
d7913476
AD
588 froms[symno] = sp1 = sp = XCALLOC (short, count);
589 tos[symno] = sp2 = XCALLOC (short, count);
c3e23647 590
43591cec 591 for (i = begin; i < end; i++)
796d61fb
AD
592 if (to_state[i] != default_state)
593 {
594 *sp1++ = from_state[i];
595 *sp2++ = to_state[i];
596 }
c3e23647
RS
597
598 tally[symno] = count;
599 width[symno] = sp1[-1] - sp[0] + 1;
600}
601
6c89f1c1
AD
602static int
603default_goto (int symbol)
604{
605 int i;
837491d8
AD
606 int m = goto_map[symbol];
607 int n = goto_map[symbol + 1];
608 int default_state = -1;
609 int max = 0;
6c89f1c1
AD
610
611 if (m == n)
612 return -1;
613
614 for (i = 0; i < nstates; i++)
615 state_count[i] = 0;
616
617 for (i = m; i < n; i++)
618 state_count[to_state[i]]++;
619
6c89f1c1 620 for (i = 0; i < nstates; i++)
796d61fb
AD
621 if (state_count[i] > max)
622 {
623 max = state_count[i];
624 default_state = i;
625 }
6c89f1c1
AD
626
627 return default_state;
628}
629
630
631/*-------------------------------------------------------------------.
632| Figure out what to do after reducing with each rule, depending on |
633| the saved state from before the beginning of parsing the data that |
634| matched this rule. |
635| |
636| The YYDEFGOTO table is output now. The detailed info is saved for |
637| putting into YYTABLE later. |
638`-------------------------------------------------------------------*/
639
640static void
641goto_actions (void)
642{
43591cec 643 int i;
bbb5bcc6 644 short *yydefgoto = XMALLOC (short, nsyms - ntokens);
bbb5bcc6 645
26f609ff 646 state_count = XCALLOC (short, nstates);
43591cec 647 for (i = ntokens; i < nsyms; ++i)
6c89f1c1 648 {
43591cec
AD
649 int default_state = default_goto (i);
650 save_column (i, default_state);
651 yydefgoto[i - ntokens] = default_state;
6c89f1c1
AD
652 }
653
f87685c3 654 output_table_data (&format_obstack, yydefgoto,
26f609ff 655 yydefgoto[0], 1, nsyms - ntokens);
f87685c3 656 muscle_insert ("defgoto", obstack_finish (&format_obstack));
43591cec 657
d7913476 658 XFREE (state_count);
43591cec 659 XFREE (yydefgoto);
6c89f1c1 660}
c3e23647
RS
661
662
9ee3c97b
AD
663/* The next few functions decide how to pack the actions and gotos
664 information into yytable. */
c3e23647 665
4a120d45 666static void
d2729d44 667sort_actions (void)
c3e23647 668{
6c89f1c1 669 int i;
c3e23647 670
d7913476 671 order = XCALLOC (short, nvectors);
c3e23647
RS
672 nentries = 0;
673
674 for (i = 0; i < nvectors; i++)
796d61fb
AD
675 if (tally[i] > 0)
676 {
837491d8
AD
677 int k;
678 int t = tally[i];
679 int w = width[i];
680 int j = nentries - 1;
c3e23647 681
796d61fb
AD
682 while (j >= 0 && (width[order[j]] < w))
683 j--;
c3e23647 684
796d61fb
AD
685 while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
686 j--;
c3e23647 687
796d61fb
AD
688 for (k = nentries - 1; k > j; k--)
689 order[k + 1] = order[k];
c3e23647 690
796d61fb
AD
691 order[j + 1] = i;
692 nentries++;
693 }
c3e23647
RS
694}
695
696
4a120d45 697static int
d2729d44 698matching_state (int vector)
c3e23647 699{
837491d8 700 int i = order[vector];
6c89f1c1
AD
701 int t;
702 int w;
6c89f1c1 703 int prev;
c3e23647 704
c3e23647 705 if (i >= nstates)
36281465 706 return -1;
c3e23647
RS
707
708 t = tally[i];
709 w = width[i];
710
711 for (prev = vector - 1; prev >= 0; prev--)
712 {
837491d8
AD
713 int j = order[prev];
714 int k;
715 int match = 1;
716
c3e23647 717 if (width[j] != w || tally[j] != t)
36281465 718 return -1;
c3e23647 719
c3e23647 720 for (k = 0; match && k < t; k++)
796d61fb
AD
721 if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
722 match = 0;
c3e23647
RS
723
724 if (match)
36281465 725 return j;
c3e23647
RS
726 }
727
36281465 728 return -1;
c3e23647
RS
729}
730
731
4a120d45 732static int
d2729d44 733pack_vector (int vector)
c3e23647 734{
837491d8 735 int i = order[vector];
6c89f1c1 736 int j;
837491d8 737 int t = tally[i];
6c89f1c1 738 int loc = 0;
837491d8
AD
739 short *from = froms[i];
740 short *to = tos[i];
c3e23647 741
340ef489 742 assert (t);
c3e23647 743
c3e23647
RS
744 for (j = lowzero - from[0]; j < MAXTABLE; j++)
745 {
837491d8
AD
746 int k;
747 int ok = 1;
c3e23647
RS
748
749 for (k = 0; ok && k < t; k++)
750 {
751 loc = j + from[k];
752 if (loc > MAXTABLE)
a0f6b076 753 fatal (_("maximum table size (%d) exceeded"), MAXTABLE);
c3e23647
RS
754
755 if (table[loc] != 0)
756 ok = 0;
757 }
758
759 for (k = 0; ok && k < vector; k++)
796d61fb
AD
760 if (pos[k] == j)
761 ok = 0;
c3e23647
RS
762
763 if (ok)
764 {
765 for (k = 0; k < t; k++)
766 {
767 loc = j + from[k];
768 table[loc] = to[k];
769 check[loc] = from[k];
770 }
771
772 while (table[lowzero] != 0)
773 lowzero++;
774
775 if (loc > high)
776 high = loc;
777
36281465 778 return j;
c3e23647
RS
779 }
780 }
275fc3ad
AD
781#define pack_vector_succeeded 0
782 assert (pack_vector_succeeded);
3843c413 783 return 0;
c3e23647
RS
784}
785
786
6c89f1c1
AD
787static void
788pack_table (void)
789{
790 int i;
791 int place;
792 int state;
793
d7913476
AD
794 base = XCALLOC (short, nvectors);
795 pos = XCALLOC (short, nentries);
796 table = XCALLOC (short, MAXTABLE);
797 check = XCALLOC (short, MAXTABLE);
6c89f1c1
AD
798
799 lowzero = 0;
800 high = 0;
801
802 for (i = 0; i < nvectors; i++)
803 base[i] = MINSHORT;
804
805 for (i = 0; i < MAXTABLE; i++)
806 check[i] = -1;
807
808 for (i = 0; i < nentries; i++)
809 {
810 state = matching_state (i);
811
812 if (state < 0)
813 place = pack_vector (i);
814 else
815 place = base[state];
816
817 pos[i] = place;
818 base[order[i]] = place;
819 }
820
821 for (i = 0; i < nvectors; i++)
822 {
796d61fb
AD
823 XFREE (froms[i]);
824 XFREE (tos[i]);
6c89f1c1
AD
825 }
826
d7913476
AD
827 XFREE (froms);
828 XFREE (tos);
829 XFREE (pos);
6c89f1c1 830}
c3e23647
RS
831
832/* the following functions output yytable, yycheck
833 and the vectors whose elements index the portion starts */
834
4a120d45 835static void
d2729d44 836output_base (void)
c3e23647 837{
26f609ff 838 /* Output pact. */
f87685c3 839 output_table_data (&format_obstack, base,
26f609ff 840 base[0], 1, nstates);
f87685c3 841 muscle_insert ("pact", obstack_finish (&format_obstack));
c3e23647 842
26f609ff 843 /* Output pgoto. */
f87685c3 844 output_table_data (&format_obstack, base,
26f609ff 845 base[nstates], nstates + 1, nvectors);
f87685c3 846 muscle_insert ("pgoto", obstack_finish (&format_obstack));
c3e23647 847
d7913476 848 XFREE (base);
c3e23647
RS
849}
850
851
4a120d45 852static void
d2729d44 853output_table (void)
c3e23647 854{
f87685c3 855 output_table_data (&format_obstack, table,
26f609ff 856 table[0], 1, high + 1);
f87685c3 857 muscle_insert ("table", obstack_finish (&format_obstack));
d7913476 858 XFREE (table);
c3e23647
RS
859}
860
861
4a120d45 862static void
d2729d44 863output_check (void)
c3e23647 864{
f87685c3 865 output_table_data (&format_obstack, check,
26f609ff 866 check[0], 1, high + 1);
f87685c3 867 muscle_insert ("check", obstack_finish (&format_obstack));
d7913476 868 XFREE (check);
c3e23647
RS
869}
870
6c89f1c1
AD
871/* compute and output yydefact, yydefgoto, yypact, yypgoto, yytable
872 and yycheck. */
873
874static void
875output_actions (void)
876{
49701457 877 int i;
6c89f1c1 878 nvectors = nstates + nvars;
c3e23647 879
d7913476
AD
880 froms = XCALLOC (short *, nvectors);
881 tos = XCALLOC (short *, nvectors);
882 tally = XCALLOC (short, nvectors);
883 width = XCALLOC (short, nvectors);
6c89f1c1
AD
884
885 token_actions ();
d7913476
AD
886 XFREE (LA);
887 XFREE (LAruleno);
6c89f1c1
AD
888
889 goto_actions ();
d7913476
AD
890 XFREE (goto_map + ntokens);
891 XFREE (from_state);
892 XFREE (to_state);
6c89f1c1
AD
893
894 sort_actions ();
895 pack_table ();
4e5caae2 896
6c89f1c1
AD
897 output_base ();
898 output_table ();
4e5caae2 899
6c89f1c1 900 output_check ();
49701457
AD
901
902 for (i = 0; i < nstates; ++i)
903 {
2cec70b9 904 free (state_table[i]->shifts);
49701457 905 XFREE (state_table[i]->reductions);
2cec70b9 906 free (state_table[i]->errs);
49701457
AD
907 free (state_table[i]);
908 }
9703cc49 909 XFREE (state_table);
6c89f1c1 910}
c3e23647 911
652def80
MA
912\f
913/*------------------------------------------------------------.
914| Copy the parser code from SKEL_FILENAME into OOUT obstack. |
915| and do the muscle substitution. |
916`------------------------------------------------------------*/
c3e23647 917
4a120d45 918static void
ea52d706 919output_parser (const char *skel_filename, FILE *out)
c3e23647 920{
6c89f1c1 921 int c;
ff61dabd 922 FILE *fskel;
897668ee
MA
923 size_t output_line;
924 size_t skeleton_line;
c3e23647 925
652def80 926 fskel = xfopen (skel_filename, "r");
ef7ddedd 927
e8cb70b9 928 /* New output code. */
897668ee
MA
929 output_line = 1;
930 skeleton_line = 1;
26f609ff
RA
931 c = getc (fskel);
932 while (c != EOF)
c3e23647 933 {
26f609ff 934 if (c != '%')
573c1d9f 935 {
26f609ff 936 if (c == '\n')
897668ee
MA
937 {
938 ++output_line;
939 ++skeleton_line;
940 }
ea52d706 941 putc (c, out);
26f609ff 942 c = getc (fskel);
bbb5bcc6 943 }
26f609ff 944 else if ((c = getc (fskel)) == '%')
bbb5bcc6 945 {
11d82f03
MA
946 /* Read the muscle. */
947 const char *muscle_key = 0;
948 const char *muscle_value = 0;
652def80 949
5b5d1929 950 while (isalnum (c = getc (fskel)) || c == '-')
11d82f03
MA
951 obstack_1grow (&muscle_obstack, c);
952 obstack_1grow (&muscle_obstack, 0);
26f609ff 953
e8cb70b9 954 /* Output the right value, or see if it's something special. */
11d82f03
MA
955 muscle_key = obstack_finish (&muscle_obstack);
956 muscle_value = muscle_find (muscle_key);
3f96f4dc 957 if (!strcmp (muscle_key, "actions"))
897668ee 958 actions_output (out, &output_line);
f499b062
AD
959 else if (!strcmp (muscle_key, "guards"))
960 guards_output (out, &output_line);
11d82f03 961 else if (!strcmp (muscle_key, "line"))
897668ee
MA
962 fprintf (out, "%d", output_line);
963 else if (!strcmp (muscle_key, "skeleton-line"))
964 fprintf (out, "%d", skeleton_line);
3f96f4dc 965 else if (muscle_value)
f0440388
MA
966 {
967 fputs (muscle_value, out);
897668ee 968 output_line += get_lines_number (muscle_value);
1fa14068 969 }
bbb5bcc6 970 else
26f609ff 971 {
ea52d706
AD
972 fputs ("%%", out);
973 fputs (muscle_key, out);
26f609ff 974 }
573c1d9f 975 }
b0cfa28a 976 else
ea52d706 977 putc ('%', out);
bbb5bcc6 978 }
26f609ff 979
e8cb70b9 980 /* End. */
ff61dabd 981 xfclose (fskel);
c3e23647
RS
982}
983
652def80
MA
984/*----------------------------------------.
985| Prepare the master parser to be output |
986`----------------------------------------*/
987
988static void
989output_master_parser (void)
990{
ea52d706 991 FILE *parser = xfopen (parser_file_name, "w");
652def80
MA
992 if (!skeleton)
993 {
994 if (semantic_parser)
995 skeleton = skeleton_find ("BISON_HAIRY", BISON_HAIRY);
996 else
997 skeleton = skeleton_find ("BISON_SIMPLE", BISON_SIMPLE);
998 }
3843c413 999 muscle_insert ("skeleton", skeleton);
f0440388 1000 muscle_insert ("parser-file-name", parser_file_name);
ea52d706
AD
1001
1002 output_parser (skeleton, parser);
1003 xfclose (parser);
652def80
MA
1004}
1005
1006
26f609ff
RA
1007/* FIXME. */
1008
11d82f03
MA
1009#define MUSCLE_INSERT_INT(Key, Value) \
1010{ \
1011 obstack_fgrow1 (&muscle_obstack, "%d", Value); \
1012 obstack_1grow (&muscle_obstack, 0); \
1013 muscle_insert (Key, obstack_finish (&muscle_obstack)); \
26f609ff
RA
1014}
1015
11d82f03
MA
1016#define MUSCLE_INSERT_STRING(Key, Value) \
1017{ \
1018 obstack_sgrow (&muscle_obstack, Value); \
1019 obstack_1grow (&muscle_obstack, 0); \
1020 muscle_insert (Key, obstack_finish (&muscle_obstack)); \
26f609ff
RA
1021}
1022
11d82f03 1023#define MUSCLE_INSERT_PREFIX(Key, Value) \
26f609ff 1024{ \
11d82f03
MA
1025 obstack_fgrow2 (&muscle_obstack, "%s%s", spec_name_prefix, Value); \
1026 obstack_1grow (&muscle_obstack, 0); \
1027 muscle_insert (Key, obstack_finish (&muscle_obstack)); \
26f609ff
RA
1028}
1029
1030static void
1031prepare (void)
1032{
11d82f03
MA
1033 MUSCLE_INSERT_INT ("last", high);
1034 MUSCLE_INSERT_INT ("flag", MINSHORT);
1035 MUSCLE_INSERT_INT ("pure", pure_parser);
1036 MUSCLE_INSERT_INT ("nsym", nsyms);
1037 MUSCLE_INSERT_INT ("debug", debug_flag);
1038 MUSCLE_INSERT_INT ("final", final_state);
1039 MUSCLE_INSERT_INT ("maxtok", max_user_token_number);
c7925b99 1040 MUSCLE_INSERT_INT ("error-verbose", error_verbose);
78af9bbc 1041 MUSCLE_INSERT_STRING ("prefix", spec_name_prefix);
11d82f03
MA
1042
1043 MUSCLE_INSERT_INT ("nnts", nvars);
1044 MUSCLE_INSERT_INT ("nrules", nrules);
1045 MUSCLE_INSERT_INT ("nstates", nstates);
1046 MUSCLE_INSERT_INT ("ntokens", ntokens);
1047
5b5d1929 1048 MUSCLE_INSERT_INT ("locations-flag", locations_flag);
26f609ff 1049}
c3e23647 1050
93ede233
AD
1051
1052/*-------------------------.
1053| Output the header file. |
1054`-------------------------*/
1055
1056static void
1057header_output (void)
1058{
1059 FILE *out = xfopen (spec_defines_file, "w");
1060 char *macro_name = compute_header_macro ();
1061
1062 fprintf (out, "#ifndef %s\n", macro_name);
1063 fprintf (out, "# define %s\n\n", macro_name);
1064
1065 fputs (muscle_find ("tokendef"), out);
1066 fprintf (out, "\
1067#ifndef YYSTYPE\n\
1068typedef %s
1069yystype;\n\
1070# define YYSTYPE yystype\n\
1071#endif\n",
1072 muscle_find ("stype"));
1073
1074 if (!pure_parser)
1075 fprintf (out, "\nextern YYSTYPE %slval;\n",
1076 spec_name_prefix);
1077 if (semantic_parser)
1078 {
1079 int i;
1080
1081 for (i = ntokens; i < nsyms; i++)
1082 /* don't make these for dummy nonterminals made by gensym. */
1083 if (*tags[i] != '@')
7742ddeb 1084 fprintf (out, "# define NT%s\t%d\n", tags[i], i);
93ede233
AD
1085 }
1086
1087 fprintf (out, "\n#endif /* not %s */\n", macro_name);
1088 free (macro_name);
1089 xfclose (out);
1090}
1091
1092
6c89f1c1
AD
1093/*----------------------------------------------------------.
1094| Output the parsing tables and the parser code to ftable. |
1095`----------------------------------------------------------*/
c3e23647 1096
6c89f1c1
AD
1097void
1098output (void)
1099{
f87685c3 1100 obstack_init (&format_obstack);
dd60faec 1101
6c89f1c1 1102 output_token_translations ();
6c89f1c1 1103 output_gram ();
26f609ff 1104
d7913476 1105 XFREE (ritem);
6c89f1c1
AD
1106 if (semantic_parser)
1107 output_stos ();
1108 output_rule_data ();
0846f581 1109 XFREE (user_toknums);
6c89f1c1 1110 output_actions ();
342b8b6e 1111
26f609ff 1112 prepare ();
d1a2daf7 1113 /* Copy definitions in directive. */
5449dd0f 1114 obstack_1grow (&attrs_obstack, 0);
11d82f03 1115 muscle_insert ("prologue", obstack_finish (&attrs_obstack));
652def80 1116
93ede233 1117 /* Output the parser. */
652def80 1118 output_master_parser ();
93ede233
AD
1119 /* Output the header if needed. */
1120 if (defines_flag)
1121 header_output ();
26f609ff 1122
3f96f4dc 1123 free (rule_table + 1);
f499b062
AD
1124 obstack_free (&muscle_obstack, NULL);
1125 obstack_free (&format_obstack, NULL);
1126 obstack_free (&action_obstack, NULL);
f499b062 1127 obstack_free (&attrs_obstack, NULL);
c3e23647 1128}