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