commands/byacc/reader.c

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