util/LLgen/src/compute.c

   1 /* Copyright (c) 1991 by the Vrije Universiteit, Amsterdam, the Netherlands.
   2  * For full copyright and restrictions on use see the file COPYING in the top
   3  * level of the LLgen tree.
   4  */
   5
   6 /*
   7  *  L L G E N
   8  *
   9  *  An Extended LL(1) Parser Generator
  10  *
  11  *  Author : Ceriel J.H. Jacobs
  12  */
  13
  14 /*
  15  * compute.c
  16  * Defines routines to compute FIRST, FOLLOW etc.
  17  * Also checks the continuation grammar from the specified grammar.
  18  */
  19
  20 # include "types.h"
  21 # include "extern.h"
  22 # include "sets.h"
  23 # include "assert.h"
  24 # include "io.h"
  25
  26 # ifndef NORCSID
  27 static string rcsid = "$Id: compute.c,v 2.13 1997/02/21 11:27:46 ceriel Exp $";
  28 # endif
  29
  30 p_set           get_set();
  31 typedef struct lngth {
  32                         /* Structure used to compute the shortest possible
  33                          * length of a terminal production of a rule.
  34                          * In case of a tie, the second field is used.
  35                          */
  36         int cnt;
  37         int val;
  38 } t_length, *p_length;
  39
  40 /* Defined in this file : */
  41 extern do_compute();
  42 STATIC createsets();
  43 STATIC walk();
  44 STATIC co_trans();
  45 STATIC int nempty();
  46 extern empty();
  47 STATIC int nfirst();
  48 STATIC first();
  49 STATIC int nfollow();
  50 STATIC follow();
  51 STATIC co_dirsymb();
  52 STATIC co_others();
  53 STATIC do_lengthcomp();
  54 STATIC complength();
  55 STATIC add();
  56 STATIC int compare();
  57 STATIC setdefaults();
  58 STATIC do_contains();
  59 STATIC contains();
  60 STATIC int nsafes();
  61 STATIC int do_safes();
  62 #ifdef NON_CORRECTING
  63 STATIC int nc_nfirst();
  64 STATIC nc_first();
  65 STATIC int nc_nfollow();
  66 STATIC nc_follow();
  67 #endif
  68
  69 do_compute() {
  70         /*
  71          * Does all the work, by calling other routines (divide and conquer)
  72          */
  73         register p_nont p;
  74         register p_start st;
  75
  76         createsets();
  77         co_trans(nempty);       /* Which nonterminals produce empty? */
  78         co_trans(nfirst);       /* Computes first sets */
  79         /*
  80          * Compute FOLLOW sets.
  81          * First put EOFILE in the follow set of the start nonterminals.
  82          */
  83         for (st = start; st; st = st->ff_next) {
  84                 p = &nonterms[st->ff_nont];
  85                 PUTIN(p->n_follow,0);
  86         }
  87         co_trans(nfollow);
  88         /*
  89          * Compute the sets which determine which alternative to choose
  90          * in case of a choice
  91          */
  92         for (p = nonterms; p < maxnt; p++) {
  93                 co_dirsymb(p->n_follow,p->n_rule);
  94         }
  95         /*
  96          * Compute the minimum length of productions of nonterminals,
  97          * and then determine the default choices
  98          */
  99         do_lengthcomp();
 100         /*
 101          * Compute the contains sets
 102          */
 103         for (p = nonterms; p < maxnt; p++) do_contains(p);
 104         for (p = nonterms; p < maxnt; p++) contains(p->n_rule, (p_set) 0);
 105         /*
 106          * Compute the safety of each nonterminal and term.
 107          * The safety gives an answer to the question whether a scan is done,
 108          * and how it should be handled.
 109          */
 110         for (p = nonterms; p < maxnt; p++) {
 111                 /*
 112                  * Don't know anything yet
 113                  */
 114                 setntsafe(p, NOSAFETY);
 115                 setntout(p, NOSAFETY);
 116         }
 117         for (st = start; st; st = st->ff_next) {
 118                 /*
 119                  * But start symbols are called with lookahead done
 120                  */
 121                 p = &nonterms[st->ff_nont];
 122                 setntsafe(p,SCANDONE);
 123         }
 124         co_trans(nsafes);
 125
 126 #ifdef NON_CORRECTING
 127         if (subpars_sim) {
 128             int s;
 129
 130             /* compute the union of the first sets of all start symbols
 131                Used to compute the nc-first-sets when -s option is given */
 132             start_firsts = get_set();
 133             for (st = start; st; st = st->ff_next) {
 134                 s = setunion(start_firsts, (&nonterms[st->ff_nont])->n_first);
 135             }
 136         }
 137
 138         if (non_corr) {
 139             /* compute the non_corr first sets for all nonterminals and terms */
 140
 141             co_trans(nc_nfirst);
 142             for (st = start; st; st = st->ff_next) {
 143                 p = &nonterms[st->ff_nont];
 144                 PUTIN(p->n_nc_follow,0);
 145             }
 146             co_trans(nc_nfollow);
 147         }
 148 #endif
 149
 150 # ifndef NDEBUG
 151         if (debug) {
 152                 fputs("Safeties:\n", stderr);
 153                 for (p = nonterms; p < maxnt; p++) {
 154                         fprintf(stderr, "%s\t%d\t%d\n",
 155                                 p->n_name,
 156                                 getntsafe(p),
 157                                 getntout(p));
 158                 }
 159         }
 160 # endif
 161 }
 162
 163 STATIC
 164 createsets() {
 165         /*
 166          * Allocate space for the sets. Also determine which files use
 167          * which nonterminals, and determine which nonterminals can be
 168          * made static.
 169          */
 170         register p_nont p;
 171         register p_file f;
 172         register p_start st;
 173         register int i;
 174         int n = NINTS(NBYTES(nnonterms));
 175         p_mem alloc();
 176
 177         for (f = files; f < maxfiles; f++) {
 178                 register p_set s;
 179                 f->f_used = s = (p_set) alloc((unsigned)n*sizeof(*(f->f_used)));
 180                 for (i = n; i; i--) *s++ = 0;
 181                 for (i = f->f_nonterminals; i != -1; i = p->n_next) {
 182                         p = &nonterms[i];
 183                         p->n_flags |= GENSTATIC;
 184                         p->n_first = get_set();
 185 #ifdef NON_CORRECTING
 186                         p->n_nc_first = get_set();
 187                         p->n_nc_follow = get_set();
 188 #endif
 189                         p->n_follow = get_set();
 190                         walk(f->f_used, p->n_rule);
 191                 }
 192         }
 193         for (f = files; f < maxfiles; f++) {
 194                 for (i = f->f_nonterminals; i != -1; i = p->n_next) {
 195                         register p_file f2;
 196
 197                         p = &nonterms[i];
 198                         for (f2 = files; f2 < maxfiles; f2++) {
 199                                 if (f2 != f && IN(f2->f_used, i)) {
 200                                         p->n_flags &= ~GENSTATIC;
 201                                 }
 202                         }
 203                 }
 204         }
 205         for (st = start; st; st = st->ff_next) {
 206                 nonterms[st->ff_nont].n_flags &= ~GENSTATIC;
 207         }
 208 }
 209
 210 STATIC
 211 walk(u, p) p_set u; register p_gram p; {
 212         /*
 213          * Walk through the grammar rule p, allocating sets
 214          */
 215
 216         for (;;) {
 217                 switch (g_gettype(p)) {
 218                   case TERM : {
 219                         register p_term q;
 220
 221                         q = g_getterm(p);
 222                         q->t_first = get_set();
 223 #ifdef NON_CORRECTING
 224                         q->t_nc_first = get_set();
 225                         q->t_nc_follow = get_set();
 226 #endif
 227                         q->t_follow = get_set();
 228                         walk(u, q->t_rule);
 229                         break; }
 230                   case ALTERNATION : {
 231                         register p_link l;
 232
 233                         l = g_getlink(p);
 234                         l->l_symbs = get_set();
 235 #ifdef NON_CORRECTING
 236                         l->l_nc_symbs = get_set();
 237 #endif
 238                         l->l_others = get_set();
 239                         walk(u, l->l_rule);
 240                         break; }
 241                   case NONTERM : {
 242                         register int i = g_getcont(p);
 243
 244                         PUTIN(u, i);
 245                         break; }
 246                   case EORULE :
 247                         return;
 248                 }
 249                 p++;
 250         }
 251 }
 252
 253 STATIC
 254 co_trans(fc) int (*fc)(); {
 255         register p_nont p;
 256         register int change;
 257
 258         do {
 259                 change = 0;
 260                 for (p = nonterms; p < maxnt; p++) {
 261                         if ((*fc)(p)) change = 1;
 262                 }
 263         } while (change);
 264 }
 265
 266 STATIC int
 267 nempty(p) register p_nont p; {
 268         if (!(p->n_flags & EMPTY) && empty(p->n_rule)) {
 269                 p->n_flags |= EMPTY;
 270                 return 1;
 271         }
 272         return 0;
 273 }
 274
 275 empty(p) register p_gram p; {
 276         /*
 277          * Does the rule pointed to by p produce empty ?
 278          */
 279
 280         for (;;) {
 281                 switch (g_gettype(p)) {
 282                   case EORULE :
 283                         return 1;
 284                   case TERM :  {
 285                         register p_term q;
 286
 287                         q = g_getterm(p);
 288                         if (r_getkind(q) == STAR
 289                             || r_getkind(q) == OPT
 290                             || empty(q->t_rule) ) break;
 291                         return 0; }
 292                   case ALTERNATION :
 293                         if (empty(g_getlink(p)->l_rule)) {
 294                                 return 1;
 295                         }
 296                         if (g_gettype(p+1) == EORULE) return 0;
 297                         break;
 298                   case NONTERM :
 299                         if (nonterms[g_getcont(p)].n_flags & EMPTY) {
 300                                 break;
 301                         }
 302                         /* Fall through */
 303                   case LITERAL :
 304                   case TERMINAL :
 305                         return 0;
 306                 }
 307                 p++;
 308         }
 309 }
 310
 311 STATIC int
 312 nfirst(p) register p_nont p; {
 313         return first(p->n_first, p->n_rule, 0);
 314 }
 315
 316 #ifdef NON_CORRECTING
 317 STATIC int nc_nfirst(p) register p_nont p; {
 318         return nc_first(p->n_nc_first, p->n_rule, 0);
 319 }
 320 #endif
 321
 322 STATIC
 323 first(setp,p,flag) p_set setp; register p_gram p; {
 324         /*
 325          * Compute the FIRST set of rule p.
 326          * If flag = 0, also the first sets for terms and alternations in
 327          * the rule p are computed.
 328          * The FIRST set is put in setp.
 329          * return 1 if the set refered to by "setp" changed
 330          */
 331         register        s;      /* Will gather return value */
 332         int             noenter;/* when set, unables entering of elements into
 333                                  * setp. This is necessary to walk through the
 334                                  * rest of rule p.
 335                                  */
 336
 337         s = 0;
 338         noenter = 0;
 339         for (;;) {
 340                 switch (g_gettype(p)) {
 341                   case EORULE :
 342                         return s;
 343                   case TERM : {
 344                         register p_term q;
 345
 346                         q = g_getterm(p);
 347                         if (flag == 0) {
 348                                 if (first(q->t_first,q->t_rule,0))/*nothing*/;
 349                         }
 350                         if (!noenter) s |= setunion(setp,q->t_first);
 351                         p++;
 352                         if (r_getkind(q) == STAR ||
 353                             r_getkind(q) == OPT ||
 354                             empty(q->t_rule)) continue;
 355                         break; }
 356                   case ALTERNATION : {
 357                         register p_link l;
 358
 359                         l = g_getlink(p);
 360                         if (flag == 0) {
 361                                 if (first(l->l_symbs,l->l_rule,0))/*nothing*/;
 362                         }
 363                         if (noenter == 0) {
 364                                 s |= setunion(setp,l->l_symbs);
 365                         }
 366                         if (g_gettype(p+1) == EORULE) return s;
 367                         }
 368                         /* Fall Through */
 369                   case ACTION :
 370                         p++;
 371                         continue;
 372                   case LITERAL :
 373                   case TERMINAL :
 374                         if ((noenter == 0) && !IN(setp,g_getcont(p))) {
 375                                 s = 1;
 376                                 PUTIN(setp,g_getcont(p));
 377                         }
 378                         p++;
 379                         break;
 380                   case NONTERM : {
 381                         register p_nont n;
 382
 383                         n = &nonterms[g_getcont(p)];
 384                         if (noenter == 0)  {
 385                                 s |= setunion(setp,n->n_first);
 386                                 if (ntneeded) NTPUTIN(setp,g_getcont(p));
 387                         }
 388                         p++;
 389                         if (n->n_flags & EMPTY) continue;
 390                         break; }
 391                 }
 392                 if (flag == 0) {
 393                         noenter = 1;
 394                         continue;
 395                 }
 396                 return s;
 397         }
 398 }
 399
 400 #ifdef NON_CORRECTING
 401 STATIC
 402 nc_first(setp,p,flag) p_set setp; register p_gram p; {
 403         /*
 404          * Compute the non_corr FIRST set of rule p.
 405          * If flag = 0, also the non_corr first sets for terms and
 406          * alternations in the rule p are computed.
 407          * The non_corr FIRST set is put in setp.
 408          * return 1 if the set refered to by "setp" changed
 409          * If the -s flag was given, the union of the first-sets of all
 410          * start symbols is used whenever an action occurs. Else, only the
 411          * first-sets of startsynbols in the  %substart are used
 412          */
 413
 414         register        s;      /* Will gather return value */
 415         int             noenter;/* when set, unables entering of elements into
 416                                  * setp. This is necessary to walk through the
 417                                  * rest of rule p.
 418                                  */
 419
 420         s = 0;
 421         noenter = 0;
 422         for (;;) {
 423                 switch (g_gettype(p)) {
 424                   case EORULE :
 425                         return s;
 426                   case TERM : {
 427                         register p_term q;
 428
 429                         q = g_getterm(p);
 430                         if (flag == 0) {
 431                                 if (nc_first(q->t_nc_first,q->t_rule,0))/*nothing*/;
 432                         }
 433                         if (!noenter) s |= setunion(setp,q->t_nc_first);
 434                         p++;
 435                         if (r_getkind(q) == STAR ||
 436                             r_getkind(q) == OPT ||
 437                             empty(q->t_rule)) continue;
 438                         break; }
 439                   case ALTERNATION : {
 440                         register p_link l;
 441
 442                         l = g_getlink(p);
 443                         if (flag == 0) {
 444                                 if (nc_first(l->l_nc_symbs,l->l_rule,0))/*nothing*/;
 445                         }
 446                         if (noenter == 0) {
 447                                 s |= setunion(setp,l->l_nc_symbs);
 448                         }
 449                         if (g_gettype(p+1) == EORULE) return s;
 450                         }
 451                         p++;
 452                         continue;
 453                   case ACTION : {
 454                         register p_start subp;
 455
 456                         if (!noenter)
 457                           if (subpars_sim)
 458                             s |= setunion(setp, start_firsts);
 459                           else {
 460                             for (subp = g_getsubparse(p); subp;
 461                                  subp = subp->ff_next)
 462                                 s |= setunion(setp, (&nonterms[subp->ff_nont])->n_nc_first);
 463
 464                           }
 465                         p++;
 466                         continue;
 467                         }
 468                   case LITERAL :
 469                   case TERMINAL :
 470                         if (g_getcont(p) == g_getcont(illegal_gram)) {
 471                                 /* Ignore for this set. */
 472                                 p++;
 473                                 continue;
 474                         }
 475                         if ((noenter == 0) && !IN(setp,g_getcont(p))) {
 476                                 s = 1;
 477                                 PUTIN(setp,g_getcont(p));
 478                         }
 479                         p++;
 480                         break;
 481                   case NONTERM : {
 482                         register p_nont n;
 483
 484                         n = &nonterms[g_getcont(p)];
 485                         if (noenter == 0)  {
 486                                 s |= setunion(setp,n->n_nc_first);
 487                                 if (ntneeded) NTPUTIN(setp,g_getcont(p));
 488                         }
 489                         p++;
 490                         if (n->n_flags & EMPTY) continue;
 491                         break; }
 492                 }
 493                 if (flag == 0) {
 494                         noenter = 1;
 495                         continue;
 496                 }
 497                 return s;
 498         }
 499 }
 500 #endif
 501
 502 STATIC int
 503 nfollow(p) register p_nont p; {
 504         return follow(p->n_follow, p->n_rule);
 505 }
 506
 507 STATIC
 508 follow(setp,p) p_set setp; register p_gram p; {
 509         /*
 510          * setp is the follow set for the rule p.
 511          * Compute the follow sets in the rule p from this set.
 512          * Return 1 if a follow set of a nonterminal changed.
 513          */
 514         register        s;      /* Will gather return value */
 515
 516         s = 0;
 517         for (;;) {
 518                 switch (g_gettype(p)) {
 519                   case EORULE :
 520                         return s;
 521                   case TERM : {
 522                         register p_term q;
 523
 524                         q = g_getterm(p);
 525                         if (empty(p+1)) {
 526                                 /*
 527                                  * If what follows the term can be empty,
 528                                  * everything that can follow the whole
 529                                  * rule can also follow the term
 530                                  */
 531                                 s |= setunion(q->t_follow,setp);
 532                         }
 533                         /*
 534                          * Everything that can start the rest of the rule
 535                          * can follow the term
 536                          */
 537                         s |= first(q->t_follow,p+1,1);
 538                         if (r_getkind(q) == STAR ||
 539                             r_getkind(q) == PLUS ||
 540                             r_getnum(q) ) {
 541                                 /*
 542                                  * If the term involves a repetition
 543                                  * of possibly more than one,
 544                                  * everything that can start the term
 545                                  * can also follow it.
 546                                  */
 547                                 s |= follow(q->t_first,q->t_rule);
 548                         }
 549                         /*
 550                          * Now propagate the set computed sofar
 551                          */
 552                         s |= follow(q->t_follow, q->t_rule);
 553                         break; }
 554                   case ALTERNATION :
 555                         /*
 556                          * Just propagate setp
 557                          */
 558                         s |= follow(setp,g_getlink(p)->l_rule);
 559                         break;
 560                   case NONTERM : {
 561                         register p_nont n;
 562
 563                         n = &nonterms[g_getcont(p)];
 564                         s |= first(n->n_follow,p+1,1);
 565                         if (empty(p+1)) {
 566                                 /*
 567                                  * If the rest of p can produce empty,
 568                                  * everything that follows p can follow
 569                                  * the nonterminal
 570                                  */
 571                                 s |= setunion(n->n_follow,setp);
 572                         }
 573                         break; }
 574                 }
 575                 p++;
 576         }
 577 }
 578
 579 #ifdef NON_CORRECTING
 580
 581 STATIC int
 582 nc_nfollow(p) register p_nont p; {
 583         return follow(p->n_nc_follow, p->n_rule);
 584 }
 585
 586 STATIC
 587 nc_follow(setp,p) p_set setp; register p_gram p; {
 588         /*
 589          * setp is the follow set for the rule p.
 590          * Compute the follow sets in the rule p from this set.
 591          * Return 1 if a follow set of a nonterminal changed.
 592          */
 593         register        s;      /* Will gather return value */
 594
 595         s = 0;
 596         for (;;) {
 597                 switch (g_gettype(p)) {
 598                   case EORULE :
 599                         return s;
 600                   case TERM : {
 601                         register p_term q;
 602
 603                         q = g_getterm(p);
 604                         if (empty(p+1)) {
 605                                 /*
 606                                  * If what follows the term can be empty,
 607                                  * everything that can follow the whole
 608                                  * rule can also follow the term
 609                                  */
 610                                 s |= setunion(q->t_nc_follow,setp);
 611                         }
 612                         /*
 613                          * Everything that can start the rest of the rule
 614                          * can follow the term
 615                          */
 616                         s |= nc_first(q->t_nc_follow,p+1,1);
 617                         if (r_getkind(q) == STAR ||
 618                             r_getkind(q) == PLUS ||
 619                             r_getnum(q) ) {
 620                                 /*
 621                                  * If the term involves a repetition
 622                                  * of possibly more than one,
 623                                  * everything that can start the term
 624                                  * can also follow it.
 625                                  */
 626                                 s |= nc_follow(q->t_nc_first,q->t_rule);
 627                         }
 628                         /*
 629                          * Now propagate the set computed sofar
 630                          */
 631                         s |= nc_follow(q->t_nc_follow, q->t_rule);
 632                         break; }
 633                   case ALTERNATION :
 634                         /*
 635                          * Just propagate setp
 636                          */
 637                         s |= nc_follow(setp,g_getlink(p)->l_rule);
 638                         break;
 639                   case NONTERM : {
 640                         register p_nont n;
 641
 642                         n = &nonterms[g_getcont(p)];
 643                         s |= nc_first(n->n_nc_follow,p+1,1);
 644                         if (empty(p+1)) {
 645                                 /*
 646                                  * If the rest of p can produce empty,
 647                                  * everything that follows p can follow
 648                                  * the nonterminal
 649                                  */
 650                                 s |= setunion(n->n_nc_follow,setp);
 651                         }
 652                         break; }
 653                 }
 654                 p++;
 655         }
 656 }
 657
 658 #endif
 659
 660 STATIC
 661 co_dirsymb(setp,p) p_set setp; register p_gram p; {
 662         /*
 663          * Walk the rule p, doing the work for alternations
 664          */
 665         register p_gram s = 0;
 666
 667         for (;;) {
 668                 switch (g_gettype(p)) {
 669                   case EORULE :
 670                         return;
 671                   case TERM : {
 672                         register p_term q;
 673
 674                         q = g_getterm(p);
 675                         co_dirsymb(q->t_follow,q->t_rule);
 676                         break; }
 677                   case ALTERNATION : {
 678                         register p_link l;
 679                         /*
 680                          * Save first alternative
 681                          */
 682                         if (!s) s = p;
 683                         l = g_getlink(p);
 684                         co_dirsymb(setp,l->l_rule);
 685                         if (empty(l->l_rule)) {
 686                                 /*
 687                                  * If the rule can produce empty, everything
 688                                  * that follows it can also start it
 689                                  */
 690                                 setunion(l->l_symbs,setp);
 691                         }
 692                         if (g_gettype(p+1) == EORULE) {
 693                                 /*
 694                                  * Every alternation is implemented as a
 695                                  * choice between two alternatives :
 696                                  * this one or one of the following.
 697                                  * The l_others set will contain the starters
 698                                  * of the other alternatives
 699                                  */
 700                                 co_others(s);
 701                                 return;
 702                         } }
 703                 }
 704                 p++;
 705         }
 706 }
 707
 708 STATIC
 709 co_others(p) register p_gram p; {
 710         /*
 711          * compute the l_others-sets for the list of alternatives
 712          * indicated by p
 713          */
 714         register p_link l1,l2;
 715
 716         l1 = g_getlink(p);
 717         p++;
 718         l2 = g_getlink(p);
 719         setunion(l1->l_others,l2->l_symbs);
 720         if (g_gettype(p+1) != EORULE) {
 721                 /*
 722                  * First compute l2->l_others
 723                  */
 724                 co_others(p);
 725                 /*
 726                  * and then l1->l_others
 727                  */
 728                 setunion(l1->l_others,l2->l_others);
 729         }
 730 }
 731
 732 static p_length length;
 733 # define INFINITY 32767
 734
 735 STATIC
 736 ncomplength(p)
 737         register p_nont p;
 738 {
 739         register p_length pl = &length[p - nonterms];
 740         int x = pl->cnt;
 741
 742         pl->cnt = -1;
 743         complength(p->n_rule, pl);
 744         return pl->cnt < INFINITY && x == INFINITY;
 745 }
 746
 747 STATIC
 748 do_lengthcomp() {
 749         /*
 750          * Compute the minimum length of a terminal production for each
 751          * nonterminal.
 752          * This length consists of two fields: the number of terminals,
 753          * and a number that is composed of
 754          * - the number of this alternative
 755          * - a crude measure of the number of terms and nonterminals in the
 756          *   production of this shortest string.
 757          */
 758         register p_length pl;
 759         register p_nont p;
 760         p_mem alloc();
 761
 762         length = (p_length) alloc((unsigned) (nnonterms * sizeof(*length)));
 763         for (pl = &length[nnonterms-1]; pl >= length; pl--) {
 764                 pl->val = pl->cnt = INFINITY;
 765         }
 766
 767         co_trans(ncomplength);
 768
 769         pl = length;
 770         for (p = nonterms; p < maxnt; p++, pl++) {
 771                 if (pl->cnt == INFINITY) {
 772                         p->n_flags |= RECURSIVE;
 773                 }
 774                 setdefaults(p->n_rule);
 775         }
 776         free ((p_mem) length);
 777 }
 778
 779 STATIC
 780 complength(p,le) register p_gram p; p_length le; {
 781         /*
 782          * Walk grammar rule p, computing minimum lengths
 783          */
 784         register p_link l;
 785         register p_term q;
 786         t_length i;
 787         t_length X;
 788         int cnt = 0;
 789
 790         X.cnt = 0;
 791         X.val = 0;
 792         for (;;) {
 793                 switch (g_gettype(p)) {
 794                   case LITERAL :
 795                   case TERMINAL :
 796 #ifdef NON_CORRECTING
 797                         if (g_getcont(p) == g_getcont(illegal_gram)) {
 798                                 add(&X, INFINITY, 0);
 799                                 break;
 800                         }
 801 #endif
 802                         add(&X, 1, 0);
 803                         break;
 804                   case ALTERNATION :
 805
 806                         X.cnt = INFINITY;
 807                         X.val = INFINITY;
 808                         while (g_gettype(p) != EORULE) {
 809                                 cnt++;
 810                                 l = g_getlink(p);
 811                                 p++;
 812                                 complength(l->l_rule,&i);
 813                                 i.val += cnt;
 814                                 if (l->l_flag & DEF) {
 815                                         X = i;
 816                                         break;
 817                                 }
 818                                 if (compare(&i, &X) < 0) {
 819                                         X = i;
 820                                 }
 821                         }
 822                         /* Fall through */
 823                   case EORULE :
 824                         le->cnt = X.cnt;
 825                         le->val = X.val;
 826                         return;
 827                   case TERM : {
 828                         register int rep;
 829
 830                         q = g_getterm(p);
 831                         rep = r_getkind(q);
 832                         X.val += 1;
 833                         if ((q->t_flags&PERSISTENT) ||
 834                             rep==FIXED || rep==PLUS) {
 835                                 complength(q->t_rule,&i);
 836                                 add(&X, i.cnt, i.val);
 837                                 if (rep == FIXED && r_getnum(q) > 0) {
 838                                         for (rep = r_getnum(q) - 1;
 839                                              rep > 0; rep--) {
 840                                                 add(&X, i.cnt, i.val);
 841                                         }
 842                                 }
 843                         }
 844                         break; }
 845                   case NONTERM : {
 846                         int nn = g_getcont(p);
 847                         register p_length pl = &length[nn];
 848                         int x = pl->cnt;
 849
 850                         if (x == INFINITY) {
 851                                 pl->cnt = -1;
 852                                 complength(nonterms[nn].n_rule,pl);
 853                                 x = pl->cnt;
 854                         }
 855                         else if (x == -1) x = INFINITY;
 856                         add(&X, x, pl->val);
 857                         X.val += 1;
 858                         }
 859                 }
 860                 p++;
 861         }
 862 }
 863
 864 STATIC
 865 add(a, c, v) register p_length a; {
 866
 867         if (a->cnt == INFINITY || c == INFINITY) {
 868                 a->cnt = INFINITY;
 869                 return;
 870         }
 871         a->val += v;
 872         a->cnt += c;
 873 }
 874
 875 STATIC int
 876 compare(a, b) register p_length a, b; {
 877         if (a->cnt != b->cnt) return a->cnt - b->cnt;
 878         return a->val - b->val;
 879 }
 880
 881 STATIC
 882 setdefaults(p) register p_gram p; {
 883         for (;;) {
 884                 switch(g_gettype(p)) {
 885                   case EORULE:
 886                         return;
 887                   case TERM:
 888                         setdefaults(g_getterm(p)->t_rule);
 889                         break;
 890                   case ALTERNATION: {
 891                         register p_link l, l1;
 892                         int temp = 0, temp1, cnt = 0;
 893                         t_length count, i;
 894
 895                         count.cnt = INFINITY;
 896                         count.val = INFINITY;
 897                         l1 = g_getlink(p);
 898                         do {
 899                                 cnt++;
 900                                 l = g_getlink(p);
 901                                 p++;
 902                                 complength(l->l_rule,&i);
 903                                 i.val += cnt;
 904                                 if (l->l_flag & DEF) temp = 1;
 905                                 temp1 = compare(&i, &count);
 906                                 if (temp1 < 0 ||
 907                                     (temp1 == 0 && l1->l_flag & AVOIDING)) {
 908                                         l1 = l;
 909                                         count = i;
 910                                 }
 911                                 setdefaults(l->l_rule);
 912                         } while (g_gettype(p) != EORULE);
 913                         if (!temp) {
 914                                 /* No user specified default */
 915                                 l1->l_flag |= DEF;
 916                         }
 917                         return; }
 918                 }
 919                 p++;
 920         }
 921 }
 922
 923 STATIC
 924 do_contains(n) register p_nont n; {
 925         /*
 926          * Compute the total set of symbols that nonterminal n can
 927          * produce
 928          */
 929
 930         if (n->n_contains == 0) {
 931                 n->n_contains = get_set();
 932                 contains(n->n_rule,n->n_contains);
 933                 /*
 934                  * If the rule can produce empty, delete all symbols that
 935                  * can follow the rule as well as be in the rule.
 936                  * This is needed because the contains-set may only contain
 937                  * symbols that are guaranteed to be eaten by the rule!
 938                  * Otherwise, the generated parser may loop forever
 939                  */
 940                 if (n->n_flags & EMPTY) {
 941                         setminus(n->n_contains,n->n_follow);
 942                 }
 943                 /*
 944                  * But the symbols that can start the rule are always
 945                  * eaten
 946                  */
 947                 setunion(n->n_contains,n->n_first);
 948         }
 949 }
 950
 951 STATIC
 952 contains(p,set) register p_gram p; register p_set set; {
 953         /*
 954          * Does the real computation of the contains-sets
 955          */
 956
 957         for (;;) {
 958                 switch (g_gettype(p)) {
 959                   case EORULE :
 960                         return;
 961                   case TERM : {
 962                         register p_term q;
 963                         int rep;
 964
 965                         q = g_getterm(p);
 966                         rep = r_getkind(q);
 967                         if ((q->t_flags & PERSISTENT) ||
 968                             rep == PLUS || rep == FIXED) {
 969                                 /*
 970                                  * In these cases, the term belongs to the
 971                                  * continuation grammar.
 972                                  * Otherwise, q->t_contains is just
 973                                  * q->t_first
 974                                  */
 975                                 if (!q->t_contains) {
 976                                     q->t_contains = get_set();
 977                                 }
 978                                 contains(q->t_rule,q->t_contains);
 979                                 if (rep != FIXED || empty(q->t_rule)) {
 980                                         setminus(q->t_contains,q->t_follow);
 981                                 }
 982                                 setunion(q->t_contains,q->t_first);
 983                         } else {
 984                                 contains(q->t_rule, (p_set) 0);
 985                                 q->t_contains = q->t_first;
 986                         }
 987                         if (set) setunion(set,q->t_contains);
 988                         break; }
 989                   case NONTERM : {
 990                         register p_nont n;
 991
 992                         n = &nonterms[g_getcont(p)];
 993                         do_contains(n);
 994                         if (set) {
 995                                 setunion(set, n->n_contains);
 996                                 if (ntneeded) NTPUTIN(set, g_getcont(p));
 997                         }
 998                         break; }
 999                   case ALTERNATION : {
1000                         register p_link l;
1001
1002                         l = g_getlink(p);
1003                         contains(l->l_rule,
1004                                 (l->l_flag & DEF) ? set : (p_set) 0);
1005                         break; }
1006                   case LITERAL :
1007                   case TERMINAL : {
1008                         register hulp;
1009
1010                         if (set) {
1011                                 hulp = g_getcont(p);
1012                                 assert(hulp < ntokens);
1013                                 PUTIN(set,hulp);
1014                         }}
1015                 }
1016                 p++;
1017         }
1018 }
1019
1020 STATIC int nsafes(p) register p_nont p; {
1021         int     ch;
1022         register int i;
1023
1024         ch = 0;
1025         i = getntsafe(p);
1026         if (i != NOSAFETY) {
1027                 i = do_safes(p->n_rule, i, &ch);
1028                 if (i < SCANDONE) i = SCANDONE;
1029                 /* After a nonterminal, we only know whether a scan was done
1030                    or not
1031                 */
1032                 if (getntout(p) != i) {
1033                         ch = 1;
1034                         setntout(p,i);
1035                 }
1036         }
1037         return ch;
1038 }
1039
1040 STATIC int
1041 do_safes(p,safe,ch) register p_gram p; register int *ch; {
1042         /*
1043          * Walk the grammar rule, doing the computation described in the
1044          * comment of the procedure above this one.
1045          */
1046         int     retval;
1047
1048         for (;;) {
1049                 switch (g_gettype(p)) {
1050                   case ACTION:
1051                         p++;
1052                         continue;
1053                   case LITERAL:
1054                   case TERMINAL:
1055                         safe = NOSCANDONE;
1056                         break;
1057                   case TERM : {
1058                         register p_term q;
1059                         int i,rep;
1060
1061                         q = g_getterm(p);
1062                         i = r_getnum(q);
1063                         rep = r_getkind(q);
1064                         retval = do_safes(q->t_rule,
1065                                t_safety(rep,i,q->t_flags&PERSISTENT,safe),ch);
1066                         settout(q, retval);
1067                         safe = t_after(rep, i, retval);
1068                         break; }
1069                   case ALTERNATION : {
1070                         register p_link l;
1071                         register int i;
1072
1073                         retval = -1;
1074                         while (g_gettype(p) == ALTERNATION) {
1075                                 l = g_getlink(p);
1076                                 p++;
1077                                 if (safe > SAFE && (l->l_flag & DEF)) {
1078                                         i = do_safes(l->l_rule,SAFESCANDONE,ch);
1079                                 }
1080                                 else    i = do_safes(l->l_rule,SAFE,ch);
1081                                 if (retval == -1) retval = i;
1082                                 else if (i != retval) {
1083                                         if (i == NOSCANDONE ||
1084                                             retval == NOSCANDONE) {
1085                                                 retval = SCANDONE;
1086                                         }
1087                                         else if (i > retval) retval = i;
1088                                 }
1089                         }
1090                         return retval; }
1091                   case NONTERM : {
1092                         register p_nont n;
1093                         register int nsafe, osafe;
1094
1095                         n = &nonterms[g_getcont(p)];
1096                         nsafe = getntsafe(n);
1097                         osafe = safe;
1098                         safe = getntout(n);
1099                         if (safe == NOSAFETY) safe = SCANDONE;
1100                         if (osafe == nsafe) break;
1101                         if (nsafe == NOSAFETY) {
1102                                 *ch = 1;
1103                                 setntsafe(n, osafe);
1104                                 break;
1105                         }
1106                         if (osafe == NOSCANDONE || nsafe == NOSCANDONE) {
1107                                 if (nsafe != SCANDONE) {
1108                                         *ch = 1;
1109                                         setntsafe(n, SCANDONE);
1110                                 }
1111                                 break;
1112                         }
1113                         if (osafe > nsafe) {
1114                                 setntsafe(n, osafe);
1115                                 *ch = 1;
1116                         }
1117                         break; }
1118                   case EORULE :
1119                         return safe;
1120                 }
1121                 p++;
1122         }
1123 }
1124
1125 t_safety(rep, count, persistent, safety) {
1126
1127         if (safety == NOSCANDONE) safety = SCANDONE;
1128         switch(rep) {
1129           default:
1130                 assert(0);
1131           case OPT:
1132                 if (!persistent || safety < SAFESCANDONE) return SAFE;
1133                 return SAFESCANDONE;
1134           case STAR:
1135                 if (persistent) return SAFESCANDONE;
1136                 return SAFE;
1137           case PLUS:
1138                 if (persistent) {
1139                         if (safety > SAFESCANDONE) return safety;
1140                         return SAFESCANDONE;
1141                 }
1142                 return safety;
1143           case FIXED:
1144                 if (!count) return safety;
1145                 return SCANDONE;
1146         }
1147         /* NOTREACHED */
1148 }
1149
1150 t_after(rep, count, outsafety) {
1151         if (count == 0 && (rep == STAR || rep == PLUS)) {
1152                 return SAFESCANDONE;
1153         }
1154         if (rep != FIXED) {
1155                 if (outsafety <= SAFESCANDONE) return SAFESCANDONE;
1156                 return SCANDONE;
1157         }
1158         return outsafety;
1159 }