src/lalr.c

   1 /* Compute look-ahead criteria for Bison.
   2
   3    Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005
   4    Free Software Foundation, Inc.
   5
   6    This file is part of Bison, the GNU Compiler Compiler.
   7
   8    Bison is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2, or (at your option)
  11    any later version.
  12
  13    Bison is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with Bison; see the file COPYING.  If not, write to
  20    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  21    Boston, MA 02110-1301, USA.  */
  22
  23
  24 /* Compute how to make the finite state machine deterministic; find
  25    which rules need look-ahead in each state, and which look-ahead
  26    tokens they accept.  */
  27
  28 #include <config.h>
  29 #include "system.h"
  30
  31 #include <bitset.h>
  32 #include <bitsetv.h>
  33 #include <quotearg.h>
  34
  35 #include "LR0.h"
  36 #include "complain.h"
  37 #include "derives.h"
  38 #include "getargs.h"
  39 #include "gram.h"
  40 #include "lalr.h"
  41 #include "nullable.h"
  42 #include "reader.h"
  43 #include "relation.h"
  44 #include "symtab.h"
  45
  46 goto_number *goto_map;
  47 static goto_number ngotos;
  48 state_number *from_state;
  49 state_number *to_state;
  50
  51 /* Linked list of goto numbers.  */
  52 typedef struct goto_list
  53 {
  54   struct goto_list *next;
  55   goto_number value;
  56 } goto_list;
  57
  58
  59 /* LA is a LR by NTOKENS matrix of bits.  LA[l, i] is 1 if the rule
  60    LArule[l] is applicable in the appropriate state when the next
  61    token is symbol i.  If LA[l, i] and LA[l, j] are both 1 for i != j,
  62    it is a conflict.  */
  63
  64 static bitsetv LA = NULL;
  65 size_t nLA;
  66
  67
  68 /* And for the famous F variable, which name is so descriptive that a
  69    comment is hardly needed.  <grin>.  */
  70 static bitsetv F = NULL;
  71
  72 static goto_number **includes;
  73 static goto_list **lookback;
  74
  75
  76
  77
  78 static void
  79 set_goto_map (void)
  80 {
  81   state_number s;
  82   goto_number *temp_map;
  83
  84   goto_map = xcalloc (nvars + 1, sizeof *goto_map);
  85   temp_map = xnmalloc (nvars + 1, sizeof *temp_map);
  86
  87   ngotos = 0;
  88   for (s = 0; s < nstates; ++s)
  89     {
  90       transitions *sp = states[s]->transitions;
  91       int i;
  92       for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
  93         {
  94           ngotos++;
  95
  96           /* Abort if (ngotos + 1) would overflow.  */
  97           if (ngotos == GOTO_NUMBER_MAXIMUM)
  98             abort ();
  99
 100           goto_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
 101         }
 102     }
 103
 104   {
 105     goto_number k = 0;
 106     int i;
 107     for (i = ntokens; i < nsyms; i++)
 108       {
 109         temp_map[i - ntokens] = k;
 110         k += goto_map[i - ntokens];
 111       }
 112
 113     for (i = ntokens; i < nsyms; i++)
 114       goto_map[i - ntokens] = temp_map[i - ntokens];
 115
 116     goto_map[nsyms - ntokens] = ngotos;
 117     temp_map[nsyms - ntokens] = ngotos;
 118   }
 119
 120   from_state = xcalloc (ngotos, sizeof *from_state);
 121   to_state = xcalloc (ngotos, sizeof *to_state);
 122
 123   for (s = 0; s < nstates; ++s)
 124     {
 125       transitions *sp = states[s]->transitions;
 126       int i;
 127       for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
 128         {
 129           goto_number k = temp_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
 130           from_state[k] = s;
 131           to_state[k] = sp->states[i]->number;
 132         }
 133     }
 134
 135   free (temp_map);
 136 }
 137
 138
 139
 140 /*----------------------------------------------------------.
 141 | Map a state/symbol pair into its numeric representation.  |
 142 `----------------------------------------------------------*/
 143
 144 static goto_number
 145 map_goto (state_number s0, symbol_number sym)
 146 {
 147   goto_number high;
 148   goto_number low;
 149   goto_number middle;
 150   state_number s;
 151
 152   low = goto_map[sym - ntokens];
 153   high = goto_map[sym - ntokens + 1] - 1;
 154
 155   for (;;)
 156     {
 157       if (high < low)
 158         abort ();
 159       middle = (low + high) / 2;
 160       s = from_state[middle];
 161       if (s == s0)
 162         return middle;
 163       else if (s < s0)
 164         low = middle + 1;
 165       else
 166         high = middle - 1;
 167     }
 168 }
 169
 170
 171 static void
 172 initialize_F (void)
 173 {
 174   goto_number **reads = xnmalloc (ngotos, sizeof *reads);
 175   goto_number *edge = xnmalloc (ngotos + 1, sizeof *edge);
 176   goto_number nedges = 0;
 177
 178   goto_number i;
 179
 180   F = bitsetv_create (ngotos, ntokens, BITSET_FIXED);
 181
 182   for (i = 0; i < ngotos; i++)
 183     {
 184       state_number stateno = to_state[i];
 185       transitions *sp = states[stateno]->transitions;
 186
 187       int j;
 188       FOR_EACH_SHIFT (sp, j)
 189         bitset_set (F[i], TRANSITION_SYMBOL (sp, j));
 190
 191       for (; j < sp->num; j++)
 192         {
 193           symbol_number sym = TRANSITION_SYMBOL (sp, j);
 194           if (nullable[sym - ntokens])
 195             edge[nedges++] = map_goto (stateno, sym);
 196         }
 197
 198       if (nedges == 0)
 199         reads[i] = NULL;
 200       else
 201         {
 202           reads[i] = xnmalloc (nedges + 1, sizeof reads[i][0]);
 203           memcpy (reads[i], edge, nedges * sizeof edge[0]);
 204           reads[i][nedges] = END_NODE;
 205           nedges = 0;
 206         }
 207     }
 208
 209   relation_digraph (reads, ngotos, &F);
 210
 211   for (i = 0; i < ngotos; i++)
 212     free (reads[i]);
 213
 214   free (reads);
 215   free (edge);
 216 }
 217
 218
 219 static void
 220 add_lookback_edge (state *s, rule *r, goto_number gotono)
 221 {
 222   int ri = state_reduction_find (s, r);
 223   goto_list *sp = xmalloc (sizeof *sp);
 224   sp->next = lookback[(s->reductions->look_ahead_tokens - LA) + ri];
 225   sp->value = gotono;
 226   lookback[(s->reductions->look_ahead_tokens - LA) + ri] = sp;
 227 }
 228
 229
 230
 231 static void
 232 build_relations (void)
 233 {
 234   goto_number *edge = xnmalloc (ngotos + 1, sizeof *edge);
 235   state_number *states1 = xnmalloc (ritem_longest_rhs () + 1, sizeof *states1);
 236   goto_number i;
 237
 238   includes = xnmalloc (ngotos, sizeof *includes);
 239
 240   for (i = 0; i < ngotos; i++)
 241     {
 242       int nedges = 0;
 243       symbol_number symbol1 = states[to_state[i]]->accessing_symbol;
 244       rule **rulep;
 245
 246       for (rulep = derives[symbol1 - ntokens]; *rulep; rulep++)
 247         {
 248           bool done;
 249           int length = 1;
 250           item_number *rp;
 251           state *s = states[from_state[i]];
 252           states1[0] = s->number;
 253
 254           for (rp = (*rulep)->rhs; *rp >= 0; rp++)
 255             {
 256               s = transitions_to (s->transitions,
 257                                   item_number_as_symbol_number (*rp));
 258               states1[length++] = s->number;
 259             }
 260
 261           if (!s->consistent)
 262             add_lookback_edge (s, *rulep, i);
 263
 264           length--;
 265           done = false;
 266           while (!done)
 267             {
 268               done = true;
 269               rp--;
 270               /* JF added rp>=ritem &&   I hope to god its right! */
 271               if (rp >= ritem && ISVAR (*rp))
 272                 {
 273                   /* Downcasting from item_number to symbol_number.  */
 274                   edge[nedges++] = map_goto (states1[--length],
 275                                              item_number_as_symbol_number (*rp));
 276                   if (nullable[*rp - ntokens])
 277                     done = false;
 278                 }
 279             }
 280         }
 281
 282       if (nedges == 0)
 283         includes[i] = NULL;
 284       else
 285         {
 286           int j;
 287           includes[i] = xnmalloc (nedges + 1, sizeof includes[i][0]);
 288           for (j = 0; j < nedges; j++)
 289             includes[i][j] = edge[j];
 290           includes[i][nedges] = END_NODE;
 291         }
 292     }
 293
 294   free (edge);
 295   free (states1);
 296
 297   relation_transpose (&includes, ngotos);
 298 }
 299
 300
 301
 302 static void
 303 compute_FOLLOWS (void)
 304 {
 305   goto_number i;
 306
 307   relation_digraph (includes, ngotos, &F);
 308
 309   for (i = 0; i < ngotos; i++)
 310     free (includes[i]);
 311
 312   free (includes);
 313 }
 314
 315
 316 static void
 317 compute_look_ahead_tokens (void)
 318 {
 319   size_t i;
 320   goto_list *sp;
 321
 322   for (i = 0; i < nLA; i++)
 323     for (sp = lookback[i]; sp; sp = sp->next)
 324       bitset_or (LA[i], LA[i], F[sp->value]);
 325
 326   /* Free LOOKBACK. */
 327   for (i = 0; i < nLA; i++)
 328     LIST_FREE (goto_list, lookback[i]);
 329
 330   free (lookback);
 331   bitsetv_free (F);
 332 }
 333
 334
 335 /*-----------------------------------------------------.
 336 | Count the number of look-ahead tokens required for S |
 337 | (N_LOOK_AHEAD_TOKENS member).                        |
 338 `-----------------------------------------------------*/
 339
 340 static int
 341 state_look_ahead_tokens_count (state *s)
 342 {
 343   int k;
 344   int n_look_ahead_tokens = 0;
 345   reductions *rp = s->reductions;
 346   transitions *sp = s->transitions;
 347
 348   /* We need a look-ahead either to distinguish different
 349      reductions (i.e., there are two or more), or to distinguish a
 350      reduction from a shift.  Otherwise, it is straightforward,
 351      and the state is `consistent'.  */
 352   if (rp->num > 1
 353       || (rp->num == 1 && sp->num &&
 354           !TRANSITION_IS_DISABLED (sp, 0) && TRANSITION_IS_SHIFT (sp, 0)))
 355     n_look_ahead_tokens += rp->num;
 356   else
 357     s->consistent = 1;
 358
 359   for (k = 0; k < sp->num; k++)
 360     if (!TRANSITION_IS_DISABLED (sp, k) && TRANSITION_IS_ERROR (sp, k))
 361       {
 362         s->consistent = 0;
 363         break;
 364       }
 365
 366   return n_look_ahead_tokens;
 367 }
 368
 369
 370 /*-----------------------------------------------------.
 371 | Compute LA, NLA, and the look_ahead_tokens members.  |
 372 `-----------------------------------------------------*/
 373
 374 static void
 375 initialize_LA (void)
 376 {
 377   state_number i;
 378   bitsetv pLA;
 379
 380   /* Compute the total number of reductions requiring a look-ahead.  */
 381   nLA = 0;
 382   for (i = 0; i < nstates; i++)
 383     nLA += state_look_ahead_tokens_count (states[i]);
 384   /* Avoid having to special case 0.  */
 385   if (!nLA)
 386     nLA = 1;
 387
 388   pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
 389   lookback = xcalloc (nLA, sizeof *lookback);
 390
 391   /* Initialize the members LOOK_AHEAD_TOKENS for each state whose reductions
 392      require look-ahead tokens.  */
 393   for (i = 0; i < nstates; i++)
 394     {
 395       int count = state_look_ahead_tokens_count (states[i]);
 396       if (count)
 397         {
 398           states[i]->reductions->look_ahead_tokens = pLA;
 399           pLA += count;
 400         }
 401     }
 402 }
 403
 404
 405 /*----------------------------------------------.
 406 | Output the look-ahead tokens for each state.  |
 407 `----------------------------------------------*/
 408
 409 static void
 410 look_ahead_tokens_print (FILE *out)
 411 {
 412   state_number i;
 413   int j, k;
 414   fprintf (out, "Look-ahead tokens: BEGIN\n");
 415   for (i = 0; i < nstates; ++i)
 416     {
 417       reductions *reds = states[i]->reductions;
 418       bitset_iterator iter;
 419       int n_look_ahead_tokens = 0;
 420
 421       if (reds->look_ahead_tokens)
 422         for (k = 0; k < reds->num; ++k)
 423           if (reds->look_ahead_tokens[k])
 424             ++n_look_ahead_tokens;
 425
 426       fprintf (out, "State %d: %d look-ahead tokens\n",
 427                i, n_look_ahead_tokens);
 428
 429       if (reds->look_ahead_tokens)
 430         for (j = 0; j < reds->num; ++j)
 431           BITSET_FOR_EACH (iter, reds->look_ahead_tokens[j], k, 0)
 432           {
 433             fprintf (out, "   on %d (%s) -> rule %d\n",
 434                      k, symbols[k]->tag,
 435                      reds->rules[j]->number);
 436           };
 437     }
 438   fprintf (out, "Look-ahead tokens: END\n");
 439 }
 440
 441 void
 442 lalr (void)
 443 {
 444   initialize_LA ();
 445   set_goto_map ();
 446   initialize_F ();
 447   build_relations ();
 448   compute_FOLLOWS ();
 449   compute_look_ahead_tokens ();
 450
 451   if (trace_flag & trace_sets)
 452     look_ahead_tokens_print (stderr);
 453 }
 454
 455
 456 void
 457 lalr_free (void)
 458 {
 459   state_number s;
 460   for (s = 0; s < nstates; ++s)
 461     states[s]->reductions->look_ahead_tokens = NULL;
 462   bitsetv_free (LA);
 463 }