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.2 2003/06/17 04:29:34 dillon 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 __P((int));
  47 static void free_itemsets __P((void));
  48 static void free_reductions __P((void));
  49 static void free_shifts __P((void));
  50 static void goto_actions __P((void));
  51 static int is_C_identifier __P((char *));
  52 static int matching_vector __P((int));
  53 static void output_actions __P((void));
  54 static void output_base __P((void));
  55 static void output_check __P((void));
  56 static void output_debug __P((void));
  57 static void output_defines __P((void));
  58 static void output_prefix __P((void));
  59 static void output_rule_data __P((void));
  60 static void output_semantic_actions __P((void));
  61 static void output_stored_text __P((void));
  62 static void output_stype __P((void));
  63 static void output_table __P((void));
  64 static void output_trailing_text __P((void));
  65 static void output_yydefred __P((void));
  66 static void pack_table __P((void));
  67 static int pack_vector __P((int));
  68 static void save_column __P((int, int));
  69 static void sort_actions __P((void));
  70 static void token_actions __P((void));
  71 static int increase_maxtable __P((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()
  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()
 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()
 182 {
 183     register int i;
 184     register 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()
 230 {
 231     register 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()
 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()
 287 {
 288     register int i, j;
 289     register int shiftcount, reducecount;
 290     register int max, min;
 291     register short *actionrow, *r, *s;
 292     register 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()
 372 {
 373     register 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(symbol)
 405 int symbol;
 406 {
 407     register int i;
 408     register int m;
 409     register int n;
 410     register int default_state;
 411     register int max;
 412
 413     m = goto_map[symbol];
 414     n = goto_map[symbol + 1];
 415
 416     if (m == n) return (0);
 417
 418     for (i = 0; i < nstates; i++)
 419         state_count[i] = 0;
 420
 421     for (i = m; i < n; i++)
 422         state_count[to_state[i]]++;
 423
 424     max = 0;
 425     default_state = 0;
 426     for (i = 0; i < nstates; i++)
 427     {
 428         if (state_count[i] > max)
 429         {
 430             max = state_count[i];
 431             default_state = i;
 432         }
 433     }
 434
 435     return (default_state);
 436 }
 437
 438
 439
 440 static void
 441 save_column(symbol, default_state)
 442 int symbol;
 443 int default_state;
 444 {
 445     register int i;
 446     register int m;
 447     register int n;
 448     register short *sp;
 449     register short *sp1;
 450     register short *sp2;
 451     register int count;
 452     register int symno;
 453
 454     m = goto_map[symbol];
 455     n = goto_map[symbol + 1];
 456
 457     count = 0;
 458     for (i = m; i < n; i++)
 459     {
 460         if (to_state[i] != default_state)
 461             ++count;
 462     }
 463     if (count == 0) return;
 464
 465     symno = symbol_value[symbol] + 2*nstates;
 466
 467     froms[symno] = sp1 = sp = NEW2(count, short);
 468     tos[symno] = sp2 = NEW2(count, short);
 469
 470     for (i = m; i < n; i++)
 471     {
 472         if (to_state[i] != default_state)
 473         {
 474             *sp1++ = from_state[i];
 475             *sp2++ = to_state[i];
 476         }
 477     }
 478
 479     tally[symno] = count;
 480     width[symno] = sp1[-1] - sp[0] + 1;
 481 }
 482
 483 static void
 484 sort_actions()
 485 {
 486   register int i;
 487   register int j;
 488   register int k;
 489   register int t;
 490   register int w;
 491
 492   order = NEW2(nvectors, short);
 493   nentries = 0;
 494
 495   for (i = 0; i < nvectors; i++)
 496     {
 497       if (tally[i] > 0)
 498         {
 499           t = tally[i];
 500           w = width[i];
 501           j = nentries - 1;
 502
 503           while (j >= 0 && (width[order[j]] < w))
 504             j--;
 505
 506           while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
 507             j--;
 508
 509           for (k = nentries - 1; k > j; k--)
 510             order[k + 1] = order[k];
 511
 512           order[j + 1] = i;
 513           nentries++;
 514         }
 515     }
 516 }
 517
 518
 519 static void
 520 pack_table()
 521 {
 522     register int i;
 523     register int place;
 524     register int state;
 525
 526     base = NEW2(nvectors, short);
 527     pos = NEW2(nentries, short);
 528
 529     maxtable = 10000;
 530     table = NEW2(maxtable, short);
 531     check = NEW2(maxtable, short);
 532
 533     lowzero = 0;
 534     high = 0;
 535
 536     for (i = 0; i < maxtable; i++)
 537         check[i] = -1;
 538
 539     for (i = 0; i < nentries; i++)
 540     {
 541         state = matching_vector(i);
 542
 543         if (state < 0)
 544             place = pack_vector(i);
 545         else
 546             place = base[state];
 547
 548         pos[i] = place;
 549         base[order[i]] = place;
 550     }
 551
 552     for (i = 0; i < nvectors; i++)
 553     {
 554         if (froms[i])
 555             FREE(froms[i]);
 556         if (tos[i])
 557             FREE(tos[i]);
 558     }
 559
 560     FREE(froms);
 561     FREE(tos);
 562     FREE(pos);
 563 }
 564
 565
 566 /*  The function matching_vector determines if the vector specified by  */
 567 /*  the input parameter matches a previously considered vector.  The    */
 568 /*  test at the start of the function checks if the vector represents   */
 569 /*  a row of shifts over terminal symbols or a row of reductions, or a  */
 570 /*  column of shifts over a nonterminal symbol.  Berkeley Yacc does not */
 571 /*  check if a column of shifts over a nonterminal symbols matches a    */
 572 /*  previously considered vector.  Because of the nature of LR parsing  */
 573 /*  tables, no two columns can match.  Therefore, the only possible     */
 574 /*  match would be between a row and a column.  Such matches are        */
 575 /*  unlikely.  Therefore, to save time, no attempt is made to see if a  */
 576 /*  column matches a previously considered vector.                      */
 577 /*                                                                      */
 578 /*  Matching_vector is poorly designed.  The test could easily be made  */
 579 /*  faster.  Also, it depends on the vectors being in a specific        */
 580 /*  order.                                                              */
 581
 582 static int
 583 matching_vector(vector)
 584 int vector;
 585 {
 586     register int i;
 587     register int j;
 588     register int k;
 589     register int t;
 590     register int w;
 591     register int match;
 592     register int prev;
 593
 594     i = order[vector];
 595     if (i >= 2*nstates)
 596         return (-1);
 597
 598     t = tally[i];
 599     w = width[i];
 600
 601     for (prev = vector - 1; prev >= 0; prev--)
 602     {
 603         j = order[prev];
 604         if (width[j] != w || tally[j] != t)
 605             return (-1);
 606
 607         match = 1;
 608         for (k = 0; match && k < t; k++)
 609         {
 610             if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
 611                 match = 0;
 612         }
 613
 614         if (match)
 615             return (j);
 616     }
 617
 618     return (-1);
 619 }
 620
 621
 622
 623 static int
 624 pack_vector(vector)
 625 int vector;
 626 {
 627     register int i, j, k, l;
 628     register int t;
 629     register int loc;
 630     register int ok;
 631     register short *from;
 632     register short *to;
 633
 634     i = order[vector];
 635     t = tally[i];
 636     assert(t);
 637
 638     from = froms[i];
 639     to = tos[i];
 640
 641     j = lowzero - from[0];
 642     for (k = 1; k < t; ++k)
 643         if (lowzero - from[k] > j)
 644             j = lowzero - from[k];
 645     for (;; ++j)
 646     {
 647         if (j == 0)
 648             continue;
 649         ok = 1;
 650         for (k = 0; ok && k < t; k++)
 651         {
 652             loc = j + from[k];
 653             if (loc >= maxtable)
 654             {
 655                 if (loc >= MAXTABLE)
 656                     fatal("maximum table size exceeded");
 657                 maxtable = increase_maxtable(loc);
 658             }
 659
 660             if (check[loc] != -1)
 661                 ok = 0;
 662         }
 663         for (k = 0; ok && k < vector; k++)
 664         {
 665             if (pos[k] == j)
 666                 ok = 0;
 667         }
 668         if (ok)
 669         {
 670             for (k = 0; k < t; k++)
 671             {
 672                 loc = j + from[k];
 673                 table[loc] = to[k];
 674                 check[loc] = from[k];
 675                 if (loc > high) high = loc;
 676             }
 677
 678             while (check[lowzero] != -1)
 679             {
 680                 if (lowzero >= maxtable)
 681                 {
 682                     if (lowzero >= MAXTABLE)
 683                     {
 684                       fatal("maximum table size exceeded in check\n");
 685                     }
 686
 687                     maxtable = increase_maxtable(loc);
 688                 }
 689
 690                 ++lowzero;
 691             }
 692
 693             return (j);
 694         }
 695     }
 696 }
 697
 698
 699
 700 static void
 701 output_base()
 702 {
 703     register int i, j;
 704
 705     fprintf(output_file, "const short %ssindex[] = {%39d,", symbol_prefix,
 706             base[0]);
 707
 708     j = 10;
 709     for (i = 1; i < nstates; i++)
 710     {
 711         if (j >= 10)
 712         {
 713             if (!rflag) ++outline;
 714             putc('\n', output_file);
 715             j = 1;
 716         }
 717         else
 718             ++j;
 719
 720         fprintf(output_file, "%5d,", base[i]);
 721     }
 722
 723     if (!rflag) outline += 2;
 724     fprintf(output_file, "\n};\nconst short %srindex[] = {%39d,", symbol_prefix,
 725             base[nstates]);
 726
 727     j = 10;
 728     for (i = nstates + 1; i < 2*nstates; i++)
 729     {
 730         if (j >= 10)
 731         {
 732             if (!rflag) ++outline;
 733             putc('\n', output_file);
 734             j = 1;
 735         }
 736         else
 737             ++j;
 738
 739         fprintf(output_file, "%5d,", base[i]);
 740     }
 741
 742     if (!rflag) outline += 2;
 743     fprintf(output_file, "\n};\nconst short %sgindex[] = {%39d,", symbol_prefix,
 744             base[2*nstates]);
 745
 746     j = 10;
 747     for (i = 2*nstates + 1; i < nvectors - 1; i++)
 748     {
 749         if (j >= 10)
 750         {
 751             if (!rflag) ++outline;
 752             putc('\n', output_file);
 753             j = 1;
 754         }
 755         else
 756             ++j;
 757
 758         fprintf(output_file, "%5d,", base[i]);
 759     }
 760
 761     if (!rflag) outline += 2;
 762     fprintf(output_file, "\n};\n");
 763     FREE(base);
 764 }
 765
 766
 767
 768 static void
 769 output_table()
 770 {
 771     register int i;
 772     register int j;
 773
 774     ++outline;
 775     fprintf(code_file, "#define YYTABLESIZE %d\n", high);
 776     fprintf(output_file, "const short %stable[] = {%40d,", symbol_prefix,
 777             table[0]);
 778
 779     j = 10;
 780     for (i = 1; i <= high; i++)
 781     {
 782         if (j >= 10)
 783         {
 784             if (!rflag) ++outline;
 785             putc('\n', output_file);
 786             j = 1;
 787         }
 788         else
 789             ++j;
 790
 791         fprintf(output_file, "%5d,", table[i]);
 792     }
 793
 794     if (!rflag) outline += 2;
 795     fprintf(output_file, "\n};\n");
 796     FREE(table);
 797 }
 798
 799
 800
 801 static void
 802 output_check()
 803 {
 804     register int i;
 805     register int j;
 806
 807     fprintf(output_file, "const short %scheck[] = {%40d,", symbol_prefix,
 808             check[0]);
 809
 810     j = 10;
 811     for (i = 1; i <= high; i++)
 812     {
 813         if (j >= 10)
 814         {
 815             if (!rflag) ++outline;
 816             putc('\n', output_file);
 817             j = 1;
 818         }
 819         else
 820             ++j;
 821
 822         fprintf(output_file, "%5d,", check[i]);
 823     }
 824
 825     if (!rflag) outline += 2;
 826     fprintf(output_file, "\n};\n");
 827     FREE(check);
 828 }
 829
 830
 831 static int
 832 is_C_identifier(name)
 833 char *name;
 834 {
 835     register char *s;
 836     register int c;
 837
 838     s = name;
 839     c = *s;
 840     if (c == '"')
 841     {
 842         c = *++s;
 843         if (!isalpha(c) && c != '_' && c != '$')
 844             return (0);
 845         while ((c = *++s) != '"')
 846         {
 847             if (!isalnum(c) && c != '_' && c != '$')
 848                 return (0);
 849         }
 850         return (1);
 851     }
 852
 853     if (!isalpha(c) && c != '_' && c != '$')
 854         return (0);
 855     while ((c = *++s))
 856     {
 857         if (!isalnum(c) && c != '_' && c != '$')
 858             return (0);
 859     }
 860     return (1);
 861 }
 862
 863
 864 static void
 865 output_defines()
 866 {
 867     register int c, i;
 868     register char *s;
 869
 870     ++outline;
 871     fprintf(code_file, "#define YYERRCODE %d\n", symbol_value[1]);
 872
 873     if(dflag)
 874     {
 875         fprintf(defines_file, "#ifndef YYERRCODE\n");
 876         fprintf(defines_file, "#define YYERRCODE %d\n", symbol_value[1]);
 877         fprintf(defines_file, "#endif\n\n");
 878     }
 879     for (i = 2; i < ntokens; ++i)
 880     {
 881         s = symbol_name[i];
 882         if (is_C_identifier(s))
 883         {
 884             fprintf(code_file, "#define ");
 885             if (dflag) fprintf(defines_file, "#define ");
 886             c = *s;
 887             if (c == '"')
 888             {
 889                 while ((c = *++s) != '"')
 890                 {
 891                     putc(c, code_file);
 892                     if (dflag) putc(c, defines_file);
 893                 }
 894             }
 895             else
 896             {
 897                 do
 898                 {
 899                     putc(c, code_file);
 900                     if (dflag) putc(c, defines_file);
 901                 }
 902                 while ((c = *++s));
 903             }
 904             ++outline;
 905             fprintf(code_file, " %d\n", symbol_value[i]);
 906             if (dflag) fprintf(defines_file, " %d\n", symbol_value[i]);
 907         }
 908     }
 909
 910     if (dflag && unionized)
 911     {
 912         fclose(union_file);
 913         union_file = fopen(union_file_name, "r");
 914         if (union_file == NULL) open_error(union_file_name);
 915         while ((c = getc(union_file)) != EOF)
 916             putc(c, defines_file);
 917         fprintf(defines_file, " YYSTYPE;\nextern YYSTYPE %slval;\n",
 918                 symbol_prefix);
 919     }
 920 }
 921
 922
 923 static void
 924 output_stored_text()
 925 {
 926     register int c;
 927     register FILE *in, *out;
 928
 929     fclose(text_file);
 930     text_file = fopen(text_file_name, "r");
 931     if (text_file == NULL)
 932         open_error(text_file_name);
 933     in = text_file;
 934     if ((c = getc(in)) == EOF)
 935         return;
 936     out = code_file;
 937     if (c ==  '\n')
 938         ++outline;
 939     putc(c, out);
 940     while ((c = getc(in)) != EOF)
 941     {
 942         if (c == '\n')
 943             ++outline;
 944         putc(c, out);
 945     }
 946     if (!lflag)
 947         fprintf(out, line_format, ++outline + 1, code_file_name);
 948 }
 949
 950
 951 static void
 952 output_debug()
 953 {
 954     register int i, j, k, max;
 955     char **symnam, *s;
 956
 957     ++outline;
 958     fprintf(code_file, "#define YYFINAL %d\n", final_state);
 959     outline += 3;
 960     fprintf(code_file, "#ifndef YYDEBUG\n#define YYDEBUG %d\n#endif\n",
 961             tflag);
 962     if (rflag)
 963         fprintf(output_file, "#ifndef YYDEBUG\n#define YYDEBUG %d\n#endif\n",
 964                 tflag);
 965
 966     max = 0;
 967     for (i = 2; i < ntokens; ++i)
 968         if (symbol_value[i] > max)
 969             max = symbol_value[i];
 970     ++outline;
 971     fprintf(code_file, "#define YYMAXTOKEN %d\n", max);
 972
 973     symnam = (char **) MALLOC((max+1)*sizeof(char *));
 974     if (symnam == 0) no_space();
 975
 976     /* Note that it is  not necessary to initialize the element         */
 977     /* symnam[max].                                                     */
 978     for (i = 0; i < max; ++i)
 979         symnam[i] = 0;
 980     for (i = ntokens - 1; i >= 2; --i)
 981         symnam[symbol_value[i]] = symbol_name[i];
 982     symnam[0] = "end-of-file";
 983
 984     if (!rflag) ++outline;
 985     fprintf(output_file, "#if YYDEBUG\n");
 986     fprintf(output_file, "const char * const %sname[] = {", symbol_prefix);
 987     j = 80;
 988     for (i = 0; i <= max; ++i)
 989     {
 990         if ((s = symnam[i]))
 991         {
 992             if (s[0] == '"')
 993             {
 994                 k = 7;
 995                 while (*++s != '"')
 996                 {
 997                     ++k;
 998                     if (*s == '\\')
 999                     {
1000                         k += 2;
1001                         if (*++s == '\\')
1002                             ++k;
1003                     }
1004                 }
1005                 j += k;
1006                 if (j > 80)
1007                 {
1008                     if (!rflag) ++outline;
1009                     putc('\n', output_file);
1010                     j = k;
1011                 }
1012                 fprintf(output_file, "\"\\\"");
1013                 s = symnam[i];
1014                 while (*++s != '"')
1015                 {
1016                     if (*s == '\\')
1017                     {
1018                         fprintf(output_file, "\\\\");
1019                         if (*++s == '\\')
1020                             fprintf(output_file, "\\\\");
1021                         else
1022                             putc(*s, output_file);
1023                     }
1024                     else
1025                         putc(*s, output_file);
1026                 }
1027                 fprintf(output_file, "\\\"\",");
1028             }
1029             else if (s[0] == '\'')
1030             {
1031                 if (s[1] == '"')
1032                 {
1033                     j += 7;
1034                     if (j > 80)
1035                     {
1036                         if (!rflag) ++outline;
1037                         putc('\n', output_file);
1038                         j = 7;
1039                     }
1040                     fprintf(output_file, "\"'\\\"'\",");
1041                 }
1042                 else
1043                 {
1044                     k = 5;
1045                     while (*++s != '\'')
1046                     {
1047                         ++k;
1048                         if (*s == '\\')
1049                         {
1050                             k += 2;
1051                             if (*++s == '\\')
1052                                 ++k;
1053                         }
1054                     }
1055                     j += k;
1056                     if (j > 80)
1057                     {
1058                         if (!rflag) ++outline;
1059                         putc('\n', output_file);
1060                         j = k;
1061                     }
1062                     fprintf(output_file, "\"'");
1063                     s = symnam[i];
1064                     while (*++s != '\'')
1065                     {
1066                         if (*s == '\\')
1067                         {
1068                             fprintf(output_file, "\\\\");
1069                             if (*++s == '\\')
1070                                 fprintf(output_file, "\\\\");
1071                             else
1072                                 putc(*s, output_file);
1073                         }
1074                         else
1075                             putc(*s, output_file);
1076                     }
1077                     fprintf(output_file, "'\",");
1078                 }
1079             }
1080             else
1081             {
1082                 k = strlen(s) + 3;
1083                 j += k;
1084                 if (j > 80)
1085                 {
1086                     if (!rflag) ++outline;
1087                     putc('\n', output_file);
1088                     j = k;
1089                 }
1090                 putc('"', output_file);
1091                 do { putc(*s, output_file); } while (*++s);
1092                 fprintf(output_file, "\",");
1093             }
1094         }
1095         else
1096         {
1097             j += 2;
1098             if (j > 80)
1099             {
1100                 if (!rflag) ++outline;
1101                 putc('\n', output_file);
1102                 j = 2;
1103             }
1104             fprintf(output_file, "0,");
1105         }
1106     }
1107     if (!rflag) outline += 2;
1108     fprintf(output_file, "\n};\n");
1109     FREE(symnam);
1110
1111     if (!rflag) ++outline;
1112     fprintf(output_file, "const char * const %srule[] = {\n", symbol_prefix);
1113     for (i = 2; i < nrules; ++i)
1114     {
1115         fprintf(output_file, "\"%s :", symbol_name[rlhs[i]]);
1116         for (j = rrhs[i]; ritem[j] > 0; ++j)
1117         {
1118             s = symbol_name[ritem[j]];
1119             if (s[0] == '"')
1120             {
1121                 fprintf(output_file, " \\\"");
1122                 while (*++s != '"')
1123                 {
1124                     if (*s == '\\')
1125                     {
1126                         if (s[1] == '\\')
1127                             fprintf(output_file, "\\\\\\\\");
1128                         else
1129                             fprintf(output_file, "\\\\%c", s[1]);
1130                         ++s;
1131                     }
1132                     else
1133                         putc(*s, output_file);
1134                 }
1135                 fprintf(output_file, "\\\"");
1136             }
1137             else if (s[0] == '\'')
1138             {
1139                 if (s[1] == '"')
1140                     fprintf(output_file, " '\\\"'");
1141                 else if (s[1] == '\\')
1142                 {
1143                     if (s[2] == '\\')
1144                         fprintf(output_file, " '\\\\\\\\");
1145                     else
1146                         fprintf(output_file, " '\\\\%c", s[2]);
1147                     s += 2;
1148                     while (*++s != '\'')
1149                         putc(*s, output_file);
1150                     putc('\'', output_file);
1151                 }
1152                 else
1153                     fprintf(output_file, " '%c'", s[1]);
1154             }
1155             else
1156                 fprintf(output_file, " %s", s);
1157         }
1158         if (!rflag) ++outline;
1159         fprintf(output_file, "\",\n");
1160     }
1161
1162     if (!rflag) outline += 2;
1163     fprintf(output_file, "};\n#endif\n");
1164 }
1165
1166
1167 static void
1168 output_stype()
1169 {
1170     if (!unionized && ntags == 0)
1171     {
1172         outline += 3;
1173         fprintf(code_file, "#ifndef YYSTYPE\ntypedef int YYSTYPE;\n#endif\n");
1174     }
1175 }
1176
1177
1178 static void
1179 output_trailing_text()
1180 {
1181     register int c, last;
1182     register FILE *in, *out;
1183
1184     if (line == 0)
1185         return;
1186
1187     in = input_file;
1188     out = code_file;
1189     c = *cptr;
1190     if (c == '\n')
1191     {
1192         ++lineno;
1193         if ((c = getc(in)) == EOF)
1194             return;
1195         if (!lflag)
1196         {
1197             ++outline;
1198             fprintf(out, line_format, lineno, input_file_name);
1199         }
1200         if (c == '\n')
1201             ++outline;
1202         putc(c, out);
1203         last = c;
1204     }
1205     else
1206     {
1207         if (!lflag)
1208         {
1209             ++outline;
1210             fprintf(out, line_format, lineno, input_file_name);
1211         }
1212         do { putc(c, out); } while ((c = *++cptr) != '\n');
1213         ++outline;
1214         putc('\n', out);
1215         last = '\n';
1216     }
1217
1218     while ((c = getc(in)) != EOF)
1219     {
1220         if (c == '\n')
1221             ++outline;
1222         putc(c, out);
1223         last = c;
1224     }
1225
1226     if (last != '\n')
1227     {
1228         ++outline;
1229         putc('\n', out);
1230     }
1231     if (!lflag)
1232         fprintf(out, line_format, ++outline + 1, code_file_name);
1233 }
1234
1235
1236 static void
1237 output_semantic_actions()
1238 {
1239     register int c, last;
1240     register FILE *out;
1241
1242     fclose(action_file);
1243     action_file = fopen(action_file_name, "r");
1244     if (action_file == NULL)
1245         open_error(action_file_name);
1246
1247     if ((c = getc(action_file)) == EOF)
1248         return;
1249
1250     out = code_file;
1251     last = c;
1252     if (c == '\n')
1253         ++outline;
1254     putc(c, out);
1255     while ((c = getc(action_file)) != EOF)
1256     {
1257         if (c == '\n')
1258             ++outline;
1259         putc(c, out);
1260         last = c;
1261     }
1262
1263     if (last != '\n')
1264     {
1265         ++outline;
1266         putc('\n', out);
1267     }
1268
1269     if (!lflag)
1270         fprintf(out, line_format, ++outline + 1, code_file_name);
1271 }
1272
1273
1274 static void
1275 free_itemsets()
1276 {
1277     register core *cp, *next;
1278
1279     FREE(state_table);
1280     for (cp = first_state; cp; cp = next)
1281     {
1282         next = cp->next;
1283         FREE(cp);
1284     }
1285 }
1286
1287
1288 static void
1289 free_shifts()
1290 {
1291     register shifts *sp, *next;
1292
1293     FREE(shift_table);
1294     for (sp = first_shift; sp; sp = next)
1295     {
1296         next = sp->next;
1297         FREE(sp);
1298     }
1299 }
1300
1301
1302
1303 static void
1304 free_reductions()
1305 {
1306     register reductions *rp, *next;
1307
1308     FREE(reduction_table);
1309     for (rp = first_reduction; rp; rp = next)
1310     {
1311         next = rp->next;
1312         FREE(rp);
1313     }
1314 }
1315
1316 /*
1317  * increase_maxtable
1318  *
1319  * inputs       - loc location in table
1320  * output       - size increased to
1321  * side effects - table is increase by at least 200 short words
1322  */
1323
1324 static int
1325 increase_maxtable(int loc)
1326 {
1327     int newmax;
1328     int l;
1329
1330     newmax = maxtable;
1331
1332     do { newmax += 200; } while (newmax <= loc);
1333     table = (short *) REALLOC(table, newmax*sizeof(short));
1334         if (table == 0) no_space();
1335         check = (short *) REALLOC(check, newmax*sizeof(short));
1336         if (check == 0) no_space();
1337         for (l  = maxtable; l < newmax; ++l)
1338         {
1339             table[l] = 0;
1340             check[l] = -1;
1341         }
1342
1343     return(newmax);
1344 }