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 static void
 198 initialize_LA (void)
 199 {
 200   int i;
 201   int j;
 202   short *np;
 203   reductions *rp;
 204
 205   size_t nLA = state_table[nstates].lookaheads;
 206   if (!nLA)
 207     nLA = 1;
 208
 209   LA = XCALLOC (unsigned, nLA * tokensetsize);
 210   LAruleno = XCALLOC (short, nLA);
 211   lookback = XCALLOC (shorts *, nLA);
 212
 213   np = LAruleno;
 214   for (i = 0; i < nstates; i++)
 215     if (!state_table[i].consistent)
 216       if ((rp = state_table[i].reduction_table))
 217         for (j = 0; j < rp->nreds; j++)
 218           *np++ = rp->rules[j];
 219 }
 220
 221
 222 static void
 223 set_goto_map (void)
 224 {
 225   shifts *sp;
 226   int i;
 227   int symbol;
 228   int k;
 229   short *temp_map;
 230   int state2;
 231   int state1;
 232
 233   goto_map = XCALLOC (short, nvars + 1) - ntokens;
 234   temp_map = XCALLOC (short, nvars + 1) - ntokens;
 235
 236   ngotos = 0;
 237   for (sp = first_shift; sp; sp = sp->next)
 238     {
 239       for (i = sp->nshifts - 1; i >= 0; i--)
 240         {
 241           symbol = state_table[sp->shifts[i]].accessing_symbol;
 242
 243           if (ISTOKEN (symbol))
 244             break;
 245
 246           if (ngotos == MAXSHORT)
 247             fatal (_("too many gotos (max %d)"), MAXSHORT);
 248
 249           ngotos++;
 250           goto_map[symbol]++;
 251         }
 252     }
 253
 254   k = 0;
 255   for (i = ntokens; i < nsyms; i++)
 256     {
 257       temp_map[i] = k;
 258       k += goto_map[i];
 259     }
 260
 261   for (i = ntokens; i < nsyms; i++)
 262     goto_map[i] = temp_map[i];
 263
 264   goto_map[nsyms] = ngotos;
 265   temp_map[nsyms] = ngotos;
 266
 267   from_state = XCALLOC (short, ngotos);
 268   to_state = XCALLOC (short, ngotos);
 269
 270   for (sp = first_shift; sp; sp = sp->next)
 271     {
 272       state1 = sp->number;
 273       for (i = sp->nshifts - 1; i >= 0; i--)
 274         {
 275           state2 = sp->shifts[i];
 276           symbol = state_table[state2].accessing_symbol;
 277
 278           if (ISTOKEN (symbol))
 279             break;
 280
 281           k = temp_map[symbol]++;
 282           from_state[k] = state1;
 283           to_state[k] = state2;
 284         }
 285     }
 286
 287   XFREE (temp_map + ntokens);
 288 }
 289
 290
 291
 292 /*----------------------------------------------------------.
 293 | Map a state/symbol pair into its numeric representation.  |
 294 `----------------------------------------------------------*/
 295
 296 static int
 297 map_goto (int state, int symbol)
 298 {
 299   int high;
 300   int low;
 301   int middle;
 302   int s;
 303
 304   low = goto_map[symbol];
 305   high = goto_map[symbol + 1] - 1;
 306
 307   while (low <= high)
 308     {
 309       middle = (low + high) / 2;
 310       s = from_state[middle];
 311       if (s == state)
 312         return middle;
 313       else if (s < state)
 314         low = middle + 1;
 315       else
 316         high = middle - 1;
 317     }
 318
 319   assert (0);
 320   /* NOTREACHED */
 321   return 0;
 322 }
 323
 324
 325 static void
 326 initialize_F (void)
 327 {
 328   short **reads = XCALLOC (short *, ngotos);
 329   short *edge = XCALLOC (short, ngotos + 1);
 330   int nedges = 0;
 331
 332   int i;
 333
 334   F = XCALLOC (unsigned, ngotos * tokensetsize);
 335
 336   for (i = 0; i < ngotos; i++)
 337     {
 338       int stateno = to_state[i];
 339       shifts *sp = state_table[stateno].shift_table;
 340
 341       if (sp)
 342         {
 343           int j;
 344           for (j = 0; j < sp->nshifts; j++)
 345             {
 346               int symbol = state_table[sp->shifts[j]].accessing_symbol;
 347               if (ISVAR (symbol))
 348                 break;
 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
 369   digraph (reads);
 370
 371   for (i = 0; i < ngotos; i++)
 372     XFREE (reads[i]);
 373
 374   XFREE (reads);
 375   XFREE (edge);
 376 }
 377
 378
 379 static void
 380 add_lookback_edge (int stateno, int ruleno, int gotono)
 381 {
 382   int i;
 383   int k;
 384   int found;
 385   shorts *sp;
 386
 387   i = state_table[stateno].lookaheads;
 388   k = state_table[stateno + 1].lookaheads;
 389   found = 0;
 390   while (!found && i < k)
 391     {
 392       if (LAruleno[i] == ruleno)
 393         found = 1;
 394       else
 395         i++;
 396     }
 397
 398   assert (found);
 399
 400   sp = XCALLOC (shorts, 1);
 401   sp->next = lookback[i];
 402   sp->value = gotono;
 403   lookback[i] = sp;
 404 }
 405
 406
 407 /*-------------------------------------------------------------------.
 408 | Return the transpose of R_ARG, of size N.  Destroy R_ARG, as it is |
 409 | replaced with the result.                                          |
 410 `-------------------------------------------------------------------*/
 411
 412 static short **
 413 transpose (short **R_arg, int n)
 414 {
 415   short **new_R;
 416   short **temp_R;
 417   short *nedges;
 418   int i;
 419
 420   nedges = XCALLOC (short, n);
 421
 422   for (i = 0; i < n; i++)
 423     {
 424       short *sp = R_arg[i];
 425       if (sp)
 426         {
 427           while (*sp >= 0)
 428             nedges[*sp++]++;
 429         }
 430     }
 431
 432   new_R = XCALLOC (short *, n);
 433   temp_R = XCALLOC (short *, n);
 434
 435   for (i = 0; i < n; i++)
 436     if (nedges[i] > 0)
 437       {
 438         short *sp = XCALLOC (short, nedges[i] + 1);
 439         new_R[i] = sp;
 440         temp_R[i] = sp;
 441         sp[nedges[i]] = -1;
 442       }
 443
 444   XFREE (nedges);
 445
 446   for (i = 0; i < n; i++)
 447     {
 448       short *sp = R_arg[i];
 449       if (sp)
 450         while (*sp >= 0)
 451           *temp_R[*sp++]++ = i;
 452     }
 453
 454   XFREE (temp_R);
 455
 456   /* Free the input: it is replaced with the result. */
 457   for (i = 0; i < n; i++)
 458     XFREE (R_arg[i]);
 459   XFREE (R_arg);
 460
 461   return new_R;
 462 }
 463
 464
 465 static void
 466 build_relations (void)
 467 {
 468   short *edge = XCALLOC (short, ngotos + 1);
 469   short *states = XCALLOC (short, ritem_longest_rhs () + 1);
 470   int i;
 471
 472   includes = XCALLOC (short *, ngotos);
 473
 474   for (i = 0; i < ngotos; i++)
 475     {
 476       int nedges = 0;
 477       int state1 = from_state[i];
 478       int symbol1 = state_table[to_state[i]].accessing_symbol;
 479       short *rulep;
 480
 481       for (rulep = derives[symbol1]; *rulep > 0; rulep++)
 482         {
 483           int done;
 484           int length = 1;
 485           int stateno = state1;
 486           short *rp;
 487           states[0] = state1;
 488
 489           for (rp = ritem + rule_table[*rulep].rhs; *rp > 0; rp++)
 490             {
 491               shifts *sp = state_table[stateno].shift_table;
 492               int j;
 493               for (j = 0; j < sp->nshifts; j++)
 494                 {
 495                   stateno = sp->shifts[j];
 496                   if (state_table[stateno].accessing_symbol == *rp)
 497                     break;
 498                 }
 499
 500               states[length++] = stateno;
 501             }
 502
 503           if (!state_table[stateno].consistent)
 504             add_lookback_edge (stateno, *rulep, i);
 505
 506           length--;
 507           done = 0;
 508           while (!done)
 509             {
 510               done = 1;
 511               rp--;
 512               /* JF added rp>=ritem &&   I hope to god its right! */
 513               if (rp >= ritem && ISVAR (*rp))
 514                 {
 515                   stateno = states[--length];
 516                   edge[nedges++] = map_goto (stateno, *rp);
 517                   if (nullable[*rp])
 518                     done = 0;
 519                 }
 520             }
 521         }
 522
 523       if (nedges)
 524         {
 525           int j;
 526           includes[i] = XCALLOC (short, nedges + 1);
 527           for (j = 0; j < nedges; j++)
 528             includes[i][j] = edge[j];
 529           includes[i][nedges] = -1;
 530         }
 531     }
 532
 533   XFREE (edge);
 534   XFREE (states);
 535
 536   includes = transpose (includes, ngotos);
 537 }
 538
 539
 540
 541 static void
 542 compute_FOLLOWS (void)
 543 {
 544   int i;
 545
 546   digraph (includes);
 547
 548   for (i = 0; i < ngotos; i++)
 549     XFREE (includes[i]);
 550
 551   XFREE (includes);
 552 }
 553
 554
 555 static void
 556 compute_lookaheads (void)
 557 {
 558   int i;
 559   shorts *sp;
 560
 561   for (i = 0; i < state_table[nstates].lookaheads; i++)
 562     for (sp = lookback[i]; sp; sp = sp->next)
 563       {
 564         int size = LA (i + 1) - LA (i);
 565         int j;
 566         for (j = 0; j < size; ++j)
 567           LA (i)[j] |= F (sp->value)[j];
 568       }
 569
 570   /* Free LOOKBACK. */
 571   for (i = 0; i < state_table[nstates].lookaheads; i++)
 572     LIST_FREE (shorts, lookback[i]);
 573
 574   XFREE (lookback);
 575   XFREE (F);
 576 }
 577
 578
 579 void
 580 lalr (void)
 581 {
 582   tokensetsize = WORDSIZE (ntokens);
 583
 584   set_state_table ();
 585   initialize_LA ();
 586   set_goto_map ();
 587   initialize_F ();
 588   build_relations ();
 589   compute_FOLLOWS ();
 590   compute_lookaheads ();
 591 }