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