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