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