src/lalr.c

   1 /* Compute look-ahead criteria for bison,
   2    Copyright 1984, 1986, 1989, 2000, 2001  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 *LAruleno;
  42 unsigned *LA;
  43
  44 short *goto_map;
  45 short *from_state;
  46 short *to_state;
  47
  48 extern void berror PARAMS ((const char *));
  49
  50 static int infinity;
  51 static int ngotos;
  52
  53 /* And for the famous F variable, which named is so descriptive that a
  54    comment is hardly needed.  <grin>.  */
  55 static unsigned *F = NULL;
  56 #define F(Rule)  (F + (Rule) * tokensetsize)
  57
  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);
  82   fp3 = F (i + 1);
  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);
  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);
 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     if (INDEX[i] == 0 && R[i])
 140       traverse (i);
 141
 142   XFREE (INDEX);
 143   XFREE (VERTICES);
 144 }
 145
 146
 147 /*--------------------.
 148 | Build STATE_TABLE.  |
 149 `--------------------*/
 150
 151 static void
 152 set_state_table (void)
 153 {
 154   /* NSTATES + 1 because lookahead for the pseudo state number NSTATES
 155      might be used (see conflicts.c).  It is too opaque for me to
 156      provide a probably less hacky implementation. --akim */
 157   state_table = XCALLOC (state_t, nstates + 1);
 158
 159   {
 160     core *sp;
 161     for (sp = first_state; sp; sp = sp->next)
 162       {
 163         state_table[sp->number].state = sp;
 164         state_table[sp->number].accessing_symbol = sp->accessing_symbol;
 165       }
 166   }
 167
 168   {
 169     shifts *sp;
 170     for (sp = first_shift; sp; sp = sp->next)
 171       state_table[sp->number].shift_table = sp;
 172   }
 173
 174   {
 175     reductions *rp;
 176     for (rp = first_reduction; rp; rp = rp->next)
 177       state_table[rp->number].reduction_table = rp;
 178   }
 179
 180   /* Initializing the lookaheads members.  Please note that it must be
 181      performed after having set some of the other members which are
 182      used below.  Change with extreme caution.  */
 183   {
 184     int i;
 185     int count = 0;
 186     for (i = 0; i < nstates; i++)
 187       {
 188         int k;
 189         reductions *rp = state_table[i].reduction_table;
 190         shifts *sp = state_table[i].shift_table;
 191
 192         state_table[i].lookaheads = count;
 193
 194         if (rp
 195             && (rp->nreds > 1
 196                 || (sp && !ISVAR (state_table[sp->shifts[0]].accessing_symbol))))
 197           count += rp->nreds;
 198         else
 199           state_table[i].consistent = 1;
 200
 201         if (sp)
 202           for (k = 0; k < sp->nshifts; k++)
 203             if (state_table[sp->shifts[k]].accessing_symbol
 204                 == error_token_number)
 205               {
 206                 state_table[i].consistent = 0;
 207                 break;
 208               }
 209       }
 210      state_table[nstates].lookaheads = count;
 211   }
 212 }
 213
 214
 215 /* Return the size of the longest ride hand side of the rules. */
 216 static size_t
 217 maxrhs (void)
 218 {
 219   short *itemp;
 220   int length;
 221   int max;
 222
 223   length = 0;
 224   max = 0;
 225   for (itemp = ritem; *itemp; itemp++)
 226     {
 227       if (*itemp > 0)
 228         {
 229           length++;
 230         }
 231       else
 232         {
 233           if (length > max)
 234             max = length;
 235           length = 0;
 236         }
 237     }
 238
 239   return max;
 240 }
 241
 242
 243 static void
 244 initialize_LA (void)
 245 {
 246   int i;
 247   int j;
 248   short *np;
 249   reductions *rp;
 250
 251   size_t nLA = state_table[nstates].lookaheads;
 252   if (!nLA)
 253     nLA = 1;
 254
 255   LA = XCALLOC (unsigned, nLA * tokensetsize);
 256   LAruleno = XCALLOC (short, nLA);
 257   lookback = XCALLOC (shorts *, nLA);
 258
 259   np = LAruleno;
 260   for (i = 0; i < nstates; i++)
 261     if (!state_table[i].consistent)
 262       if ((rp = state_table[i].reduction_table))
 263         for (j = 0; j < rp->nreds; j++)
 264           *np++ = rp->rules[j];
 265 }
 266
 267
 268 static void
 269 set_goto_map (void)
 270 {
 271   shifts *sp;
 272   int i;
 273   int symbol;
 274   int k;
 275   short *temp_map;
 276   int state2;
 277   int state1;
 278
 279   goto_map = XCALLOC (short, nvars + 1) - ntokens;
 280   temp_map = XCALLOC (short, nvars + 1) - ntokens;
 281
 282   ngotos = 0;
 283   for (sp = first_shift; sp; sp = sp->next)
 284     {
 285       for (i = sp->nshifts - 1; i >= 0; i--)
 286         {
 287           symbol = state_table[sp->shifts[i]].accessing_symbol;
 288
 289           if (ISTOKEN (symbol))
 290             break;
 291
 292           if (ngotos == MAXSHORT)
 293             fatal (_("too many gotos (max %d)"), MAXSHORT);
 294
 295           ngotos++;
 296           goto_map[symbol]++;
 297         }
 298     }
 299
 300   k = 0;
 301   for (i = ntokens; i < nsyms; i++)
 302     {
 303       temp_map[i] = k;
 304       k += goto_map[i];
 305     }
 306
 307   for (i = ntokens; i < nsyms; i++)
 308     goto_map[i] = temp_map[i];
 309
 310   goto_map[nsyms] = ngotos;
 311   temp_map[nsyms] = ngotos;
 312
 313   from_state = XCALLOC (short, ngotos);
 314   to_state = XCALLOC (short, ngotos);
 315
 316   for (sp = first_shift; sp; sp = sp->next)
 317     {
 318       state1 = sp->number;
 319       for (i = sp->nshifts - 1; i >= 0; i--)
 320         {
 321           state2 = sp->shifts[i];
 322           symbol = state_table[state2].accessing_symbol;
 323
 324           if (ISTOKEN (symbol))
 325             break;
 326
 327           k = temp_map[symbol]++;
 328           from_state[k] = state1;
 329           to_state[k] = state2;
 330         }
 331     }
 332
 333   XFREE (temp_map + ntokens);
 334 }
 335
 336
 337
 338 /*----------------------------------------------------------.
 339 | Map a state/symbol pair into its numeric representation.  |
 340 `----------------------------------------------------------*/
 341
 342 static int
 343 map_goto (int state, int symbol)
 344 {
 345   int high;
 346   int low;
 347   int middle;
 348   int s;
 349
 350   low = goto_map[symbol];
 351   high = goto_map[symbol + 1] - 1;
 352
 353   while (low <= high)
 354     {
 355       middle = (low + high) / 2;
 356       s = from_state[middle];
 357       if (s == state)
 358         return middle;
 359       else if (s < state)
 360         low = middle + 1;
 361       else
 362         high = middle - 1;
 363     }
 364
 365   assert (0);
 366   /* NOTREACHED */
 367   return 0;
 368 }
 369
 370
 371 static void
 372 initialize_F (void)
 373 {
 374   int i;
 375   int j;
 376   int k;
 377   shifts *sp;
 378   short *edge;
 379   unsigned *rowp;
 380   short *rp;
 381   short **reads;
 382   int nedges;
 383   int stateno;
 384   int symbol;
 385   int nwords;
 386
 387   nwords = ngotos * tokensetsize;
 388   F = XCALLOC (unsigned, nwords);
 389
 390   reads = XCALLOC (short *, ngotos);
 391   edge = XCALLOC (short, ngotos + 1);
 392   nedges = 0;
 393
 394   rowp = F;
 395   for (i = 0; i < ngotos; i++)
 396     {
 397       stateno = to_state[i];
 398       sp = state_table[stateno].shift_table;
 399
 400       if (sp)
 401         {
 402           k = sp->nshifts;
 403
 404           for (j = 0; j < k; j++)
 405             {
 406               symbol = state_table[sp->shifts[j]].accessing_symbol;
 407               if (ISVAR (symbol))
 408                 break;
 409               SETBIT (rowp, symbol);
 410             }
 411
 412           for (; j < k; j++)
 413             {
 414               symbol = state_table[sp->shifts[j]].accessing_symbol;
 415               if (nullable[symbol])
 416                 edge[nedges++] = map_goto (stateno, symbol);
 417             }
 418
 419           if (nedges)
 420             {
 421               reads[i] = rp = XCALLOC (short, nedges + 1);
 422
 423               for (j = 0; j < nedges; j++)
 424                 rp[j] = edge[j];
 425
 426               rp[nedges] = -1;
 427               nedges = 0;
 428             }
 429         }
 430
 431       rowp += tokensetsize;
 432     }
 433
 434   digraph (reads);
 435
 436   for (i = 0; i < ngotos; i++)
 437     XFREE (reads[i]);
 438
 439   XFREE (reads);
 440   XFREE (edge);
 441 }
 442
 443
 444 static void
 445 add_lookback_edge (int stateno, int ruleno, int gotono)
 446 {
 447   int i;
 448   int k;
 449   int found;
 450   shorts *sp;
 451
 452   i = state_table[stateno].lookaheads;
 453   k = state_table[stateno + 1].lookaheads;
 454   found = 0;
 455   while (!found && i < k)
 456     {
 457       if (LAruleno[i] == ruleno)
 458         found = 1;
 459       else
 460         i++;
 461     }
 462
 463   assert (found);
 464
 465   sp = XCALLOC (shorts, 1);
 466   sp->next = lookback[i];
 467   sp->value = gotono;
 468   lookback[i] = sp;
 469 }
 470
 471
 472 static short **
 473 transpose (short **R_arg, int n)
 474 {
 475   short **new_R;
 476   short **temp_R;
 477   short *nedges;
 478   short *sp;
 479   int i;
 480   int k;
 481
 482   nedges = XCALLOC (short, n);
 483
 484   for (i = 0; i < n; i++)
 485     {
 486       sp = R_arg[i];
 487       if (sp)
 488         {
 489           while (*sp >= 0)
 490             nedges[*sp++]++;
 491         }
 492     }
 493
 494   new_R = XCALLOC (short *, n);
 495   temp_R = XCALLOC (short *, n);
 496
 497   for (i = 0; i < n; i++)
 498     {
 499       k = nedges[i];
 500       if (k > 0)
 501         {
 502           sp = XCALLOC (short, k + 1);
 503           new_R[i] = sp;
 504           temp_R[i] = sp;
 505           sp[k] = -1;
 506         }
 507     }
 508
 509   XFREE (nedges);
 510
 511   for (i = 0; i < n; i++)
 512     {
 513       sp = R_arg[i];
 514       if (sp)
 515         {
 516           while (*sp >= 0)
 517             *temp_R[*sp++]++ = i;
 518         }
 519     }
 520
 521   XFREE (temp_R);
 522
 523   return new_R;
 524 }
 525
 526
 527 static void
 528 build_relations (void)
 529 {
 530   int i;
 531   int j;
 532   int k;
 533   short *rulep;
 534   short *rp;
 535   shifts *sp;
 536   int length;
 537   int nedges;
 538   int done;
 539   int state1;
 540   int stateno;
 541   int symbol1;
 542   int symbol2;
 543   short *shortp;
 544   short *edge;
 545   short *states;
 546   short **new_includes;
 547
 548   includes = XCALLOC (short *, ngotos);
 549   edge = XCALLOC (short, ngotos + 1);
 550   states = XCALLOC (short, maxrhs () + 1);
 551
 552   for (i = 0; i < ngotos; i++)
 553     {
 554       nedges = 0;
 555       state1 = from_state[i];
 556       symbol1 = state_table[to_state[i]].accessing_symbol;
 557
 558       for (rulep = derives[symbol1]; *rulep > 0; rulep++)
 559         {
 560           length = 1;
 561           states[0] = state1;
 562           stateno = state1;
 563
 564           for (rp = ritem + rule_table[*rulep].rhs; *rp > 0; rp++)
 565             {
 566               symbol2 = *rp;
 567               sp = state_table[stateno].shift_table;
 568               k = sp->nshifts;
 569
 570               for (j = 0; j < k; j++)
 571                 {
 572                   stateno = sp->shifts[j];
 573                   if (state_table[stateno].accessing_symbol == symbol2)
 574                     break;
 575                 }
 576
 577               states[length++] = stateno;
 578             }
 579
 580           if (!state_table[stateno].consistent)
 581             add_lookback_edge (stateno, *rulep, i);
 582
 583           length--;
 584           done = 0;
 585           while (!done)
 586             {
 587               done = 1;
 588               rp--;
 589               /* JF added rp>=ritem &&   I hope to god its right! */
 590               if (rp >= ritem && ISVAR (*rp))
 591                 {
 592                   stateno = states[--length];
 593                   edge[nedges++] = map_goto (stateno, *rp);
 594                   if (nullable[*rp])
 595                     done = 0;
 596                 }
 597             }
 598         }
 599
 600       if (nedges)
 601         {
 602           includes[i] = shortp = XCALLOC (short, nedges + 1);
 603           for (j = 0; j < nedges; j++)
 604             shortp[j] = edge[j];
 605           shortp[nedges] = -1;
 606         }
 607     }
 608
 609   new_includes = transpose (includes, ngotos);
 610
 611   for (i = 0; i < ngotos; i++)
 612     if (includes[i])
 613       XFREE (includes[i]);
 614
 615   XFREE (includes);
 616
 617   includes = new_includes;
 618
 619   XFREE (edge);
 620   XFREE (states);
 621 }
 622
 623
 624
 625 static void
 626 compute_FOLLOWS (void)
 627 {
 628   int i;
 629
 630   digraph (includes);
 631
 632   for (i = 0; i < ngotos; i++)
 633     XFREE (includes[i]);
 634
 635   XFREE (includes);
 636 }
 637
 638
 639 static void
 640 compute_lookaheads (void)
 641 {
 642   int i;
 643   shorts *sp;
 644
 645   for (i = 0; i < state_table[nstates].lookaheads; i++)
 646     for (sp = lookback[i]; sp; sp = sp->next)
 647       {
 648         unsigned *fp1 = LA (i);
 649         unsigned *fp2 = F (sp->value);
 650         while (fp1 < LA (i + 1))
 651           *fp1++ |= *fp2++;
 652       }
 653
 654   /* Free LOOKBACK. */
 655   for (i = 0; i < state_table[nstates].lookaheads; i++)
 656     {
 657       shorts *sptmp;
 658       for (sp = lookback[i]; sp; sp = sptmp)
 659         {
 660           sptmp = sp->next;
 661           XFREE (sp);
 662         }
 663     }
 664
 665   XFREE (lookback);
 666   XFREE (F);
 667 }
 668
 669
 670 void
 671 lalr (void)
 672 {
 673   tokensetsize = WORDSIZE (ntokens);
 674
 675   set_state_table ();
 676   initialize_LA ();
 677   set_goto_map ();
 678   initialize_F ();
 679   build_relations ();
 680   compute_FOLLOWS ();
 681   compute_lookaheads ();
 682 }