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 }
 878
 879
 880 expand_rules()
 881 {
 882     maxrules += 100;
 883     plhs = (bucket **) REALLOC(plhs, maxrules*sizeof(bucket *));
 884     if (plhs == 0) no_space();
 885     rprec = (short *) REALLOC(rprec, maxrules*sizeof(short));
 886     if (rprec == 0) no_space();
 887     rassoc = (char *) REALLOC(rassoc, maxrules*sizeof(char));
 888     if (rassoc == 0) no_space();
 889 }
 890
 891
 892 advance_to_start()
 893 {
 894     register int c;
 895     register bucket *bp;
 896     char *s_cptr;
 897     int s_lineno;
 898
 899     for (;;)
 900     {
 901         c = nextc();
 902         if (c != '%') break;
 903         s_cptr = cptr;
 904         switch (keyword())
 905         {
 906         case MARK:
 907             no_grammar();
 908
 909         case TEXT:
 910             copy_text(local_file);
 911             break;
 912
 913         case START:
 914             declare_start();
 915             break;
 916
 917         default:
 918             syntax_error(lineno, line, s_cptr);
 919         }
 920     }
 921
 922     c = nextc();
 923     if (!isalpha(c) && c != '_' && c != '.' && c != '_')
 924         syntax_error(lineno, line, cptr);
 925     bp = get_name();
 926     if (goal == 0)
 927     {
 928         if (bp->class == TERM)
 929             terminal_start(bp->name);
 930         goal = bp;
 931     }
 932
 933     s_lineno = lineno;
 934     c = nextc();
 935     if (c == EOF) unexpected_EOF();
 936     if (c != ':') syntax_error(lineno, line, cptr);
 937     start_rule(bp, s_lineno);
 938     ++cptr;
 939 }
 940
 941
 942 start_rule(bp, s_lineno)
 943 register bucket *bp;
 944 int s_lineno;
 945 {
 946     if (bp->class == TERM)
 947         terminal_lhs(s_lineno);
 948     bp->class = NONTERM;
 949     if (nrules >= maxrules)
 950         expand_rules();
 951     plhs[nrules] = bp;
 952     rprec[nrules] = UNDEFINED;
 953     rassoc[nrules] = TOKEN;
 954 }
 955
 956
 957 end_rule()
 958 {
 959     register int i;
 960
 961     if (!last_was_action && plhs[nrules]->tag)
 962     {
 963         for (i = nitems - 1; pitem[i]; --i) continue;
 964         if (pitem[i+1] == 0 || pitem[i+1]->tag != plhs[nrules]->tag)
 965             default_action_warning();   /** if classes don't match exactly **/
 966     }                                   /** bug: could be superclass... **/
 967
 968     last_was_action = 0;
 969     if (nitems >= maxitems) expand_items();
 970     pitem[nitems] = 0;
 971     ++nitems;
 972     ++nrules;
 973 }
 974
 975
 976 insert_empty_rule()
 977 {
 978     register bucket *bp, **bpp;
 979
 980     assert(cache);
 981     sprintf(cache, "$$%d", ++gensym);
 982     bp = make_bucket(cache);
 983     last_symbol->next = bp;
 984     last_symbol = bp;
 985     bp->tag = plhs[nrules]->tag;
 986     bp->class = NONTERM;
 987
 988     if ((nitems += 2) > maxitems)
 989         expand_items();
 990     bpp = pitem + nitems - 1;
 991     *bpp-- = bp;
 992     while (bpp[0] = bpp[-1]) --bpp;
 993
 994     if (++nrules >= maxrules)
 995         expand_rules();
 996     plhs[nrules] = plhs[nrules-1];
 997     plhs[nrules-1] = bp;
 998     rprec[nrules] = rprec[nrules-1];
 999     rprec[nrules-1] = 0;
1000     rassoc[nrules] = rassoc[nrules-1];
1001     rassoc[nrules-1] = TOKEN;
1002 }
1003
1004
1005 add_symbol()
1006 {
1007     register int c;
1008     register bucket *bp;
1009     int s_lineno = lineno;
1010
1011     c = *cptr;
1012     if (c == '\'' || c == '"')
1013         bp = get_literal();
1014     else
1015         bp = get_name();
1016
1017     c = nextc();
1018     if (c == ':')
1019     {
1020         end_rule();
1021         start_rule(bp, s_lineno);
1022         ++cptr;
1023         return;
1024     }
1025
1026     if (last_was_action)
1027         insert_empty_rule();
1028     last_was_action = 0;
1029
1030     if (++nitems > maxitems)
1031         expand_items();
1032     pitem[nitems-1] = bp;
1033 }
1034
1035
1036 copy_action()
1037 {
1038     register int c;
1039     register int i, n;
1040     int depth;
1041     int quote;
1042     char *tag;
1043     FILE *f = action_file;
1044     int a_lineno = lineno;
1045     char *a_line = dup_line();
1046     char *a_cptr = a_line + (cptr - line);
1047         char buffer [10000];
1048         int len = 0;
1049         int comment_lines = 0;
1050         char *mbody;
1051         memset (buffer, 0, 10000);
1052
1053     if (last_was_action)
1054         insert_empty_rule();
1055     last_was_action = 1;
1056
1057     fprintf(f, "case %d:\n", nrules - 2);
1058     if (*cptr == '=') ++cptr;
1059
1060     n = 0;
1061
1062     for (i = nitems - 1; pitem[i]; --i) ++n;
1063
1064     depth = 0;
1065 loop:
1066     c = *cptr;
1067     if (c == '$')
1068     {
1069         if (cptr[1] == '<')
1070         {
1071             int d_lineno = lineno;
1072             char *d_line = dup_line();
1073             char *d_cptr = d_line + (cptr - line);
1074
1075             ++cptr;
1076             tag = get_tag(1);
1077             c = *cptr;
1078             if (c == '$')
1079             {
1080                         if (tag && strcmp(tag, "Object")) {
1081                                 len += sprintf(buffer + len, "((%s)yyVal)", tag);
1082                         } else {
1083                                 strcat (buffer + len, "yyVal");
1084                                 len += 5;
1085                         }
1086                 ++cptr;
1087                 FREE(d_line);
1088                 goto loop;
1089             }
1090             else if (isdigit(c))
1091             {
1092                 i = get_number();
1093                 if (i > n) dollar_warning(d_lineno, i);
1094                 if (tag && strcmp(tag, "Object"))
1095                         len += sprintf(buffer + len, "((%s)yyVals[%d+yyTop])", tag, i - n);
1096                 else
1097                         len += sprintf(buffer + len, "yyVals[%d+yyTop]", i - n);
1098                 FREE(d_line);
1099                 goto loop;
1100             }
1101             else if (c == '-' && isdigit(cptr[1]))
1102             {
1103                 ++cptr;
1104                 i = -get_number() - n;
1105                 if (tag && strcmp(tag, "Object"))
1106                         len += sprintf(buffer + len, "((%s)yyVals[%d+yyTop])", tag, i);
1107                 else
1108                         len += sprintf(buffer + len, "yyVals[%d+yyTop]", i);
1109                 FREE(d_line);
1110                 goto loop;
1111             }
1112             else
1113                 dollar_error(d_lineno, d_line, d_cptr);
1114         }
1115         else if (cptr[1] == '$')
1116         {
1117             if (ntags && plhs[nrules]->tag == 0)
1118                 untyped_lhs();
1119                 strcat (buffer, "yyVal");
1120                 len += 5;
1121             cptr += 2;
1122             goto loop;
1123         }
1124         else if (isdigit(cptr[1]))
1125         {
1126             ++cptr;
1127             i = get_number();
1128             if (ntags)
1129             {
1130                 if (i <= 0 || i > n)
1131                     unknown_rhs(i);
1132                 tag = pitem[nitems + i - n - 1]->tag;
1133                 if (tag == 0)
1134                     untyped_rhs(i, pitem[nitems + i - n - 1]->name),
1135                     len += sprintf(buffer + len, "yyVals[%d+yyTop]", i - n);
1136                 else if (strcmp(tag, "Object"))
1137                     len += sprintf(buffer + len, "((%s)yyVals[%d+yyTop])", tag, i - n);
1138                 else
1139                     len += sprintf(buffer + len, "yyVals[%d+yyTop]", i - n);
1140             }
1141             else
1142             {
1143                 if (i > n)
1144                     dollar_warning(lineno, i);
1145
1146                 len += sprintf(buffer + len,"yyVals[%d+yyTop]", i - n);
1147             }
1148             goto loop;
1149         }
1150         else if (cptr[1] == '-')
1151         {
1152             cptr += 2;
1153             i = get_number();
1154             if (ntags)
1155                 unknown_rhs(-i);
1156             len += sprintf(buffer + len, "yyVals[%d+yyTop]", -i - n);
1157             goto loop;
1158         }
1159     }
1160     if (isalpha(c) || c == '_' || c == '$')
1161     {
1162         do
1163         {
1164             buffer[len++] = c;
1165             c = *++cptr;
1166         } while (isalnum(c) || c == '_' || c == '$');
1167         goto loop;
1168     }
1169         buffer[len++] = c;
1170     ++cptr;
1171     switch (c)
1172     {
1173     case '\n':
1174     next_line:
1175         get_line();
1176         if (line) goto loop;
1177         unterminated_action(a_lineno, a_line, a_cptr);
1178
1179     case ';':
1180         if (depth > 0) goto loop;
1181         break;
1182
1183     case '{':
1184         ++depth;
1185         goto loop;
1186
1187     case '}':
1188         if (--depth > 0) goto loop;
1189         break;
1190
1191     case '\'':
1192     case '"':
1193         {
1194             int s_lineno = lineno;
1195             char *s_line = dup_line();
1196             char *s_cptr = s_line + (cptr - line - 1);
1197
1198             quote = c;
1199             for (;;)
1200             {
1201                 c = *cptr++;
1202                 buffer[len++] = c;
1203                 if (c == quote)
1204                 {
1205                     FREE(s_line);
1206                     goto loop;
1207                 }
1208                 if (c == '\n')
1209                     unterminated_string(s_lineno, s_line, s_cptr);
1210                 if (c == '\\')
1211                 {
1212                     c = *cptr++;
1213                     buffer[len++] = c;
1214                     if (c == '\n')
1215                     {
1216                         get_line();
1217                         if (line == 0)
1218                             unterminated_string(s_lineno, s_line, s_cptr);
1219                     }
1220                 }
1221             }
1222         }
1223
1224     case '/':
1225         c = *cptr;
1226         if (c == '/')
1227         {
1228             buffer[len++] = '*';
1229             while ((c = *++cptr) != '\n')
1230             {
1231                         if (c == '*' && cptr[1] == '/'){
1232                                 buffer[len++] = '*';
1233                                 buffer[len++] = ' ';
1234                         } else {
1235                                 buffer[len++] = c;
1236                         }
1237                 }
1238             buffer[len++] = '*';
1239                 buffer[len++] = '/';
1240                 buffer[len++] = '\n';
1241             goto next_line;
1242         }
1243         if (c == '*')
1244         {
1245             int c_lineno = lineno;
1246             char *c_line = dup_line();
1247             char *c_cptr = c_line + (cptr - line - 1);
1248
1249             buffer[len++] = '*';
1250             ++cptr;
1251             for (;;)
1252             {
1253                 c = *cptr++;
1254                 buffer[len++] = c;
1255                 if (c == '*' && *cptr == '/')
1256                 {
1257                     buffer[len++] = '/';
1258                     ++cptr;
1259                     FREE(c_line);
1260                     goto loop;
1261                 }
1262                 if (c == '\n')
1263                 {
1264                         ++comment_lines;
1265                     get_line();
1266                     if (line == 0)
1267                         unterminated_comment(c_lineno, c_line, c_cptr);
1268                 }
1269             }
1270         }
1271         goto loop;
1272
1273     default:
1274         goto loop;
1275     }
1276
1277         if (comment_lines > 0)
1278                 comment_lines++;
1279
1280         if ((lineno - (a_lineno + comment_lines)) > 2)
1281         {
1282                 char mname[20];
1283                 char line_define[256];
1284
1285                 sprintf(mname, "case_%d()", nrules - 2);
1286
1287                 putc(' ', f); putc(' ', f);
1288                 fputs(mname, f);
1289                 fprintf(f, ";");
1290                 if (nmethods == 0)
1291                 {
1292                         maxmethods = 100;
1293                         methods = NEW2(maxmethods, char *);
1294                 }
1295                 else if (nmethods == maxmethods)
1296                 {
1297                         maxmethods += 500;
1298                         methods = REALLOC (methods, maxmethods*sizeof(char *));
1299                 }
1300
1301                 sprintf(line_define, line_format, a_lineno, input_file_name);
1302
1303                 mbody = NEW2(5+strlen(line_define)+1+strlen(mname)+strlen(buffer)+1, char);
1304                 strcpy(mbody, "void ");
1305                 strcat(mbody, mname);
1306                 strcat(mbody, "\n");
1307                 strcat(mbody, line_define);
1308                 strcat(mbody, buffer);
1309                 methods[nmethods++] = mbody;
1310         }
1311         else
1312         {
1313             fprintf(f, line_format, lineno, input_file_name);
1314                 putc(' ', f); putc(' ', f);
1315                 fwrite(buffer, 1, len, f);
1316         }
1317
1318         fprintf(f, "\n  break;\n");
1319 }
1320
1321
1322 int
1323 mark_symbol()
1324 {
1325     register int c;
1326     register bucket *bp;
1327
1328     c = cptr[1];
1329     if (c == '%' || c == '\\')
1330     {
1331         cptr += 2;
1332         return (1);
1333     }
1334
1335     if (c == '=')
1336         cptr += 2;
1337     else if ((c == 'p' || c == 'P') &&
1338              ((c = cptr[2]) == 'r' || c == 'R') &&
1339              ((c = cptr[3]) == 'e' || c == 'E') &&
1340              ((c = cptr[4]) == 'c' || c == 'C') &&
1341              ((c = cptr[5], !IS_IDENT(c))))
1342         cptr += 5;
1343     else
1344         syntax_error(lineno, line, cptr);
1345
1346     c = nextc();
1347     if (isalpha(c) || c == '_' || c == '.' || c == '$')
1348         bp = get_name();
1349     else if (c == '\'' || c == '"')
1350         bp = get_literal();
1351     else
1352     {
1353         syntax_error(lineno, line, cptr);
1354         /*NOTREACHED*/
1355     }
1356
1357     if (rprec[nrules] != UNDEFINED && bp->prec != rprec[nrules])
1358         prec_redeclared();
1359
1360     rprec[nrules] = bp->prec;
1361     rassoc[nrules] = bp->assoc;
1362     return (0);
1363 }
1364
1365
1366 read_grammar()
1367 {
1368     register int c;
1369
1370     initialize_grammar();
1371     advance_to_start();
1372
1373     for (;;)
1374     {
1375         c = nextc();
1376         if (c == EOF) break;
1377         if (isalpha(c) || c == '_' || c == '.' || c == '$' || c == '\'' ||
1378                 c == '"')
1379             add_symbol();
1380         else if (c == '{' || c == '=')
1381             copy_action();
1382         else if (c == '|')
1383         {
1384             end_rule();
1385             start_rule(plhs[nrules-1], 0);
1386             ++cptr;
1387         }
1388         else if (c == '%')
1389         {
1390             if (mark_symbol()) break;
1391         }
1392         else
1393             syntax_error(lineno, line, cptr);
1394     }
1395     end_rule();
1396 }
1397
1398
1399 free_tags()
1400 {
1401     register int i;
1402
1403     if (tag_table == 0) return;
1404
1405     for (i = 0; i < ntags; ++i)
1406     {
1407         assert(tag_table[i]);
1408         FREE(tag_table[i]);
1409     }
1410     FREE(tag_table);
1411 }
1412
1413
1414 pack_names()
1415 {
1416     register bucket *bp;
1417     register char *p, *s, *t;
1418
1419     name_pool_size = 13;  /* 13 == sizeof("$end") + sizeof("$accept") */
1420     for (bp = first_symbol; bp; bp = bp->next)
1421         name_pool_size += strlen(bp->name) + 1;
1422     name_pool = MALLOC(name_pool_size);
1423     if (name_pool == 0) no_space();
1424
1425     strcpy(name_pool, "$accept");
1426     strcpy(name_pool+8, "$end");
1427     t = name_pool + 13;
1428     for (bp = first_symbol; bp; bp = bp->next)
1429     {
1430         p = t;
1431         s = bp->name;
1432         while (*t++ = *s++) continue;
1433         FREE(bp->name);
1434         bp->name = p;
1435     }
1436 }
1437
1438
1439 check_symbols()
1440 {
1441     register bucket *bp;
1442
1443     if (goal->class == UNKNOWN)
1444         undefined_goal(goal->name);
1445
1446     for (bp = first_symbol; bp; bp = bp->next)
1447     {
1448         if (bp->class == UNKNOWN)
1449         {
1450             undefined_symbol_warning(bp->name);
1451             bp->class = TERM;
1452         }
1453     }
1454 }
1455
1456
1457 pack_symbols()
1458 {
1459     register bucket *bp;
1460     register bucket **v;
1461     register int i, j, k, n;
1462
1463     nsyms = 2;
1464     ntokens = 1;
1465     for (bp = first_symbol; bp; bp = bp->next)
1466     {
1467         ++nsyms;
1468         if (bp->class == TERM) ++ntokens;
1469     }
1470     start_symbol = ntokens;
1471     nvars = nsyms - ntokens;
1472
1473     symbol_name = (char **) MALLOC(nsyms*sizeof(char *));
1474     if (symbol_name == 0) no_space();
1475     symbol_value = (short *) MALLOC(nsyms*sizeof(short));
1476     if (symbol_value == 0) no_space();
1477     symbol_prec = (short *) MALLOC(nsyms*sizeof(short));
1478     if (symbol_prec == 0) no_space();
1479     symbol_assoc = MALLOC(nsyms);
1480     if (symbol_assoc == 0) no_space();
1481
1482     v = (bucket **) MALLOC(nsyms*sizeof(bucket *));
1483     if (v == 0) no_space();
1484
1485     v[0] = 0;
1486     v[start_symbol] = 0;
1487
1488     i = 1;
1489     j = start_symbol + 1;
1490     for (bp = first_symbol; bp; bp = bp->next)
1491     {
1492         if (bp->class == TERM)
1493             v[i++] = bp;
1494         else
1495             v[j++] = bp;
1496     }
1497     assert(i == ntokens && j == nsyms);
1498
1499     for (i = 1; i < ntokens; ++i)
1500         v[i]->index = i;
1501
1502     goal->index = start_symbol + 1;
1503     k = start_symbol + 2;
1504     while (++i < nsyms)
1505         if (v[i] != goal)
1506         {
1507             v[i]->index = k;
1508             ++k;
1509         }
1510
1511     goal->value = 0;
1512     k = 1;
1513     for (i = start_symbol + 1; i < nsyms; ++i)
1514     {
1515         if (v[i] != goal)
1516         {
1517             v[i]->value = k;
1518             ++k;
1519         }
1520     }
1521
1522     k = 0;
1523     for (i = 1; i < ntokens; ++i)
1524     {
1525         n = v[i]->value;
1526         if (n > 256)
1527         {
1528             for (j = k++; j > 0 && symbol_value[j-1] > n; --j)
1529                 symbol_value[j] = symbol_value[j-1];
1530             symbol_value[j] = n;
1531         }
1532     }
1533
1534     if (v[1]->value == UNDEFINED)
1535         v[1]->value = 256;
1536
1537     j = 0;
1538     n = 257;
1539     for (i = 2; i < ntokens; ++i)
1540     {
1541         if (v[i]->value == UNDEFINED)
1542         {
1543             while (j < k && n == symbol_value[j])
1544             {
1545                 while (++j < k && n == symbol_value[j]) continue;
1546                 ++n;
1547             }
1548             v[i]->value = n;
1549             ++n;
1550         }
1551     }
1552
1553     symbol_name[0] = name_pool + 8;
1554     symbol_value[0] = 0;
1555     symbol_prec[0] = 0;
1556     symbol_assoc[0] = TOKEN;
1557     for (i = 1; i < ntokens; ++i)
1558     {
1559         symbol_name[i] = v[i]->name;
1560         symbol_value[i] = v[i]->value;
1561         symbol_prec[i] = v[i]->prec;
1562         symbol_assoc[i] = v[i]->assoc;
1563     }
1564     symbol_name[start_symbol] = name_pool;
1565     symbol_value[start_symbol] = -1;
1566     symbol_prec[start_symbol] = 0;
1567     symbol_assoc[start_symbol] = TOKEN;
1568     for (++i; i < nsyms; ++i)
1569     {
1570         k = v[i]->index;
1571         symbol_name[k] = v[i]->name;
1572         symbol_value[k] = v[i]->value;
1573         symbol_prec[k] = v[i]->prec;
1574         symbol_assoc[k] = v[i]->assoc;
1575     }
1576
1577     FREE(v);
1578 }
1579
1580
1581 pack_grammar()
1582 {
1583     register int i, j;
1584     int assoc, prec;
1585
1586     ritem = (short *) MALLOC(nitems*sizeof(short));
1587     if (ritem == 0) no_space();
1588     rlhs = (short *) MALLOC(nrules*sizeof(short));
1589     if (rlhs == 0) no_space();
1590     rrhs = (short *) MALLOC((nrules+1)*sizeof(short));
1591     if (rrhs == 0) no_space();
1592     rprec = (short *) REALLOC(rprec, nrules*sizeof(short));
1593     if (rprec == 0) no_space();
1594     rassoc = REALLOC(rassoc, nrules);
1595     if (rassoc == 0) no_space();
1596
1597     ritem[0] = -1;
1598     ritem[1] = goal->index;
1599     ritem[2] = 0;
1600     ritem[3] = -2;
1601     rlhs[0] = 0;
1602     rlhs[1] = 0;
1603     rlhs[2] = start_symbol;
1604     rrhs[0] = 0;
1605     rrhs[1] = 0;
1606     rrhs[2] = 1;
1607
1608     j = 4;
1609     for (i = 3; i < nrules; ++i)
1610     {
1611         rlhs[i] = plhs[i]->index;
1612         rrhs[i] = j;
1613         assoc = TOKEN;
1614         prec = 0;
1615         while (pitem[j])
1616         {
1617             ritem[j] = pitem[j]->index;
1618             if (pitem[j]->class == TERM)
1619             {
1620                 prec = pitem[j]->prec;
1621                 assoc = pitem[j]->assoc;
1622             }
1623             ++j;
1624         }
1625         ritem[j] = -i;
1626         ++j;
1627         if (rprec[i] == UNDEFINED)
1628         {
1629             rprec[i] = prec;
1630             rassoc[i] = assoc;
1631         }
1632     }
1633     rrhs[i] = j;
1634
1635     FREE(plhs);
1636     FREE(pitem);
1637 }
1638
1639
1640 print_grammar()
1641 {
1642     register int i, j, k;
1643     int spacing;
1644     register FILE *f = verbose_file;
1645
1646     if (!vflag) return;
1647
1648     k = 1;
1649     for (i = 2; i < nrules; ++i)
1650     {
1651         if (rlhs[i] != rlhs[i-1])
1652         {
1653             if (i != 2) fprintf(f, "\n");
1654             fprintf(f, "%4d  %s :", i - 2, symbol_name[rlhs[i]]);
1655             spacing = strlen(symbol_name[rlhs[i]]) + 1;
1656         }
1657         else
1658         {
1659             fprintf(f, "%4d  ", i - 2);
1660             j = spacing;
1661             while (--j >= 0) putc(' ', f);
1662             putc('|', f);
1663         }
1664
1665         while (ritem[k] >= 0)
1666         {
1667             fprintf(f, " %s", symbol_name[ritem[k]]);
1668             ++k;
1669         }
1670         ++k;
1671         putc('\n', f);
1672     }
1673 }
1674
1675
1676 reader()
1677 {
1678     create_symbol_table();
1679     read_declarations();
1680     read_grammar();
1681     free_symbol_table();
1682     free_tags();
1683     pack_names();
1684     check_symbols();
1685     pack_symbols();
1686     pack_grammar();
1687     free_symbols();
1688     print_grammar();
1689 }