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