usr.bin/yacc/lalr.c

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