src/lalr.c

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