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