src/output.c

   1 /* Output the generated parsing program for bison,
   2    Copyright (C) 1984, 1986, 1989, 1992, 2000 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 "getargs.h"
  95 #include "alloc.h"
  96 #include "files.h"
  97 #include "gram.h"
  98 #include "state.h"
  99 #include "complain.h"
 100 #include "output.h"
 101 #include "lalr.h"
 102
 103 extern void berror PARAMS((const char *));
 104
 105 extern char **tags;
 106 extern short *user_toknums;
 107 extern int final_state;
 108 extern errs **err_table;
 109
 110 extern void reader_output_yylsp PARAMS ((FILE *));
 111
 112 static int nvectors;
 113 static int nentries;
 114 static short **froms;
 115 static short **tos;
 116 static short *tally;
 117 static short *width;
 118 static short *actrow;
 119 static short *state_count;
 120 static short *order;
 121 static short *base;
 122 static short *pos;
 123 static short *table;
 124 static short *check;
 125 static int lowzero;
 126 static int high;
 127
 128
 129
 130 static inline void
 131 output_short_table (FILE *out,
 132                     const char *table_name,
 133                     short *short_table,
 134                     short first_value,
 135                     short begin, short end)
 136 {
 137   int i, j;
 138
 139   fprintf (out, "static const short %s[] = {%6d", table_name, first_value);
 140
 141   j = 10;
 142   for (i = begin; i < end; i++)
 143     {
 144       putc (',', out);
 145
 146       if (j >= 10)
 147         {
 148           putc ('\n', out);
 149           j = 1;
 150         }
 151       else
 152         {
 153           j++;
 154         }
 155
 156       fprintf (out, "%6d", short_table[i]);
 157     }
 158
 159   fprintf (out, "\n};\n");
 160 }
 161
 162
 163 /*--------------------------------------------------------------.
 164 | output_headers -- Output constant strings to the beginning of |
 165 | certain files.                                                |
 166 `--------------------------------------------------------------*/
 167
 168 #define GUARDSTR        \
 169 "\n\
 170 #include \"%s\"\n\
 171 extern int yyerror;\n\
 172 extern int yycost;\n\
 173 extern char * yymsg;\n\
 174 extern YYSTYPE yyval;\n\
 175 \n\
 176 yyguard(n, yyvsp, yylsp)\n\
 177 register int n;\n\
 178 register YYSTYPE *yyvsp;\n\
 179 register YYLTYPE *yylsp;\n\
 180 {\n\
 181   yyerror = 0;\n\
 182   yycost = 0;\n\
 183   yymsg = 0;\n\
 184   switch (n)\n\
 185     {"
 186
 187 #define ACTSTR          \
 188 "\n\
 189 #include \"%s\"\n\
 190 extern YYSTYPE yyval;\n\
 191 extern int yychar;\n\
 192 \n\
 193 yyaction(n, yyvsp, yylsp)\n\
 194 register int n;\n\
 195 register YYSTYPE *yyvsp;\n\
 196 register YYLTYPE *yylsp;\n\
 197 {\n\
 198   switch (n)\n\
 199     {"
 200
 201 #define ACTSTR_SIMPLE   "\n  switch (yyn) {\n"
 202
 203 void
 204 output_headers (void)
 205 {
 206   if (semantic_parser)
 207     fprintf (fguard, GUARDSTR, attrsfile);
 208
 209   if (noparserflag)
 210     return;
 211
 212   fprintf (faction, (semantic_parser ? ACTSTR : ACTSTR_SIMPLE), attrsfile);
 213 /*  if (semantic_parser)        JF moved this below
 214     fprintf(ftable, "#include \"%s\"\n", attrsfile);
 215   fprintf(ftable, "#include <stdio.h>\n\n");
 216 */
 217
 218   /* Rename certain symbols if -p was specified.  */
 219   if (spec_name_prefix)
 220     {
 221       fprintf (ftable, "#define yyparse %sparse\n", spec_name_prefix);
 222       fprintf (ftable, "#define yylex %slex\n", spec_name_prefix);
 223       fprintf (ftable, "#define yyerror %serror\n", spec_name_prefix);
 224       fprintf (ftable, "#define yylval %slval\n", spec_name_prefix);
 225       fprintf (ftable, "#define yychar %schar\n", spec_name_prefix);
 226       fprintf (ftable, "#define yydebug %sdebug\n", spec_name_prefix);
 227       fprintf (ftable, "#define yynerrs %snerrs\n", spec_name_prefix);
 228     }
 229 }
 230
 231
 232 /*-------------------------------------------------------.
 233 | Output constant strings to the ends of certain files.  |
 234 `-------------------------------------------------------*/
 235
 236 void
 237 output_trailers (void)
 238 {
 239   if (semantic_parser)
 240     fprintf (fguard, "\n    }\n}\n");
 241
 242   fprintf (faction, "\n");
 243
 244   if (noparserflag)
 245     return;
 246
 247   if (semantic_parser)
 248     fprintf (faction, "    }\n");
 249   fprintf (faction, "}\n");
 250 }
 251
 252
 253
 254 static void
 255 output_token_translations (void)
 256 {
 257   int i, j;
 258 /*   short *sp; JF unused */
 259
 260   if (translations)
 261     {
 262       fprintf (ftable,
 263                "\n#define YYTRANSLATE(x) ((unsigned)(x) <= %d ? yytranslate[x] : %d)\n",
 264                max_user_token_number, nsyms);
 265
 266       if (ntokens < 127)        /* play it very safe; check maximum element value.  */
 267         fprintf (ftable, "\nstatic const char yytranslate[] = {     0");
 268       else
 269         fprintf (ftable, "\nstatic const short yytranslate[] = {     0");
 270
 271       j = 10;
 272       for (i = 1; i <= max_user_token_number; i++)
 273         {
 274           putc (',', ftable);
 275
 276           if (j >= 10)
 277             {
 278               putc ('\n', ftable);
 279               j = 1;
 280             }
 281           else
 282             {
 283               j++;
 284             }
 285
 286           fprintf (ftable, "%6d", token_translations[i]);
 287         }
 288
 289       fprintf (ftable, "\n};\n");
 290     }
 291   else
 292     {
 293       fprintf (ftable, "\n#define YYTRANSLATE(x) (x)\n");
 294     }
 295 }
 296
 297
 298 static void
 299 output_gram (void)
 300 {
 301   int j;
 302   short *sp;
 303
 304   /* With the ordinary parser,
 305      yyprhs and yyrhs are needed only for yydebug. */
 306   /* With the noparser option, all tables are generated */
 307   if (!semantic_parser && !noparserflag)
 308     fprintf (ftable, "\n#if YYDEBUG != 0\n");
 309
 310   output_short_table (ftable, "yyprhs", rrhs,
 311                       0, 1, nrules + 1);
 312
 313   fprintf (ftable, "\nstatic const short yyrhs[] = {%6d", ritem[0]);
 314
 315   j = 10;
 316   for (sp = ritem + 1; *sp; sp++)
 317     {
 318       putc (',', ftable);
 319
 320       if (j >= 10)
 321         {
 322           putc ('\n', ftable);
 323           j = 1;
 324         }
 325       else
 326         {
 327           j++;
 328         }
 329
 330       if (*sp > 0)
 331         fprintf (ftable, "%6d", *sp);
 332       else
 333         fprintf (ftable, "     0");
 334     }
 335
 336   fprintf (ftable, "\n};\n");
 337
 338   if (!semantic_parser && !noparserflag)
 339     fprintf (ftable, "\n#endif\n");
 340 }
 341
 342
 343 static void
 344 output_stos (void)
 345 {
 346   output_short_table (ftable, "yystos", accessing_symbol,
 347                       0, 1, nstates);
 348 }
 349
 350
 351 static void
 352 output_rule_data (void)
 353 {
 354   int i;
 355   int j;
 356
 357   fputs ("\n\
 358 #if YYDEBUG != 0\n\
 359 /* YYRLINE[yyn]: source line where rule number YYN was defined. */\n",
 360          ftable);
 361
 362   output_short_table (ftable, "yyrline", rline,
 363                       0, 1, nrules + 1);
 364
 365   fputs ("#endif\n\n", ftable);
 366
 367   if (toknumflag || noparserflag)
 368     {
 369       fprintf (ftable, "#define YYNTOKENS %d\n", ntokens);
 370       fprintf (ftable, "#define YYNNTS %d\n", nvars);
 371       fprintf (ftable, "#define YYNRULES %d\n", nrules);
 372       fprintf (ftable, "#define YYNSTATES %d\n", nstates);
 373       fprintf (ftable, "#define YYMAXUTOK %d\n\n", max_user_token_number);
 374     }
 375
 376   if (!toknumflag && !noparserflag)
 377     fprintf (ftable, "\n#if YYDEBUG != 0 || defined (YYERROR_VERBOSE)\n\n");
 378
 379   /* Output the table of symbol names.  */
 380
 381   fprintf (ftable,
 382            "static const char * const yytname[] = {   \"%s\"", tags[0]);
 383
 384   j = strlen (tags[0]) + 44;
 385   for (i = 1; i < nsyms; i++)
 386     /* this used to be i<=nsyms, but that output a final "" symbol
 387        almost by accident */
 388     {
 389       char *p;
 390       putc (',', ftable);
 391       j++;
 392
 393       if (j > 75)
 394         {
 395           putc ('\n', ftable);
 396           j = 0;
 397         }
 398
 399       putc ('\"', ftable);
 400       j++;
 401
 402       for (p = tags[i]; p && *p; p++)
 403         {
 404           if (*p == '"' || *p == '\\')
 405             {
 406               fprintf (ftable, "\\%c", *p);
 407               j += 2;
 408             }
 409           else if (*p == '\n')
 410             {
 411               fprintf (ftable, "\\n");
 412               j += 2;
 413             }
 414           else if (*p == '\t')
 415             {
 416               fprintf (ftable, "\\t");
 417               j += 2;
 418             }
 419           else if (*p == '\b')
 420             {
 421               fprintf (ftable, "\\b");
 422               j += 2;
 423             }
 424           else if (*p < 040 || *p >= 0177)
 425             {
 426               fprintf (ftable, "\\%03o", *p);
 427               j += 4;
 428             }
 429           else
 430             {
 431               putc (*p, ftable);
 432               j++;
 433             }
 434         }
 435
 436       putc ('\"', ftable);
 437       j++;
 438     }
 439   /* add a NULL entry to list of tokens */
 440   fprintf (ftable, ", NULL\n};\n");
 441
 442   if (!toknumflag && !noparserflag)
 443     fprintf (ftable, "#endif\n\n");
 444
 445   /* Output YYTOKNUM. */
 446   if (toknumflag)
 447     {
 448       output_short_table (ftable, "yytoknum", user_toknums,
 449                           0, 1, ntokens + 1);
 450     }
 451
 452   /* Output YYR1. */
 453   fputs ("\
 454 /* YYR1[YYN]: Symbol number of symbol that rule YYN derives. */\n", ftable);
 455
 456   output_short_table (ftable, "yyr1", rlhs,
 457                       0, 1, nrules + 1);
 458   FREE (rlhs + 1);
 459
 460   putc ('\n', ftable);
 461
 462   /* Output YYR2. */
 463   fputs ("\
 464 /* YYR2[YYN]: Number of symbols composing right hand side of rule YYN. */\n\
 465 static const short yyr2[] = {     0", ftable);
 466   j = 10;
 467   for (i = 1; i < nrules; i++)
 468     {
 469       putc (',', ftable);
 470
 471       if (j >= 10)
 472         {
 473           putc ('\n', ftable);
 474           j = 1;
 475         }
 476       else
 477         {
 478           j++;
 479         }
 480
 481       fprintf (ftable, "%6d", rrhs[i + 1] - rrhs[i] - 1);
 482     }
 483
 484   putc (',', ftable);
 485   if (j >= 10)
 486     putc ('\n', ftable);
 487
 488   fprintf (ftable, "%6d\n};\n", nitems - rrhs[nrules] - 1);
 489   FREE (rrhs + 1);
 490 }
 491
 492
 493 static void
 494 output_defines (void)
 495 {
 496   fprintf (ftable, "\n\n#define\tYYFINAL\t\t%d\n", final_state);
 497   fprintf (ftable, "#define\tYYFLAG\t\t%d\n", MINSHORT);
 498   fprintf (ftable, "#define\tYYNTBASE\t%d\n", ntokens);
 499 }
 500
 501
 502 /*------------------------------------------------------------------.
 503 | Decide what to do for each type of token if seen as the lookahead |
 504 | token in specified state.  The value returned is used as the      |
 505 | default action (yydefact) for the state.  In addition, actrow is  |
 506 | filled with what to do for each kind of token, index by symbol    |
 507 | number, with zero meaning do the default action.  The value       |
 508 | MINSHORT, a very negative number, means this situation is an      |
 509 | error.  The parser recognizes this value specially.               |
 510 |                                                                   |
 511 | This is where conflicts are resolved.  The loop over lookahead    |
 512 | rules considered lower-numbered rules last, and the last rule     |
 513 | considered that likes a token gets to handle it.                  |
 514 `------------------------------------------------------------------*/
 515
 516 static int
 517 action_row (int state)
 518 {
 519   int i;
 520   int j;
 521   int k;
 522   int m = 0;
 523   int n = 0;
 524   int count;
 525   int default_rule;
 526   int nreds;
 527   int max;
 528   int rule;
 529   int shift_state;
 530   int symbol;
 531   unsigned mask;
 532   unsigned *wordp;
 533   reductions *redp;
 534   shifts *shiftp;
 535   errs *errp;
 536   int nodefault = 0;            /* set nonzero to inhibit having any default reduction */
 537
 538   for (i = 0; i < ntokens; i++)
 539     actrow[i] = 0;
 540
 541   default_rule = 0;
 542   nreds = 0;
 543   redp = reduction_table[state];
 544
 545   if (redp)
 546     {
 547       nreds = redp->nreds;
 548
 549       if (nreds >= 1)
 550         {
 551           /* loop over all the rules available here which require
 552              lookahead */
 553           m = lookaheads[state];
 554           n = lookaheads[state + 1];
 555
 556           for (i = n - 1; i >= m; i--)
 557             {
 558               rule = -LAruleno[i];
 559               wordp = LA + i * tokensetsize;
 560               mask = 1;
 561
 562               /* and find each token which the rule finds acceptable
 563                  to come next */
 564               for (j = 0; j < ntokens; j++)
 565                 {
 566                   /* and record this rule as the rule to use if that
 567                      token follows.  */
 568                   if (mask & *wordp)
 569                     actrow[j] = rule;
 570
 571                   mask <<= 1;
 572                   if (mask == 0)
 573                     {
 574                       mask = 1;
 575                       wordp++;
 576                     }
 577                 }
 578             }
 579         }
 580     }
 581
 582   shiftp = shift_table[state];
 583
 584   /* Now see which tokens are allowed for shifts in this state.  For
 585      them, record the shift as the thing to do.  So shift is preferred
 586      to reduce.  */
 587
 588   if (shiftp)
 589     {
 590       k = shiftp->nshifts;
 591
 592       for (i = 0; i < k; i++)
 593         {
 594           shift_state = shiftp->shifts[i];
 595           if (!shift_state)
 596             continue;
 597
 598           symbol = accessing_symbol[shift_state];
 599
 600           if (ISVAR (symbol))
 601             break;
 602
 603           actrow[symbol] = shift_state;
 604
 605           /* Do not use any default reduction if there is a shift for
 606              error */
 607           if (symbol == error_token_number)
 608             nodefault = 1;
 609         }
 610     }
 611
 612   errp = err_table[state];
 613
 614   /* See which tokens are an explicit error in this state (due to
 615      %nonassoc).  For them, record MINSHORT as the action.  */
 616
 617   if (errp)
 618     {
 619       k = errp->nerrs;
 620
 621       for (i = 0; i < k; i++)
 622         {
 623           symbol = errp->errs[i];
 624           actrow[symbol] = MINSHORT;
 625         }
 626     }
 627
 628   /* Now find the most common reduction and make it the default action
 629      for this state.  */
 630
 631   if (nreds >= 1 && !nodefault)
 632     {
 633       if (consistent[state])
 634         default_rule = redp->rules[0];
 635       else
 636         {
 637           max = 0;
 638           for (i = m; i < n; i++)
 639             {
 640               count = 0;
 641               rule = -LAruleno[i];
 642
 643               for (j = 0; j < ntokens; j++)
 644                 {
 645                   if (actrow[j] == rule)
 646                     count++;
 647                 }
 648
 649               if (count > max)
 650                 {
 651                   max = count;
 652                   default_rule = rule;
 653                 }
 654             }
 655
 656           /* actions which match the default are replaced with zero,
 657              which means "use the default" */
 658
 659           if (max > 0)
 660             {
 661               for (j = 0; j < ntokens; j++)
 662                 {
 663                   if (actrow[j] == default_rule)
 664                     actrow[j] = 0;
 665                 }
 666
 667               default_rule = -default_rule;
 668             }
 669         }
 670     }
 671
 672   /* If have no default rule, the default is an error.
 673      So replace any action which says "error" with "use default".  */
 674
 675   if (default_rule == 0)
 676     for (j = 0; j < ntokens; j++)
 677       {
 678         if (actrow[j] == MINSHORT)
 679           actrow[j] = 0;
 680       }
 681
 682   return default_rule;
 683 }
 684
 685
 686 static void
 687 save_row (int state)
 688 {
 689   int i;
 690   int count;
 691   short *sp;
 692   short *sp1;
 693   short *sp2;
 694
 695   count = 0;
 696   for (i = 0; i < ntokens; i++)
 697     {
 698       if (actrow[i] != 0)
 699         count++;
 700     }
 701
 702   if (count == 0)
 703     return;
 704
 705   froms[state] = sp1 = sp = NEW2 (count, short);
 706   tos[state] = sp2 = NEW2 (count, short);
 707
 708   for (i = 0; i < ntokens; i++)
 709     {
 710       if (actrow[i] != 0)
 711         {
 712           *sp1++ = i;
 713           *sp2++ = actrow[i];
 714         }
 715     }
 716
 717   tally[state] = count;
 718   width[state] = sp1[-1] - sp[0] + 1;
 719 }
 720
 721
 722 /*------------------------------------------------------------------.
 723 | Figure out the actions for the specified state, indexed by        |
 724 | lookahead token type.                                             |
 725 |                                                                   |
 726 | The YYDEFACT table is output now.  The detailed info is saved for |
 727 | putting into YYTABLE later.                                       |
 728 `------------------------------------------------------------------*/
 729
 730 static void
 731 token_actions (void)
 732 {
 733   int i;
 734   short *yydefact = NEW2 (nstates, short);
 735
 736   actrow = NEW2 (ntokens, short);
 737   for (i = 0; i < nstates; ++i)
 738     {
 739       yydefact[i] = action_row (i);
 740       save_row (i);
 741     }
 742   FREE (actrow);
 743
 744   output_short_table (ftable, "yydefact", yydefact,
 745                       yydefact[0], 1, nstates);
 746   FREE (yydefact);
 747 }
 748
 749
 750 static void
 751 free_shifts (void)
 752 {
 753   shifts *sp, *sptmp;   /* JF derefrenced freed ptr */
 754
 755   FREE (shift_table);
 756
 757   for (sp = first_shift; sp; sp = sptmp)
 758     {
 759       sptmp = sp->next;
 760       FREE (sp);
 761     }
 762 }
 763
 764
 765 static void
 766 free_reductions (void)
 767 {
 768   reductions *rp, *rptmp;       /* JF fixed freed ptr */
 769
 770   FREE (reduction_table);
 771
 772   for (rp = first_reduction; rp; rp = rptmp)
 773     {
 774       rptmp = rp->next;
 775       FREE (rp);
 776     }
 777 }
 778
 779
 780
 781 static void
 782 save_column (int symbol, int default_state)
 783 {
 784   int i;
 785   int m;
 786   int n;
 787   short *sp;
 788   short *sp1;
 789   short *sp2;
 790   int count;
 791   int symno;
 792
 793   m = goto_map[symbol];
 794   n = goto_map[symbol + 1];
 795
 796   count = 0;
 797   for (i = m; i < n; i++)
 798     {
 799       if (to_state[i] != default_state)
 800         count++;
 801     }
 802
 803   if (count == 0)
 804     return;
 805
 806   symno = symbol - ntokens + nstates;
 807
 808   froms[symno] = sp1 = sp = NEW2 (count, short);
 809   tos[symno] = sp2 = NEW2 (count, short);
 810
 811   for (i = m; i < n; i++)
 812     {
 813       if (to_state[i] != default_state)
 814         {
 815           *sp1++ = from_state[i];
 816           *sp2++ = to_state[i];
 817         }
 818     }
 819
 820   tally[symno] = count;
 821   width[symno] = sp1[-1] - sp[0] + 1;
 822 }
 823
 824 static int
 825 default_goto (int symbol)
 826 {
 827   int i;
 828   int m;
 829   int n;
 830   int default_state;
 831   int max;
 832
 833   m = goto_map[symbol];
 834   n = goto_map[symbol + 1];
 835
 836   if (m == n)
 837     return -1;
 838
 839   for (i = 0; i < nstates; i++)
 840     state_count[i] = 0;
 841
 842   for (i = m; i < n; i++)
 843     state_count[to_state[i]]++;
 844
 845   max = 0;
 846   default_state = -1;
 847
 848   for (i = 0; i < nstates; i++)
 849     {
 850       if (state_count[i] > max)
 851         {
 852           max = state_count[i];
 853           default_state = i;
 854         }
 855     }
 856
 857   return default_state;
 858 }
 859
 860
 861 /*-------------------------------------------------------------------.
 862 | Figure out what to do after reducing with each rule, depending on  |
 863 | the saved state from before the beginning of parsing the data that |
 864 | matched this rule.                                                 |
 865 |                                                                    |
 866 | The YYDEFGOTO table is output now.  The detailed info is saved for |
 867 | putting into YYTABLE later.                                        |
 868 `-------------------------------------------------------------------*/
 869
 870 static void
 871 goto_actions (void)
 872 {
 873   int i, j, k;
 874
 875   state_count = NEW2 (nstates, short);
 876
 877   k = default_goto (ntokens);
 878   fprintf (ftable, "\nstatic const short yydefgoto[] = {%6d", k);
 879   save_column (ntokens, k);
 880
 881   j = 10;
 882   for (i = ntokens + 1; i < nsyms; i++)
 883     {
 884       putc (',', ftable);
 885
 886       if (j >= 10)
 887         {
 888           putc ('\n', ftable);
 889           j = 1;
 890         }
 891       else
 892         {
 893           j++;
 894         }
 895
 896       k = default_goto (i);
 897       fprintf (ftable, "%6d", k);
 898       save_column (i, k);
 899     }
 900
 901   fprintf (ftable, "\n};\n");
 902   FREE (state_count);
 903 }
 904
 905
 906 /* The next few functions decide how to pack the actions and gotos
 907    information into yytable. */
 908
 909 static void
 910 sort_actions (void)
 911 {
 912   int i;
 913   int j;
 914   int k;
 915   int t;
 916   int w;
 917
 918   order = NEW2 (nvectors, short);
 919   nentries = 0;
 920
 921   for (i = 0; i < nvectors; i++)
 922     {
 923       if (tally[i] > 0)
 924         {
 925           t = tally[i];
 926           w = width[i];
 927           j = nentries - 1;
 928
 929           while (j >= 0 && (width[order[j]] < w))
 930             j--;
 931
 932           while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
 933             j--;
 934
 935           for (k = nentries - 1; k > j; k--)
 936             order[k + 1] = order[k];
 937
 938           order[j + 1] = i;
 939           nentries++;
 940         }
 941     }
 942 }
 943
 944
 945 static int
 946 matching_state (int vector)
 947 {
 948   int i;
 949   int j;
 950   int k;
 951   int t;
 952   int w;
 953   int match;
 954   int prev;
 955
 956   i = order[vector];
 957   if (i >= nstates)
 958     return -1;
 959
 960   t = tally[i];
 961   w = width[i];
 962
 963   for (prev = vector - 1; prev >= 0; prev--)
 964     {
 965       j = order[prev];
 966       if (width[j] != w || tally[j] != t)
 967         return -1;
 968
 969       match = 1;
 970       for (k = 0; match && k < t; k++)
 971         {
 972           if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
 973             match = 0;
 974         }
 975
 976       if (match)
 977         return j;
 978     }
 979
 980   return -1;
 981 }
 982
 983
 984 static int
 985 pack_vector (int vector)
 986 {
 987   int i;
 988   int j;
 989   int k;
 990   int t;
 991   int loc = 0;
 992   int ok;
 993   short *from;
 994   short *to;
 995
 996   i = order[vector];
 997   t = tally[i];
 998
 999   if (t == 0)
1000     berror ("pack_vector");
1001
1002   from = froms[i];
1003   to = tos[i];
1004
1005   for (j = lowzero - from[0]; j < MAXTABLE; j++)
1006     {
1007       ok = 1;
1008
1009       for (k = 0; ok && k < t; k++)
1010         {
1011           loc = j + from[k];
1012           if (loc > MAXTABLE)
1013             fatal (_("maximum table size (%d) exceeded"), MAXTABLE);
1014
1015           if (table[loc] != 0)
1016             ok = 0;
1017         }
1018
1019       for (k = 0; ok && k < vector; k++)
1020         {
1021           if (pos[k] == j)
1022             ok = 0;
1023         }
1024
1025       if (ok)
1026         {
1027           for (k = 0; k < t; k++)
1028             {
1029               loc = j + from[k];
1030               table[loc] = to[k];
1031               check[loc] = from[k];
1032             }
1033
1034           while (table[lowzero] != 0)
1035             lowzero++;
1036
1037           if (loc > high)
1038             high = loc;
1039
1040           return j;
1041         }
1042     }
1043
1044   berror ("pack_vector");
1045   return 0;                     /* JF keep lint happy */
1046 }
1047
1048
1049 static void
1050 pack_table (void)
1051 {
1052   int i;
1053   int place;
1054   int state;
1055
1056   base = NEW2 (nvectors, short);
1057   pos = NEW2 (nentries, short);
1058   table = NEW2 (MAXTABLE, short);
1059   check = NEW2 (MAXTABLE, short);
1060
1061   lowzero = 0;
1062   high = 0;
1063
1064   for (i = 0; i < nvectors; i++)
1065     base[i] = MINSHORT;
1066
1067   for (i = 0; i < MAXTABLE; i++)
1068     check[i] = -1;
1069
1070   for (i = 0; i < nentries; i++)
1071     {
1072       state = matching_state (i);
1073
1074       if (state < 0)
1075         place = pack_vector (i);
1076       else
1077         place = base[state];
1078
1079       pos[i] = place;
1080       base[order[i]] = place;
1081     }
1082
1083   for (i = 0; i < nvectors; i++)
1084     {
1085       if (froms[i])
1086         FREE (froms[i]);
1087       if (tos[i])
1088         FREE (tos[i]);
1089     }
1090
1091   FREE (froms);
1092   FREE (tos);
1093   FREE (pos);
1094 }
1095
1096 /* the following functions output yytable, yycheck
1097    and the vectors whose elements index the portion starts */
1098
1099 static void
1100 output_base (void)
1101 {
1102   output_short_table (ftable, "yypact", base,
1103                       base[0], 1, nstates);
1104
1105   putc ('\n', ftable);
1106
1107   output_short_table (ftable, "yypgoto", base,
1108                       base[nstates], nstates + 1, nvectors);
1109
1110   FREE (base);
1111 }
1112
1113
1114 static void
1115 output_table (void)
1116 {
1117   fprintf (ftable, "\n\n#define\tYYLAST\t\t%d\n\n\n", high);
1118   output_short_table (ftable, "yytable", table,
1119                       table[0], 1, high + 1);
1120   FREE (table);
1121 }
1122
1123
1124 static void
1125 output_check (void)
1126 {
1127   output_short_table (ftable, "yycheck", check,
1128                       check[0], 1, high + 1);
1129   FREE (check);
1130 }
1131
1132 /* compute and output yydefact, yydefgoto, yypact, yypgoto, yytable
1133    and yycheck.  */
1134
1135 static void
1136 output_actions (void)
1137 {
1138   nvectors = nstates + nvars;
1139
1140   froms = NEW2 (nvectors, short *);
1141   tos = NEW2 (nvectors, short *);
1142   tally = NEW2 (nvectors, short);
1143   width = NEW2 (nvectors, short);
1144
1145   token_actions ();
1146   free_shifts ();
1147   free_reductions ();
1148   FREE (lookaheads);
1149   FREE (LA);
1150   FREE (LAruleno);
1151   FREE (accessing_symbol);
1152
1153   goto_actions ();
1154   FREE (goto_map + ntokens);
1155   FREE (from_state);
1156   FREE (to_state);
1157
1158   sort_actions ();
1159   pack_table ();
1160   putc ('\n', ftable);
1161   output_base ();
1162   output_table ();
1163   putc ('\n', ftable);
1164   output_check ();
1165 }
1166
1167 /* copy the parser code into the ftable file at the end.  */
1168
1169 static void
1170 output_parser (void)
1171 {
1172   int c;
1173 #ifdef DONTDEF
1174   FILE *fpars;
1175 #else
1176 #define fpars fparser
1177 #endif
1178
1179   if (pure_parser)
1180     fprintf (ftable, "#define YYPURE 1\n\n");
1181
1182 #ifdef DONTDEF                  /* JF no longer needed 'cuz open_extra_files changes the
1183                                    currently open parser from bison.simple to bison.hairy */
1184   if (semantic_parser)
1185     fpars = fparser;
1186   else
1187     fpars = fparser1;
1188 #endif
1189
1190   /* Loop over lines in the standard parser file.  */
1191
1192   while (1)
1193     {
1194       int write_line = 1;
1195
1196       c = getc (fpars);
1197
1198       /* See if the line starts with `#line.
1199          If so, set write_line to 0.  */
1200       if (nolinesflag)
1201         if (c == '#')
1202           {
1203             c = getc (fpars);
1204             if (c == 'l')
1205               {
1206                 c = getc (fpars);
1207                 if (c == 'i')
1208                   {
1209                     c = getc (fpars);
1210                     if (c == 'n')
1211                       {
1212                         c = getc (fpars);
1213                         if (c == 'e')
1214                           write_line = 0;
1215                         else
1216                           fprintf (ftable, "#lin");
1217                       }
1218                     else
1219                       fprintf (ftable, "#li");
1220                   }
1221                 else
1222                   fprintf (ftable, "#l");
1223               }
1224             else
1225               fprintf (ftable, "#");
1226           }
1227
1228       /* now write out the line... */
1229       for (; c != '\n' && c != EOF; c = getc (fpars))
1230         if (write_line)
1231           {
1232             if (c == '$')
1233               {
1234                 /* `$' in the parser file indicates where to put the actions.
1235                    Copy them in at this point.  */
1236                 rewind (faction);
1237                 for (c = getc (faction); c != EOF; c = getc (faction))
1238                   putc (c, ftable);
1239               }
1240             else
1241               putc (c, ftable);
1242           }
1243       if (c == EOF)
1244         break;
1245       putc (c, ftable);
1246     }
1247 }
1248
1249 static void
1250 output_program (void)
1251 {
1252   int c;
1253
1254   if (!nolinesflag)
1255     fprintf (ftable, "#line %d \"%s\"\n", lineno, infile);
1256
1257   c = getc (finput);
1258   while (c != EOF)
1259     {
1260       putc (c, ftable);
1261       c = getc (finput);
1262     }
1263 }
1264
1265
1266 static void
1267 free_itemsets (void)
1268 {
1269   core *cp, *cptmp;
1270
1271   FREE (state_table);
1272
1273   for (cp = first_state; cp; cp = cptmp)
1274     {
1275       cptmp = cp->next;
1276       FREE (cp);
1277     }
1278 }
1279
1280
1281 /*----------------------------------------------------------.
1282 | Output the parsing tables and the parser code to ftable.  |
1283 `----------------------------------------------------------*/
1284
1285 void
1286 output (void)
1287 {
1288   int c;
1289
1290   /* output_token_defines(ftable);      / * JF put out token defines FIRST */
1291   if (!semantic_parser)         /* JF Put out other stuff */
1292     {
1293       rewind (fattrs);
1294       while ((c = getc (fattrs)) != EOF)
1295         putc (c, ftable);
1296     }
1297   reader_output_yylsp (ftable);
1298   if (debugflag)
1299     fputs ("\
1300 #ifndef YYDEBUG\n\
1301 #define YYDEBUG 1\n\
1302 #endif\n\
1303 \n",
1304            ftable);
1305
1306   if (semantic_parser)
1307     fprintf (ftable, "#include \"%s\"\n", attrsfile);
1308
1309   if (!noparserflag)
1310     fprintf (ftable, "#include <stdio.h>\n\n");
1311
1312   /* Make "const" do nothing if not in ANSI C.  */
1313   fputs ("\
1314 #ifndef __cplusplus\n\
1315 # ifndef __STDC__\n\
1316 #  define const\n\
1317 # endif\n\
1318 #endif\n\
1319 \n",
1320          ftable);
1321
1322   free_itemsets ();
1323   output_defines ();
1324   output_token_translations ();
1325 /*   if (semantic_parser) */
1326   /* This is now unconditional because debugging printouts can use it.  */
1327   output_gram ();
1328   FREE (ritem);
1329   if (semantic_parser)
1330     output_stos ();
1331   output_rule_data ();
1332   output_actions ();
1333   if (!noparserflag)
1334     output_parser ();
1335   output_program ();
1336 }