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