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