usr.bin/yacc/output.c

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