usr.bin/yacc/output.c

   1 /*
   2  * Copyright (c) 1989 The Regents of the University of California.
   3  * All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Robert Paul Corbett.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #if 0
  38 #ifndef lint
  39 static char sccsid[] = "@(#)output.c    5.7 (Berkeley) 5/24/93";
  40 #endif
  41 #endif
  42
  43 #include <sys/cdefs.h>
  44 __FBSDID("$FreeBSD$");
  45
  46 #include <limits.h>
  47 #include <stdlib.h>
  48 #include <string.h>
  49 #include "defs.h"
  50
  51 static int nvectors;
  52 static int nentries;
  53 static short **froms;
  54 static short **tos;
  55 static short *tally;
  56 static short *width;
  57 static short *state_count;
  58 static short *order;
  59 static short *base;
  60 static short *pos;
  61 static int maxtable;
  62 static short *table;
  63 static short *check;
  64 static int lowzero;
  65 static int high;
  66
  67 static int default_goto(int);
  68 static void free_itemsets(void);
  69 static void free_reductions(void);
  70 static void free_shifts(void);
  71 static void goto_actions(void);
  72 static int is_C_identifier(char *);
  73 static int matching_vector(int);
  74 static void output_actions(void);
  75 static void output_base(void);
  76 static void output_check(void);
  77 static void output_debug(void);
  78 static void output_defines(void);
  79 static void output_prefix(void);
  80 static void output_rule_data(void);
  81 static void output_semantic_actions(void);
  82 static void output_stored_text(void);
  83 static void output_stype(void);
  84 static void output_table(void);
  85 static void output_trailing_text(void);
  86 static void output_yydefred(void);
  87 static void pack_table(void);
  88 static int pack_vector(int);
  89 static void save_column(int, int);
  90 static void sort_actions(void);
  91 static void token_actions(void);
  92 static int increase_maxtable(int);
  93
  94 static const char line_format[] = "#line %d \"%s\"\n";
  95
  96
  97 void
  98 output()
  99 {
 100     free_itemsets();
 101     free_shifts();
 102     free_reductions();
 103     output_prefix();
 104     output_stored_text();
 105     output_defines();
 106     output_rule_data();
 107     output_yydefred();
 108     output_actions();
 109     free_parser();
 110     output_debug();
 111     output_stype();
 112     if (rflag) write_section(tables);
 113     write_section(header);
 114     output_trailing_text();
 115     write_section(body);
 116     output_semantic_actions();
 117     write_section(trailer);
 118 }
 119
 120
 121 static void
 122 output_prefix()
 123 {
 124     if (symbol_prefix == NULL)
 125         symbol_prefix = "yy";
 126     else
 127     {
 128         ++outline;
 129         fprintf(code_file, "#define yyparse %sparse\n", symbol_prefix);
 130         ++outline;
 131         fprintf(code_file, "#define yylex %slex\n", symbol_prefix);
 132         ++outline;
 133         fprintf(code_file, "#define yyerror %serror\n", symbol_prefix);
 134         ++outline;
 135         fprintf(code_file, "#define yychar %schar\n", symbol_prefix);
 136         ++outline;
 137         fprintf(code_file, "#define yyval %sval\n", symbol_prefix);
 138         ++outline;
 139         fprintf(code_file, "#define yylval %slval\n", symbol_prefix);
 140         ++outline;
 141         fprintf(code_file, "#define yydebug %sdebug\n", symbol_prefix);
 142         ++outline;
 143         fprintf(code_file, "#define yynerrs %snerrs\n", symbol_prefix);
 144         ++outline;
 145         fprintf(code_file, "#define yyerrflag %serrflag\n", symbol_prefix);
 146         ++outline;
 147         fprintf(code_file, "#define yyss %sss\n", symbol_prefix);
 148         ++outline;
 149         fprintf(code_file, "#define yyssp %sssp\n", symbol_prefix);
 150         ++outline;
 151         fprintf(code_file, "#define yyvs %svs\n", symbol_prefix);
 152         ++outline;
 153         fprintf(code_file, "#define yyvsp %svsp\n", symbol_prefix);
 154         ++outline;
 155         fprintf(code_file, "#define yylhs %slhs\n", symbol_prefix);
 156         ++outline;
 157         fprintf(code_file, "#define yylen %slen\n", symbol_prefix);
 158         ++outline;
 159         fprintf(code_file, "#define yydefred %sdefred\n", symbol_prefix);
 160         ++outline;
 161         fprintf(code_file, "#define yydgoto %sdgoto\n", symbol_prefix);
 162         ++outline;
 163         fprintf(code_file, "#define yysindex %ssindex\n", symbol_prefix);
 164         ++outline;
 165         fprintf(code_file, "#define yyrindex %srindex\n", symbol_prefix);
 166         ++outline;
 167         fprintf(code_file, "#define yygindex %sgindex\n", symbol_prefix);
 168         ++outline;
 169         fprintf(code_file, "#define yytable %stable\n", symbol_prefix);
 170         ++outline;
 171         fprintf(code_file, "#define yycheck %scheck\n", symbol_prefix);
 172         ++outline;
 173         fprintf(code_file, "#define yyname %sname\n", symbol_prefix);
 174         ++outline;
 175         fprintf(code_file, "#define yyrule %srule\n", symbol_prefix);
 176         ++outline;
 177         fprintf(code_file, "#define yysslim %ssslim\n", symbol_prefix);
 178         ++outline;
 179         fprintf(code_file, "#define yystacksize %sstacksize\n", symbol_prefix);
 180     }
 181     ++outline;
 182     fprintf(code_file, "#define YYPREFIX \"%s\"\n", symbol_prefix);
 183 }
 184
 185
 186 static void
 187 output_rule_data()
 188 {
 189     int i;
 190     int j;
 191
 192
 193     fprintf(output_file, "const short %slhs[] = {%42d,", symbol_prefix,
 194             symbol_value[start_symbol]);
 195
 196     j = 10;
 197     for (i = 3; i < nrules; i++)
 198     {
 199         if (j >= 10)
 200         {
 201             if (!rflag) ++outline;
 202             putc('\n', output_file);
 203             j = 1;
 204         }
 205         else
 206             ++j;
 207
 208         fprintf(output_file, "%5d,", symbol_value[rlhs[i]]);
 209     }
 210     if (!rflag) outline += 2;
 211     fprintf(output_file, "\n};\n");
 212
 213     fprintf(output_file, "const short %slen[] = {%42d,", symbol_prefix, 2);
 214
 215     j = 10;
 216     for (i = 3; i < nrules; i++)
 217     {
 218         if (j >= 10)
 219         {
 220             if (!rflag) ++outline;
 221             putc('\n', output_file);
 222             j = 1;
 223         }
 224         else
 225           j++;
 226
 227         fprintf(output_file, "%5d,", rrhs[i + 1] - rrhs[i] - 1);
 228     }
 229     if (!rflag) outline += 2;
 230     fprintf(output_file, "\n};\n");
 231 }
 232
 233
 234 static void
 235 output_yydefred()
 236 {
 237     int i, j;
 238
 239     fprintf(output_file, "const short %sdefred[] = {%39d,", symbol_prefix,
 240             (defred[0] ? defred[0] - 2 : 0));
 241
 242     j = 10;
 243     for (i = 1; i < nstates; i++)
 244     {
 245         if (j < 10)
 246             ++j;
 247         else
 248         {
 249             if (!rflag) ++outline;
 250             putc('\n', output_file);
 251             j = 1;
 252         }
 253
 254         fprintf(output_file, "%5d,", (defred[i] ? defred[i] - 2 : 0));
 255     }
 256
 257     if (!rflag) outline += 2;
 258     fprintf(output_file, "\n};\n");
 259 }
 260
 261
 262 static void
 263 output_actions()
 264 {
 265     nvectors = 2*nstates + nvars;
 266
 267     froms = NEW2(nvectors, short *);
 268     tos = NEW2(nvectors, short *);
 269     tally = NEW2(nvectors, short);
 270     width = NEW2(nvectors, short);
 271
 272     token_actions();
 273     FREE(lookaheads);
 274     FREE(LA);
 275     FREE(LAruleno);
 276     FREE(accessing_symbol);
 277
 278     goto_actions();
 279     FREE(goto_map + ntokens);
 280     FREE(from_state);
 281     FREE(to_state);
 282
 283     sort_actions();
 284     pack_table();
 285     output_base();
 286     output_table();
 287     output_check();
 288 }
 289
 290
 291 static void
 292 token_actions()
 293 {
 294     int i, j;
 295     int shiftcount, reducecount;
 296     int max, min;
 297     short *actionrow, *r, *s;
 298     action *p;
 299
 300     actionrow = NEW2(2*ntokens, short);
 301     for (i = 0; i < nstates; ++i)
 302     {
 303         if (parser[i])
 304         {
 305             for (j = 0; j < 2*ntokens; ++j)
 306             actionrow[j] = 0;
 307
 308             shiftcount = 0;
 309             reducecount = 0;
 310             for (p = parser[i]; p; p = p->next)
 311             {
 312                 if (p->suppressed == 0)
 313                 {
 314                     if (p->action_code == SHIFT)
 315                     {
 316                         ++shiftcount;
 317                         actionrow[p->symbol] = p->number;
 318                     }
 319                     else if (p->action_code == REDUCE && p->number != defred[i])
 320                     {
 321                         ++reducecount;
 322                         actionrow[p->symbol + ntokens] = p->number;
 323                     }
 324                 }
 325             }
 326
 327             tally[i] = shiftcount;
 328             tally[nstates+i] = reducecount;
 329             width[i] = 0;
 330             width[nstates+i] = 0;
 331             if (shiftcount > 0)
 332             {
 333                 froms[i] = r = NEW2(shiftcount, short);
 334                 tos[i] = s = NEW2(shiftcount, short);
 335                 min = SHRT_MAX;
 336                 max = 0;
 337                 for (j = 0; j < ntokens; ++j)
 338                 {
 339                     if (actionrow[j])
 340                     {
 341                         if (min > symbol_value[j])
 342                             min = symbol_value[j];
 343                         if (max < symbol_value[j])
 344                             max = symbol_value[j];
 345                         *r++ = symbol_value[j];
 346                         *s++ = actionrow[j];
 347                     }
 348                 }
 349                 width[i] = max - min + 1;
 350             }
 351             if (reducecount > 0)
 352             {
 353                 froms[nstates+i] = r = NEW2(reducecount, short);
 354                 tos[nstates+i] = s = NEW2(reducecount, short);
 355                 min = SHRT_MAX;
 356                 max = 0;
 357                 for (j = 0; j < ntokens; ++j)
 358                 {
 359                     if (actionrow[ntokens+j])
 360                     {
 361                         if (min > symbol_value[j])
 362                             min = symbol_value[j];
 363                         if (max < symbol_value[j])
 364                             max = symbol_value[j];
 365                         *r++ = symbol_value[j];
 366                         *s++ = actionrow[ntokens+j] - 2;
 367                     }
 368                 }
 369                 width[nstates+i] = max - min + 1;
 370             }
 371         }
 372     }
 373     FREE(actionrow);
 374 }
 375
 376 static void
 377 goto_actions()
 378 {
 379     int i, j, k;
 380
 381     state_count = NEW2(nstates, short);
 382
 383     k = default_goto(start_symbol + 1);
 384     fprintf(output_file, "const short %sdgoto[] = {%40d,", symbol_prefix, k);
 385     save_column(start_symbol + 1, k);
 386
 387     j = 10;
 388     for (i = start_symbol + 2; i < nsyms; i++)
 389     {
 390         if (j >= 10)
 391         {
 392             if (!rflag) ++outline;
 393             putc('\n', output_file);
 394             j = 1;
 395         }
 396         else
 397             ++j;
 398
 399         k = default_goto(i);
 400         fprintf(output_file, "%5d,", k);
 401         save_column(i, k);
 402     }
 403
 404     if (!rflag) outline += 2;
 405     fprintf(output_file, "\n};\n");
 406     FREE(state_count);
 407 }
 408
 409 static int
 410 default_goto(symbol)
 411 int symbol;
 412 {
 413     int i;
 414     int m;
 415     int n;
 416     int default_state;
 417     int max;
 418
 419     m = goto_map[symbol];
 420     n = goto_map[symbol + 1];
 421
 422     if (m == n) return (0);
 423
 424     for (i = 0; i < nstates; i++)
 425         state_count[i] = 0;
 426
 427     for (i = m; i < n; i++)
 428         state_count[to_state[i]]++;
 429
 430     max = 0;
 431     default_state = 0;
 432     for (i = 0; i < nstates; i++)
 433     {
 434         if (state_count[i] > max)
 435         {
 436             max = state_count[i];
 437             default_state = i;
 438         }
 439     }
 440
 441     return (default_state);
 442 }
 443
 444
 445
 446 static void
 447 save_column(symbol, default_state)
 448 int symbol;
 449 int default_state;
 450 {
 451     int i;
 452     int m;
 453     int n;
 454     short *sp;
 455     short *sp1;
 456     short *sp2;
 457     int count;
 458     int symno;
 459
 460     m = goto_map[symbol];
 461     n = goto_map[symbol + 1];
 462
 463     count = 0;
 464     for (i = m; i < n; i++)
 465     {
 466         if (to_state[i] != default_state)
 467             ++count;
 468     }
 469     if (count == 0) return;
 470
 471     symno = symbol_value[symbol] + 2*nstates;
 472
 473     froms[symno] = sp1 = sp = NEW2(count, short);
 474     tos[symno] = sp2 = NEW2(count, short);
 475
 476     for (i = m; i < n; i++)
 477     {
 478         if (to_state[i] != default_state)
 479         {
 480             *sp1++ = from_state[i];
 481             *sp2++ = to_state[i];
 482         }
 483     }
 484
 485     tally[symno] = count;
 486     width[symno] = sp1[-1] - sp[0] + 1;
 487 }
 488
 489 static void
 490 sort_actions()
 491 {
 492   int i;
 493   int j;
 494   int k;
 495   int t;
 496   int w;
 497
 498   order = NEW2(nvectors, short);
 499   nentries = 0;
 500
 501   for (i = 0; i < nvectors; i++)
 502     {
 503       if (tally[i] > 0)
 504         {
 505           t = tally[i];
 506           w = width[i];
 507           j = nentries - 1;
 508
 509           while (j >= 0 && (width[order[j]] < w))
 510             j--;
 511
 512           while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
 513             j--;
 514
 515           for (k = nentries - 1; k > j; k--)
 516             order[k + 1] = order[k];
 517
 518           order[j + 1] = i;
 519           nentries++;
 520         }
 521     }
 522 }
 523
 524
 525 static void
 526 pack_table()
 527 {
 528     int i;
 529     int place;
 530     int state;
 531
 532     base = NEW2(nvectors, short);
 533     pos = NEW2(nentries, short);
 534
 535     maxtable = 10000;
 536     table = NEW2(maxtable, short);
 537     check = NEW2(maxtable, short);
 538
 539     lowzero = 0;
 540     high = 0;
 541
 542     for (i = 0; i < maxtable; i++)
 543         check[i] = -1;
 544
 545     for (i = 0; i < nentries; i++)
 546     {
 547         state = matching_vector(i);
 548
 549         if (state < 0)
 550             place = pack_vector(i);
 551         else
 552             place = base[state];
 553
 554         pos[i] = place;
 555         base[order[i]] = place;
 556     }
 557
 558     for (i = 0; i < nvectors; i++)
 559     {
 560         if (froms[i])
 561             FREE(froms[i]);
 562         if (tos[i])
 563             FREE(tos[i]);
 564     }
 565
 566     FREE(froms);
 567     FREE(tos);
 568     FREE(pos);
 569 }
 570
 571
 572 /*  The function matching_vector determines if the vector specified by  */
 573 /*  the input parameter matches a previously considered vector.  The    */
 574 /*  test at the start of the function checks if the vector represents   */
 575 /*  a row of shifts over terminal symbols or a row of reductions, or a  */
 576 /*  column of shifts over a nonterminal symbol.  Berkeley Yacc does not */
 577 /*  check if a column of shifts over a nonterminal symbols matches a    */
 578 /*  previously considered vector.  Because of the nature of LR parsing  */
 579 /*  tables, no two columns can match.  Therefore, the only possible     */
 580 /*  match would be between a row and a column.  Such matches are        */
 581 /*  unlikely.  Therefore, to save time, no attempt is made to see if a  */
 582 /*  column matches a previously considered vector.                      */
 583 /*                                                                      */
 584 /*  Matching_vector is poorly designed.  The test could easily be made  */
 585 /*  faster.  Also, it depends on the vectors being in a specific        */
 586 /*  order.                                                              */
 587
 588 static int
 589 matching_vector(vector)
 590 int vector;
 591 {
 592     int i;
 593     int j;
 594     int k;
 595     int t;
 596     int w;
 597     int match;
 598     int prev;
 599
 600     i = order[vector];
 601     if (i >= 2*nstates)
 602         return (-1);
 603
 604     t = tally[i];
 605     w = width[i];
 606
 607     for (prev = vector - 1; prev >= 0; prev--)
 608     {
 609         j = order[prev];
 610         if (width[j] != w || tally[j] != t)
 611             return (-1);
 612
 613         match = 1;
 614         for (k = 0; match && k < t; k++)
 615         {
 616             if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
 617                 match = 0;
 618         }
 619
 620         if (match)
 621             return (j);
 622     }
 623
 624     return (-1);
 625 }
 626
 627
 628
 629 static int
 630 pack_vector(vector)
 631 int vector;
 632 {
 633     int i, j, k;
 634     int t;
 635     int loc;
 636     int ok;
 637     short *from;
 638     short *to;
 639
 640     loc = 0;
 641     i = order[vector];
 642     t = tally[i];
 643     assert(t);
 644
 645     from = froms[i];
 646     to = tos[i];
 647
 648     j = lowzero - from[0];
 649     for (k = 1; k < t; ++k)
 650         if (lowzero - from[k] > j)
 651             j = lowzero - from[k];
 652     for (;; ++j)
 653     {
 654         if (j == 0)
 655             continue;
 656         ok = 1;
 657         for (k = 0; ok && k < t; k++)
 658         {
 659             loc = j + from[k];
 660             if (loc >= maxtable)
 661             {
 662                 if (loc >= MAXTABLE)
 663                     fatal("maximum table size exceeded");
 664                 maxtable = increase_maxtable(loc);
 665             }
 666
 667             if (check[loc] != -1)
 668                 ok = 0;
 669         }
 670         for (k = 0; ok && k < vector; k++)
 671         {
 672             if (pos[k] == j)
 673                 ok = 0;
 674         }
 675         if (ok)
 676         {
 677             for (k = 0; k < t; k++)
 678             {
 679                 loc = j + from[k];
 680                 table[loc] = to[k];
 681                 check[loc] = from[k];
 682                 if (loc > high) high = loc;
 683             }
 684
 685             while (check[lowzero] != -1)
 686             {
 687                 if (lowzero >= maxtable)
 688                 {
 689                     if (lowzero >= MAXTABLE)
 690                     {
 691                       fatal("maximum table size exceeded in check\n");
 692                     }
 693
 694                     maxtable = increase_maxtable(loc);
 695                 }
 696
 697                 ++lowzero;
 698             }
 699
 700             return (j);
 701         }
 702     }
 703 }
 704
 705
 706
 707 static void
 708 output_base()
 709 {
 710     int i, j;
 711
 712     fprintf(output_file, "const short %ssindex[] = {%39d,", symbol_prefix,
 713             base[0]);
 714
 715     j = 10;
 716     for (i = 1; i < nstates; i++)
 717     {
 718         if (j >= 10)
 719         {
 720             if (!rflag) ++outline;
 721             putc('\n', output_file);
 722             j = 1;
 723         }
 724         else
 725             ++j;
 726
 727         fprintf(output_file, "%5d,", base[i]);
 728     }
 729
 730     if (!rflag) outline += 2;
 731     fprintf(output_file, "\n};\nconst short %srindex[] = {%39d,", symbol_prefix,
 732             base[nstates]);
 733
 734     j = 10;
 735     for (i = nstates + 1; i < 2*nstates; i++)
 736     {
 737         if (j >= 10)
 738         {
 739             if (!rflag) ++outline;
 740             putc('\n', output_file);
 741             j = 1;
 742         }
 743         else
 744             ++j;
 745
 746         fprintf(output_file, "%5d,", base[i]);
 747     }
 748
 749     if (!rflag) outline += 2;
 750     fprintf(output_file, "\n};\nconst short %sgindex[] = {%39d,", symbol_prefix,
 751             base[2*nstates]);
 752
 753     j = 10;
 754     for (i = 2*nstates + 1; i < nvectors - 1; i++)
 755     {
 756         if (j >= 10)
 757         {
 758             if (!rflag) ++outline;
 759             putc('\n', output_file);
 760             j = 1;
 761         }
 762         else
 763             ++j;
 764
 765         fprintf(output_file, "%5d,", base[i]);
 766     }
 767
 768     if (!rflag) outline += 2;
 769     fprintf(output_file, "\n};\n");
 770     FREE(base);
 771 }
 772
 773
 774
 775 static void
 776 output_table()
 777 {
 778     int i;
 779     int j;
 780
 781     ++outline;
 782     fprintf(code_file, "#define YYTABLESIZE %d\n", high);
 783     fprintf(output_file, "const short %stable[] = {%40d,", symbol_prefix,
 784             table[0]);
 785
 786     j = 10;
 787     for (i = 1; i <= high; i++)
 788     {
 789         if (j >= 10)
 790         {
 791             if (!rflag) ++outline;
 792             putc('\n', output_file);
 793             j = 1;
 794         }
 795         else
 796             ++j;
 797
 798         fprintf(output_file, "%5d,", table[i]);
 799     }
 800
 801     if (!rflag) outline += 2;
 802     fprintf(output_file, "\n};\n");
 803     FREE(table);
 804 }
 805
 806
 807
 808 static void
 809 output_check()
 810 {
 811     int i;
 812     int j;
 813
 814     fprintf(output_file, "const short %scheck[] = {%40d,", symbol_prefix,
 815             check[0]);
 816
 817     j = 10;
 818     for (i = 1; i <= high; i++)
 819     {
 820         if (j >= 10)
 821         {
 822             if (!rflag) ++outline;
 823             putc('\n', output_file);
 824             j = 1;
 825         }
 826         else
 827             ++j;
 828
 829         fprintf(output_file, "%5d,", check[i]);
 830     }
 831
 832     if (!rflag) outline += 2;
 833     fprintf(output_file, "\n};\n");
 834     FREE(check);
 835 }
 836
 837
 838 static int
 839 is_C_identifier(name)
 840 char *name;
 841 {
 842     char *s;
 843     int c;
 844
 845     s = name;
 846     c = *s;
 847     if (c == '"')
 848     {
 849         c = *++s;
 850         if (!isalpha(c) && c != '_' && c != '$')
 851             return (0);
 852         while ((c = *++s) != '"')
 853         {
 854             if (!isalnum(c) && c != '_' && c != '$')
 855                 return (0);
 856         }
 857         return (1);
 858     }
 859
 860     if (!isalpha(c) && c != '_' && c != '$')
 861         return (0);
 862     while ((c = *++s))
 863     {
 864         if (!isalnum(c) && c != '_' && c != '$')
 865             return (0);
 866     }
 867     return (1);
 868 }
 869
 870
 871 static void
 872 output_defines()
 873 {
 874     int c, i;
 875     char *s;
 876
 877     ++outline;
 878     fprintf(code_file, "#define YYERRCODE %d\n", symbol_value[1]);
 879
 880     if(dflag)
 881     {
 882         fprintf(defines_file, "#ifndef YYERRCODE\n");
 883         fprintf(defines_file, "#define YYERRCODE %d\n", symbol_value[1]);
 884         fprintf(defines_file, "#endif\n\n");
 885     }
 886     for (i = 2; i < ntokens; ++i)
 887     {
 888         s = symbol_name[i];
 889         if (is_C_identifier(s))
 890         {
 891             fprintf(code_file, "#define ");
 892             if (dflag) fprintf(defines_file, "#define ");
 893             c = *s;
 894             if (c == '"')
 895             {
 896                 while ((c = *++s) != '"')
 897                 {
 898                     putc(c, code_file);
 899                     if (dflag) putc(c, defines_file);
 900                 }
 901             }
 902             else
 903             {
 904                 do
 905                 {
 906                     putc(c, code_file);
 907                     if (dflag) putc(c, defines_file);
 908                 }
 909                 while ((c = *++s));
 910             }
 911             ++outline;
 912             fprintf(code_file, " %d\n", symbol_value[i]);
 913             if (dflag) fprintf(defines_file, " %d\n", symbol_value[i]);
 914         }
 915     }
 916
 917     if (dflag && unionized)
 918     {
 919         fclose(union_file);
 920         union_file = fopen(union_file_name, "r");
 921         if (union_file == NULL) open_error(union_file_name);
 922         while ((c = getc(union_file)) != EOF)
 923             putc(c, defines_file);
 924         fprintf(defines_file, " YYSTYPE;\nextern YYSTYPE %slval;\n",
 925                 symbol_prefix);
 926     }
 927 }
 928
 929
 930 static void
 931 output_stored_text()
 932 {
 933     int c;
 934     FILE *in, *out;
 935
 936     fclose(text_file);
 937     text_file = fopen(text_file_name, "r");
 938     if (text_file == NULL)
 939         open_error(text_file_name);
 940     in = text_file;
 941     if ((c = getc(in)) == EOF)
 942         return;
 943     out = code_file;
 944     if (c ==  '\n')
 945         ++outline;
 946     putc(c, out);
 947     while ((c = getc(in)) != EOF)
 948     {
 949         if (c == '\n')
 950             ++outline;
 951         putc(c, out);
 952     }
 953     if (!lflag)
 954         fprintf(out, line_format, ++outline + 1, code_file_name);
 955 }
 956
 957
 958 static void
 959 output_debug()
 960 {
 961     int i, j, k, max;
 962     char **symnam, *s;
 963     static char eof[] = "end-of-file";
 964
 965     ++outline;
 966     fprintf(code_file, "#define YYFINAL %d\n", final_state);
 967     outline += 3;
 968     fprintf(code_file, "#ifndef YYDEBUG\n#define YYDEBUG %d\n#endif\n",
 969             tflag);
 970     if (rflag)
 971         fprintf(output_file, "#ifndef YYDEBUG\n#define YYDEBUG %d\n#endif\n",
 972                 tflag);
 973
 974     max = 0;
 975     for (i = 2; i < ntokens; ++i)
 976         if (symbol_value[i] > max)
 977             max = symbol_value[i];
 978     ++outline;
 979     fprintf(code_file, "#define YYMAXTOKEN %d\n", max);
 980
 981     symnam = (char **) MALLOC((max+1)*sizeof(char *));
 982     if (symnam == 0) no_space();
 983
 984     /* Note that it is  not necessary to initialize the element         */
 985     /* symnam[max].                                                     */
 986     for (i = 0; i < max; ++i)
 987         symnam[i] = 0;
 988     for (i = ntokens - 1; i >= 2; --i)
 989         symnam[symbol_value[i]] = symbol_name[i];
 990     symnam[0] = eof;
 991
 992     if (!rflag) ++outline;
 993     fprintf(output_file, "#if YYDEBUG\n");
 994     fprintf(output_file, "const char * const %sname[] = {", symbol_prefix);
 995     j = 80;
 996     for (i = 0; i <= max; ++i)
 997     {
 998         if ((s = symnam[i]))
 999         {
1000             if (s[0] == '"')
1001             {
1002                 k = 7;
1003                 while (*++s != '"')
1004                 {
1005                     ++k;
1006                     if (*s == '\\')
1007                     {
1008                         k += 2;
1009                         if (*++s == '\\')
1010                             ++k;
1011                     }
1012                 }
1013                 j += k;
1014                 if (j > 80)
1015                 {
1016                     if (!rflag) ++outline;
1017                     putc('\n', output_file);
1018                     j = k;
1019                 }
1020                 fprintf(output_file, "\"\\\"");
1021                 s = symnam[i];
1022                 while (*++s != '"')
1023                 {
1024                     if (*s == '\\')
1025                     {
1026                         fprintf(output_file, "\\\\");
1027                         if (*++s == '\\')
1028                             fprintf(output_file, "\\\\");
1029                         else
1030                             putc(*s, output_file);
1031                     }
1032                     else
1033                         putc(*s, output_file);
1034                 }
1035                 fprintf(output_file, "\\\"\",");
1036             }
1037             else if (s[0] == '\'')
1038             {
1039                 if (s[1] == '"')
1040                 {
1041                     j += 7;
1042                     if (j > 80)
1043                     {
1044                         if (!rflag) ++outline;
1045                         putc('\n', output_file);
1046                         j = 7;
1047                     }
1048                     fprintf(output_file, "\"'\\\"'\",");
1049                 }
1050                 else
1051                 {
1052                     k = 5;
1053                     while (*++s != '\'')
1054                     {
1055                         ++k;
1056                         if (*s == '\\')
1057                         {
1058                             k += 2;
1059                             if (*++s == '\\')
1060                                 ++k;
1061                         }
1062                     }
1063                     j += k;
1064                     if (j > 80)
1065                     {
1066                         if (!rflag) ++outline;
1067                         putc('\n', output_file);
1068                         j = k;
1069                     }
1070                     fprintf(output_file, "\"'");
1071                     s = symnam[i];
1072                     while (*++s != '\'')
1073                     {
1074                         if (*s == '\\')
1075                         {
1076                             fprintf(output_file, "\\\\");
1077                             if (*++s == '\\')
1078                                 fprintf(output_file, "\\\\");
1079                             else
1080                                 putc(*s, output_file);
1081                         }
1082                         else
1083                             putc(*s, output_file);
1084                     }
1085                     fprintf(output_file, "'\",");
1086                 }
1087             }
1088             else
1089             {
1090                 k = strlen(s) + 3;
1091                 j += k;
1092                 if (j > 80)
1093                 {
1094                     if (!rflag) ++outline;
1095                     putc('\n', output_file);
1096                     j = k;
1097                 }
1098                 putc('"', output_file);
1099                 do { putc(*s, output_file); } while (*++s);
1100                 fprintf(output_file, "\",");
1101             }
1102         }
1103         else
1104         {
1105             j += 2;
1106             if (j > 80)
1107             {
1108                 if (!rflag) ++outline;
1109                 putc('\n', output_file);
1110                 j = 2;
1111             }
1112             fprintf(output_file, "0,");
1113         }
1114     }
1115     if (!rflag) outline += 2;
1116     fprintf(output_file, "\n};\n");
1117     FREE(symnam);
1118
1119     if (!rflag) ++outline;
1120     fprintf(output_file, "const char * const %srule[] = {\n", symbol_prefix);
1121     for (i = 2; i < nrules; ++i)
1122     {
1123         fprintf(output_file, "\"%s :", symbol_name[rlhs[i]]);
1124         for (j = rrhs[i]; ritem[j] > 0; ++j)
1125         {
1126             s = symbol_name[ritem[j]];
1127             if (s[0] == '"')
1128             {
1129                 fprintf(output_file, " \\\"");
1130                 while (*++s != '"')
1131                 {
1132                     if (*s == '\\')
1133                     {
1134                         if (s[1] == '\\')
1135                             fprintf(output_file, "\\\\\\\\");
1136                         else
1137                             fprintf(output_file, "\\\\%c", s[1]);
1138                         ++s;
1139                     }
1140                     else
1141                         putc(*s, output_file);
1142                 }
1143                 fprintf(output_file, "\\\"");
1144             }
1145             else if (s[0] == '\'')
1146             {
1147                 if (s[1] == '"')
1148                     fprintf(output_file, " '\\\"'");
1149                 else if (s[1] == '\\')
1150                 {
1151                     if (s[2] == '\\')
1152                         fprintf(output_file, " '\\\\\\\\");
1153                     else
1154                         fprintf(output_file, " '\\\\%c", s[2]);
1155                     s += 2;
1156                     while (*++s != '\'')
1157                         putc(*s, output_file);
1158                     putc('\'', output_file);
1159                 }
1160                 else
1161                     fprintf(output_file, " '%c'", s[1]);
1162             }
1163             else
1164                 fprintf(output_file, " %s", s);
1165         }
1166         if (!rflag) ++outline;
1167         fprintf(output_file, "\",\n");
1168     }
1169
1170     if (!rflag) outline += 2;
1171     fprintf(output_file, "};\n#endif\n");
1172 }
1173
1174
1175 static void
1176 output_stype()
1177 {
1178     if (!unionized && ntags == 0)
1179     {
1180         outline += 3;
1181         fprintf(code_file, "#ifndef YYSTYPE\ntypedef int YYSTYPE;\n#endif\n");
1182     }
1183 }
1184
1185
1186 static void
1187 output_trailing_text()
1188 {
1189     int c, last;
1190     FILE *in, *out;
1191
1192     if (line == 0)
1193         return;
1194
1195     in = input_file;
1196     out = code_file;
1197     c = *cptr;
1198     if (c == '\n')
1199     {
1200         ++lineno;
1201         if ((c = getc(in)) == EOF)
1202             return;
1203         if (!lflag)
1204         {
1205             ++outline;
1206             fprintf(out, line_format, lineno, input_file_name);
1207         }
1208         if (c == '\n')
1209             ++outline;
1210         putc(c, out);
1211         last = c;
1212     }
1213     else
1214     {
1215         if (!lflag)
1216         {
1217             ++outline;
1218             fprintf(out, line_format, lineno, input_file_name);
1219         }
1220         do { putc(c, out); } while ((c = *++cptr) != '\n');
1221         ++outline;
1222         putc('\n', out);
1223         last = '\n';
1224     }
1225
1226     while ((c = getc(in)) != EOF)
1227     {
1228         if (c == '\n')
1229             ++outline;
1230         putc(c, out);
1231         last = c;
1232     }
1233
1234     if (last != '\n')
1235     {
1236         ++outline;
1237         putc('\n', out);
1238     }
1239     if (!lflag)
1240         fprintf(out, line_format, ++outline + 1, code_file_name);
1241 }
1242
1243
1244 static void
1245 output_semantic_actions()
1246 {
1247     int c, last;
1248     FILE *out;
1249
1250     fclose(action_file);
1251     action_file = fopen(action_file_name, "r");
1252     if (action_file == NULL)
1253         open_error(action_file_name);
1254
1255     if ((c = getc(action_file)) == EOF)
1256         return;
1257
1258     out = code_file;
1259     last = c;
1260     if (c == '\n')
1261         ++outline;
1262     putc(c, out);
1263     while ((c = getc(action_file)) != EOF)
1264     {
1265         if (c == '\n')
1266             ++outline;
1267         putc(c, out);
1268         last = c;
1269     }
1270
1271     if (last != '\n')
1272     {
1273         ++outline;
1274         putc('\n', out);
1275     }
1276
1277     if (!lflag)
1278         fprintf(out, line_format, ++outline + 1, code_file_name);
1279 }
1280
1281
1282 static void
1283 free_itemsets()
1284 {
1285     core *cp, *next;
1286
1287     FREE(state_table);
1288     for (cp = first_state; cp; cp = next)
1289     {
1290         next = cp->next;
1291         FREE(cp);
1292     }
1293 }
1294
1295
1296 static void
1297 free_shifts()
1298 {
1299     shifts *sp, *next;
1300
1301     FREE(shift_table);
1302     for (sp = first_shift; sp; sp = next)
1303     {
1304         next = sp->next;
1305         FREE(sp);
1306     }
1307 }
1308
1309
1310
1311 static void
1312 free_reductions()
1313 {
1314     reductions *rp, *next;
1315
1316     FREE(reduction_table);
1317     for (rp = first_reduction; rp; rp = next)
1318     {
1319         next = rp->next;
1320         FREE(rp);
1321     }
1322 }
1323
1324 /*
1325  * increase_maxtable
1326  *
1327  * inputs       - loc location in table
1328  * output       - size increased to
1329  * side effects - table is increase by at least 200 short words
1330  */
1331
1332 static int
1333 increase_maxtable(int loc)
1334 {
1335     int newmax;
1336     int l;
1337
1338     newmax = maxtable;
1339
1340     do { newmax += 200; } while (newmax <= loc);
1341     table = (short *) REALLOC(table, newmax*sizeof(short));
1342         if (table == 0) no_space();
1343         check = (short *) REALLOC(check, newmax*sizeof(short));
1344         if (check == 0) no_space();
1345         for (l  = maxtable; l < newmax; ++l)
1346         {
1347             table[l] = 0;
1348             check[l] = -1;
1349         }
1350
1351     return(newmax);
1352 }