src/lalr.c

   1 /* Compute lookahead criteria for Bison.
   2
   3    Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005,
   4    2006, 2007 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 lookahead in each state, and which lookahead
  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 an NLA 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           aver (ngotos != GOTO_NUMBER_MAXIMUM);
  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       aver (low <= high);
 157       middle = (low + high) / 2;
 158       s = from_state[middle];
 159       if (s == s0)
 160         return middle;
 161       else if (s < s0)
 162         low = middle + 1;
 163       else
 164         high = middle - 1;
 165     }
 166 }
 167
 168
 169 static void
 170 initialize_F (void)
 171 {
 172   goto_number **reads = xnmalloc (ngotos, sizeof *reads);
 173   goto_number *edge = xnmalloc (ngotos + 1, sizeof *edge);
 174   goto_number nedges = 0;
 175
 176   goto_number i;
 177
 178   F = bitsetv_create (ngotos, ntokens, BITSET_FIXED);
 179
 180   for (i = 0; i < ngotos; i++)
 181     {
 182       state_number stateno = to_state[i];
 183       transitions *sp = states[stateno]->transitions;
 184
 185       int j;
 186       FOR_EACH_SHIFT (sp, j)
 187         bitset_set (F[i], TRANSITION_SYMBOL (sp, j));
 188
 189       for (; j < sp->num; j++)
 190         {
 191           symbol_number sym = TRANSITION_SYMBOL (sp, j);
 192           if (nullable[sym - ntokens])
 193             edge[nedges++] = map_goto (stateno, sym);
 194         }
 195
 196       if (nedges == 0)
 197         reads[i] = NULL;
 198       else
 199         {
 200           reads[i] = xnmalloc (nedges + 1, sizeof reads[i][0]);
 201           memcpy (reads[i], edge, nedges * sizeof edge[0]);
 202           reads[i][nedges] = END_NODE;
 203           nedges = 0;
 204         }
 205     }
 206
 207   relation_digraph (reads, ngotos, &F);
 208
 209   for (i = 0; i < ngotos; i++)
 210     free (reads[i]);
 211
 212   free (reads);
 213   free (edge);
 214 }
 215
 216
 217 static void
 218 add_lookback_edge (state *s, rule *r, goto_number gotono)
 219 {
 220   int ri = state_reduction_find (s, r);
 221   goto_list *sp = xmalloc (sizeof *sp);
 222   sp->next = lookback[(s->reductions->lookahead_tokens - LA) + ri];
 223   sp->value = gotono;
 224   lookback[(s->reductions->lookahead_tokens - LA) + ri] = sp;
 225 }
 226
 227
 228
 229 static void
 230 build_relations (void)
 231 {
 232   goto_number *edge = xnmalloc (ngotos + 1, sizeof *edge);
 233   state_number *states1 = xnmalloc (ritem_longest_rhs () + 1, sizeof *states1);
 234   goto_number i;
 235
 236   includes = xnmalloc (ngotos, sizeof *includes);
 237
 238   for (i = 0; i < ngotos; i++)
 239     {
 240       int nedges = 0;
 241       symbol_number symbol1 = states[to_state[i]]->accessing_symbol;
 242       rule **rulep;
 243
 244       for (rulep = derives[symbol1 - ntokens]; *rulep; rulep++)
 245         {
 246           bool done;
 247           int length = 1;
 248           item_number const *rp;
 249           state *s = states[from_state[i]];
 250           states1[0] = s->number;
 251
 252           for (rp = (*rulep)->rhs; ! item_number_is_rule_number (*rp); rp++)
 253             {
 254               s = transitions_to (s->transitions,
 255                                   item_number_as_symbol_number (*rp));
 256               states1[length++] = s->number;
 257             }
 258
 259           if (!s->consistent)
 260             add_lookback_edge (s, *rulep, i);
 261
 262           length--;
 263           done = false;
 264           while (!done)
 265             {
 266               done = true;
 267               /* Each rhs ends in an item number, and there is a
 268                  sentinel before the first rhs, so it is safe to
 269                  decrement RP here.  */
 270               rp--;
 271               if (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_lookahead_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 lookahead tokens required for S |
 337 | (N_LOOKAHEAD_TOKENS member).                        |
 338 `----------------------------------------------------*/
 339
 340 static int
 341 state_lookahead_tokens_count (state *s)
 342 {
 343   int k;
 344   int n_lookahead_tokens = 0;
 345   reductions *rp = s->reductions;
 346   transitions *sp = s->transitions;
 347
 348   /* We need a lookahead 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_lookahead_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_lookahead_tokens;
 367 }
 368
 369
 370 /*----------------------------------------------------.
 371 | Compute LA, NLA, and the lookahead_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 lookahead.  */
 381   nLA = 0;
 382   for (i = 0; i < nstates; i++)
 383     nLA += state_lookahead_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 LOOKAHEAD_TOKENS for each state whose reductions
 392      require lookahead tokens.  */
 393   for (i = 0; i < nstates; i++)
 394     {
 395       int count = state_lookahead_tokens_count (states[i]);
 396       if (count)
 397         {
 398           states[i]->reductions->lookahead_tokens = pLA;
 399           pLA += count;
 400         }
 401     }
 402 }
 403
 404
 405 /*---------------------------------------------.
 406 | Output the lookahead tokens for each state.  |
 407 `---------------------------------------------*/
 408
 409 static void
 410 lookahead_tokens_print (FILE *out)
 411 {
 412   state_number i;
 413   int j, k;
 414   fprintf (out, "Lookahead tokens: BEGIN\n");
 415   for (i = 0; i < nstates; ++i)
 416     {
 417       reductions *reds = states[i]->reductions;
 418       bitset_iterator iter;
 419       int n_lookahead_tokens = 0;
 420
 421       if (reds->lookahead_tokens)
 422         for (k = 0; k < reds->num; ++k)
 423           if (reds->lookahead_tokens[k])
 424             ++n_lookahead_tokens;
 425
 426       fprintf (out, "State %d: %d lookahead tokens\n",
 427                i, n_lookahead_tokens);
 428
 429       if (reds->lookahead_tokens)
 430         for (j = 0; j < reds->num; ++j)
 431           BITSET_FOR_EACH (iter, reds->lookahead_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, "Lookahead 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_lookahead_tokens ();
 450
 451   if (trace_flag & trace_sets)
 452     lookahead_tokens_print (stderr);
 453 }
 454
 455
 456 void
 457 lalr_update_state_numbers (state_number old_to_new[], state_number nstates_old)
 458 {
 459   goto_number ngotos_reachable = 0;
 460   symbol_number nonterminal = 0;
 461   aver (nsyms == nvars + ntokens);
 462   {
 463     goto_number i;
 464     for (i = 0; i < ngotos; ++i)
 465       {
 466         while (i == goto_map[nonterminal])
 467           goto_map[nonterminal++] = ngotos_reachable;
 468         /* If old_to_new[from_state[i]] = nstates_old, remove this goto
 469            entry.  */
 470         if (old_to_new[from_state[i]] != nstates_old)
 471           {
 472             /* from_state[i] is not removed, so it and thus to_state[i] are
 473                reachable, so to_state[i] != nstates_old.  */
 474             aver (old_to_new[to_state[i]] != nstates_old);
 475             from_state[ngotos_reachable] = old_to_new[from_state[i]];
 476             to_state[ngotos_reachable] = old_to_new[to_state[i]];
 477             ++ngotos_reachable;
 478           }
 479       }
 480   }
 481   while (nonterminal <= nvars)
 482     {
 483       aver (ngotos == goto_map[nonterminal]);
 484       goto_map[nonterminal++] = ngotos_reachable;
 485     }
 486   ngotos = ngotos_reachable;
 487 }
 488
 489
 490 void
 491 lalr_free (void)
 492 {
 493   state_number s;
 494   for (s = 0; s < nstates; ++s)
 495     states[s]->reductions->lookahead_tokens = NULL;
 496   bitsetv_free (LA);
 497 }