mcs/jay/reader.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
  37 #ifndef lint
  38 static char sccsid[] = "@(#)reader.c    5.7 (Berkeley) 1/20/91";
  39 #endif /* not lint */
  40
  41 #include "defs.h"
  42
  43 /* this resolves "unresolved symbol _snprintf" on Windows */
  44 #if defined (_MSC_VER)
  45 #define snprintf _snprintf
  46 #endif
  47
  48 /*  The line size must be a positive integer.  One hundred was chosen   */
  49 /*  because few lines in Yacc input grammars exceed 100 characters.     */
  50 /*  Note that if a line exceeds LINESIZE characters, the line buffer    */
  51 /*  will be expanded to accomodate it.                                  */
  52
  53 #define LINESIZE 100
  54
  55 char *cache;
  56 int cinc, cache_size;
  57
  58 int ntags, tagmax;
  59 char **tag_table;
  60
  61 char saw_eof;
  62 char *cptr, *line;
  63 int linesize;
  64
  65 bucket *goal;
  66 int prec;
  67 int gensym;
  68 char last_was_action;
  69
  70 int maxitems;
  71 bucket **pitem;
  72
  73 int maxrules;
  74 bucket **plhs;
  75
  76 int maxmethods;
  77
  78 int name_pool_size;
  79 char *name_pool;
  80
  81 char *line_format = "\t\t\t\t\t// line %d \"%s\"\n";
  82 char *default_line_format = "\t\t\t\t\t// line %d\n";
  83
  84
  85 cachec(c)
  86 int c;
  87 {
  88     assert(cinc >= 0);
  89     if (cinc >= cache_size)
  90     {
  91         cache_size += 256;
  92         cache = REALLOC(cache, cache_size);
  93         if (cache == 0) no_space();
  94     }
  95     cache[cinc] = c;
  96     ++cinc;
  97 }
  98
  99
 100 get_line()
 101 {
 102     register FILE *f = input_file;
 103     register int c;
 104     register int i;
 105
 106     if (saw_eof || (c = getc(f)) == EOF)
 107     {
 108         if (line) { FREE(line); line = 0; }
 109         cptr = 0;
 110         saw_eof = 1;
 111         return;
 112     }
 113
 114     if (line == 0 || linesize != (LINESIZE + 1))
 115     {
 116         if (line) FREE(line);
 117         linesize = LINESIZE + 1;
 118         line = MALLOC(linesize);
 119         if (line == 0) no_space();
 120     }
 121
 122     i = 0;
 123     ++lineno;
 124     for (;;)
 125     {
 126         line[i]  =  c;
 127         if (c == '\n') { cptr = line; return; }
 128         if (++i >= linesize)
 129         {
 130             linesize += LINESIZE;
 131             line = REALLOC(line, linesize);
 132             if (line ==  0) no_space();
 133         }
 134         c = getc(f);
 135         if (c ==  EOF)
 136         {
 137             line[i] = '\n';
 138             saw_eof = 1;
 139             cptr = line;
 140             return;
 141         }
 142     }
 143 }
 144
 145
 146 char *
 147 dup_line()
 148 {
 149     register char *p, *s, *t;
 150
 151     if (line == 0) return (0);
 152     s = line;
 153     while (*s != '\n') ++s;
 154     p = MALLOC(s - line + 1);
 155     if (p == 0) no_space();
 156
 157     s = line;
 158     t = p;
 159     while ((*t++ = *s++) != '\n') continue;
 160     return (p);
 161 }
 162
 163
 164 skip_comment()
 165 {
 166     register char *s;
 167
 168     int st_lineno = lineno;
 169     char *st_line = dup_line();
 170     char *st_cptr = st_line + (cptr - line);
 171
 172     s = cptr + 2;
 173     for (;;)
 174     {
 175         if (*s == '*' && s[1] == '/')
 176         {
 177             cptr = s + 2;
 178             FREE(st_line);
 179             return;
 180         }
 181         if (*s == '\n')
 182         {
 183             get_line();
 184             if (line == 0)
 185                 unterminated_comment(st_lineno, st_line, st_cptr);
 186             s = cptr;
 187         }
 188         else
 189             ++s;
 190     }
 191 }
 192
 193
 194 int
 195 nextc()
 196 {
 197     register char *s;
 198
 199     if (line == 0)
 200     {
 201         get_line();
 202         if (line == 0)
 203             return (EOF);
 204     }
 205
 206     s = cptr;
 207     for (;;)
 208     {
 209         switch (*s)
 210         {
 211         case '\n':
 212             get_line();
 213             if (line == 0) return (EOF);
 214             s = cptr;
 215             break;
 216
 217         case ' ':
 218         case '\t':
 219         case '\f':
 220         case '\r':
 221         case '\v':
 222         case ',':
 223         case ';':
 224             ++s;
 225             break;
 226
 227         case '\\':
 228             cptr = s;
 229             return ('%');
 230
 231         case '/':
 232             if (s[1] == '*')
 233             {
 234                 cptr = s;
 235                 skip_comment();
 236                 s = cptr;
 237                 break;
 238             }
 239             else if (s[1] == '/')
 240             {
 241                 get_line();
 242                 if (line == 0) return (EOF);
 243                 s = cptr;
 244                 break;
 245             }
 246             /* fall through */
 247
 248         default:
 249             cptr = s;
 250             return (*s);
 251         }
 252     }
 253 }
 254
 255
 256 int
 257 keyword()
 258 {
 259     register int c;
 260     char *t_cptr = cptr;
 261
 262     c = *++cptr;
 263     if (isalpha(c))
 264     {
 265         cinc = 0;
 266         for (;;)
 267         {
 268             if (isalpha(c))
 269             {
 270                 if (isupper(c)) c = tolower(c);
 271                 cachec(c);
 272             }
 273             else if (isdigit(c) || c == '_' || c == '.' || c == '$')
 274                 cachec(c);
 275             else
 276                 break;
 277             c = *++cptr;
 278         }
 279         cachec(NUL);
 280
 281         if (strcmp(cache, "token") == 0 || strcmp(cache, "term") == 0)
 282             return (TOKEN);
 283         if (strcmp(cache, "type") == 0)
 284             return (TYPE);
 285         if (strcmp(cache, "left") == 0)
 286             return (LEFT);
 287         if (strcmp(cache, "right") == 0)
 288             return (RIGHT);
 289         if (strcmp(cache, "nonassoc") == 0 || strcmp(cache, "binary") == 0)
 290             return (NONASSOC);
 291         if (strcmp(cache, "start") == 0)
 292             return (START);
 293     }
 294     else
 295     {
 296         ++cptr;
 297         if (c == '{')
 298             return (TEXT);
 299         if (c == '%' || c == '\\')
 300             return (MARK);
 301         if (c == '<')
 302             return (LEFT);
 303         if (c == '>')
 304             return (RIGHT);
 305         if (c == '0')
 306             return (TOKEN);
 307         if (c == '2')
 308             return (NONASSOC);
 309     }
 310     syntax_error(lineno, line, t_cptr);
 311     /*NOTREACHED*/
 312 }
 313
 314
 315 copy_text(f)
 316 FILE *f;
 317 {
 318     register int c;
 319     int quote;
 320     int need_newline = 0;
 321     int t_lineno = lineno;
 322     char *t_line = dup_line();
 323     char *t_cptr = t_line + (cptr - line - 2);
 324
 325     if (*cptr == '\n')
 326     {
 327         get_line();
 328         if (line == 0)
 329             unterminated_text(t_lineno, t_line, t_cptr);
 330     }
 331     fprintf(f, line_format, lineno, input_file_name);
 332
 333 loop:
 334     c = *cptr++;
 335     switch (c)
 336     {
 337     case '\n':
 338     next_line:
 339         putc('\n', f);
 340         need_newline = 0;
 341         get_line();
 342         if (line) goto loop;
 343         unterminated_text(t_lineno, t_line, t_cptr);
 344
 345     case '\'':
 346     case '"':
 347         {
 348             int s_lineno = lineno;
 349             char *s_line = dup_line();
 350             char *s_cptr = s_line + (cptr - line - 1);
 351
 352             quote = c;
 353             putc(c, f);
 354             for (;;)
 355             {
 356                 c = *cptr++;
 357                 putc(c, f);
 358                 if (c == quote)
 359                 {
 360                     need_newline = 1;
 361                     FREE(s_line);
 362                     goto loop;
 363                 }
 364                 if (c == '\n')
 365                     unterminated_string(s_lineno, s_line, s_cptr);
 366                 if (c == '\\')
 367                 {
 368                     c = *cptr++;
 369                     putc(c, f);
 370                     if (c == '\n')
 371                     {
 372                         get_line();
 373                         if (line == 0)
 374                             unterminated_string(s_lineno, s_line, s_cptr);
 375                     }
 376                 }
 377             }
 378         }
 379
 380     case '/':
 381         putc(c, f);
 382         need_newline = 1;
 383         c = *cptr;
 384         if (c == '/')
 385         {
 386             do putc(c, f); while ((c = *++cptr) != '\n');
 387             goto next_line;
 388         }
 389         if (c == '*')
 390         {
 391             int c_lineno = lineno;
 392             char *c_line = dup_line();
 393             char *c_cptr = c_line + (cptr - line - 1);
 394
 395             putc('*', f);
 396             ++cptr;
 397             for (;;)
 398             {
 399                 c = *cptr++;
 400                 putc(c, f);
 401                 if (c == '*' && *cptr == '/')
 402                 {
 403                     putc('/', f);
 404                     ++cptr;
 405                     FREE(c_line);
 406                     goto loop;
 407                 }
 408                 if (c == '\n')
 409                 {
 410                     get_line();
 411                     if (line == 0)
 412                         unterminated_comment(c_lineno, c_line, c_cptr);
 413                 }
 414             }
 415         }
 416         need_newline = 1;
 417         goto loop;
 418
 419     case '%':
 420     case '\\':
 421         if (*cptr == '}')
 422         {
 423             if (need_newline) putc('\n', f);
 424             ++cptr;
 425             FREE(t_line);
 426             return;
 427         }
 428         /* fall through */
 429
 430     default:
 431         putc(c, f);
 432         need_newline = 1;
 433         goto loop;
 434     }
 435 }
 436
 437 int
 438 hexval(c)
 439 int c;
 440 {
 441     if (c >= '0' && c <= '9')
 442         return (c - '0');
 443     if (c >= 'A' && c <= 'F')
 444         return (c - 'A' + 10);
 445     if (c >= 'a' && c <= 'f')
 446         return (c - 'a' + 10);
 447     return (-1);
 448 }
 449
 450
 451 bucket *
 452 get_literal()
 453 {
 454     register int c, quote;
 455     register int i;
 456     register int n;
 457     register char *s;
 458     register bucket *bp;
 459     int s_lineno = lineno;
 460     char *s_line = dup_line();
 461     char *s_cptr = s_line + (cptr - line);
 462
 463     quote = *cptr++;
 464     cinc = 0;
 465     for (;;)
 466     {
 467         c = *cptr++;
 468         if (c == quote) break;
 469         if (c == '\n') unterminated_string(s_lineno, s_line, s_cptr);
 470         if (c == '\\')
 471         {
 472             char *c_cptr = cptr - 1;
 473
 474             c = *cptr++;
 475             switch (c)
 476             {
 477             case '\n':
 478                 get_line();
 479                 if (line == 0) unterminated_string(s_lineno, s_line, s_cptr);
 480                 continue;
 481
 482             case '0': case '1': case '2': case '3':
 483             case '4': case '5': case '6': case '7':
 484                 n = c - '0';
 485                 c = *cptr;
 486                 if (IS_OCTAL(c))
 487                 {
 488                     n = (n << 3) + (c - '0');
 489                     c = *++cptr;
 490                     if (IS_OCTAL(c))
 491                     {
 492                         n = (n << 3) + (c - '0');
 493                         ++cptr;
 494                     }
 495                 }
 496                 if (n > MAXCHAR) illegal_character(c_cptr);
 497                 c = n;
 498                 break;
 499
 500             case 'x':
 501                 c = *cptr++;
 502                 n = hexval(c);
 503                 if (n < 0 || n >= 16)
 504                     illegal_character(c_cptr);
 505                 for (;;)
 506                 {
 507                     c = *cptr;
 508                     i = hexval(c);
 509                     if (i < 0 || i >= 16) break;
 510                     ++cptr;
 511                     n = (n << 4) + i;
 512                     if (n > MAXCHAR) illegal_character(c_cptr);
 513                 }
 514                 c = n;
 515                 break;
 516
 517             case 'a': c = 7; break;
 518             case 'b': c = '\b'; break;
 519             case 'f': c = '\f'; break;
 520             case 'n': c = '\n'; break;
 521             case 'r': c = '\r'; break;
 522             case 't': c = '\t'; break;
 523             case 'v': c = '\v'; break;
 524             }
 525         }
 526         cachec(c);
 527     }
 528     FREE(s_line);
 529
 530     n = cinc;
 531     s = MALLOC(n);
 532     if (s == 0) no_space();
 533
 534     for (i = 0; i < n; ++i)
 535         s[i] = cache[i];
 536
 537     cinc = 0;
 538     if (n == 1)
 539         cachec('\'');
 540     else
 541         cachec('"');
 542
 543     for (i = 0; i < n; ++i)
 544     {
 545         c = ((unsigned char *)s)[i];
 546         if (c == '\\' || c == cache[0])
 547         {
 548             cachec('\\');
 549             cachec(c);
 550         }
 551         else if (isprint(c))
 552             cachec(c);
 553         else
 554         {
 555             cachec('\\');
 556             switch (c)
 557             {
 558             case 7: cachec('a'); break;
 559             case '\b': cachec('b'); break;
 560             case '\f': cachec('f'); break;
 561             case '\n': cachec('n'); break;
 562             case '\r': cachec('r'); break;
 563             case '\t': cachec('t'); break;
 564             case '\v': cachec('v'); break;
 565             default:
 566                 cachec(((c >> 6) & 7) + '0');
 567                 cachec(((c >> 3) & 7) + '0');
 568                 cachec((c & 7) + '0');
 569                 break;
 570             }
 571         }
 572     }
 573
 574     if (n == 1)
 575         cachec('\'');
 576     else
 577         cachec('"');
 578
 579     cachec(NUL);
 580     bp = lookup(cache);
 581     bp->class = TERM;
 582     if (n == 1 && bp->value == UNDEFINED)
 583         bp->value = *(unsigned char *)s;
 584     FREE(s);
 585
 586     return (bp);
 587 }
 588
 589
 590 int
 591 is_reserved(name)
 592 char *name;
 593 {
 594     char *s;
 595
 596     if (strcmp(name, ".") == 0 ||
 597             strcmp(name, "$accept") == 0 ||
 598             strcmp(name, "$end") == 0)
 599         return (1);
 600
 601     if (name[0] == '$' && name[1] == '$' && isdigit(name[2]))
 602     {
 603         s = name + 3;
 604         while (isdigit(*s)) ++s;
 605         if (*s == NUL) return (1);
 606     }
 607
 608     return (0);
 609 }
 610
 611
 612 bucket *
 613 get_name()
 614 {
 615     register int c;
 616
 617     cinc = 0;
 618     for (c = *cptr; IS_IDENT(c); c = *++cptr)
 619         cachec(c);
 620     cachec(NUL);
 621
 622     if (is_reserved(cache)) used_reserved(cache);
 623
 624     return (lookup(cache));
 625 }
 626
 627
 628 int
 629 get_number()
 630 {
 631     register int c;
 632     register int n;
 633
 634     n = 0;
 635     for (c = *cptr; isdigit(c); c = *++cptr)
 636         n = 10*n + (c - '0');
 637
 638     return (n);
 639 }
 640
 641
 642 char *
 643 get_tag(int emptyOk)
 644 {
 645     register int c;
 646     register int i;
 647     register char *s;
 648     int t_lineno = lineno;
 649     char *t_line = dup_line();
 650     char *t_cptr = t_line + (cptr - line);
 651
 652     ++cptr;
 653     c = nextc();
 654     if (c == EOF) unexpected_EOF();
 655     if (emptyOk && c == '>') {
 656       ++cptr; return 0; // 0 indicates empty tag if emptyOk
 657     }
 658     if (!isalpha(c) && c != '_' && c != '$')
 659         illegal_tag(t_lineno, t_line, t_cptr);
 660
 661     cinc = 0;
 662     do { cachec(c); c = *++cptr; } while (IS_IDENT(c));
 663     cachec(NUL);
 664
 665     c = nextc();
 666     if (c == EOF) unexpected_EOF();
 667     if (c != '>')
 668         illegal_tag(t_lineno, t_line, t_cptr);
 669     ++cptr;
 670
 671     for (i = 0; i < ntags; ++i)
 672     {
 673         if (strcmp(cache, tag_table[i]) == 0)
 674             return (tag_table[i]);
 675     }
 676
 677     if (ntags >= tagmax)
 678     {
 679         tagmax += 16;
 680         tag_table = (char **)
 681                         (tag_table ? REALLOC(tag_table, tagmax*sizeof(char *))
 682                                    : MALLOC(tagmax*sizeof(char *)));
 683         if (tag_table == 0) no_space();
 684     }
 685
 686     s = MALLOC(cinc);
 687     if  (s == 0) no_space();
 688     strcpy(s, cache);
 689     tag_table[ntags] = s;
 690     ++ntags;
 691     FREE(t_line);
 692     return (s);
 693 }
 694
 695
 696 declare_tokens(assoc)
 697 int assoc;
 698 {
 699     register int c;
 700     register bucket *bp;
 701     int value;
 702     char *tag = 0;
 703
 704     if (assoc != TOKEN) ++prec;
 705
 706     c = nextc();
 707     if (c == EOF) unexpected_EOF();
 708     if (c == '<')
 709     {
 710         tag = get_tag(0);
 711         c = nextc();
 712         if (c == EOF) unexpected_EOF();
 713     }
 714
 715     for (;;)
 716     {
 717         if (isalpha(c) || c == '_' || c == '.' || c == '$')
 718             bp = get_name();
 719         else if (c == '\'' || c == '"')
 720             bp = get_literal();
 721         else
 722             return;
 723
 724         if (bp == goal) tokenized_start(bp->name);
 725         bp->class = TERM;
 726
 727         if (tag)
 728         {
 729             if (bp->tag && tag != bp->tag)
 730                 retyped_warning(bp->name);
 731             bp->tag = tag;
 732         }
 733
 734         if (assoc != TOKEN)
 735         {
 736             if (bp->prec && prec != bp->prec)
 737                 reprec_warning(bp->name);
 738             bp->assoc = assoc;
 739             bp->prec = prec;
 740         }
 741
 742         c = nextc();
 743         if (c == EOF) unexpected_EOF();
 744         value = UNDEFINED;
 745         if (isdigit(c))
 746         {
 747             value = get_number();
 748             if (bp->value != UNDEFINED && value != bp->value)
 749                 revalued_warning(bp->name);
 750             bp->value = value;
 751             c = nextc();
 752             if (c == EOF) unexpected_EOF();
 753         }
 754     }
 755 }
 756
 757
 758 declare_types()
 759 {
 760     register int c;
 761     register bucket *bp;
 762     char *tag;
 763
 764     c = nextc();
 765     if (c == EOF) unexpected_EOF();
 766     if (c != '<') syntax_error(lineno, line, cptr);
 767     tag = get_tag(0);
 768
 769     for (;;)
 770     {
 771         c = nextc();
 772         if (isalpha(c) || c == '_' || c == '.' || c == '$')
 773             bp = get_name();
 774         else if (c == '\'' || c == '"')
 775             bp = get_literal();
 776         else
 777             return;
 778
 779         if (bp->tag && tag != bp->tag)
 780             retyped_warning(bp->name);
 781         bp->tag = tag;
 782     }
 783 }
 784
 785
 786 declare_start()
 787 {
 788     register int c;
 789     register bucket *bp;
 790
 791     c = nextc();
 792     if (c == EOF) unexpected_EOF();
 793     if (!isalpha(c) && c != '_' && c != '.' && c != '$')
 794         syntax_error(lineno, line, cptr);
 795     bp = get_name();
 796     if (bp->class == TERM)
 797         terminal_start(bp->name);
 798     if (goal && goal != bp)
 799         restarted_warning();
 800     goal = bp;
 801 }
 802
 803
 804 read_declarations()
 805 {
 806     register int c, k;
 807
 808     cache_size = 256;
 809     cache = MALLOC(cache_size);
 810     if (cache == 0) no_space();
 811
 812     for (;;)
 813     {
 814         c = nextc();
 815         if (c == EOF) unexpected_EOF();
 816         if (c != '%') syntax_error(lineno, line, cptr);
 817         switch (k = keyword())
 818         {
 819         case MARK:
 820             return;
 821
 822         case TEXT:
 823             copy_text(prolog_file);
 824             break;
 825
 826         case TOKEN:
 827         case LEFT:
 828         case RIGHT:
 829         case NONASSOC:
 830             declare_tokens(k);
 831             break;
 832
 833         case TYPE:
 834             declare_types();
 835             break;
 836
 837         case START:
 838             declare_start();
 839             break;
 840         }
 841     }
 842 }
 843
 844
 845 initialize_grammar()
 846 {
 847     nitems = 4;
 848     maxitems = 300;
 849     pitem = (bucket **) MALLOC(maxitems*sizeof(bucket *));
 850     if (pitem == 0) no_space();
 851     pitem[0] = 0;
 852     pitem[1] = 0;
 853     pitem[2] = 0;
 854     pitem[3] = 0;
 855
 856         nmethods = 0;
 857     nrules = 3;
 858     maxrules = 100;
 859     plhs = (bucket **) MALLOC(maxrules*sizeof(bucket *));
 860     if (plhs == 0) no_space();
 861     plhs[0] = 0;
 862     plhs[1] = 0;
 863     plhs[2] = 0;
 864     rprec = (short *) MALLOC(maxrules*sizeof(short));
 865     if (rprec == 0) no_space();
 866     rprec[0] = 0;
 867     rprec[1] = 0;
 868     rprec[2] = 0;
 869     rassoc = (char *) MALLOC(maxrules*sizeof(char));
 870     if (rassoc == 0) no_space();
 871     rassoc[0] = TOKEN;
 872     rassoc[1] = TOKEN;
 873     rassoc[2] = TOKEN;
 874 }
 875
 876
 877 expand_items()
 878 {
 879     maxitems += 300;
 880     pitem = (bucket **) REALLOC(pitem, maxitems*sizeof(bucket *));
 881     if (pitem == 0) no_space();
 882     memset(pitem+maxitems-300, 0, 300*sizeof(bucket *));
 883 }
 884
 885
 886 expand_rules()
 887 {
 888     maxrules += 100;
 889     plhs = (bucket **) REALLOC(plhs, maxrules*sizeof(bucket *));
 890     if (plhs == 0) no_space();
 891     rprec = (short *) REALLOC(rprec, maxrules*sizeof(short));
 892     if (rprec == 0) no_space();
 893     rassoc = (char *) REALLOC(rassoc, maxrules*sizeof(char));
 894     if (rassoc == 0) no_space();
 895 }
 896
 897
 898 advance_to_start()
 899 {
 900     register int c;
 901     register bucket *bp;
 902     char *s_cptr;
 903     int s_lineno;
 904
 905     for (;;)
 906     {
 907         c = nextc();
 908         if (c != '%') break;
 909         s_cptr = cptr;
 910         switch (keyword())
 911         {
 912         case MARK:
 913             no_grammar();
 914
 915         case TEXT:
 916             copy_text(local_file);
 917             break;
 918
 919         case START:
 920             declare_start();
 921             break;
 922
 923         default:
 924             syntax_error(lineno, line, s_cptr);
 925         }
 926     }
 927
 928     c = nextc();
 929     if (!isalpha(c) && c != '_' && c != '.' && c != '_')
 930         syntax_error(lineno, line, cptr);
 931     bp = get_name();
 932     if (goal == 0)
 933     {
 934         if (bp->class == TERM)
 935             terminal_start(bp->name);
 936         goal = bp;
 937     }
 938
 939     s_lineno = lineno;
 940     c = nextc();
 941     if (c == EOF) unexpected_EOF();
 942     if (c != ':') syntax_error(lineno, line, cptr);
 943     start_rule(bp, s_lineno);
 944     ++cptr;
 945 }
 946
 947
 948 start_rule(bp, s_lineno)
 949 register bucket *bp;
 950 int s_lineno;
 951 {
 952     if (bp->class == TERM)
 953         terminal_lhs(s_lineno);
 954     bp->class = NONTERM;
 955     if (nrules >= maxrules)
 956         expand_rules();
 957     plhs[nrules] = bp;
 958     rprec[nrules] = UNDEFINED;
 959     rassoc[nrules] = TOKEN;
 960 }
 961
 962
 963 end_rule()
 964 {
 965     register int i;
 966
 967     if (nitems >= maxitems) expand_items();
 968
 969     if (!last_was_action && plhs[nrules]->tag)
 970     {
 971         for (i = nitems - 1; pitem[i]; --i) continue;
 972         if (pitem[i+1] == 0 || pitem[i+1]->tag != plhs[nrules]->tag)
 973             default_action_warning();   /** if classes don't match exactly **/
 974     }                                   /** bug: could be superclass... **/
 975
 976     last_was_action = 0;
 977     pitem[nitems] = 0;
 978     ++nitems;
 979     ++nrules;
 980 }
 981
 982
 983 insert_empty_rule()
 984 {
 985     register bucket *bp, **bpp;
 986
 987     assert(cache);
 988     sprintf(cache, "$$%d", ++gensym);
 989     bp = make_bucket(cache);
 990     last_symbol->next = bp;
 991     last_symbol = bp;
 992     bp->tag = plhs[nrules]->tag;
 993     bp->class = NONTERM;
 994
 995     if ((nitems += 2) > maxitems)
 996         expand_items();
 997     bpp = pitem + nitems - 1;
 998     *bpp-- = bp;
 999     while (bpp[0] = bpp[-1]) --bpp;
1000
1001     if (++nrules >= maxrules)
1002         expand_rules();
1003     plhs[nrules] = plhs[nrules-1];
1004     plhs[nrules-1] = bp;
1005     rprec[nrules] = rprec[nrules-1];
1006     rprec[nrules-1] = 0;
1007     rassoc[nrules] = rassoc[nrules-1];
1008     rassoc[nrules-1] = TOKEN;
1009 }
1010
1011
1012 add_symbol()
1013 {
1014     register int c;
1015     register bucket *bp;
1016     int s_lineno = lineno;
1017
1018     c = *cptr;
1019     if (c == '\'' || c == '"')
1020         bp = get_literal();
1021     else
1022         bp = get_name();
1023
1024     c = nextc();
1025     if (c == ':')
1026     {
1027         end_rule();
1028         start_rule(bp, s_lineno);
1029         ++cptr;
1030         return;
1031     }
1032
1033     if (last_was_action)
1034         insert_empty_rule();
1035     last_was_action = 0;
1036
1037     if (++nitems > maxitems)
1038         expand_items();
1039     pitem[nitems-1] = bp;
1040 }
1041
1042
1043 copy_action()
1044 {
1045     register int c;
1046     register int i, n;
1047     int depth;
1048     int quote;
1049     char *tag;
1050     FILE *f = action_file;
1051     int a_lineno = lineno;
1052     char *a_line = dup_line();
1053     char *a_cptr = a_line + (cptr - line);
1054         char buffer [10000];
1055         int len = 0;
1056         int comment_lines = 0;
1057         char *mbody;
1058         memset (buffer, 0, 10000);
1059
1060     if (last_was_action)
1061         insert_empty_rule();
1062     last_was_action = 1;
1063
1064     fprintf(f, "case %d:\n", nrules - 2);
1065     if (*cptr == '=') ++cptr;
1066
1067     n = 0;
1068
1069     for (i = nitems - 1; pitem[i]; --i) ++n;
1070
1071     depth = 0;
1072 loop:
1073     c = *cptr;
1074     if (c == '$')
1075     {
1076         if (cptr[1] == '<')
1077         {
1078             int d_lineno = lineno;
1079             char *d_line = dup_line();
1080             char *d_cptr = d_line + (cptr - line);
1081
1082             ++cptr;
1083             tag = get_tag(1);
1084             c = *cptr;
1085             if (c == '$')
1086             {
1087                         if (tag && strcmp(tag, "Object")) {
1088                                 len += sprintf(buffer + len, "((%s)yyVal)", tag);
1089                         } else {
1090                                 strcat (buffer + len, "yyVal");
1091                                 len += 5;
1092                         }
1093                 ++cptr;
1094                 FREE(d_line);
1095                 goto loop;
1096             }
1097             else if (isdigit(c))
1098             {
1099                 i = get_number();
1100                 if (i > n) dollar_warning(d_lineno, i);
1101                 if (tag && strcmp(tag, "Object"))
1102                         len += sprintf(buffer + len, "((%s)yyVals[%d+yyTop])", tag, i - n);
1103                 else
1104                         len += sprintf(buffer + len, "yyVals[%d+yyTop]", i - n);
1105                 FREE(d_line);
1106                 goto loop;
1107             }
1108             else if (c == '-' && isdigit(cptr[1]))
1109             {
1110                 ++cptr;
1111                 i = -get_number() - n;
1112                 if (tag && strcmp(tag, "Object"))
1113                         len += sprintf(buffer + len, "((%s)yyVals[%d+yyTop])", tag, i);
1114                 else
1115                         len += sprintf(buffer + len, "yyVals[%d+yyTop]", i);
1116                 FREE(d_line);
1117                 goto loop;
1118             }
1119             else
1120                 dollar_error(d_lineno, d_line, d_cptr);
1121         }
1122         else if (cptr[1] == '$')
1123         {
1124             if (ntags && plhs[nrules]->tag == 0)
1125                 untyped_lhs();
1126                 strcat (buffer, "yyVal");
1127                 len += 5;
1128             cptr += 2;
1129             goto loop;
1130         }
1131         else if (isdigit(cptr[1]))
1132         {
1133             ++cptr;
1134             i = get_number();
1135             if (ntags)
1136             {
1137                 if (i <= 0 || i > n)
1138                     unknown_rhs(i);
1139                 tag = pitem[nitems + i - n - 1]->tag;
1140                 if (tag == 0)
1141                     untyped_rhs(i, pitem[nitems + i - n - 1]->name),
1142                     len += sprintf(buffer + len, "yyVals[%d+yyTop]", i - n);
1143                 else if (strcmp(tag, "Object"))
1144                     len += sprintf(buffer + len, "((%s)yyVals[%d+yyTop])", tag, i - n);
1145                 else
1146                     len += sprintf(buffer + len, "yyVals[%d+yyTop]", i - n);
1147             }
1148             else
1149             {
1150                 if (i > n)
1151                     dollar_warning(lineno, i);
1152
1153                 len += sprintf(buffer + len,"yyVals[%d+yyTop]", i - n);
1154             }
1155             goto loop;
1156         }
1157         else if (cptr[1] == '-')
1158         {
1159             cptr += 2;
1160             i = get_number();
1161             if (ntags)
1162                 unknown_rhs(-i);
1163             len += sprintf(buffer + len, "yyVals[%d+yyTop]", -i - n);
1164             goto loop;
1165         }
1166     }
1167     if (isalpha(c) || c == '_' || c == '$')
1168     {
1169         do
1170         {
1171             buffer[len++] = c;
1172             c = *++cptr;
1173         } while (isalnum(c) || c == '_' || c == '$');
1174         goto loop;
1175     }
1176         buffer[len++] = c;
1177     ++cptr;
1178     switch (c)
1179     {
1180     case '\n':
1181     next_line:
1182         get_line();
1183         if (line) goto loop;
1184         unterminated_action(a_lineno, a_line, a_cptr);
1185
1186     case ';':
1187         if (depth > 0) goto loop;
1188         break;
1189
1190     case '{':
1191         ++depth;
1192         goto loop;
1193
1194     case '}':
1195         if (--depth > 0) goto loop;
1196         break;
1197
1198     case '\'':
1199     case '"':
1200         {
1201             int s_lineno = lineno;
1202             char *s_line = dup_line();
1203             char *s_cptr = s_line + (cptr - line - 1);
1204
1205             quote = c;
1206             for (;;)
1207             {
1208                 c = *cptr++;
1209                 buffer[len++] = c;
1210                 if (c == quote)
1211                 {
1212                     FREE(s_line);
1213                     goto loop;
1214                 }
1215                 if (c == '\n')
1216                     unterminated_string(s_lineno, s_line, s_cptr);
1217                 if (c == '\\')
1218                 {
1219                     c = *cptr++;
1220                     buffer[len++] = c;
1221                     if (c == '\n')
1222                     {
1223                         get_line();
1224                         if (line == 0)
1225                             unterminated_string(s_lineno, s_line, s_cptr);
1226                     }
1227                 }
1228             }
1229         }
1230
1231     case '/':
1232         c = *cptr;
1233         if (c == '/')
1234         {
1235             buffer[len++] = '*';
1236             while ((c = *++cptr) != '\n')
1237             {
1238                         if (c == '*' && cptr[1] == '/'){
1239                                 buffer[len++] = '*';
1240                                 buffer[len++] = ' ';
1241                         } else {
1242                                 buffer[len++] = c;
1243                         }
1244                 }
1245             buffer[len++] = '*';
1246                 buffer[len++] = '/';
1247                 buffer[len++] = '\n';
1248             goto next_line;
1249         }
1250         if (c == '*')
1251         {
1252             int c_lineno = lineno;
1253             char *c_line = dup_line();
1254             char *c_cptr = c_line + (cptr - line - 1);
1255
1256             buffer[len++] = '*';
1257             ++cptr;
1258             for (;;)
1259             {
1260                 c = *cptr++;
1261                 buffer[len++] = c;
1262                 if (c == '*' && *cptr == '/')
1263                 {
1264                     buffer[len++] = '/';
1265                     ++cptr;
1266                     FREE(c_line);
1267                     goto loop;
1268                 }
1269                 if (c == '\n')
1270                 {
1271                         ++comment_lines;
1272                     get_line();
1273                     if (line == 0)
1274                         unterminated_comment(c_lineno, c_line, c_cptr);
1275                 }
1276             }
1277         }
1278         goto loop;
1279
1280     default:
1281         goto loop;
1282     }
1283
1284         if (comment_lines > 0)
1285                 comment_lines++;
1286
1287         if ((lineno - (a_lineno + comment_lines)) > 2)
1288         {
1289                 char mname[28];
1290                 char *line_define;
1291
1292                 // the maximum size of of an unsigned int in characters is 20, with 8 for 'case_()\0'
1293                 sprintf(mname, "case_%d()", nrules - 2);
1294
1295                 putc(' ', f); putc(' ', f);
1296                 fputs(mname, f);
1297                 fprintf(f, ";");
1298                 if (nmethods == 0)
1299                 {
1300                         maxmethods = 100;
1301                         methods = NEW2(maxmethods, char *);
1302                 }
1303                 else if (nmethods == maxmethods)
1304                 {
1305                         maxmethods += 500;
1306                         methods = REALLOC (methods, maxmethods*sizeof(char *));
1307                 }
1308
1309                 line_define = NEW2(snprintf(NULL, 0, line_format, a_lineno, input_file_name)+1, char);
1310                 sprintf(line_define, line_format, a_lineno, input_file_name);
1311
1312                 mbody = NEW2(5+strlen(line_define)+1+strlen(mname)+strlen(buffer)+1, char);
1313                 strcpy(mbody, "void ");
1314                 strcat(mbody, mname);
1315                 strcat(mbody, "\n");
1316                 strcat(mbody, line_define);
1317                 strcat(mbody, buffer);
1318                 methods[nmethods++] = mbody;
1319
1320                 FREE(line_define);
1321         }
1322         else
1323         {
1324             fprintf(f, line_format, lineno, input_file_name);
1325                 putc(' ', f); putc(' ', f);
1326                 fwrite(buffer, 1, len, f);
1327         }
1328
1329         fprintf(f, "\n  break;\n");
1330 }
1331
1332
1333 int
1334 mark_symbol()
1335 {
1336     register int c;
1337     register bucket *bp;
1338
1339     c = cptr[1];
1340     if (c == '%' || c == '\\')
1341     {
1342         cptr += 2;
1343         return (1);
1344     }
1345
1346     if (c == '=')
1347         cptr += 2;
1348     else if ((c == 'p' || c == 'P') &&
1349              ((c = cptr[2]) == 'r' || c == 'R') &&
1350              ((c = cptr[3]) == 'e' || c == 'E') &&
1351              ((c = cptr[4]) == 'c' || c == 'C') &&
1352              ((c = cptr[5], !IS_IDENT(c))))
1353         cptr += 5;
1354     else
1355         syntax_error(lineno, line, cptr);
1356
1357     c = nextc();
1358     if (isalpha(c) || c == '_' || c == '.' || c == '$')
1359         bp = get_name();
1360     else if (c == '\'' || c == '"')
1361         bp = get_literal();
1362     else
1363     {
1364         syntax_error(lineno, line, cptr);
1365         /*NOTREACHED*/
1366     }
1367
1368     if (rprec[nrules] != UNDEFINED && bp->prec != rprec[nrules])
1369         prec_redeclared();
1370
1371     rprec[nrules] = bp->prec;
1372     rassoc[nrules] = bp->assoc;
1373     return (0);
1374 }
1375
1376
1377 read_grammar()
1378 {
1379     register int c;
1380
1381     initialize_grammar();
1382     advance_to_start();
1383
1384     for (;;)
1385     {
1386         c = nextc();
1387         if (c == EOF) break;
1388         if (isalpha(c) || c == '_' || c == '.' || c == '$' || c == '\'' ||
1389                 c == '"')
1390             add_symbol();
1391         else if (c == '{' || c == '=')
1392             copy_action();
1393         else if (c == '|')
1394         {
1395             end_rule();
1396             start_rule(plhs[nrules-1], 0);
1397             ++cptr;
1398         }
1399         else if (c == '%')
1400         {
1401             if (mark_symbol()) break;
1402         }
1403         else
1404             syntax_error(lineno, line, cptr);
1405     }
1406     end_rule();
1407 }
1408
1409
1410 free_tags()
1411 {
1412     register int i;
1413
1414     if (tag_table == 0) return;
1415
1416     for (i = 0; i < ntags; ++i)
1417     {
1418         assert(tag_table[i]);
1419         FREE(tag_table[i]);
1420     }
1421     FREE(tag_table);
1422 }
1423
1424
1425 pack_names()
1426 {
1427     register bucket *bp;
1428     register char *p, *s, *t;
1429
1430     name_pool_size = 13;  /* 13 == sizeof("$end") + sizeof("$accept") */
1431     for (bp = first_symbol; bp; bp = bp->next)
1432         name_pool_size += strlen(bp->name) + 1;
1433     name_pool = MALLOC(name_pool_size);
1434     if (name_pool == 0) no_space();
1435
1436     strcpy(name_pool, "$accept");
1437     strcpy(name_pool+8, "$end");
1438     t = name_pool + 13;
1439     for (bp = first_symbol; bp; bp = bp->next)
1440     {
1441         p = t;
1442         s = bp->name;
1443         while (*t++ = *s++) continue;
1444         FREE(bp->name);
1445         bp->name = p;
1446     }
1447 }
1448
1449
1450 check_symbols()
1451 {
1452     register bucket *bp;
1453
1454     if (goal->class == UNKNOWN)
1455         undefined_goal(goal->name);
1456
1457     for (bp = first_symbol; bp; bp = bp->next)
1458     {
1459         if (bp->class == UNKNOWN)
1460         {
1461             undefined_symbol_warning(bp->name);
1462             bp->class = TERM;
1463         }
1464     }
1465 }
1466
1467
1468 pack_symbols()
1469 {
1470     register bucket *bp;
1471     register bucket **v;
1472     register int i, j, k, n;
1473
1474     nsyms = 2;
1475     ntokens = 1;
1476     for (bp = first_symbol; bp; bp = bp->next)
1477     {
1478         ++nsyms;
1479         if (bp->class == TERM) ++ntokens;
1480     }
1481     start_symbol = ntokens;
1482     nvars = nsyms - ntokens;
1483
1484     symbol_name = (char **) MALLOC(nsyms*sizeof(char *));
1485     if (symbol_name == 0) no_space();
1486     symbol_value = (short *) MALLOC(nsyms*sizeof(short));
1487     if (symbol_value == 0) no_space();
1488     symbol_prec = (short *) MALLOC(nsyms*sizeof(short));
1489     if (symbol_prec == 0) no_space();
1490     symbol_assoc = MALLOC(nsyms);
1491     if (symbol_assoc == 0) no_space();
1492
1493     v = (bucket **) MALLOC(nsyms*sizeof(bucket *));
1494     if (v == 0) no_space();
1495
1496     v[0] = 0;
1497     v[start_symbol] = 0;
1498
1499     i = 1;
1500     j = start_symbol + 1;
1501     for (bp = first_symbol; bp; bp = bp->next)
1502     {
1503         if (bp->class == TERM)
1504             v[i++] = bp;
1505         else
1506             v[j++] = bp;
1507     }
1508     assert(i == ntokens && j == nsyms);
1509
1510     for (i = 1; i < ntokens; ++i)
1511         v[i]->index = i;
1512
1513     goal->index = start_symbol + 1;
1514     k = start_symbol + 2;
1515     while (++i < nsyms)
1516         if (v[i] != goal)
1517         {
1518             v[i]->index = k;
1519             ++k;
1520         }
1521
1522     goal->value = 0;
1523     k = 1;
1524     for (i = start_symbol + 1; i < nsyms; ++i)
1525     {
1526         if (v[i] != goal)
1527         {
1528             v[i]->value = k;
1529             ++k;
1530         }
1531     }
1532
1533     k = 0;
1534     for (i = 1; i < ntokens; ++i)
1535     {
1536         n = v[i]->value;
1537         if (n > 256)
1538         {
1539             for (j = k++; j > 0 && symbol_value[j-1] > n; --j)
1540                 symbol_value[j] = symbol_value[j-1];
1541             symbol_value[j] = n;
1542         }
1543     }
1544
1545     if (v[1]->value == UNDEFINED)
1546         v[1]->value = 256;
1547
1548     j = 0;
1549     n = 257;
1550     for (i = 2; i < ntokens; ++i)
1551     {
1552         if (v[i]->value == UNDEFINED)
1553         {
1554             while (j < k && n == symbol_value[j])
1555             {
1556                 while (++j < k && n == symbol_value[j]) continue;
1557                 ++n;
1558             }
1559             v[i]->value = n;
1560             ++n;
1561         }
1562     }
1563
1564     symbol_name[0] = name_pool + 8;
1565     symbol_value[0] = 0;
1566     symbol_prec[0] = 0;
1567     symbol_assoc[0] = TOKEN;
1568     for (i = 1; i < ntokens; ++i)
1569     {
1570         symbol_name[i] = v[i]->name;
1571         symbol_value[i] = v[i]->value;
1572         symbol_prec[i] = v[i]->prec;
1573         symbol_assoc[i] = v[i]->assoc;
1574     }
1575     symbol_name[start_symbol] = name_pool;
1576     symbol_value[start_symbol] = -1;
1577     symbol_prec[start_symbol] = 0;
1578     symbol_assoc[start_symbol] = TOKEN;
1579     for (++i; i < nsyms; ++i)
1580     {
1581         k = v[i]->index;
1582         symbol_name[k] = v[i]->name;
1583         symbol_value[k] = v[i]->value;
1584         symbol_prec[k] = v[i]->prec;
1585         symbol_assoc[k] = v[i]->assoc;
1586     }
1587
1588     FREE(v);
1589 }
1590
1591
1592 pack_grammar()
1593 {
1594     register int i, j;
1595     int assoc, prec;
1596
1597     ritem = (short *) MALLOC(nitems*sizeof(short));
1598     if (ritem == 0) no_space();
1599     rlhs = (short *) MALLOC(nrules*sizeof(short));
1600     if (rlhs == 0) no_space();
1601     rrhs = (short *) MALLOC((nrules+1)*sizeof(short));
1602     if (rrhs == 0) no_space();
1603     rprec = (short *) REALLOC(rprec, nrules*sizeof(short));
1604     if (rprec == 0) no_space();
1605     rassoc = REALLOC(rassoc, nrules);
1606     if (rassoc == 0) no_space();
1607
1608     ritem[0] = -1;
1609     ritem[1] = goal->index;
1610     ritem[2] = 0;
1611     ritem[3] = -2;
1612     rlhs[0] = 0;
1613     rlhs[1] = 0;
1614     rlhs[2] = start_symbol;
1615     rrhs[0] = 0;
1616     rrhs[1] = 0;
1617     rrhs[2] = 1;
1618
1619     j = 4;
1620     for (i = 3; i < nrules; ++i)
1621     {
1622         rlhs[i] = plhs[i]->index;
1623         rrhs[i] = j;
1624         assoc = TOKEN;
1625         prec = 0;
1626         while (pitem[j])
1627         {
1628             ritem[j] = pitem[j]->index;
1629             if (pitem[j]->class == TERM)
1630             {
1631                 prec = pitem[j]->prec;
1632                 assoc = pitem[j]->assoc;
1633             }
1634             ++j;
1635         }
1636         ritem[j] = -i;
1637         ++j;
1638         if (rprec[i] == UNDEFINED)
1639         {
1640             rprec[i] = prec;
1641             rassoc[i] = assoc;
1642         }
1643     }
1644     rrhs[i] = j;
1645
1646     FREE(plhs);
1647     FREE(pitem);
1648 }
1649
1650
1651 print_grammar()
1652 {
1653     register int i, j, k;
1654     int spacing;
1655     register FILE *f = verbose_file;
1656
1657     if (!vflag) return;
1658
1659     k = 1;
1660     for (i = 2; i < nrules; ++i)
1661     {
1662         if (rlhs[i] != rlhs[i-1])
1663         {
1664             if (i != 2) fprintf(f, "\n");
1665             fprintf(f, "%4d  %s :", i - 2, symbol_name[rlhs[i]]);
1666             spacing = strlen(symbol_name[rlhs[i]]) + 1;
1667         }
1668         else
1669         {
1670             fprintf(f, "%4d  ", i - 2);
1671             j = spacing;
1672             while (--j >= 0) putc(' ', f);
1673             putc('|', f);
1674         }
1675
1676         while (ritem[k] >= 0)
1677         {
1678             fprintf(f, " %s", symbol_name[ritem[k]]);
1679             ++k;
1680         }
1681         ++k;
1682         putc('\n', f);
1683     }
1684 }
1685
1686
1687 reader()
1688 {
1689     create_symbol_table();
1690     read_declarations();
1691     read_grammar();
1692     free_symbol_table();
1693     free_tags();
1694     pack_names();
1695     check_symbols();
1696     pack_symbols();
1697     pack_grammar();
1698     free_symbols();
1699     print_grammar();
1700 }