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