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