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