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 "relation.h"
  31 #include "quotearg.h"
  32 #include "symtab.h"
  33 #include "gram.h"
  34 #include "reader.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 goto_number_t *goto_map = NULL;
  43 static goto_number_t ngotos = 0;
  44 state_number_t *from_state = NULL;
  45 state_number_t *to_state = NULL;
  46
  47 /* Linked list of goto numbers.  */
  48 typedef struct goto_list_s
  49 {
  50   struct goto_list_s *next;
  51   goto_number_t value;
  52 } goto_list_t;
  53
  54
  55 rule_t **LArule = NULL;
  56 bitsetv LA = NULL;
  57 size_t nLA;
  58
  59
  60 /* And for the famous F variable, which name is so descriptive that a
  61    comment is hardly needed.  <grin>.  */
  62 static bitsetv F = NULL;
  63
  64 static goto_number_t **includes;
  65 static goto_list_t **lookback;
  66
  67
  68
  69
  70 static void
  71 initialize_LA (void)
  72 {
  73   state_number_t i;
  74   int j;
  75   rule_t **np;
  76
  77   /* Avoid having to special case 0.  */
  78   if (!nLA)
  79     nLA = 1;
  80
  81   LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
  82   LArule = XCALLOC (rule_t *, nLA);
  83   lookback = XCALLOC (goto_list_t *, nLA);
  84
  85   np = LArule;
  86   for (i = 0; i < nstates; i++)
  87     if (!states[i]->consistent)
  88       for (j = 0; j < states[i]->reductions->num; j++)
  89         *np++ = &rules[states[i]->reductions->rules[j]];
  90 }
  91
  92
  93 static void
  94 set_goto_map (void)
  95 {
  96   state_number_t state;
  97   goto_number_t *temp_map;
  98
  99   goto_map = XCALLOC (goto_number_t, nvars + 1) - ntokens;
 100   temp_map = XCALLOC (goto_number_t, nvars + 1) - ntokens;
 101
 102   ngotos = 0;
 103   for (state = 0; state < nstates; ++state)
 104     {
 105       transitions_t *sp = states[state]->transitions;
 106       int i;
 107       for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
 108         {
 109           if (ngotos == GOTO_NUMBER_MAX)
 110             fatal (_("too many gotos (max %d)"), GOTO_NUMBER_MAX);
 111
 112           ngotos++;
 113           goto_map[TRANSITION_SYMBOL (sp, i)]++;
 114         }
 115     }
 116
 117   {
 118     int k = 0;
 119     int i;
 120     for (i = ntokens; i < nsyms; i++)
 121       {
 122         temp_map[i] = k;
 123         k += goto_map[i];
 124       }
 125
 126     for (i = ntokens; i < nsyms; i++)
 127       goto_map[i] = temp_map[i];
 128
 129     goto_map[nsyms] = ngotos;
 130     temp_map[nsyms] = ngotos;
 131   }
 132
 133   from_state = XCALLOC (state_number_t, ngotos);
 134   to_state = XCALLOC (state_number_t, ngotos);
 135
 136   for (state = 0; state < nstates; ++state)
 137     {
 138       transitions_t *sp = states[state]->transitions;
 139       int i;
 140       for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
 141         {
 142           int k = temp_map[TRANSITION_SYMBOL (sp, i)]++;
 143           from_state[k] = state;
 144           to_state[k] = sp->states[i];
 145         }
 146     }
 147
 148   XFREE (temp_map + ntokens);
 149 }
 150
 151
 152
 153 /*----------------------------------------------------------.
 154 | Map a state/symbol pair into its numeric representation.  |
 155 `----------------------------------------------------------*/
 156
 157 static int
 158 map_goto (state_number_t state, symbol_number_t symbol)
 159 {
 160   int high;
 161   int low;
 162   int middle;
 163   state_number_t s;
 164
 165   low = goto_map[symbol];
 166   high = goto_map[symbol + 1] - 1;
 167
 168   while (low <= high)
 169     {
 170       middle = (low + high) / 2;
 171       s = from_state[middle];
 172       if (s == state)
 173         return middle;
 174       else if (s < state)
 175         low = middle + 1;
 176       else
 177         high = middle - 1;
 178     }
 179
 180   assert (0);
 181   /* NOTREACHED */
 182   return 0;
 183 }
 184
 185
 186 static void
 187 initialize_F (void)
 188 {
 189   goto_number_t **reads = XCALLOC (goto_number_t *, ngotos);
 190   goto_number_t *edge = XCALLOC (goto_number_t, ngotos + 1);
 191   int nedges = 0;
 192
 193   int i;
 194
 195   F = bitsetv_create (ngotos, ntokens, BITSET_FIXED);
 196
 197   for (i = 0; i < ngotos; i++)
 198     {
 199       state_number_t stateno = to_state[i];
 200       transitions_t *sp = states[stateno]->transitions;
 201
 202       int j;
 203       for (j = 0; j < sp->num && TRANSITION_IS_SHIFT (sp, j); j++)
 204         bitset_set (F[i], TRANSITION_SYMBOL (sp, j));
 205
 206       for (; j < sp->num; j++)
 207         {
 208           symbol_number_t symbol = TRANSITION_SYMBOL (sp, j);
 209           if (nullable[symbol])
 210             edge[nedges++] = map_goto (stateno, symbol);
 211         }
 212
 213       if (nedges)
 214         {
 215           reads[i] = XCALLOC (goto_number_t, nedges + 1);
 216           memcpy (reads[i], edge, nedges * sizeof (edge[0]));
 217           reads[i][nedges] = -1;
 218           nedges = 0;
 219         }
 220     }
 221
 222   relation_digraph (reads, ngotos, &F);
 223
 224   for (i = 0; i < ngotos; i++)
 225     XFREE (reads[i]);
 226
 227   XFREE (reads);
 228   XFREE (edge);
 229 }
 230
 231
 232 static void
 233 add_lookback_edge (state_t *state, rule_number_t ruleno, int gotono)
 234 {
 235   int i;
 236   goto_list_t *sp;
 237
 238   for (i = 0; i < state->nlookaheads; ++i)
 239     if (state->lookaheads_rule[i]->number == ruleno)
 240       break;
 241
 242   assert (state->lookaheads_rule[i]->number == ruleno);
 243
 244   sp = XCALLOC (goto_list_t, 1);
 245   sp->next = lookback[(state->lookaheads - LA) + i];
 246   sp->value = gotono;
 247   lookback[(state->lookaheads - LA) + i] = sp;
 248 }
 249
 250
 251
 252 static void
 253 build_relations (void)
 254 {
 255   goto_number_t *edge = XCALLOC (goto_number_t, ngotos + 1);
 256   state_number_t *states1 = XCALLOC (state_number_t, ritem_longest_rhs () + 1);
 257   int i;
 258
 259   includes = XCALLOC (goto_number_t *, ngotos);
 260
 261   for (i = 0; i < ngotos; i++)
 262     {
 263       int nedges = 0;
 264       symbol_number_t symbol1 = states[to_state[i]]->accessing_symbol;
 265       rule_number_t *rulep;
 266
 267       for (rulep = derives[symbol1]; *rulep > 0; rulep++)
 268         {
 269           int done;
 270           int length = 1;
 271           item_number_t *rp;
 272           state_t *state = states[from_state[i]];
 273           states1[0] = state->number;
 274
 275           for (rp = rules[*rulep].rhs; *rp >= 0; rp++)
 276             {
 277               state = transitions_to (state->transitions,
 278                                       item_number_as_symbol_number (*rp));
 279               states1[length++] = state->number;
 280             }
 281
 282           if (!state->consistent)
 283             add_lookback_edge (state, *rulep, i);
 284
 285           length--;
 286           done = 0;
 287           while (!done)
 288             {
 289               done = 1;
 290               rp--;
 291               /* JF added rp>=ritem &&   I hope to god its right! */
 292               if (rp >= ritem && ISVAR (*rp))
 293                 {
 294                   /* Downcasting from item_number_t to symbol_number_t. */
 295                   edge[nedges++] = map_goto (states1[--length],
 296                                              item_number_as_symbol_number (*rp));
 297                   if (nullable[*rp])
 298                     done = 0;
 299                 }
 300             }
 301         }
 302
 303       if (nedges)
 304         {
 305           int j;
 306           includes[i] = XCALLOC (goto_number_t, nedges + 1);
 307           for (j = 0; j < nedges; j++)
 308             includes[i][j] = edge[j];
 309           includes[i][nedges] = -1;
 310         }
 311     }
 312
 313   XFREE (edge);
 314   XFREE (states1);
 315
 316   relation_transpose (&includes, ngotos);
 317 }
 318
 319
 320
 321 static void
 322 compute_FOLLOWS (void)
 323 {
 324   int i;
 325
 326   relation_digraph (includes, ngotos, &F);
 327
 328   for (i = 0; i < ngotos; i++)
 329     XFREE (includes[i]);
 330
 331   XFREE (includes);
 332 }
 333
 334
 335 static void
 336 compute_lookaheads (void)
 337 {
 338   size_t i;
 339   goto_list_t *sp;
 340
 341   for (i = 0; i < nLA; i++)
 342     for (sp = lookback[i]; sp; sp = sp->next)
 343       bitset_or (LA[i], LA[i], F[sp->value]);
 344
 345   /* Free LOOKBACK. */
 346   for (i = 0; i < nLA; i++)
 347     LIST_FREE (goto_list_t, lookback[i]);
 348
 349   XFREE (lookback);
 350   bitsetv_free (F);
 351 }
 352
 353
 354 /*-------------------------------------------------------------.
 355 | Count the number of lookaheads required for each state       |
 356 | (NLOOKAHEADS member).  Compute the total number of LA, NLA.  |
 357 `-------------------------------------------------------------*/
 358
 359 static void
 360 states_lookaheads_count (void)
 361 {
 362   state_number_t i;
 363   nLA = 0;
 364
 365   /* Count   */
 366   for (i = 0; i < nstates; i++)
 367     {
 368       int k;
 369       int nlookaheads = 0;
 370       reductions_t *rp = states[i]->reductions;
 371       transitions_t *sp = states[i]->transitions;
 372
 373       /* We need a lookahead either to distinguish different
 374          reductions (i.e., there are two or more), or to distinguish a
 375          reduction from a shift.  Otherwise, it is straightforward,
 376          and the state is `consistent'.  */
 377       if (rp->num > 1
 378           || (rp->num == 1 && sp->num && TRANSITION_IS_SHIFT (sp, 0)))
 379         nlookaheads += rp->num;
 380       else
 381         states[i]->consistent = 1;
 382
 383       for (k = 0; k < sp->num; k++)
 384         if (TRANSITION_IS_ERROR (sp, k))
 385           {
 386             states[i]->consistent = 0;
 387             break;
 388           }
 389
 390       states[i]->nlookaheads = nlookaheads;
 391       nLA += nlookaheads;
 392     }
 393 }
 394
 395
 396 /*--------------------------------------.
 397 | Initializing the lookaheads members.  |
 398 `--------------------------------------*/
 399
 400 static void
 401 states_lookaheads_initialize (void)
 402 {
 403   state_number_t i;
 404   bitsetv pLA = LA;
 405   rule_t **pLArule = LArule;
 406
 407   /* Initialize the members LOOKAHEADS and LOOKAHEADS_RULE for each
 408      state.  */
 409   for (i = 0; i < nstates; i++)
 410     {
 411       states[i]->lookaheads = pLA;
 412       states[i]->lookaheads_rule = pLArule;
 413       pLA += states[i]->nlookaheads;
 414       pLArule += states[i]->nlookaheads;
 415     }
 416 }
 417
 418
 419 /*---------------------------------------.
 420 | Output the lookaheads for each state.  |
 421 `---------------------------------------*/
 422
 423 static void
 424 lookaheads_print (FILE *out)
 425 {
 426   state_number_t i;
 427   int j, k;
 428   fprintf (out, "Lookaheads: BEGIN\n");
 429   for (i = 0; i < nstates; ++i)
 430     {
 431       bitset_iterator iter;
 432
 433       fprintf (out, "State %d: %d lookaheads\n",
 434                i, states[i]->nlookaheads);
 435
 436       for (j = 0; j < states[i]->nlookaheads; ++j)
 437         BITSET_FOR_EACH (iter, states[i]->lookaheads[j], k, 0)
 438         {
 439           fprintf (out, "   on %d (%s) -> rule %d\n",
 440                    k, symbols[k]->tag,
 441                    states[i]->lookaheads_rule[j]->number - 1);
 442         };
 443     }
 444   fprintf (out, "Lookaheads: END\n");
 445 }
 446
 447 void
 448 lalr (void)
 449 {
 450   states_lookaheads_count ();
 451   initialize_LA ();
 452   states_lookaheads_initialize ();
 453   set_goto_map ();
 454   initialize_F ();
 455   build_relations ();
 456   compute_FOLLOWS ();
 457   compute_lookaheads ();
 458
 459   if (trace_flag)
 460     lookaheads_print (stderr);
 461 }