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