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