src/output.c

   1 /* Output the generated parsing program for bison,
   2    Copyright (C) 1984, 1986, 1989, 1992 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
   7 it 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,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU 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
  18 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19 Boston, MA 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   fprintf(ftable, "\n#if YYDEBUG != 0\n");
 438   fprintf(ftable, "static const short yyrline[] = { 0");
 439
 440   j = 10;
 441   for (i = 1; i <= nrules; i++)
 442     {
 443       putc(',', ftable);
 444
 445       if (j >= 10)
 446         {
 447           putc('\n', ftable);
 448           j = 1;
 449         }
 450       else
 451         {
 452           j++;
 453         }
 454
 455       fprintf(ftable, "%6d", rline[i]);
 456     }
 457   fprintf(ftable, "\n};\n#endif\n\n");
 458
 459   if (toknumflag || noparserflag)
 460     {
 461       fprintf(ftable, "#define YYNTOKENS %d\n", ntokens);
 462       fprintf(ftable, "#define YYNNTS %d\n", nvars);
 463       fprintf(ftable, "#define YYNRULES %d\n", nrules);
 464       fprintf(ftable, "#define YYNSTATES %d\n", nstates);
 465       fprintf(ftable, "#define YYMAXUTOK %d\n\n", max_user_token_number);
 466     }
 467
 468   if (! toknumflag  && ! noparserflag)
 469     fprintf(ftable, "\n#if YYDEBUG != 0 || defined (YYERROR_VERBOSE)\n\n");
 470
 471   /* Output the table of symbol names.  */
 472
 473   fprintf(ftable,
 474           "static const char * const yytname[] = {   \"%s\"",
 475           tags[0]);
 476
 477   j = strlen (tags[0]) + 44;
 478   for (i = 1; i < nsyms; i++)
 479                 /* this used to be i<=nsyms, but that output a final "" symbol
 480                         almost by accident */
 481     {
 482       register char *p;
 483       putc(',', ftable);
 484       j++;
 485
 486       if (j > 75)
 487         {
 488           putc('\n', ftable);
 489           j = 0;
 490         }
 491
 492       putc ('\"', ftable);
 493       j++;
 494
 495       for (p = tags[i]; p && *p; p++)
 496         {
 497           if (*p == '"' || *p == '\\')
 498             {
 499               fprintf(ftable, "\\%c", *p);
 500               j += 2;
 501             }
 502           else if (*p == '\n')
 503             {
 504               fprintf(ftable, "\\n");
 505               j += 2;
 506             }
 507           else if (*p == '\t')
 508             {
 509               fprintf(ftable, "\\t");
 510               j += 2;
 511             }
 512           else if (*p == '\b')
 513             {
 514               fprintf(ftable, "\\b");
 515               j += 2;
 516             }
 517           else if (*p < 040 || *p >= 0177)
 518             {
 519               fprintf(ftable, "\\%03o", *p);
 520               j += 4;
 521             }
 522           else
 523             {
 524               putc(*p, ftable);
 525               j++;
 526             }
 527         }
 528
 529       putc ('\"', ftable);
 530       j++;
 531     }
 532     fprintf(ftable, ", NULL\n};\n");    /* add a NULL entry to list of tokens */
 533
 534   if (! toknumflag  && ! noparserflag)
 535     fprintf(ftable, "#endif\n\n");
 536
 537   if (toknumflag)
 538     {
 539       fprintf(ftable, "static const short yytoknum[] = { 0");
 540       j = 10;
 541       for (i = 1; i <= ntokens; i++) {
 542           putc(',', ftable);
 543           if (j >= 10)
 544             {
 545               putc('\n', ftable);
 546               j = 1;
 547             }
 548           else
 549             j++;
 550           fprintf(ftable, "%6d", user_toknums[i]);
 551       }
 552       fprintf(ftable, "\n};\n\n");
 553     }
 554
 555   fprintf(ftable, "static const short yyr1[] = {     0");
 556
 557   j = 10;
 558   for (i = 1; i <= nrules; i++)
 559     {
 560       putc(',', ftable);
 561
 562       if (j >= 10)
 563         {
 564           putc('\n', ftable);
 565           j = 1;
 566         }
 567       else
 568         {
 569           j++;
 570         }
 571
 572       fprintf(ftable, "%6d", rlhs[i]);
 573     }
 574
 575   FREE(rlhs + 1);
 576
 577   fprintf(ftable, "\n};\n\nstatic const short yyr2[] = {     0");
 578
 579   j = 10;
 580   for (i = 1; i < nrules; i++)
 581     {
 582       putc(',', ftable);
 583
 584       if (j >= 10)
 585         {
 586           putc('\n', ftable);
 587           j = 1;
 588         }
 589       else
 590         {
 591           j++;
 592         }
 593
 594       fprintf(ftable, "%6d", rrhs[i + 1] - rrhs[i] - 1);
 595     }
 596
 597   putc(',', ftable);
 598   if (j >= 10)
 599     putc('\n', ftable);
 600
 601   fprintf(ftable, "%6d\n};\n", nitems - rrhs[nrules] - 1);
 602   FREE(rrhs + 1);
 603 }
 604
 605
 606 void
 607 output_defines (void)
 608 {
 609   fprintf(ftable, "\n\n#define\tYYFINAL\t\t%d\n", final_state);
 610   fprintf(ftable, "#define\tYYFLAG\t\t%d\n", MINSHORT);
 611   fprintf(ftable, "#define\tYYNTBASE\t%d\n", ntokens);
 612 }
 613
 614
 615
 616 /* compute and output yydefact, yydefgoto, yypact, yypgoto, yytable and yycheck.  */
 617
 618 void
 619 output_actions (void)
 620 {
 621   nvectors = nstates + nvars;
 622
 623   froms = NEW2(nvectors, short *);
 624   tos = NEW2(nvectors, short *);
 625   tally = NEW2(nvectors, short);
 626   width = NEW2(nvectors, short);
 627
 628   token_actions();
 629   free_shifts();
 630   free_reductions();
 631   FREE(lookaheads);
 632   FREE(LA);
 633   FREE(LAruleno);
 634   FREE(accessing_symbol);
 635
 636   goto_actions();
 637   FREE(goto_map + ntokens);
 638   FREE(from_state);
 639   FREE(to_state);
 640
 641   sort_actions();
 642   pack_table();
 643   output_base();
 644   output_table();
 645   output_check();
 646 }
 647
 648
 649
 650 /* figure out the actions for the specified state, indexed by lookahead token type.
 651
 652    The yydefact table is output now.  The detailed info
 653    is saved for putting into yytable later.  */
 654
 655 void
 656 token_actions (void)
 657 {
 658   register int i;
 659   register int j;
 660   register int k;
 661
 662   actrow = NEW2(ntokens, short);
 663
 664   k = action_row(0);
 665   fprintf(ftable, "\nstatic const short yydefact[] = {%6d", k);
 666   save_row(0);
 667
 668   j = 10;
 669   for (i = 1; i < nstates; i++)
 670     {
 671       putc(',', ftable);
 672
 673       if (j >= 10)
 674         {
 675           putc('\n', ftable);
 676           j = 1;
 677         }
 678       else
 679         {
 680           j++;
 681         }
 682
 683       k = action_row(i);
 684       fprintf(ftable, "%6d", k);
 685       save_row(i);
 686     }
 687
 688   fprintf(ftable, "\n};\n");
 689   FREE(actrow);
 690 }
 691
 692
 693
 694 /* Decide what to do for each type of token if seen as the lookahead token in specified state.
 695    The value returned is used as the default action (yydefact) for the state.
 696    In addition, actrow is filled with what to do for each kind of token,
 697    index by symbol number, with zero meaning do the default action.
 698    The value MINSHORT, a very negative number, means this situation
 699    is an error.  The parser recognizes this value specially.
 700
 701    This is where conflicts are resolved.  The loop over lookahead rules
 702    considered lower-numbered rules last, and the last rule considered that likes
 703    a token gets to handle it.  */
 704
 705 int
 706 action_row (int state)
 707 {
 708   register int i;
 709   register int j;
 710   register int k;
 711   register int m = 0;
 712   register int n = 0;
 713   register int count;
 714   register int default_rule;
 715   register int nreds;
 716   register int max;
 717   register int rule;
 718   register int shift_state;
 719   register int symbol;
 720   register unsigned mask;
 721   register unsigned *wordp;
 722   register reductions *redp;
 723   register shifts *shiftp;
 724   register errs *errp;
 725   int nodefault = 0;  /* set nonzero to inhibit having any default reduction */
 726
 727   for (i = 0; i < ntokens; i++)
 728     actrow[i] = 0;
 729
 730   default_rule = 0;
 731   nreds = 0;
 732   redp = reduction_table[state];
 733
 734   if (redp)
 735     {
 736       nreds = redp->nreds;
 737
 738       if (nreds >= 1)
 739         {
 740           /* loop over all the rules available here which require lookahead */
 741           m = lookaheads[state];
 742           n = lookaheads[state + 1];
 743
 744           for (i = n - 1; i >= m; i--)
 745             {
 746               rule = - LAruleno[i];
 747               wordp = LA + i * tokensetsize;
 748               mask = 1;
 749
 750               /* and find each token which the rule finds acceptable to come next */
 751               for (j = 0; j < ntokens; j++)
 752                 {
 753                   /* and record this rule as the rule to use if that token follows.  */
 754                   if (mask & *wordp)
 755                     actrow[j] = rule;
 756
 757                   mask <<= 1;
 758                   if (mask == 0)
 759                     {
 760                       mask = 1;
 761                       wordp++;
 762                     }
 763                 }
 764             }
 765         }
 766     }
 767
 768   shiftp = shift_table[state];
 769
 770   /* now see which tokens are allowed for shifts in this state.
 771      For them, record the shift as the thing to do.  So shift is preferred to reduce.  */
 772
 773   if (shiftp)
 774     {
 775       k = shiftp->nshifts;
 776
 777       for (i = 0; i < k; i++)
 778         {
 779           shift_state = shiftp->shifts[i];
 780           if (! shift_state) continue;
 781
 782           symbol = accessing_symbol[shift_state];
 783
 784           if (ISVAR(symbol))
 785             break;
 786
 787           actrow[symbol] = shift_state;
 788
 789           /* do not use any default reduction if there is a shift for error */
 790
 791           if (symbol == error_token_number) nodefault = 1;
 792         }
 793     }
 794
 795   errp = err_table[state];
 796
 797   /* See which tokens are an explicit error in this state
 798      (due to %nonassoc).  For them, record MINSHORT as the action.  */
 799
 800   if (errp)
 801     {
 802       k = errp->nerrs;
 803
 804       for (i = 0; i < k; i++)
 805         {
 806           symbol = errp->errs[i];
 807           actrow[symbol] = MINSHORT;
 808         }
 809     }
 810
 811   /* now find the most common reduction and make it the default action for this state.  */
 812
 813   if (nreds >= 1 && ! nodefault)
 814     {
 815       if (consistent[state])
 816         default_rule = redp->rules[0];
 817       else
 818         {
 819           max = 0;
 820           for (i = m; i < n; i++)
 821             {
 822               count = 0;
 823               rule = - LAruleno[i];
 824
 825               for (j = 0; j < ntokens; j++)
 826                 {
 827                   if (actrow[j] == rule)
 828                     count++;
 829                 }
 830
 831               if (count > max)
 832                 {
 833                   max = count;
 834                   default_rule = rule;
 835                 }
 836             }
 837
 838           /* actions which match the default are replaced with zero,
 839              which means "use the default" */
 840
 841           if (max > 0)
 842             {
 843               for (j = 0; j < ntokens; j++)
 844                 {
 845                   if (actrow[j] == default_rule)
 846                     actrow[j] = 0;
 847                 }
 848
 849               default_rule = - default_rule;
 850             }
 851         }
 852     }
 853
 854   /* If have no default rule, the default is an error.
 855      So replace any action which says "error" with "use default".  */
 856
 857   if (default_rule == 0)
 858     for (j = 0; j < ntokens; j++)
 859       {
 860         if (actrow[j] == MINSHORT)
 861           actrow[j] = 0;
 862       }
 863
 864   return (default_rule);
 865 }
 866
 867
 868 void
 869 save_row (int state)
 870 {
 871   register int i;
 872   register int count;
 873   register short *sp;
 874   register short *sp1;
 875   register short *sp2;
 876
 877   count = 0;
 878   for (i = 0; i < ntokens; i++)
 879     {
 880       if (actrow[i] != 0)
 881         count++;
 882     }
 883
 884   if (count == 0)
 885     return;
 886
 887   froms[state] = sp1 = sp = NEW2(count, short);
 888   tos[state] = sp2 = NEW2(count, short);
 889
 890   for (i = 0; i < ntokens; i++)
 891     {
 892       if (actrow[i] != 0)
 893         {
 894           *sp1++ = i;
 895           *sp2++ = actrow[i];
 896         }
 897     }
 898
 899   tally[state] = count;
 900   width[state] = sp1[-1] - sp[0] + 1;
 901 }
 902
 903
 904
 905 /* figure out what to do after reducing with each rule,
 906    depending on the saved state from before the beginning
 907    of parsing the data that matched this rule.
 908
 909    The yydefgoto table is output now.  The detailed info
 910    is saved for putting into yytable later.  */
 911
 912 void
 913 goto_actions (void)
 914 {
 915   register int i;
 916   register int j;
 917   register int k;
 918
 919   state_count = NEW2(nstates, short);
 920
 921   k = default_goto(ntokens);
 922   fprintf(ftable, "\nstatic const short yydefgoto[] = {%6d", k);
 923   save_column(ntokens, k);
 924
 925   j = 10;
 926   for (i = ntokens + 1; i < nsyms; i++)
 927     {
 928       putc(',', ftable);
 929
 930       if (j >= 10)
 931         {
 932           putc('\n', ftable);
 933           j = 1;
 934         }
 935       else
 936         {
 937           j++;
 938         }
 939
 940       k = default_goto(i);
 941       fprintf(ftable, "%6d", k);
 942       save_column(i, k);
 943     }
 944
 945   fprintf(ftable, "\n};\n");
 946   FREE(state_count);
 947 }
 948
 949
 950
 951 int
 952 default_goto (int symbol)
 953 {
 954   register int i;
 955   register int m;
 956   register int n;
 957   register int default_state;
 958   register int max;
 959
 960   m = goto_map[symbol];
 961   n = goto_map[symbol + 1];
 962
 963   if (m == n)
 964     return (-1);
 965
 966   for (i = 0; i < nstates; i++)
 967     state_count[i] = 0;
 968
 969   for (i = m; i < n; i++)
 970     state_count[to_state[i]]++;
 971
 972   max = 0;
 973   default_state = -1;
 974
 975   for (i = 0; i < nstates; i++)
 976     {
 977       if (state_count[i] > max)
 978         {
 979           max = state_count[i];
 980           default_state = i;
 981         }
 982     }
 983
 984   return (default_state);
 985 }
 986
 987
 988 void
 989 save_column (int symbol, int default_state)
 990 {
 991   register int i;
 992   register int m;
 993   register int n;
 994   register short *sp;
 995   register short *sp1;
 996   register short *sp2;
 997   register int count;
 998   register int symno;
 999
1000   m = goto_map[symbol];
1001   n = goto_map[symbol + 1];
1002
1003   count = 0;
1004   for (i = m; i < n; i++)
1005     {
1006       if (to_state[i] != default_state)
1007         count++;
1008     }
1009
1010   if (count == 0)
1011     return;
1012
1013   symno = symbol - ntokens + nstates;
1014
1015   froms[symno] = sp1 = sp = NEW2(count, short);
1016   tos[symno] = sp2 = NEW2(count, short);
1017
1018   for (i = m; i < n; i++)
1019     {
1020       if (to_state[i] != default_state)
1021         {
1022           *sp1++ = from_state[i];
1023           *sp2++ = to_state[i];
1024         }
1025     }
1026
1027   tally[symno] = count;
1028   width[symno] = sp1[-1] - sp[0] + 1;
1029 }
1030
1031
1032
1033 /* the next few functions decide how to pack
1034    the actions and gotos information into yytable. */
1035
1036 void
1037 sort_actions (void)
1038 {
1039   register int i;
1040   register int j;
1041   register int k;
1042   register int t;
1043   register int w;
1044
1045   order = NEW2(nvectors, short);
1046   nentries = 0;
1047
1048   for (i = 0; i < nvectors; i++)
1049     {
1050       if (tally[i] > 0)
1051         {
1052           t = tally[i];
1053           w = width[i];
1054           j = nentries - 1;
1055
1056           while (j >= 0 && (width[order[j]] < w))
1057             j--;
1058
1059           while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
1060             j--;
1061
1062           for (k = nentries - 1; k > j; k--)
1063             order[k + 1] = order[k];
1064
1065           order[j + 1] = i;
1066           nentries++;
1067         }
1068     }
1069 }
1070
1071
1072 void
1073 pack_table (void)
1074 {
1075   register int i;
1076   register int place;
1077   register int state;
1078
1079   base = NEW2(nvectors, short);
1080   pos = NEW2(nentries, short);
1081   table = NEW2(MAXTABLE, short);
1082   check = NEW2(MAXTABLE, short);
1083
1084   lowzero = 0;
1085   high = 0;
1086
1087   for (i = 0; i < nvectors; i++)
1088     base[i] = MINSHORT;
1089
1090   for (i = 0; i < MAXTABLE; i++)
1091     check[i] = -1;
1092
1093   for (i = 0; i < nentries; i++)
1094     {
1095       state = matching_state(i);
1096
1097       if (state < 0)
1098         place = pack_vector(i);
1099       else
1100         place = base[state];
1101
1102       pos[i] = place;
1103       base[order[i]] = place;
1104     }
1105
1106   for (i = 0; i < nvectors; i++)
1107     {
1108       if (froms[i])
1109         FREE(froms[i]);
1110       if (tos[i])
1111         FREE(tos[i]);
1112     }
1113
1114   FREE(froms);
1115   FREE(tos);
1116   FREE(pos);
1117 }
1118
1119
1120
1121 int
1122 matching_state (int vector)
1123 {
1124   register int i;
1125   register int j;
1126   register int k;
1127   register int t;
1128   register int w;
1129   register int match;
1130   register int prev;
1131
1132   i = order[vector];
1133   if (i >= nstates)
1134     return (-1);
1135
1136   t = tally[i];
1137   w = width[i];
1138
1139   for (prev = vector - 1; prev >= 0; prev--)
1140     {
1141       j = order[prev];
1142       if (width[j] != w || tally[j] != t)
1143         return (-1);
1144
1145       match = 1;
1146       for (k = 0; match && k < t; k++)
1147         {
1148           if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
1149             match = 0;
1150         }
1151
1152       if (match)
1153         return (j);
1154     }
1155
1156   return (-1);
1157 }
1158
1159
1160
1161 int
1162 pack_vector (int vector)
1163 {
1164   register int i;
1165   register int j;
1166   register int k;
1167   register int t;
1168   register int loc = 0;
1169   register int ok;
1170   register short *from;
1171   register short *to;
1172
1173   i = order[vector];
1174   t = tally[i];
1175
1176   if (t == 0)
1177     berror("pack_vector");
1178
1179   from = froms[i];
1180   to = tos[i];
1181
1182   for (j = lowzero - from[0]; j < MAXTABLE; j++)
1183     {
1184       ok = 1;
1185
1186       for (k = 0; ok && k < t; k++)
1187         {
1188           loc = j + from[k];
1189           if (loc > MAXTABLE)
1190             fatals(_("maximum table size (%s) exceeded"), int_to_string(MAXTABLE));
1191
1192           if (table[loc] != 0)
1193             ok = 0;
1194         }
1195
1196       for (k = 0; ok && k < vector; k++)
1197         {
1198           if (pos[k] == j)
1199             ok = 0;
1200         }
1201
1202       if (ok)
1203         {
1204           for (k = 0; k < t; k++)
1205             {
1206               loc = j + from[k];
1207               table[loc] = to[k];
1208               check[loc] = from[k];
1209             }
1210
1211           while (table[lowzero] != 0)
1212             lowzero++;
1213
1214           if (loc > high)
1215             high = loc;
1216
1217           return (j);
1218         }
1219     }
1220
1221   berror("pack_vector");
1222   return 0;     /* JF keep lint happy */
1223 }
1224
1225
1226
1227 /* the following functions output yytable, yycheck
1228    and the vectors whose elements index the portion starts */
1229
1230 void
1231 output_base (void)
1232 {
1233   register int i;
1234   register int j;
1235
1236   fprintf(ftable, "\nstatic const short yypact[] = {%6d", base[0]);
1237
1238   j = 10;
1239   for (i = 1; i < nstates; i++)
1240     {
1241       putc(',', ftable);
1242
1243       if (j >= 10)
1244         {
1245           putc('\n', ftable);
1246           j = 1;
1247         }
1248       else
1249         {
1250           j++;
1251         }
1252
1253       fprintf(ftable, "%6d", base[i]);
1254     }
1255
1256   fprintf(ftable, "\n};\n\nstatic const short yypgoto[] = {%6d", base[nstates]);
1257
1258   j = 10;
1259   for (i = nstates + 1; i < nvectors; i++)
1260     {
1261       putc(',', ftable);
1262
1263       if (j >= 10)
1264         {
1265           putc('\n', ftable);
1266           j = 1;
1267         }
1268       else
1269         {
1270           j++;
1271         }
1272
1273       fprintf(ftable, "%6d", base[i]);
1274     }
1275
1276   fprintf(ftable, "\n};\n");
1277   FREE(base);
1278 }
1279
1280
1281 void
1282 output_table (void)
1283 {
1284   register int i;
1285   register int j;
1286
1287   fprintf(ftable, "\n\n#define\tYYLAST\t\t%d\n\n", high);
1288   fprintf(ftable, "\nstatic const short yytable[] = {%6d", table[0]);
1289
1290   j = 10;
1291   for (i = 1; i <= high; i++)
1292     {
1293       putc(',', ftable);
1294
1295       if (j >= 10)
1296         {
1297           putc('\n', ftable);
1298           j = 1;
1299         }
1300       else
1301         {
1302           j++;
1303         }
1304
1305       fprintf(ftable, "%6d", table[i]);
1306     }
1307
1308   fprintf(ftable, "\n};\n");
1309   FREE(table);
1310 }
1311
1312
1313 void
1314 output_check (void)
1315 {
1316   register int i;
1317   register int j;
1318
1319   fprintf(ftable, "\nstatic const short yycheck[] = {%6d", check[0]);
1320
1321   j = 10;
1322   for (i = 1; i <= high; i++)
1323     {
1324       putc(',', ftable);
1325
1326       if (j >= 10)
1327         {
1328           putc('\n', ftable);
1329           j = 1;
1330         }
1331       else
1332         {
1333           j++;
1334         }
1335
1336       fprintf(ftable, "%6d", check[i]);
1337     }
1338
1339   fprintf(ftable, "\n};\n");
1340   FREE(check);
1341 }
1342
1343
1344
1345 /* copy the parser code into the ftable file at the end.  */
1346
1347 void
1348 output_parser (void)
1349 {
1350   register int c;
1351 #ifdef DONTDEF
1352   FILE *fpars;
1353 #else
1354 #define fpars fparser
1355 #endif
1356
1357   if (pure_parser)
1358     fprintf(ftable, "#define YYPURE 1\n\n");
1359
1360 #ifdef DONTDEF  /* JF no longer needed 'cuz open_extra_files changes the
1361                    currently open parser from bison.simple to bison.hairy */
1362   if (semantic_parser)
1363     fpars = fparser;
1364   else fpars = fparser1;
1365 #endif
1366
1367   /* Loop over lines in the standard parser file.  */
1368
1369   while (1)
1370     {
1371       int write_line = 1;
1372
1373       c = getc(fpars);
1374
1375       /* See if the line starts with `#line.
1376          If so, set write_line to 0.  */
1377       if (nolinesflag)
1378         if (c == '#')
1379           {
1380             c = getc(fpars);
1381             if (c == 'l')
1382               {
1383                 c = getc(fpars);
1384                 if (c == 'i')
1385                   {
1386                     c = getc(fpars);
1387                     if (c == 'n')
1388                       {
1389                         c = getc(fpars);
1390                         if (c == 'e')
1391                           write_line = 0;
1392                         else
1393                           fprintf(ftable, "#lin");
1394                       }
1395                     else
1396                       fprintf(ftable, "#li");
1397                   }
1398                 else
1399                   fprintf(ftable, "#l");
1400               }
1401             else
1402               fprintf(ftable, "#");
1403           }
1404
1405       /* now write out the line... */
1406       for (; c != '\n' && c != EOF; c = getc(fpars))
1407         if (write_line) {
1408           if (c == '$')
1409             {
1410               /* `$' in the parser file indicates where to put the actions.
1411                  Copy them in at this point.  */
1412               rewind(faction);
1413               for(c=getc(faction);c!=EOF;c=getc(faction))
1414                 putc(c,ftable);
1415             }
1416           else
1417             putc(c, ftable);
1418         }
1419       if (c == EOF)
1420         break;
1421       putc(c, ftable);
1422     }
1423 }
1424
1425 void
1426 output_program (void)
1427 {
1428   register int c;
1429
1430   if (!nolinesflag)
1431     fprintf(ftable, "#line %d \"%s\"\n", lineno, infile);
1432
1433   c = getc(finput);
1434   while (c != EOF)
1435     {
1436       putc(c, ftable);
1437       c = getc(finput);
1438     }
1439 }
1440
1441
1442 void
1443 free_itemsets (void)
1444 {
1445   register core *cp,*cptmp;
1446
1447   FREE(state_table);
1448
1449   for (cp = first_state; cp; cp = cptmp) {
1450     cptmp=cp->next;
1451     FREE(cp);
1452   }
1453 }
1454
1455
1456 void
1457 free_shifts (void)
1458 {
1459   register shifts *sp,*sptmp;/* JF derefrenced freed ptr */
1460
1461   FREE(shift_table);
1462
1463   for (sp = first_shift; sp; sp = sptmp) {
1464     sptmp=sp->next;
1465     FREE(sp);
1466   }
1467 }
1468
1469
1470 void
1471 free_reductions (void)
1472 {
1473   register reductions *rp,*rptmp;/* JF fixed freed ptr */
1474
1475   FREE(reduction_table);
1476
1477   for (rp = first_reduction; rp; rp = rptmp) {
1478     rptmp=rp->next;
1479     FREE(rp);
1480   }
1481 }