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 short **transpose();
  64
  65 static int infinity;
  66 static int maxrhs;
  67 static int ngotos;
  68 static unsigned *F;
  69 static short **includes;
  70 static shorts **lookback;
  71 static short **R;
  72 static short *INDEX;
  73 static short *VERTICES;
  74 static int top;
  75
  76
  77 lalr()
  78 {
  79     tokensetsize = WORDSIZE(ntokens);
  80
  81     set_state_table();
  82     set_accessing_symbol();
  83     set_shift_table();
  84     set_reduction_table();
  85     set_maxrhs();
  86     initialize_LA();
  87     set_goto_map();
  88     initialize_F();
  89     build_relations();
  90     compute_FOLLOWS();
  91     compute_lookaheads();
  92 }
  93
  94
  95
  96 set_state_table()
  97 {
  98     register core *sp;
  99
 100     state_table = NEW2(nstates, core *);
 101     for (sp = first_state; sp; sp = sp->next)
 102         state_table[sp->number] = sp;
 103 }
 104
 105
 106
 107 set_accessing_symbol()
 108 {
 109     register core *sp;
 110
 111     accessing_symbol = NEW2(nstates, short);
 112     for (sp = first_state; sp; sp = sp->next)
 113         accessing_symbol[sp->number] = sp->accessing_symbol;
 114 }
 115
 116
 117
 118 set_shift_table()
 119 {
 120     register shifts *sp;
 121
 122     shift_table = NEW2(nstates, shifts *);
 123     for (sp = first_shift; sp; sp = sp->next)
 124         shift_table[sp->number] = sp;
 125 }
 126
 127
 128
 129 set_reduction_table()
 130 {
 131     register reductions *rp;
 132
 133     reduction_table = NEW2(nstates, reductions *);
 134     for (rp = first_reduction; rp; rp = rp->next)
 135         reduction_table[rp->number] = rp;
 136 }
 137
 138
 139
 140 set_maxrhs()
 141 {
 142   register short *itemp;
 143   register short *item_end;
 144   register int length;
 145   register int max;
 146
 147   length = 0;
 148   max = 0;
 149   item_end = ritem + nitems;
 150   for (itemp = ritem; itemp < item_end; itemp++)
 151     {
 152       if (*itemp >= 0)
 153         {
 154           length++;
 155         }
 156       else
 157         {
 158           if (length > max) max = length;
 159           length = 0;
 160         }
 161     }
 162
 163   maxrhs = max;
 164 }
 165
 166
 167
 168 initialize_LA()
 169 {
 170   register int i, j, k;
 171   register reductions *rp;
 172
 173   lookaheads = NEW2(nstates + 1, short);
 174
 175   k = 0;
 176   for (i = 0; i < nstates; i++)
 177     {
 178       lookaheads[i] = k;
 179       rp = reduction_table[i];
 180       if (rp)
 181         k += rp->nreds;
 182     }
 183   lookaheads[nstates] = k;
 184
 185   LA = NEW2(k * tokensetsize, unsigned);
 186   LAruleno = NEW2(k, short);
 187   lookback = NEW2(k, shorts *);
 188
 189   k = 0;
 190   for (i = 0; i < nstates; i++)
 191     {
 192       rp = reduction_table[i];
 193       if (rp)
 194         {
 195           for (j = 0; j < rp->nreds; j++)
 196             {
 197               LAruleno[k] = rp->rules[j];
 198               k++;
 199             }
 200         }
 201     }
 202 }
 203
 204
 205 set_goto_map()
 206 {
 207   register shifts *sp;
 208   register int i;
 209   register int symbol;
 210   register int k;
 211   register short *temp_map;
 212   register int state2;
 213   register int state1;
 214
 215   goto_map = NEW2(nvars + 1, short) - ntokens;
 216   temp_map = NEW2(nvars + 1, short) - ntokens;
 217
 218   ngotos = 0;
 219   for (sp = first_shift; sp; sp = sp->next)
 220     {
 221       for (i = sp->nshifts - 1; i >= 0; i--)
 222         {
 223           symbol = accessing_symbol[sp->shift[i]];
 224
 225           if (ISTOKEN(symbol)) break;
 226
 227           if (ngotos == MAXSHORT)
 228             fatal("too many gotos");
 229
 230           ngotos++;
 231           goto_map[symbol]++;
 232         }
 233     }
 234
 235   k = 0;
 236   for (i = ntokens; i < nsyms; i++)
 237     {
 238       temp_map[i] = k;
 239       k += goto_map[i];
 240     }
 241
 242   for (i = ntokens; i < nsyms; i++)
 243     goto_map[i] = temp_map[i];
 244
 245   goto_map[nsyms] = ngotos;
 246   temp_map[nsyms] = ngotos;
 247
 248   from_state = NEW2(ngotos, short);
 249   to_state = NEW2(ngotos, short);
 250
 251   for (sp = first_shift; sp; sp = sp->next)
 252     {
 253       state1 = sp->number;
 254       for (i = sp->nshifts - 1; i >= 0; i--)
 255         {
 256           state2 = sp->shift[i];
 257           symbol = accessing_symbol[state2];
 258
 259           if (ISTOKEN(symbol)) break;
 260
 261           k = temp_map[symbol]++;
 262           from_state[k] = state1;
 263           to_state[k] = state2;
 264         }
 265     }
 266
 267   FREE(temp_map + ntokens);
 268 }
 269
 270
 271
 272 /*  Map_goto maps a state/symbol pair into its numeric representation.  */
 273
 274 int
 275 map_goto(state, symbol)
 276 int state;
 277 int symbol;
 278 {
 279     register int high;
 280     register int low;
 281     register int middle;
 282     register int s;
 283
 284     low = goto_map[symbol];
 285     high = goto_map[symbol + 1];
 286
 287     for (;;)
 288     {
 289         assert(low <= high);
 290         middle = (low + high) >> 1;
 291         s = from_state[middle];
 292         if (s == state)
 293             return (middle);
 294         else if (s < state)
 295             low = middle + 1;
 296         else
 297             high = middle - 1;
 298     }
 299 }
 300
 301
 302
 303 initialize_F()
 304 {
 305   register int i;
 306   register int j;
 307   register int k;
 308   register shifts *sp;
 309   register short *edge;
 310   register unsigned *rowp;
 311   register short *rp;
 312   register short **reads;
 313   register int nedges;
 314   register int stateno;
 315   register int symbol;
 316   register int nwords;
 317
 318   nwords = ngotos * tokensetsize;
 319   F = NEW2(nwords, unsigned);
 320
 321   reads = NEW2(ngotos, short *);
 322   edge = NEW2(ngotos + 1, short);
 323   nedges = 0;
 324
 325   rowp = F;
 326   for (i = 0; i < ngotos; i++)
 327     {
 328       stateno = to_state[i];
 329       sp = shift_table[stateno];
 330
 331       if (sp)
 332         {
 333           k = sp->nshifts;
 334
 335           for (j = 0; j < k; j++)
 336             {
 337               symbol = accessing_symbol[sp->shift[j]];
 338               if (ISVAR(symbol))
 339                 break;
 340               SETBIT(rowp, symbol);
 341             }
 342
 343           for (; j < k; j++)
 344             {
 345               symbol = accessing_symbol[sp->shift[j]];
 346               if (nullable[symbol])
 347                 edge[nedges++] = map_goto(stateno, symbol);
 348             }
 349
 350           if (nedges)
 351             {
 352               reads[i] = rp = NEW2(nedges + 1, short);
 353
 354               for (j = 0; j < nedges; j++)
 355                 rp[j] = edge[j];
 356
 357               rp[nedges] = -1;
 358               nedges = 0;
 359             }
 360         }
 361
 362       rowp += tokensetsize;
 363     }
 364
 365   SETBIT(F, 0);
 366   digraph(reads);
 367
 368   for (i = 0; i < ngotos; i++)
 369     {
 370       if (reads[i])
 371         FREE(reads[i]);
 372     }
 373
 374   FREE(reads);
 375   FREE(edge);
 376 }
 377
 378
 379
 380 build_relations()
 381 {
 382   register int i;
 383   register int j;
 384   register int k;
 385   register short *rulep;
 386   register short *rp;
 387   register shifts *sp;
 388   register int length;
 389   register int nedges;
 390   register int done;
 391   register int state1;
 392   register int stateno;
 393   register int symbol1;
 394   register int symbol2;
 395   register short *shortp;
 396   register short *edge;
 397   register short *states;
 398   register short **new_includes;
 399
 400   includes = NEW2(ngotos, short *);
 401   edge = NEW2(ngotos + 1, short);
 402   states = NEW2(maxrhs + 1, short);
 403
 404   for (i = 0; i < ngotos; i++)
 405     {
 406       nedges = 0;
 407       state1 = from_state[i];
 408       symbol1 = accessing_symbol[to_state[i]];
 409
 410       for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
 411         {
 412           length = 1;
 413           states[0] = state1;
 414           stateno = state1;
 415
 416           for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
 417             {
 418               symbol2 = *rp;
 419               sp = shift_table[stateno];
 420               k = sp->nshifts;
 421
 422               for (j = 0; j < k; j++)
 423                 {
 424                   stateno = sp->shift[j];
 425                   if (accessing_symbol[stateno] == symbol2) break;
 426                 }
 427
 428               states[length++] = stateno;
 429             }
 430
 431           add_lookback_edge(stateno, *rulep, i);
 432
 433           length--;
 434           done = 0;
 435           while (!done)
 436             {
 437               done = 1;
 438               rp--;
 439               if (ISVAR(*rp))
 440                 {
 441                   stateno = states[--length];
 442                   edge[nedges++] = map_goto(stateno, *rp);
 443                   if (nullable[*rp] && length > 0) done = 0;
 444                 }
 445             }
 446         }
 447
 448       if (nedges)
 449         {
 450           includes[i] = shortp = NEW2(nedges + 1, short);
 451           for (j = 0; j < nedges; j++)
 452             shortp[j] = edge[j];
 453           shortp[nedges] = -1;
 454         }
 455     }
 456
 457   new_includes = transpose(includes, ngotos);
 458
 459   for (i = 0; i < ngotos; i++)
 460     if (includes[i])
 461       FREE(includes[i]);
 462
 463   FREE(includes);
 464
 465   includes = new_includes;
 466
 467   FREE(edge);
 468   FREE(states);
 469 }
 470
 471
 472 add_lookback_edge(stateno, ruleno, gotono)
 473 int stateno, ruleno, gotono;
 474 {
 475     register int i, k;
 476     register int found;
 477     register shorts *sp;
 478
 479     i = lookaheads[stateno];
 480     k = lookaheads[stateno + 1];
 481     found = 0;
 482     while (!found && i < k)
 483     {
 484         if (LAruleno[i] == ruleno)
 485             found = 1;
 486         else
 487             ++i;
 488     }
 489     assert(found);
 490
 491     sp = NEW(shorts);
 492     sp->next = lookback[i];
 493     sp->value = gotono;
 494     lookback[i] = sp;
 495 }
 496
 497
 498
 499 short **
 500 transpose(R, n)
 501 short **R;
 502 int n;
 503 {
 504   register short **new_R;
 505   register short **temp_R;
 506   register short *nedges;
 507   register short *sp;
 508   register int i;
 509   register int k;
 510
 511   nedges = NEW2(n, short);
 512
 513   for (i = 0; i < n; i++)
 514     {
 515       sp = R[i];
 516       if (sp)
 517         {
 518           while (*sp >= 0)
 519             nedges[*sp++]++;
 520         }
 521     }
 522
 523   new_R = NEW2(n, short *);
 524   temp_R = NEW2(n, short *);
 525
 526   for (i = 0; i < n; i++)
 527     {
 528       k = nedges[i];
 529       if (k > 0)
 530         {
 531           sp = NEW2(k + 1, short);
 532           new_R[i] = sp;
 533           temp_R[i] = sp;
 534           sp[k] = -1;
 535         }
 536     }
 537
 538   FREE(nedges);
 539
 540   for (i = 0; i < n; i++)
 541     {
 542       sp = R[i];
 543       if (sp)
 544         {
 545           while (*sp >= 0)
 546             *temp_R[*sp++]++ = i;
 547         }
 548     }
 549
 550   FREE(temp_R);
 551
 552   return (new_R);
 553 }
 554
 555
 556
 557 compute_FOLLOWS()
 558 {
 559   digraph(includes);
 560 }
 561
 562
 563 compute_lookaheads()
 564 {
 565   register int i, n;
 566   register unsigned *fp1, *fp2, *fp3;
 567   register shorts *sp, *next;
 568   register unsigned *rowp;
 569
 570   rowp = LA;
 571   n = lookaheads[nstates];
 572   for (i = 0; i < n; i++)
 573     {
 574       fp3 = rowp + tokensetsize;
 575       for (sp = lookback[i]; sp; sp = sp->next)
 576         {
 577           fp1 = rowp;
 578           fp2 = F + tokensetsize * sp->value;
 579           while (fp1 < fp3)
 580             *fp1++ |= *fp2++;
 581         }
 582       rowp = fp3;
 583     }
 584
 585   for (i = 0; i < n; i++)
 586     for (sp = lookback[i]; sp; sp = next)
 587       {
 588         next = sp->next;
 589         FREE(sp);
 590       }
 591
 592   FREE(lookback);
 593   FREE(F);
 594 }
 595
 596
 597 digraph(relation)
 598 short **relation;
 599 {
 600   register int i;
 601
 602   infinity = ngotos + 2;
 603   INDEX = NEW2(ngotos + 1, short);
 604   VERTICES = NEW2(ngotos + 1, short);
 605   top = 0;
 606
 607   R = relation;
 608
 609   for (i = 0; i < ngotos; i++)
 610     INDEX[i] = 0;
 611
 612   for (i = 0; i < ngotos; i++)
 613     {
 614       if (INDEX[i] == 0 && R[i])
 615         traverse(i);
 616     }
 617
 618   FREE(INDEX);
 619   FREE(VERTICES);
 620 }
 621
 622
 623
 624 traverse(i)
 625 register int i;
 626 {
 627   register unsigned *fp1;
 628   register unsigned *fp2;
 629   register unsigned *fp3;
 630   register int j;
 631   register short *rp;
 632
 633   int height;
 634   unsigned *base;
 635
 636   VERTICES[++top] = i;
 637   INDEX[i] = height = top;
 638
 639   base = F + i * tokensetsize;
 640   fp3 = base + tokensetsize;
 641
 642   rp = R[i];
 643   if (rp)
 644     {
 645       while ((j = *rp++) >= 0)
 646         {
 647           if (INDEX[j] == 0)
 648             traverse(j);
 649
 650           if (INDEX[i] > INDEX[j])
 651             INDEX[i] = INDEX[j];
 652
 653           fp1 = base;
 654           fp2 = F + j * tokensetsize;
 655
 656           while (fp1 < fp3)
 657             *fp1++ |= *fp2++;
 658         }
 659     }
 660
 661   if (INDEX[i] == height)
 662     {
 663       for (;;)
 664         {
 665           j = VERTICES[top--];
 666           INDEX[j] = infinity;
 667
 668           if (i == j)
 669             break;
 670
 671           fp1 = base;
 672           fp2 = F + j * tokensetsize;
 673
 674           while (fp1 < fp3)
 675             *fp2++ = *fp1++;
 676         }
 677     }
 678 }