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     state_t *sp;
 149     for (sp = first_state; sp; sp = sp->next)
 150       state_table[sp->number] = sp;
 151   }
 152
 153   {
 154     shifts *sp;
 155     for (sp = first_shift; sp; sp = sp->next)
 156       assert (state_table[sp->number]->shifts == sp);
 157   }
 158
 159   /* Pessimization, but simplification of the code: make sure all the
 160      states have a shifts, even if reduced to 0 shifts.  */
 161   {
 162     int i;
 163     for (i = 0; i < nstates; i++)
 164       if (!state_table[i]->shifts)
 165         state_table[i]->shifts = shifts_new (0);
 166   }
 167
 168   /* Initializing the lookaheads members.  Please note that it must be
 169      performed after having set some of the other members which are
 170      used below.  Change with extreme caution.  */
 171   {
 172     int i;
 173     int count = 0;
 174     for (i = 0; i < nstates; i++)
 175       {
 176         int k;
 177         reductions *rp = state_table[i]->reductions;
 178         shifts *sp = state_table[i]->shifts;
 179
 180         state_table[i]->lookaheads = count;
 181
 182         if (rp
 183             && (rp->nreds > 1 || (sp->nshifts && SHIFT_IS_SHIFT (sp, 0))))
 184           count += rp->nreds;
 185         else
 186           state_table[i]->consistent = 1;
 187
 188         for (k = 0; k < sp->nshifts; k++)
 189           if (SHIFT_IS_ERROR (sp, k))
 190             {
 191               state_table[i]->consistent = 0;
 192               break;
 193             }
 194       }
 195
 196     /* Seems to be needed by conflicts.c. */
 197     state_table[nstates] = STATE_ALLOC (0);
 198     state_table[nstates]->lookaheads = count;
 199   }
 200 }
 201
 202
 203 static void
 204 initialize_LA (void)
 205 {
 206   int i;
 207   int j;
 208   short *np;
 209   reductions *rp;
 210
 211   size_t nLA = state_table[nstates]->lookaheads;
 212   if (!nLA)
 213     nLA = 1;
 214
 215   LA = XCALLOC (unsigned, nLA * tokensetsize);
 216   LAruleno = XCALLOC (short, nLA);
 217   lookback = XCALLOC (shorts *, nLA);
 218
 219   np = LAruleno;
 220   for (i = 0; i < nstates; i++)
 221     if (!state_table[i]->consistent)
 222       if ((rp = state_table[i]->reductions))
 223         for (j = 0; j < rp->nreds; j++)
 224           *np++ = rp->rules[j];
 225 }
 226
 227
 228 static void
 229 set_goto_map (void)
 230 {
 231   shifts *sp;
 232   int i;
 233   int symbol;
 234   int k;
 235   short *temp_map;
 236   int state2;
 237   int state1;
 238
 239   goto_map = XCALLOC (short, nvars + 1) - ntokens;
 240   temp_map = XCALLOC (short, nvars + 1) - ntokens;
 241
 242   ngotos = 0;
 243   for (sp = first_shift; sp; sp = sp->next)
 244     for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i)
 245       {
 246         symbol = state_table[sp->shifts[i]]->accessing_symbol;
 247
 248         if (ngotos == MAXSHORT)
 249           fatal (_("too many gotos (max %d)"), MAXSHORT);
 250
 251         ngotos++;
 252         goto_map[symbol]++;
 253       }
 254
 255   k = 0;
 256   for (i = ntokens; i < nsyms; i++)
 257     {
 258       temp_map[i] = k;
 259       k += goto_map[i];
 260     }
 261
 262   for (i = ntokens; i < nsyms; i++)
 263     goto_map[i] = temp_map[i];
 264
 265   goto_map[nsyms] = ngotos;
 266   temp_map[nsyms] = ngotos;
 267
 268   from_state = XCALLOC (short, ngotos);
 269   to_state = XCALLOC (short, ngotos);
 270
 271   for (sp = first_shift; sp; sp = sp->next)
 272     {
 273       state1 = sp->number;
 274       for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i)
 275         {
 276           state2 = sp->shifts[i];
 277           symbol = state_table[state2]->accessing_symbol;
 278
 279           k = temp_map[symbol]++;
 280           from_state[k] = state1;
 281           to_state[k] = state2;
 282         }
 283     }
 284
 285   XFREE (temp_map + ntokens);
 286 }
 287
 288
 289
 290 /*----------------------------------------------------------.
 291 | Map a state/symbol pair into its numeric representation.  |
 292 `----------------------------------------------------------*/
 293
 294 static int
 295 map_goto (int state, int symbol)
 296 {
 297   int high;
 298   int low;
 299   int middle;
 300   int s;
 301
 302   low = goto_map[symbol];
 303   high = goto_map[symbol + 1] - 1;
 304
 305   while (low <= high)
 306     {
 307       middle = (low + high) / 2;
 308       s = from_state[middle];
 309       if (s == state)
 310         return middle;
 311       else if (s < state)
 312         low = middle + 1;
 313       else
 314         high = middle - 1;
 315     }
 316
 317   assert (0);
 318   /* NOTREACHED */
 319   return 0;
 320 }
 321
 322
 323 static void
 324 initialize_F (void)
 325 {
 326   short **reads = XCALLOC (short *, ngotos);
 327   short *edge = XCALLOC (short, ngotos + 1);
 328   int nedges = 0;
 329
 330   int i;
 331
 332   F = XCALLOC (unsigned, ngotos * tokensetsize);
 333
 334   for (i = 0; i < ngotos; i++)
 335     {
 336       int stateno = to_state[i];
 337       shifts *sp = state_table[stateno]->shifts;
 338
 339       int j;
 340       for (j = 0; j < sp->nshifts && SHIFT_IS_SHIFT (sp, j); j++)
 341         {
 342           int symbol = state_table[sp->shifts[j]]->accessing_symbol;
 343           SETBIT (F (i), symbol);
 344         }
 345
 346       for (; j < sp->nshifts; j++)
 347         {
 348           int symbol = state_table[sp->shifts[j]]->accessing_symbol;
 349           if (nullable[symbol])
 350             edge[nedges++] = map_goto (stateno, symbol);
 351         }
 352
 353       if (nedges)
 354         {
 355           reads[i] = XCALLOC (short, nedges + 1);
 356           shortcpy (reads[i], edge, nedges);
 357           reads[i][nedges] = -1;
 358           nedges = 0;
 359         }
 360     }
 361
 362   digraph (reads);
 363
 364   for (i = 0; i < ngotos; i++)
 365     XFREE (reads[i]);
 366
 367   XFREE (reads);
 368   XFREE (edge);
 369 }
 370
 371
 372 static void
 373 add_lookback_edge (int stateno, int ruleno, int gotono)
 374 {
 375   int i;
 376   int k;
 377   int found;
 378   shorts *sp;
 379
 380   i = state_table[stateno]->lookaheads;
 381   k = state_table[stateno + 1]->lookaheads;
 382   found = 0;
 383   while (!found && i < k)
 384     {
 385       if (LAruleno[i] == ruleno)
 386         found = 1;
 387       else
 388         i++;
 389     }
 390
 391   assert (found);
 392
 393   sp = XCALLOC (shorts, 1);
 394   sp->next = lookback[i];
 395   sp->value = gotono;
 396   lookback[i] = sp;
 397 }
 398
 399
 400 static void
 401 matrix_print (FILE *out, short **matrix, int n)
 402 {
 403   int i, j;
 404
 405   for (i = 0; i < n; ++i)
 406     {
 407       fprintf (out, "%3d: ", i);
 408       if (matrix[i])
 409         for (j = 0; matrix[i][j] != -1; ++j)
 410           fprintf (out, "%3d ", matrix[i][j]);
 411       fputc ('\n', out);
 412     }
 413   fputc ('\n', out);
 414 }
 415
 416 /*-------------------------------------------------------------------.
 417 | Return the transpose of R_ARG, of size N.  Destroy R_ARG, as it is |
 418 | replaced with the result.                                          |
 419 |                                                                    |
 420 | R_ARG[I] is NULL or a -1 terminated list of numbers.               |
 421 |                                                                    |
 422 | RESULT[NUM] is NULL or the -1 terminated list of the I such as NUM |
 423 | is in R_ARG[I].                                                    |
 424 `-------------------------------------------------------------------*/
 425
 426 static short **
 427 transpose (short **R_arg, int n)
 428 {
 429   /* The result. */
 430   short **new_R = XCALLOC (short *, n);
 431   /* END_R[I] -- next entry of NEW_R[I]. */
 432   short **end_R = XCALLOC (short *, n);
 433   /* NEDGES[I] -- total size of NEW_R[I]. */
 434   short *nedges = XCALLOC (short, n);
 435   int i, j;
 436
 437   if (trace_flag)
 438     {
 439       fputs ("transpose: input\n", stderr);
 440       matrix_print (stderr, R_arg, n);
 441     }
 442
 443   /* Count. */
 444   for (i = 0; i < n; i++)
 445     if (R_arg[i])
 446       for (j = 0; R_arg[i][j] >= 0; ++j)
 447         ++nedges[R_arg[i][j]];
 448
 449   /* Allocate. */
 450   for (i = 0; i < n; i++)
 451     if (nedges[i] > 0)
 452       {
 453         short *sp = XCALLOC (short, nedges[i] + 1);
 454         sp[nedges[i]] = -1;
 455         new_R[i] = sp;
 456         end_R[i] = sp;
 457       }
 458
 459   /* Store. */
 460   for (i = 0; i < n; i++)
 461     if (R_arg[i])
 462       for (j = 0; R_arg[i][j] >= 0; ++j)
 463         {
 464           *end_R[R_arg[i][j]] = i;
 465           ++end_R[R_arg[i][j]];
 466         }
 467
 468   free (nedges);
 469   free (end_R);
 470
 471   /* Free the input: it is replaced with the result. */
 472   for (i = 0; i < n; i++)
 473     XFREE (R_arg[i]);
 474   free (R_arg);
 475
 476   if (trace_flag)
 477     {
 478       fputs ("transpose: output\n", stderr);
 479       matrix_print (stderr, new_R, n);
 480     }
 481
 482   return new_R;
 483 }
 484
 485
 486 static void
 487 build_relations (void)
 488 {
 489   short *edge = XCALLOC (short, ngotos + 1);
 490   short *states = XCALLOC (short, ritem_longest_rhs () + 1);
 491   int i;
 492
 493   includes = XCALLOC (short *, ngotos);
 494
 495   for (i = 0; i < ngotos; i++)
 496     {
 497       int nedges = 0;
 498       int state1 = from_state[i];
 499       int symbol1 = state_table[to_state[i]]->accessing_symbol;
 500       short *rulep;
 501
 502       for (rulep = derives[symbol1]; *rulep > 0; rulep++)
 503         {
 504           int done;
 505           int length = 1;
 506           int stateno = state1;
 507           short *rp;
 508           states[0] = state1;
 509
 510           for (rp = ritem + rule_table[*rulep].rhs; *rp > 0; rp++)
 511             {
 512               shifts *sp = state_table[stateno]->shifts;
 513               int j;
 514               for (j = 0; j < sp->nshifts; j++)
 515                 {
 516                   stateno = sp->shifts[j];
 517                   if (state_table[stateno]->accessing_symbol == *rp)
 518                     break;
 519                 }
 520
 521               states[length++] = stateno;
 522             }
 523
 524           if (!state_table[stateno]->consistent)
 525             add_lookback_edge (stateno, *rulep, i);
 526
 527           length--;
 528           done = 0;
 529           while (!done)
 530             {
 531               done = 1;
 532               rp--;
 533               /* JF added rp>=ritem &&   I hope to god its right! */
 534               if (rp >= ritem && ISVAR (*rp))
 535                 {
 536                   stateno = states[--length];
 537                   edge[nedges++] = map_goto (stateno, *rp);
 538                   if (nullable[*rp])
 539                     done = 0;
 540                 }
 541             }
 542         }
 543
 544       if (nedges)
 545         {
 546           int j;
 547           includes[i] = XCALLOC (short, nedges + 1);
 548           for (j = 0; j < nedges; j++)
 549             includes[i][j] = edge[j];
 550           includes[i][nedges] = -1;
 551         }
 552     }
 553
 554   XFREE (edge);
 555   XFREE (states);
 556
 557   includes = transpose (includes, ngotos);
 558 }
 559
 560
 561
 562 static void
 563 compute_FOLLOWS (void)
 564 {
 565   int i;
 566
 567   digraph (includes);
 568
 569   for (i = 0; i < ngotos; i++)
 570     XFREE (includes[i]);
 571
 572   XFREE (includes);
 573 }
 574
 575
 576 static void
 577 compute_lookaheads (void)
 578 {
 579   int i;
 580   shorts *sp;
 581
 582   for (i = 0; i < state_table[nstates]->lookaheads; i++)
 583     for (sp = lookback[i]; sp; sp = sp->next)
 584       {
 585         int size = LA (i + 1) - LA (i);
 586         int j;
 587         for (j = 0; j < size; ++j)
 588           LA (i)[j] |= F (sp->value)[j];
 589       }
 590
 591   /* Free LOOKBACK. */
 592   for (i = 0; i < state_table[nstates]->lookaheads; i++)
 593     LIST_FREE (shorts, lookback[i]);
 594
 595   XFREE (lookback);
 596   XFREE (F);
 597 }
 598
 599
 600 void
 601 lalr (void)
 602 {
 603   tokensetsize = WORDSIZE (ntokens);
 604
 605   set_state_table ();
 606   initialize_LA ();
 607   set_goto_map ();
 608   initialize_F ();
 609   build_relations ();
 610   compute_FOLLOWS ();
 611   compute_lookaheads ();
 612 }