src/lalr.c

   1 /* Compute look-ahead criteria for bison,
   2    Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002
   3    Free Software Foundation, Inc.
   4
   5    This file is part of Bison, the GNU Compiler Compiler.
   6
   7    Bison is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2, or (at your option)
  10    any later version.
  11
  12    Bison is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with Bison; see the file COPYING.  If not, write to
  19    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  20    Boston, MA 02111-1307, USA.  */
  21
  22
  23 /* Compute how to make the finite state machine deterministic; find
  24    which rules need lookahead in each state, and which lookahead
  25    tokens they accept.  */
  26
  27 #include "system.h"
  28 #include "bitset.h"
  29 #include "bitsetv.h"
  30 #include "quotearg.h"
  31 #include "symtab.h"
  32 #include "gram.h"
  33 #include "reader.h"
  34 #include "types.h"
  35 #include "LR0.h"
  36 #include "complain.h"
  37 #include "lalr.h"
  38 #include "nullable.h"
  39 #include "derives.h"
  40 #include "getargs.h"
  41
  42 /* All the decorated states, indexed by the state number.  */
  43 state_t **states = NULL;
  44
  45 rule_t **LArule = NULL;
  46 bitsetv LA = NULL;
  47 size_t nLA;
  48
  49 static int ngotos;
  50 short *goto_map = NULL;
  51 short *from_state = NULL;
  52 short *to_state = NULL;
  53
  54 /* And for the famous F variable, which name is so descriptive that a
  55    comment is hardly needed.  <grin>.  */
  56 static bitsetv F = NULL;
  57
  58 static short **includes;
  59 static shorts **lookback;
  60
  61
  62 /*---------------------------------------------------------------.
  63 | digraph & traverse.                                            |
  64 |                                                                |
  65 | The following variables are used as common storage between the |
  66 | two.                                                           |
  67 `---------------------------------------------------------------*/
  68
  69 static short **R;
  70 static short *INDEX;
  71 static short *VERTICES;
  72 static int top;
  73 static int infinity;
  74
  75 static void
  76 traverse (int i)
  77 {
  78   int j;
  79   int height;
  80
  81   VERTICES[++top] = i;
  82   INDEX[i] = height = top;
  83
  84   if (R[i])
  85     for (j = 0; R[i][j] >= 0; ++j)
  86       {
  87         if (INDEX[R[i][j]] == 0)
  88           traverse (R[i][j]);
  89
  90         if (INDEX[i] > INDEX[R[i][j]])
  91           INDEX[i] = INDEX[R[i][j]];
  92
  93         bitset_or (F[i], F[i], F[R[i][j]]);
  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         bitset_copy (F[j], F[i]);
 106       }
 107 }
 108
 109
 110 static void
 111 digraph (short **relation)
 112 {
 113   int i;
 114
 115   infinity = ngotos + 2;
 116   INDEX = XCALLOC (short, ngotos + 1);
 117   VERTICES = XCALLOC (short, ngotos + 1);
 118   top = 0;
 119
 120   R = relation;
 121
 122   for (i = 0; i < ngotos; i++)
 123     INDEX[i] = 0;
 124
 125   for (i = 0; i < ngotos; i++)
 126     if (INDEX[i] == 0 && R[i])
 127       traverse (i);
 128
 129   XFREE (INDEX);
 130   XFREE (VERTICES);
 131 }
 132
 133
 134 static void
 135 initialize_LA (void)
 136 {
 137   size_t i;
 138   int j;
 139   rule_t **np;
 140
 141   /* Avoid having to special case 0.  */
 142   if (!nLA)
 143     nLA = 1;
 144
 145   LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
 146   LArule = XCALLOC (rule_t *, nLA);
 147   lookback = XCALLOC (shorts *, nLA);
 148
 149   np = LArule;
 150   for (i = 0; i < nstates; i++)
 151     if (!states[i]->consistent)
 152       for (j = 0; j < states[i]->reductions->nreds; j++)
 153         *np++ = &rules[states[i]->reductions->rules[j]];
 154 }
 155
 156
 157 static void
 158 set_goto_map (void)
 159 {
 160   size_t state;
 161   int i;
 162   short *temp_map;
 163
 164   goto_map = XCALLOC (short, nvars + 1) - ntokens;
 165   temp_map = XCALLOC (short, nvars + 1) - ntokens;
 166
 167   ngotos = 0;
 168   for (state = 0; state < nstates; ++state)
 169     {
 170       shifts *sp = states[state]->shifts;
 171       for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i)
 172         {
 173           if (ngotos == SHRT_MAX)
 174             fatal (_("too many gotos (max %d)"), SHRT_MAX);
 175
 176           ngotos++;
 177           goto_map[SHIFT_SYMBOL (sp, i)]++;
 178         }
 179     }
 180
 181   {
 182     int k = 0;
 183     for (i = ntokens; i < nsyms; i++)
 184       {
 185         temp_map[i] = k;
 186         k += goto_map[i];
 187       }
 188
 189     for (i = ntokens; i < nsyms; i++)
 190       goto_map[i] = temp_map[i];
 191
 192     goto_map[nsyms] = ngotos;
 193     temp_map[nsyms] = ngotos;
 194   }
 195
 196   from_state = XCALLOC (short, ngotos);
 197   to_state = XCALLOC (short, ngotos);
 198
 199   for (state = 0; state < nstates; ++state)
 200     {
 201       shifts *sp = states[state]->shifts;
 202       for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i)
 203         {
 204           int k = temp_map[SHIFT_SYMBOL (sp, i)]++;
 205           from_state[k] = state;
 206           to_state[k] = sp->shifts[i];
 207         }
 208     }
 209
 210   XFREE (temp_map + ntokens);
 211 }
 212
 213
 214
 215 /*----------------------------------------------------------.
 216 | Map a state/symbol pair into its numeric representation.  |
 217 `----------------------------------------------------------*/
 218
 219 static int
 220 map_goto (int state, int symbol)
 221 {
 222   int high;
 223   int low;
 224   int middle;
 225   int s;
 226
 227   low = goto_map[symbol];
 228   high = goto_map[symbol + 1] - 1;
 229
 230   while (low <= high)
 231     {
 232       middle = (low + high) / 2;
 233       s = from_state[middle];
 234       if (s == state)
 235         return middle;
 236       else if (s < state)
 237         low = middle + 1;
 238       else
 239         high = middle - 1;
 240     }
 241
 242   assert (0);
 243   /* NOTREACHED */
 244   return 0;
 245 }
 246
 247
 248 static void
 249 initialize_F (void)
 250 {
 251   short **reads = XCALLOC (short *, ngotos);
 252   short *edge = XCALLOC (short, ngotos + 1);
 253   int nedges = 0;
 254
 255   int i;
 256
 257   F = bitsetv_create (ngotos, ntokens, BITSET_FIXED);
 258
 259   for (i = 0; i < ngotos; i++)
 260     {
 261       int stateno = to_state[i];
 262       shifts *sp = states[stateno]->shifts;
 263
 264       int j;
 265       for (j = 0; j < sp->nshifts && SHIFT_IS_SHIFT (sp, j); j++)
 266         bitset_set (F[i], SHIFT_SYMBOL (sp, j));
 267
 268       for (; j < sp->nshifts; j++)
 269         {
 270           int symbol = SHIFT_SYMBOL (sp, j);
 271           if (nullable[symbol])
 272             edge[nedges++] = map_goto (stateno, symbol);
 273         }
 274
 275       if (nedges)
 276         {
 277           reads[i] = XCALLOC (short, nedges + 1);
 278           memcpy (reads[i], edge, nedges * sizeof (edge[0]));
 279           reads[i][nedges] = -1;
 280           nedges = 0;
 281         }
 282     }
 283
 284   digraph (reads);
 285
 286   for (i = 0; i < ngotos; i++)
 287     XFREE (reads[i]);
 288
 289   XFREE (reads);
 290   XFREE (edge);
 291 }
 292
 293
 294 static void
 295 add_lookback_edge (state_t *state, int ruleno, int gotono)
 296 {
 297   int i;
 298   shorts *sp;
 299
 300   for (i = 0; i < state->nlookaheads; ++i)
 301     if (LArule[state->lookaheadsp + i]->number == ruleno)
 302       break;
 303
 304   assert (LArule[state->lookaheadsp + i]->number == ruleno);
 305
 306   sp = XCALLOC (shorts, 1);
 307   sp->next = lookback[state->lookaheadsp + i];
 308   sp->value = gotono;
 309   lookback[state->lookaheadsp + i] = sp;
 310 }
 311
 312
 313 static void
 314 matrix_print (FILE *out, short **matrix, int n)
 315 {
 316   int i, j;
 317
 318   for (i = 0; i < n; ++i)
 319     {
 320       fprintf (out, "%3d: ", i);
 321       if (matrix[i])
 322         for (j = 0; matrix[i][j] != -1; ++j)
 323           fprintf (out, "%3d ", matrix[i][j]);
 324       fputc ('\n', out);
 325     }
 326   fputc ('\n', out);
 327 }
 328
 329 /*-------------------------------------------------------------------.
 330 | Return the transpose of R_ARG, of size N.  Destroy R_ARG, as it is |
 331 | replaced with the result.                                          |
 332 |                                                                    |
 333 | R_ARG[I] is NULL or a -1 terminated list of numbers.               |
 334 |                                                                    |
 335 | RESULT[NUM] is NULL or the -1 terminated list of the I such as NUM |
 336 | is in R_ARG[I].                                                    |
 337 `-------------------------------------------------------------------*/
 338
 339 static short **
 340 transpose (short **R_arg, int n)
 341 {
 342   /* The result. */
 343   short **new_R = XCALLOC (short *, n);
 344   /* END_R[I] -- next entry of NEW_R[I]. */
 345   short **end_R = XCALLOC (short *, n);
 346   /* NEDGES[I] -- total size of NEW_R[I]. */
 347   short *nedges = XCALLOC (short, n);
 348   int i, j;
 349
 350   if (trace_flag)
 351     {
 352       fputs ("transpose: input\n", stderr);
 353       matrix_print (stderr, R_arg, n);
 354     }
 355
 356   /* Count. */
 357   for (i = 0; i < n; i++)
 358     if (R_arg[i])
 359       for (j = 0; R_arg[i][j] >= 0; ++j)
 360         ++nedges[R_arg[i][j]];
 361
 362   /* Allocate. */
 363   for (i = 0; i < n; i++)
 364     if (nedges[i] > 0)
 365       {
 366         short *sp = XCALLOC (short, nedges[i] + 1);
 367         sp[nedges[i]] = -1;
 368         new_R[i] = sp;
 369         end_R[i] = sp;
 370       }
 371
 372   /* Store. */
 373   for (i = 0; i < n; i++)
 374     if (R_arg[i])
 375       for (j = 0; R_arg[i][j] >= 0; ++j)
 376         {
 377           *end_R[R_arg[i][j]] = i;
 378           ++end_R[R_arg[i][j]];
 379         }
 380
 381   free (nedges);
 382   free (end_R);
 383
 384   /* Free the input: it is replaced with the result. */
 385   for (i = 0; i < n; i++)
 386     XFREE (R_arg[i]);
 387   free (R_arg);
 388
 389   if (trace_flag)
 390     {
 391       fputs ("transpose: output\n", stderr);
 392       matrix_print (stderr, new_R, n);
 393     }
 394
 395   return new_R;
 396 }
 397
 398
 399 static void
 400 build_relations (void)
 401 {
 402   short *edge = XCALLOC (short, ngotos + 1);
 403   short *states1 = XCALLOC (short, ritem_longest_rhs () + 1);
 404   int i;
 405
 406   includes = XCALLOC (short *, ngotos);
 407
 408   for (i = 0; i < ngotos; i++)
 409     {
 410       int nedges = 0;
 411       int symbol1 = states[to_state[i]]->accessing_symbol;
 412       short *rulep;
 413
 414       for (rulep = derives[symbol1]; *rulep > 0; rulep++)
 415         {
 416           int done;
 417           int length = 1;
 418           item_number_t *rp;
 419           state_t *state = states[from_state[i]];
 420           states1[0] = state->number;
 421
 422           for (rp = rules[*rulep].rhs; *rp >= 0; rp++)
 423             {
 424               shifts *sp = state->shifts;
 425               int j;
 426               for (j = 0; j < sp->nshifts; j++)
 427                 {
 428                   state = states[sp->shifts[j]];
 429                   if (state->accessing_symbol == *rp)
 430                     break;
 431                 }
 432
 433               states1[length++] = state->number;
 434             }
 435
 436           if (!state->consistent)
 437             add_lookback_edge (state, *rulep, i);
 438
 439           length--;
 440           done = 0;
 441           while (!done)
 442             {
 443               done = 1;
 444               rp--;
 445               /* JF added rp>=ritem &&   I hope to god its right! */
 446               if (rp >= ritem && ISVAR (*rp))
 447                 {
 448                   edge[nedges++] = map_goto (states1[--length], *rp);
 449                   if (nullable[*rp])
 450                     done = 0;
 451                 }
 452             }
 453         }
 454
 455       if (nedges)
 456         {
 457           int j;
 458           includes[i] = XCALLOC (short, nedges + 1);
 459           for (j = 0; j < nedges; j++)
 460             includes[i][j] = edge[j];
 461           includes[i][nedges] = -1;
 462         }
 463     }
 464
 465   XFREE (edge);
 466   XFREE (states1);
 467
 468   includes = transpose (includes, ngotos);
 469 }
 470
 471
 472
 473 static void
 474 compute_FOLLOWS (void)
 475 {
 476   int i;
 477
 478   digraph (includes);
 479
 480   for (i = 0; i < ngotos; i++)
 481     XFREE (includes[i]);
 482
 483   XFREE (includes);
 484 }
 485
 486
 487 static void
 488 compute_lookaheads (void)
 489 {
 490   size_t i;
 491   shorts *sp;
 492
 493   for (i = 0; i < nLA; i++)
 494     for (sp = lookback[i]; sp; sp = sp->next)
 495       bitset_or (LA[i], LA[i], F[sp->value]);
 496
 497   /* Free LOOKBACK. */
 498   for (i = 0; i < nLA; i++)
 499     LIST_FREE (shorts, lookback[i]);
 500
 501   XFREE (lookback);
 502   bitsetv_free (F);
 503 }
 504
 505
 506 /*--------------------------------------.
 507 | Initializing the lookaheads members.  |
 508 `--------------------------------------*/
 509
 510 static void
 511 initialize_lookaheads (void)
 512 {
 513   size_t i;
 514   nLA = 0;
 515   for (i = 0; i < nstates; i++)
 516     {
 517       int k;
 518       int nlookaheads = 0;
 519       reductions *rp = states[i]->reductions;
 520       shifts *sp = states[i]->shifts;
 521
 522       /* We need a lookahead either to distinguish different
 523          reductions (i.e., there are two or more), or to distinguish a
 524          reduction from a shift.  Otherwise, it is straightforward,
 525          and the state is `consistent'.  */
 526       if (rp->nreds > 1
 527           || (rp->nreds == 1 && sp->nshifts && SHIFT_IS_SHIFT (sp, 0)))
 528         nlookaheads += rp->nreds;
 529       else
 530         states[i]->consistent = 1;
 531
 532       for (k = 0; k < sp->nshifts; k++)
 533         if (SHIFT_IS_ERROR (sp, k))
 534           {
 535             states[i]->consistent = 0;
 536             break;
 537           }
 538
 539       states[i]->nlookaheads = nlookaheads;
 540       states[i]->lookaheadsp = nLA;
 541       nLA += nlookaheads;
 542     }
 543 }
 544
 545
 546 /*---------------------------------------.
 547 | Output the lookaheads for each state.  |
 548 `---------------------------------------*/
 549
 550 static void
 551 lookaheads_print (FILE *out)
 552 {
 553   size_t i;
 554   int j, k;
 555   fprintf (out, "Lookaheads: BEGIN\n");
 556   for (i = 0; i < nstates; ++i)
 557     {
 558       fprintf (out, "State %d: %d lookaheads\n",
 559                i, states[i]->nlookaheads);
 560
 561       for (j = 0; j < states[i]->nlookaheads; ++j)
 562         for (k = 0; k < ntokens; ++k)
 563           if (bitset_test (LA[states[i]->lookaheadsp + j], k))
 564             fprintf (out, "   on %d (%s) -> rule %d\n",
 565                      k, quotearg_style (escape_quoting_style, symbols[k]->tag),
 566                      LArule[states[i]->lookaheadsp + j]->number - 1);
 567     }
 568   fprintf (out, "Lookaheads: END\n");
 569 }
 570
 571 void
 572 lalr (void)
 573 {
 574   initialize_lookaheads ();
 575   initialize_LA ();
 576   set_goto_map ();
 577   initialize_F ();
 578   build_relations ();
 579   compute_FOLLOWS ();
 580   compute_lookaheads ();
 581
 582   if (trace_flag)
 583     lookaheads_print (stderr);
 584 }