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