src/lalr.c

   1 /* Compute look-ahead criteria for bison,
   2    Copyright 1984, 1986, 1989, 2000 Free Software Foundation, Inc.
   3
   4    This file is part of Bison, the GNU Compiler Compiler.
   5
   6    Bison is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    Bison is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with Bison; see the file COPYING.  If not, write to
  18    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19    Boston, MA 02111-1307, USA.  */
  20
  21
  22 /* Compute how to make the finite state machine deterministic; find
  23    which rules need lookahead in each state, and which lookahead
  24    tokens they accept.  */
  25
  26 #include "system.h"
  27 #include "types.h"
  28 #include "LR0.h"
  29 #include "gram.h"
  30 #include "complain.h"
  31 #include "lalr.h"
  32 #include "nullable.h"
  33 #include "derives.h"
  34
  35 /* All the decorated states, indexed by the state number.  Warning:
  36    there is a state_TABLE in LR0.c, but it is different and static.
  37    */
  38 state_t *state_table = NULL;
  39
  40 int tokensetsize;
  41 short *lookaheads;
  42 short *LAruleno;
  43 unsigned *LA;
  44
  45 char *consistent;
  46 shifts **shift_table;
  47 reductions **reduction_table;
  48 short *goto_map;
  49 short *from_state;
  50 short *to_state;
  51
  52 extern void berror PARAMS ((const char *));
  53
  54 static int infinity;
  55 static int maxrhs;
  56 static int ngotos;
  57 static unsigned *F;
  58 static short **includes;
  59 static shorts **lookback;
  60 static short **R;
  61 static short *INDEX;
  62 static short *VERTICES;
  63 static int top;
  64
  65
  66 static void
  67 traverse (int i)
  68 {
  69   unsigned *fp1;
  70   unsigned *fp2;
  71   unsigned *fp3;
  72   int j;
  73   short *rp;
  74
  75   int height;
  76   unsigned *base;
  77
  78   VERTICES[++top] = i;
  79   INDEX[i] = height = top;
  80
  81   base = F + i * tokensetsize;
  82   fp3 = base + tokensetsize;
  83
  84   rp = R[i];
  85   if (rp)
  86     {
  87       while ((j = *rp++) >= 0)
  88         {
  89           if (INDEX[j] == 0)
  90             traverse (j);
  91
  92           if (INDEX[i] > INDEX[j])
  93             INDEX[i] = INDEX[j];
  94
  95           fp1 = base;
  96           fp2 = F + j * tokensetsize;
  97
  98           while (fp1 < fp3)
  99             *fp1++ |= *fp2++;
 100         }
 101     }
 102
 103   if (INDEX[i] == height)
 104     {
 105       for (;;)
 106         {
 107           j = VERTICES[top--];
 108           INDEX[j] = infinity;
 109
 110           if (i == j)
 111             break;
 112
 113           fp1 = base;
 114           fp2 = F + j * tokensetsize;
 115
 116           while (fp1 < fp3)
 117             *fp2++ = *fp1++;
 118         }
 119     }
 120 }
 121
 122
 123 static void
 124 digraph (short **relation)
 125 {
 126   int i;
 127
 128   infinity = ngotos + 2;
 129   INDEX = XCALLOC (short, ngotos + 1);
 130   VERTICES = XCALLOC (short, ngotos + 1);
 131   top = 0;
 132
 133   R = relation;
 134
 135   for (i = 0; i < ngotos; i++)
 136     INDEX[i] = 0;
 137
 138   for (i = 0; i < ngotos; i++)
 139     {
 140       if (INDEX[i] == 0 && R[i])
 141         traverse (i);
 142     }
 143
 144   XFREE (INDEX);
 145   XFREE (VERTICES);
 146 }
 147
 148 static void
 149 set_state_table (void)
 150 {
 151   core *sp;
 152
 153   state_table = XCALLOC (state_t, nstates);
 154
 155   for (sp = first_state; sp; sp = sp->next)
 156     {
 157       state_table[sp->number].state = sp;
 158       state_table[sp->number].accessing_symbol = sp->accessing_symbol;
 159     }
 160 }
 161
 162
 163 static void
 164 set_shift_table (void)
 165 {
 166   shifts *sp;
 167
 168   shift_table = XCALLOC (shifts *, nstates);
 169
 170   for (sp = first_shift; sp; sp = sp->next)
 171     shift_table[sp->number] = sp;
 172 }
 173
 174
 175 static void
 176 set_reduction_table (void)
 177 {
 178   reductions *rp;
 179
 180   reduction_table = XCALLOC (reductions *, nstates);
 181
 182   for (rp = first_reduction; rp; rp = rp->next)
 183     reduction_table[rp->number] = rp;
 184 }
 185
 186
 187 static void
 188 set_maxrhs (void)
 189 {
 190   short *itemp;
 191   int length;
 192   int max;
 193
 194   length = 0;
 195   max = 0;
 196   for (itemp = ritem; *itemp; itemp++)
 197     {
 198       if (*itemp > 0)
 199         {
 200           length++;
 201         }
 202       else
 203         {
 204           if (length > max)
 205             max = length;
 206           length = 0;
 207         }
 208     }
 209
 210   maxrhs = max;
 211 }
 212
 213
 214 static void
 215 initialize_LA (void)
 216 {
 217   int i;
 218   int j;
 219   int count;
 220   reductions *rp;
 221   shifts *sp;
 222   short *np;
 223
 224   consistent = XCALLOC (char, nstates);
 225   lookaheads = XCALLOC (short, nstates + 1);
 226
 227   count = 0;
 228   for (i = 0; i < nstates; i++)
 229     {
 230       int k;
 231
 232       lookaheads[i] = count;
 233
 234       rp = reduction_table[i];
 235       sp = shift_table[i];
 236       if (rp
 237           && (rp->nreds > 1
 238               || (sp && !ISVAR (state_table[sp->shifts[0]].accessing_symbol))))
 239         count += rp->nreds;
 240       else
 241         consistent[i] = 1;
 242
 243       if (sp)
 244         for (k = 0; k < sp->nshifts; k++)
 245           if (state_table[sp->shifts[k]].accessing_symbol
 246               == error_token_number)
 247             {
 248               consistent[i] = 0;
 249               break;
 250             }
 251     }
 252
 253   lookaheads[nstates] = count;
 254
 255   if (count == 0)
 256     {
 257       LA = XCALLOC (unsigned, 1 * tokensetsize);
 258       LAruleno = XCALLOC (short, 1);
 259       lookback = XCALLOC (shorts *, 1);
 260     }
 261   else
 262     {
 263       LA = XCALLOC (unsigned, count * tokensetsize);
 264       LAruleno = XCALLOC (short, count);
 265       lookback = XCALLOC (shorts *, count);
 266     }
 267
 268   np = LAruleno;
 269   for (i = 0; i < nstates; i++)
 270     {
 271       if (!consistent[i])
 272         {
 273           if ((rp = reduction_table[i]))
 274             for (j = 0; j < rp->nreds; j++)
 275               *np++ = rp->rules[j];
 276         }
 277     }
 278 }
 279
 280
 281 static void
 282 set_goto_map (void)
 283 {
 284   shifts *sp;
 285   int i;
 286   int symbol;
 287   int k;
 288   short *temp_map;
 289   int state2;
 290   int state1;
 291
 292   goto_map = XCALLOC (short, nvars + 1) - ntokens;
 293   temp_map = XCALLOC (short, nvars + 1) - ntokens;
 294
 295   ngotos = 0;
 296   for (sp = first_shift; sp; sp = sp->next)
 297     {
 298       for (i = sp->nshifts - 1; i >= 0; i--)
 299         {
 300           symbol = state_table[sp->shifts[i]].accessing_symbol;
 301
 302           if (ISTOKEN (symbol))
 303             break;
 304
 305           if (ngotos == MAXSHORT)
 306             fatal (_("too many gotos (max %d)"), MAXSHORT);
 307
 308           ngotos++;
 309           goto_map[symbol]++;
 310         }
 311     }
 312
 313   k = 0;
 314   for (i = ntokens; i < nsyms; i++)
 315     {
 316       temp_map[i] = k;
 317       k += goto_map[i];
 318     }
 319
 320   for (i = ntokens; i < nsyms; i++)
 321     goto_map[i] = temp_map[i];
 322
 323   goto_map[nsyms] = ngotos;
 324   temp_map[nsyms] = ngotos;
 325
 326   from_state = XCALLOC (short, ngotos);
 327   to_state = XCALLOC (short, ngotos);
 328
 329   for (sp = first_shift; sp; sp = sp->next)
 330     {
 331       state1 = sp->number;
 332       for (i = sp->nshifts - 1; i >= 0; i--)
 333         {
 334           state2 = sp->shifts[i];
 335           symbol = state_table[state2].accessing_symbol;
 336
 337           if (ISTOKEN (symbol))
 338             break;
 339
 340           k = temp_map[symbol]++;
 341           from_state[k] = state1;
 342           to_state[k] = state2;
 343         }
 344     }
 345
 346   XFREE (temp_map + ntokens);
 347 }
 348
 349
 350
 351 /*----------------------------------------------------------.
 352 | Map a state/symbol pair into its numeric representation.  |
 353 `----------------------------------------------------------*/
 354
 355 static int
 356 map_goto (int state, int symbol)
 357 {
 358   int high;
 359   int low;
 360   int middle;
 361   int s;
 362
 363   low = goto_map[symbol];
 364   high = goto_map[symbol + 1] - 1;
 365
 366   while (low <= high)
 367     {
 368       middle = (low + high) / 2;
 369       s = from_state[middle];
 370       if (s == state)
 371         return middle;
 372       else if (s < state)
 373         low = middle + 1;
 374       else
 375         high = middle - 1;
 376     }
 377
 378   assert (0);
 379   /* NOTREACHED */
 380   return 0;
 381 }
 382
 383
 384 static void
 385 initialize_F (void)
 386 {
 387   int i;
 388   int j;
 389   int k;
 390   shifts *sp;
 391   short *edge;
 392   unsigned *rowp;
 393   short *rp;
 394   short **reads;
 395   int nedges;
 396   int stateno;
 397   int symbol;
 398   int nwords;
 399
 400   nwords = ngotos * tokensetsize;
 401   F = XCALLOC (unsigned, nwords);
 402
 403   reads = XCALLOC (short *, ngotos);
 404   edge = XCALLOC (short, ngotos + 1);
 405   nedges = 0;
 406
 407   rowp = F;
 408   for (i = 0; i < ngotos; i++)
 409     {
 410       stateno = to_state[i];
 411       sp = shift_table[stateno];
 412
 413       if (sp)
 414         {
 415           k = sp->nshifts;
 416
 417           for (j = 0; j < k; j++)
 418             {
 419               symbol = state_table[sp->shifts[j]].accessing_symbol;
 420               if (ISVAR (symbol))
 421                 break;
 422               SETBIT (rowp, symbol);
 423             }
 424
 425           for (; j < k; j++)
 426             {
 427               symbol = state_table[sp->shifts[j]].accessing_symbol;
 428               if (nullable[symbol])
 429                 edge[nedges++] = map_goto (stateno, symbol);
 430             }
 431
 432           if (nedges)
 433             {
 434               reads[i] = rp = XCALLOC (short, nedges + 1);
 435
 436               for (j = 0; j < nedges; j++)
 437                 rp[j] = edge[j];
 438
 439               rp[nedges] = -1;
 440               nedges = 0;
 441             }
 442         }
 443
 444       rowp += tokensetsize;
 445     }
 446
 447   digraph (reads);
 448
 449   for (i = 0; i < ngotos; i++)
 450     {
 451       if (reads[i])
 452         XFREE (reads[i]);
 453     }
 454
 455   XFREE (reads);
 456   XFREE (edge);
 457 }
 458
 459
 460 static void
 461 add_lookback_edge (int stateno, int ruleno, int gotono)
 462 {
 463   int i;
 464   int k;
 465   int found;
 466   shorts *sp;
 467
 468   i = lookaheads[stateno];
 469   k = lookaheads[stateno + 1];
 470   found = 0;
 471   while (!found && i < k)
 472     {
 473       if (LAruleno[i] == ruleno)
 474         found = 1;
 475       else
 476         i++;
 477     }
 478
 479   assert (found);
 480
 481   sp = XCALLOC (shorts, 1);
 482   sp->next = lookback[i];
 483   sp->value = gotono;
 484   lookback[i] = sp;
 485 }
 486
 487
 488 static short **
 489 transpose (short **R_arg, int n)
 490 {
 491   short **new_R;
 492   short **temp_R;
 493   short *nedges;
 494   short *sp;
 495   int i;
 496   int k;
 497
 498   nedges = XCALLOC (short, n);
 499
 500   for (i = 0; i < n; i++)
 501     {
 502       sp = R_arg[i];
 503       if (sp)
 504         {
 505           while (*sp >= 0)
 506             nedges[*sp++]++;
 507         }
 508     }
 509
 510   new_R = XCALLOC (short *, n);
 511   temp_R = XCALLOC (short *, n);
 512
 513   for (i = 0; i < n; i++)
 514     {
 515       k = nedges[i];
 516       if (k > 0)
 517         {
 518           sp = XCALLOC (short, k + 1);
 519           new_R[i] = sp;
 520           temp_R[i] = sp;
 521           sp[k] = -1;
 522         }
 523     }
 524
 525   XFREE (nedges);
 526
 527   for (i = 0; i < n; i++)
 528     {
 529       sp = R_arg[i];
 530       if (sp)
 531         {
 532           while (*sp >= 0)
 533             *temp_R[*sp++]++ = i;
 534         }
 535     }
 536
 537   XFREE (temp_R);
 538
 539   return new_R;
 540 }
 541
 542
 543 static void
 544 build_relations (void)
 545 {
 546   int i;
 547   int j;
 548   int k;
 549   short *rulep;
 550   short *rp;
 551   shifts *sp;
 552   int length;
 553   int nedges;
 554   int done;
 555   int state1;
 556   int stateno;
 557   int symbol1;
 558   int symbol2;
 559   short *shortp;
 560   short *edge;
 561   short *states;
 562   short **new_includes;
 563
 564   includes = XCALLOC (short *, ngotos);
 565   edge = XCALLOC (short, ngotos + 1);
 566   states = XCALLOC (short, maxrhs + 1);
 567
 568   for (i = 0; i < ngotos; i++)
 569     {
 570       nedges = 0;
 571       state1 = from_state[i];
 572       symbol1 = state_table[to_state[i]].accessing_symbol;
 573
 574       for (rulep = derives[symbol1]; *rulep > 0; rulep++)
 575         {
 576           length = 1;
 577           states[0] = state1;
 578           stateno = state1;
 579
 580           for (rp = ritem + rrhs[*rulep]; *rp > 0; rp++)
 581             {
 582               symbol2 = *rp;
 583               sp = shift_table[stateno];
 584               k = sp->nshifts;
 585
 586               for (j = 0; j < k; j++)
 587                 {
 588                   stateno = sp->shifts[j];
 589                   if (state_table[stateno].accessing_symbol == symbol2)
 590                     break;
 591                 }
 592
 593               states[length++] = stateno;
 594             }
 595
 596           if (!consistent[stateno])
 597             add_lookback_edge (stateno, *rulep, i);
 598
 599           length--;
 600           done = 0;
 601           while (!done)
 602             {
 603               done = 1;
 604               rp--;
 605               /* JF added rp>=ritem &&   I hope to god its right! */
 606               if (rp >= ritem && ISVAR (*rp))
 607                 {
 608                   stateno = states[--length];
 609                   edge[nedges++] = map_goto (stateno, *rp);
 610                   if (nullable[*rp])
 611                     done = 0;
 612                 }
 613             }
 614         }
 615
 616       if (nedges)
 617         {
 618           includes[i] = shortp = XCALLOC (short, nedges + 1);
 619           for (j = 0; j < nedges; j++)
 620             shortp[j] = edge[j];
 621           shortp[nedges] = -1;
 622         }
 623     }
 624
 625   new_includes = transpose (includes, ngotos);
 626
 627   for (i = 0; i < ngotos; i++)
 628     if (includes[i])
 629       XFREE (includes[i]);
 630
 631   XFREE (includes);
 632
 633   includes = new_includes;
 634
 635   XFREE (edge);
 636   XFREE (states);
 637 }
 638
 639
 640
 641 static void
 642 compute_FOLLOWS (void)
 643 {
 644   int i;
 645
 646   digraph (includes);
 647
 648   for (i = 0; i < ngotos; i++)
 649     {
 650       if (includes[i])
 651         XFREE (includes[i]);
 652     }
 653
 654   XFREE (includes);
 655 }
 656
 657
 658 static void
 659 compute_lookaheads (void)
 660 {
 661   int i;
 662   int n;
 663   unsigned *fp1;
 664   unsigned *fp2;
 665   unsigned *fp3;
 666   shorts *sp;
 667   unsigned *rowp;
 668   shorts *sptmp;                /* JF */
 669
 670   rowp = LA;
 671   n = lookaheads[nstates];
 672   for (i = 0; i < n; i++)
 673     {
 674       fp3 = rowp + tokensetsize;
 675       for (sp = lookback[i]; sp; sp = sp->next)
 676         {
 677           fp1 = rowp;
 678           fp2 = F + tokensetsize * sp->value;
 679           while (fp1 < fp3)
 680             *fp1++ |= *fp2++;
 681         }
 682
 683       rowp = fp3;
 684     }
 685
 686   for (i = 0; i < n; i++)
 687     {
 688       /* JF removed ref to freed storage */
 689       for (sp = lookback[i]; sp; sp = sptmp)
 690         {
 691           sptmp = sp->next;
 692           XFREE (sp);
 693         }
 694     }
 695
 696   XFREE (lookback);
 697   XFREE (F);
 698 }
 699
 700
 701 void
 702 lalr (void)
 703 {
 704   tokensetsize = WORDSIZE (ntokens);
 705
 706   set_state_table ();
 707   set_shift_table ();
 708   set_reduction_table ();
 709   set_maxrhs ();
 710   initialize_LA ();
 711   set_goto_map ();
 712   initialize_F ();
 713   build_relations ();
 714   compute_FOLLOWS ();
 715   compute_lookaheads ();
 716 }