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