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