src/output.c

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