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