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