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