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