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