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.2 2003/06/17 04:29:34 dillon 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 __P((int, int, int));
  66 static void build_relations __P((void));
  67 static void compute_FOLLOWS __P((void));
  68 static void compute_lookaheads __P((void));
  69 static void digraph __P((short **));
  70 static void initialize_F __P((void));
  71 static void initialize_LA __P((void));
  72 static int map_goto __P((int, int));
  73 static void set_accessing_symbol __P((void));
  74 static void set_goto_map __P((void));
  75 static void set_maxrhs __P((void));
  76 static void set_reduction_table __P((void));
  77 static void set_shift_table __P((void));
  78 static void set_state_table __P((void));
  79 static short **transpose __P((short **, int));
  80 static void traverse __P((register 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()
  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()
 116 {
 117     register 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()
 128 {
 129     register 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()
 140 {
 141     register 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()
 152 {
 153     register 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()
 164 {
 165   register short *itemp;
 166   register short *item_end;
 167   register int length;
 168   register 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()
 193 {
 194   register int i, j, k;
 195   register 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()
 231 {
 232   register shifts *sp;
 233   register int i;
 234   register int symbol;
 235   register int k;
 236   register short *temp_map;
 237   register int state2;
 238   register 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(state, symbol)
 301 int state;
 302 int symbol;
 303 {
 304     register int high;
 305     register int low;
 306     register int middle;
 307     register int s;
 308
 309     low = goto_map[symbol];
 310     high = goto_map[symbol + 1];
 311
 312     for (;;)
 313     {
 314         assert(low <= high);
 315         middle = (low + high) >> 1;
 316         s = from_state[middle];
 317         if (s == state)
 318             return (middle);
 319         else if (s < state)
 320             low = middle + 1;
 321         else
 322             high = middle - 1;
 323     }
 324 }
 325
 326
 327
 328 static void
 329 initialize_F()
 330 {
 331   register int i;
 332   register int j;
 333   register int k;
 334   register shifts *sp;
 335   register short *edge;
 336   register unsigned *rowp;
 337   register short *rp;
 338   register short **reads;
 339   register int nedges;
 340   register int stateno;
 341   register int symbol;
 342   register int nwords;
 343
 344   nwords = ngotos * tokensetsize;
 345   F = NEW2(nwords, unsigned);
 346
 347   reads = NEW2(ngotos, short *);
 348   edge = NEW2(ngotos + 1, short);
 349   nedges = 0;
 350
 351   rowp = F;
 352   for (i = 0; i < ngotos; i++)
 353     {
 354       stateno = to_state[i];
 355       sp = shift_table[stateno];
 356
 357       if (sp)
 358         {
 359           k = sp->nshifts;
 360
 361           for (j = 0; j < k; j++)
 362             {
 363               symbol = accessing_symbol[sp->shift[j]];
 364               if (ISVAR(symbol))
 365                 break;
 366               SETBIT(rowp, symbol);
 367             }
 368
 369           for (; j < k; j++)
 370             {
 371               symbol = accessing_symbol[sp->shift[j]];
 372               if (nullable[symbol])
 373                 edge[nedges++] = map_goto(stateno, symbol);
 374             }
 375
 376           if (nedges)
 377             {
 378               reads[i] = rp = NEW2(nedges + 1, short);
 379
 380               for (j = 0; j < nedges; j++)
 381                 rp[j] = edge[j];
 382
 383               rp[nedges] = -1;
 384               nedges = 0;
 385             }
 386         }
 387
 388       rowp += tokensetsize;
 389     }
 390
 391   SETBIT(F, 0);
 392   digraph(reads);
 393
 394   for (i = 0; i < ngotos; i++)
 395     {
 396       if (reads[i])
 397         FREE(reads[i]);
 398     }
 399
 400   FREE(reads);
 401   FREE(edge);
 402 }
 403
 404
 405
 406 static void
 407 build_relations()
 408 {
 409   register int i;
 410   register int j;
 411   register int k;
 412   register short *rulep;
 413   register short *rp;
 414   register shifts *sp;
 415   register int length;
 416   register int nedges;
 417   register int done;
 418   register int state1;
 419   register int stateno;
 420   register int symbol1;
 421   register int symbol2;
 422   register short *shortp;
 423   register short *edge;
 424   register short *states;
 425   register short **new_includes;
 426
 427   includes = NEW2(ngotos, short *);
 428   edge = NEW2(ngotos + 1, short);
 429   states = NEW2(maxrhs + 1, short);
 430
 431   for (i = 0; i < ngotos; i++)
 432     {
 433       nedges = 0;
 434       state1 = from_state[i];
 435       symbol1 = accessing_symbol[to_state[i]];
 436
 437       for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
 438         {
 439           length = 1;
 440           states[0] = state1;
 441           stateno = state1;
 442
 443           for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
 444             {
 445               symbol2 = *rp;
 446               sp = shift_table[stateno];
 447               k = sp->nshifts;
 448
 449               for (j = 0; j < k; j++)
 450                 {
 451                   stateno = sp->shift[j];
 452                   if (accessing_symbol[stateno] == symbol2) break;
 453                 }
 454
 455               states[length++] = stateno;
 456             }
 457
 458           add_lookback_edge(stateno, *rulep, i);
 459
 460           length--;
 461           done = 0;
 462           while (!done)
 463             {
 464               done = 1;
 465               rp--;
 466               if (ISVAR(*rp))
 467                 {
 468                   stateno = states[--length];
 469                   edge[nedges++] = map_goto(stateno, *rp);
 470                   if (nullable[*rp] && length > 0) done = 0;
 471                 }
 472             }
 473         }
 474
 475       if (nedges)
 476         {
 477           includes[i] = shortp = NEW2(nedges + 1, short);
 478           for (j = 0; j < nedges; j++)
 479             shortp[j] = edge[j];
 480           shortp[nedges] = -1;
 481         }
 482     }
 483
 484   new_includes = transpose(includes, ngotos);
 485
 486   for (i = 0; i < ngotos; i++)
 487     if (includes[i])
 488       FREE(includes[i]);
 489
 490   FREE(includes);
 491
 492   includes = new_includes;
 493
 494   FREE(edge);
 495   FREE(states);
 496 }
 497
 498
 499 static void
 500 add_lookback_edge(stateno, ruleno, gotono)
 501 int stateno, ruleno, gotono;
 502 {
 503     register int i, k;
 504     register int found;
 505     register shorts *sp;
 506
 507     i = lookaheads[stateno];
 508     k = lookaheads[stateno + 1];
 509     found = 0;
 510     while (!found && i < k)
 511     {
 512         if (LAruleno[i] == ruleno)
 513             found = 1;
 514         else
 515             ++i;
 516     }
 517     assert(found);
 518
 519     sp = NEW(shorts);
 520     sp->next = lookback[i];
 521     sp->value = gotono;
 522     lookback[i] = sp;
 523 }
 524
 525
 526
 527 static short **
 528 transpose(R, n)
 529 short **R;
 530 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
 584
 585 static void
 586 compute_FOLLOWS()
 587 {
 588   digraph(includes);
 589 }
 590
 591
 592 static void
 593 compute_lookaheads()
 594 {
 595   register int i, n;
 596   register unsigned *fp1, *fp2, *fp3;
 597   register shorts *sp, *next;
 598   register unsigned *rowp;
 599
 600   rowp = LA;
 601   n = lookaheads[nstates];
 602   for (i = 0; i < n; i++)
 603     {
 604       fp3 = rowp + tokensetsize;
 605       for (sp = lookback[i]; sp; sp = sp->next)
 606         {
 607           fp1 = rowp;
 608           fp2 = F + tokensetsize * sp->value;
 609           while (fp1 < fp3)
 610             *fp1++ |= *fp2++;
 611         }
 612       rowp = fp3;
 613     }
 614
 615   for (i = 0; i < n; i++)
 616     for (sp = lookback[i]; sp; sp = next)
 617       {
 618         next = sp->next;
 619         FREE(sp);
 620       }
 621
 622   FREE(lookback);
 623   FREE(F);
 624 }
 625
 626
 627 static void
 628 digraph(relation)
 629 short **relation;
 630 {
 631   register int i;
 632
 633   infinity = ngotos + 2;
 634   INDEX = NEW2(ngotos + 1, short);
 635   VERTICES = NEW2(ngotos + 1, short);
 636   top = 0;
 637
 638   R = relation;
 639
 640   for (i = 0; i < ngotos; i++)
 641     INDEX[i] = 0;
 642
 643   for (i = 0; i < ngotos; i++)
 644     {
 645       if (INDEX[i] == 0 && R[i])
 646         traverse(i);
 647     }
 648
 649   FREE(INDEX);
 650   FREE(VERTICES);
 651 }
 652
 653
 654
 655 static void
 656 traverse(i)
 657 register int i;
 658 {
 659   register unsigned *fp1;
 660   register unsigned *fp2;
 661   register unsigned *fp3;
 662   register int j;
 663   register short *rp;
 664
 665   int height;
 666   unsigned *base;
 667
 668   VERTICES[++top] = i;
 669   INDEX[i] = height = top;
 670
 671   base = F + i * tokensetsize;
 672   fp3 = base + tokensetsize;
 673
 674   rp = R[i];
 675   if (rp)
 676     {
 677       while ((j = *rp++) >= 0)
 678         {
 679           if (INDEX[j] == 0)
 680             traverse(j);
 681
 682           if (INDEX[i] > INDEX[j])
 683             INDEX[i] = INDEX[j];
 684
 685           fp1 = base;
 686           fp2 = F + j * tokensetsize;
 687
 688           while (fp1 < fp3)
 689             *fp1++ |= *fp2++;
 690         }
 691     }
 692
 693   if (INDEX[i] == height)
 694     {
 695       for (;;)
 696         {
 697           j = VERTICES[top--];
 698           INDEX[j] = infinity;
 699
 700           if (i == j)
 701             break;
 702
 703           fp1 = base;
 704           fp2 = F + j * tokensetsize;
 705
 706           while (fp1 < fp3)
 707             *fp2++ = *fp1++;
 708         }
 709     }
 710 }