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