output.c

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