mcs/jay/lalr.c

   1 /*
   2  * Copyright (c) 1989 The Regents of the University of California.
   3  * All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Robert Paul Corbett.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #ifndef lint
  38 static char sccsid[] = "@(#)lalr.c      5.3 (Berkeley) 6/1/90";
  39 #endif /* not lint */
  40
  41 #include "defs.h"
  42
  43 typedef
  44   struct shorts
  45     {
  46       struct shorts *next;
  47       short value;
  48     }
  49   shorts;
  50
  51 int tokensetsize;
  52 short *lookaheads;
  53 short *LAruleno;
  54 unsigned *LA;
  55 short *accessing_symbol;
  56 core **state_table;
  57 shifts **shift_table;
  58 reductions **reduction_table;
  59 short *goto_map;
  60 short *from_state;
  61 short *to_state;
  62
  63 static short **
  64 transpose (short **R, int n);
  65
  66 static int infinity;
  67 static int maxrhs;
  68 static int ngotos;
  69 static unsigned *F;
  70 static short **includes;
  71 static shorts **lookback;
  72 static short **R;
  73 static short *INDEX;
  74 static short *VERTICES;
  75 static int top;
  76
  77 static void
  78 set_state_table (void);
  79
  80 static void
  81 set_accessing_symbol (void);
  82
  83 static void
  84 set_shift_table (void);
  85
  86 static void
  87 set_reduction_table (void);
  88
  89 static void
  90 set_maxrhs (void);
  91
  92 static void
  93 initialize_LA (void);
  94
  95 static void
  96 set_goto_map (void);
  97
  98 static void
  99 initialize_F (void);
 100
 101 static void
 102 build_relations (void);
 103
 104 static void
 105 compute_FOLLOWS (void);
 106
 107 static void
 108 compute_lookaheads (void);
 109
 110 static void
 111 traverse (int i);
 112
 113 static void
 114 digraph (short **relation);
 115
 116 static void
 117 add_lookback_edge (int stateno, int ruleno, int gotono);
 118
 119 void
 120 lalr (void)
 121 {
 122     tokensetsize = WORDSIZE(ntokens);
 123
 124     set_state_table();
 125     set_accessing_symbol();
 126     set_shift_table();
 127     set_reduction_table();
 128     set_maxrhs();
 129     initialize_LA();
 130     set_goto_map();
 131     initialize_F();
 132     build_relations();
 133     compute_FOLLOWS();
 134     compute_lookaheads();
 135 }
 136
 137 static void
 138 set_state_table (void)
 139 {
 140     register core *sp;
 141
 142     state_table = NEW2(nstates, core *);
 143     for (sp = first_state; sp; sp = sp->next)
 144         state_table[sp->number] = sp;
 145 }
 146
 147 static void
 148 set_accessing_symbol (void)
 149 {
 150     register core *sp;
 151
 152     accessing_symbol = NEW2(nstates, short);
 153     for (sp = first_state; sp; sp = sp->next)
 154         accessing_symbol[sp->number] = sp->accessing_symbol;
 155 }
 156
 157 static void
 158 set_shift_table (void)
 159 {
 160     register shifts *sp;
 161
 162     shift_table = NEW2(nstates, shifts *);
 163     for (sp = first_shift; sp; sp = sp->next)
 164         shift_table[sp->number] = sp;
 165 }
 166
 167 static void
 168 set_reduction_table (void)
 169 {
 170     register reductions *rp;
 171
 172     reduction_table = NEW2(nstates, reductions *);
 173     for (rp = first_reduction; rp; rp = rp->next)
 174         reduction_table[rp->number] = rp;
 175 }
 176
 177 static void
 178 set_maxrhs (void)
 179 {
 180   register short *itemp;
 181   register short *item_end;
 182   register int length;
 183   register int max;
 184
 185   length = 0;
 186   max = 0;
 187   item_end = ritem + nitems;
 188   for (itemp = ritem; itemp < item_end; itemp++)
 189     {
 190       if (*itemp >= 0)
 191         {
 192           length++;
 193         }
 194       else
 195         {
 196           if (length > max) max = length;
 197           length = 0;
 198         }
 199     }
 200
 201   maxrhs = max;
 202 }
 203
 204 static void
 205 initialize_LA (void)
 206 {
 207   register int i, j, k;
 208   register reductions *rp;
 209
 210   lookaheads = NEW2(nstates + 1, short);
 211
 212   k = 0;
 213   for (i = 0; i < nstates; i++)
 214     {
 215       lookaheads[i] = k;
 216       rp = reduction_table[i];
 217       if (rp)
 218         k += rp->nreds;
 219     }
 220   lookaheads[nstates] = k;
 221
 222   LA = NEW2(k * tokensetsize, unsigned);
 223   LAruleno = NEW2(k, short);
 224   lookback = NEW2(k, shorts *);
 225
 226   k = 0;
 227   for (i = 0; i < nstates; i++)
 228     {
 229       rp = reduction_table[i];
 230       if (rp)
 231         {
 232           for (j = 0; j < rp->nreds; j++)
 233             {
 234               LAruleno[k] = rp->rules[j];
 235               k++;
 236             }
 237         }
 238     }
 239 }
 240
 241 static void
 242 set_goto_map (void)
 243 {
 244   register shifts *sp;
 245   register int i;
 246   register int symbol;
 247   register int k;
 248   register short *temp_map;
 249   register int state2;
 250   register int state1;
 251
 252   goto_map = NEW2(nvars + 1, short) - ntokens;
 253   temp_map = NEW2(nvars + 1, short) - ntokens;
 254
 255   ngotos = 0;
 256   for (sp = first_shift; sp; sp = sp->next)
 257     {
 258       for (i = sp->nshifts - 1; i >= 0; i--)
 259         {
 260           symbol = accessing_symbol[sp->shift[i]];
 261
 262           if (ISTOKEN(symbol)) break;
 263
 264           if (ngotos == MAXSHORT)
 265             fatal("too many gotos");
 266
 267           ngotos++;
 268           goto_map[symbol]++;
 269         }
 270     }
 271
 272   k = 0;
 273   for (i = ntokens; i < nsyms; i++)
 274     {
 275       temp_map[i] = k;
 276       k += goto_map[i];
 277     }
 278
 279   for (i = ntokens; i < nsyms; i++)
 280     goto_map[i] = temp_map[i];
 281
 282   goto_map[nsyms] = ngotos;
 283   temp_map[nsyms] = ngotos;
 284
 285   from_state = NEW2(ngotos, short);
 286   to_state = NEW2(ngotos, short);
 287
 288   for (sp = first_shift; sp; sp = sp->next)
 289     {
 290       state1 = sp->number;
 291       for (i = sp->nshifts - 1; i >= 0; i--)
 292         {
 293           state2 = sp->shift[i];
 294           symbol = accessing_symbol[state2];
 295
 296           if (ISTOKEN(symbol)) break;
 297
 298           k = temp_map[symbol]++;
 299           from_state[k] = state1;
 300           to_state[k] = state2;
 301         }
 302     }
 303
 304   FREE(temp_map + ntokens);
 305 }
 306
 307
 308
 309 /*  Map_goto maps a state/symbol pair into its numeric representation.  */
 310
 311 static int
 312 map_goto (int state, int symbol)
 313 {
 314     register int high;
 315     register int low;
 316     register int middle;
 317     register int s;
 318
 319     low = goto_map[symbol];
 320     high = goto_map[symbol + 1];
 321
 322     for (;;)
 323     {
 324         assert(low <= high);
 325         middle = (low + high) >> 1;
 326         s = from_state[middle];
 327         if (s == state)
 328             return (middle);
 329         else if (s < state)
 330             low = middle + 1;
 331         else
 332             high = middle - 1;
 333     }
 334 }
 335
 336 static void
 337 initialize_F (void)
 338 {
 339   register int i;
 340   register int j;
 341   register int k;
 342   register shifts *sp;
 343   register short *edge;
 344   register unsigned *rowp;
 345   register short *rp;
 346   register short **reads;
 347   register int nedges;
 348   register int stateno;
 349   register int symbol;
 350   register int nwords;
 351
 352   nwords = ngotos * tokensetsize;
 353   F = NEW2(nwords, unsigned);
 354
 355   reads = NEW2(ngotos, short *);
 356   edge = NEW2(ngotos + 1, short);
 357   nedges = 0;
 358
 359   rowp = F;
 360   for (i = 0; i < ngotos; i++)
 361     {
 362       stateno = to_state[i];
 363       sp = shift_table[stateno];
 364
 365       if (sp)
 366         {
 367           k = sp->nshifts;
 368
 369           for (j = 0; j < k; j++)
 370             {
 371               symbol = accessing_symbol[sp->shift[j]];
 372               if (ISVAR(symbol))
 373                 break;
 374               SETBIT(rowp, symbol);
 375             }
 376
 377           for (; j < k; j++)
 378             {
 379               symbol = accessing_symbol[sp->shift[j]];
 380               if (nullable[symbol])
 381                 edge[nedges++] = map_goto(stateno, symbol);
 382             }
 383
 384           if (nedges)
 385             {
 386               reads[i] = rp = NEW2(nedges + 1, short);
 387
 388               for (j = 0; j < nedges; j++)
 389                 rp[j] = edge[j];
 390
 391               rp[nedges] = -1;
 392               nedges = 0;
 393             }
 394         }
 395
 396       rowp += tokensetsize;
 397     }
 398
 399   SETBIT(F, 0);
 400   digraph(reads);
 401
 402   for (i = 0; i < ngotos; i++)
 403     {
 404       if (reads[i])
 405         FREE(reads[i]);
 406     }
 407
 408   FREE(reads);
 409   FREE(edge);
 410 }
 411
 412 static void
 413 build_relations (void)
 414 {
 415   register int i;
 416   register int j;
 417   register int k;
 418   register short *rulep;
 419   register short *rp;
 420   register shifts *sp;
 421   register int length;
 422   register int nedges;
 423   register int done;
 424   register int state1;
 425   register int stateno;
 426   register int symbol1;
 427   register int symbol2;
 428   register short *shortp;
 429   register short *edge;
 430   register short *states;
 431   register short **new_includes;
 432
 433   includes = NEW2(ngotos, short *);
 434   edge = NEW2(ngotos + 1, short);
 435   states = NEW2(maxrhs + 1, short);
 436
 437   for (i = 0; i < ngotos; i++)
 438     {
 439       nedges = 0;
 440       state1 = from_state[i];
 441       symbol1 = accessing_symbol[to_state[i]];
 442
 443       for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
 444         {
 445           length = 1;
 446           states[0] = state1;
 447           stateno = state1;
 448
 449           for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
 450             {
 451               symbol2 = *rp;
 452               sp = shift_table[stateno];
 453               k = sp->nshifts;
 454
 455               for (j = 0; j < k; j++)
 456                 {
 457                   stateno = sp->shift[j];
 458                   if (accessing_symbol[stateno] == symbol2) break;
 459                 }
 460
 461               states[length++] = stateno;
 462             }
 463
 464           add_lookback_edge(stateno, *rulep, i);
 465
 466           length--;
 467           done = 0;
 468           while (!done)
 469             {
 470               done = 1;
 471               rp--;
 472               if (ISVAR(*rp))
 473                 {
 474                   stateno = states[--length];
 475                   edge[nedges++] = map_goto(stateno, *rp);
 476                   if (nullable[*rp] && length > 0) done = 0;
 477                 }
 478             }
 479         }
 480
 481       if (nedges)
 482         {
 483           includes[i] = shortp = NEW2(nedges + 1, short);
 484           for (j = 0; j < nedges; j++)
 485             shortp[j] = edge[j];
 486           shortp[nedges] = -1;
 487         }
 488     }
 489
 490   new_includes = transpose(includes, ngotos);
 491
 492   for (i = 0; i < ngotos; i++)
 493     if (includes[i])
 494       FREE(includes[i]);
 495
 496   FREE(includes);
 497
 498   includes = new_includes;
 499
 500   FREE(edge);
 501   FREE(states);
 502 }
 503
 504 static void
 505 add_lookback_edge (int stateno, int ruleno, int gotono)
 506 {
 507     register int i, k;
 508     register int found;
 509     register shorts *sp;
 510
 511     i = lookaheads[stateno];
 512     k = lookaheads[stateno + 1];
 513     found = 0;
 514     while (!found && i < k)
 515     {
 516         if (LAruleno[i] == ruleno)
 517             found = 1;
 518         else
 519             ++i;
 520     }
 521     assert(found);
 522
 523     sp = NEW(shorts);
 524     sp->next = lookback[i];
 525     sp->value = gotono;
 526     lookback[i] = sp;
 527 }
 528
 529 static short **
 530 transpose (short **R, int n)
 531 {
 532   register short **new_R;
 533   register short **temp_R;
 534   register short *nedges;
 535   register short *sp;
 536   register int i;
 537   register int k;
 538
 539   nedges = NEW2(n, short);
 540
 541   for (i = 0; i < n; i++)
 542     {
 543       sp = R[i];
 544       if (sp)
 545         {
 546           while (*sp >= 0)
 547             nedges[*sp++]++;
 548         }
 549     }
 550
 551   new_R = NEW2(n, short *);
 552   temp_R = NEW2(n, short *);
 553
 554   for (i = 0; i < n; i++)
 555     {
 556       k = nedges[i];
 557       if (k > 0)
 558         {
 559           sp = NEW2(k + 1, short);
 560           new_R[i] = sp;
 561           temp_R[i] = sp;
 562           sp[k] = -1;
 563         }
 564     }
 565
 566   FREE(nedges);
 567
 568   for (i = 0; i < n; i++)
 569     {
 570       sp = R[i];
 571       if (sp)
 572         {
 573           while (*sp >= 0)
 574             *temp_R[*sp++]++ = i;
 575         }
 576     }
 577
 578   FREE(temp_R);
 579
 580   return (new_R);
 581 }
 582
 583 static void
 584 compute_FOLLOWS (void)
 585 {
 586   digraph(includes);
 587 }
 588
 589 static void
 590 compute_lookaheads (void)
 591 {
 592   register int i, n;
 593   register unsigned *fp1, *fp2, *fp3;
 594   register shorts *sp, *next;
 595   register unsigned *rowp;
 596
 597   rowp = LA;
 598   n = lookaheads[nstates];
 599   for (i = 0; i < n; i++)
 600     {
 601       fp3 = rowp + tokensetsize;
 602       for (sp = lookback[i]; sp; sp = sp->next)
 603         {
 604           fp1 = rowp;
 605           fp2 = F + tokensetsize * sp->value;
 606           while (fp1 < fp3)
 607             *fp1++ |= *fp2++;
 608         }
 609       rowp = fp3;
 610     }
 611
 612   for (i = 0; i < n; i++)
 613     for (sp = lookback[i]; sp; sp = next)
 614       {
 615         next = sp->next;
 616         FREE(sp);
 617       }
 618
 619   FREE(lookback);
 620   FREE(F);
 621 }
 622
 623 static void
 624 digraph (short **relation)
 625 {
 626   register int i;
 627
 628   infinity = ngotos + 2;
 629   INDEX = NEW2(ngotos + 1, short);
 630   VERTICES = NEW2(ngotos + 1, short);
 631   top = 0;
 632
 633   R = relation;
 634
 635   for (i = 0; i < ngotos; i++)
 636     INDEX[i] = 0;
 637
 638   for (i = 0; i < ngotos; i++)
 639     {
 640       if (INDEX[i] == 0 && R[i])
 641         traverse(i);
 642     }
 643
 644   FREE(INDEX);
 645   FREE(VERTICES);
 646 }
 647
 648 static void
 649 traverse (int i)
 650 {
 651   register unsigned *fp1;
 652   register unsigned *fp2;
 653   register unsigned *fp3;
 654   register int j;
 655   register short *rp;
 656
 657   int height;
 658   unsigned *base;
 659
 660   VERTICES[++top] = i;
 661   INDEX[i] = height = top;
 662
 663   base = F + i * tokensetsize;
 664   fp3 = base + tokensetsize;
 665
 666   rp = R[i];
 667   if (rp)
 668     {
 669       while ((j = *rp++) >= 0)
 670         {
 671           if (INDEX[j] == 0)
 672             traverse(j);
 673
 674           if (INDEX[i] > INDEX[j])
 675             INDEX[i] = INDEX[j];
 676
 677           fp1 = base;
 678           fp2 = F + j * tokensetsize;
 679
 680           while (fp1 < fp3)
 681             *fp1++ |= *fp2++;
 682         }
 683     }
 684
 685   if (INDEX[i] == height)
 686     {
 687       for (;;)
 688         {
 689           j = VERTICES[top--];
 690           INDEX[j] = infinity;
 691
 692           if (i == j)
 693             break;
 694
 695           fp1 = base;
 696           fp2 = F + j * tokensetsize;
 697
 698           while (fp1 < fp3)
 699             *fp2++ = *fp1++;
 700         }
 701     }
 702 }