src/lalr.c

   1 /* Compute look-ahead criteria for Bison.
   2
   3    Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005,
   4    2006 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 const *rp;
 251           state *s = states[from_state[i]];
 252           states1[0] = s->number;
 253
 254           for (rp = (*rulep)->rhs; ! item_number_is_rule_number (*rp); 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               /* Each rhs ends in an item number, and there is a
 270                  sentinel before the first rhs, so it is safe to
 271                  decrement RP here.  */
 272               rp--;
 273               if (ISVAR (*rp))
 274                 {
 275                   /* Downcasting from item_number to symbol_number.  */
 276                   edge[nedges++] = map_goto (states1[--length],
 277                                              item_number_as_symbol_number (*rp));
 278                   if (nullable[*rp - ntokens])
 279                     done = false;
 280                 }
 281             }
 282         }
 283
 284       if (nedges == 0)
 285         includes[i] = NULL;
 286       else
 287         {
 288           int j;
 289           includes[i] = xnmalloc (nedges + 1, sizeof includes[i][0]);
 290           for (j = 0; j < nedges; j++)
 291             includes[i][j] = edge[j];
 292           includes[i][nedges] = END_NODE;
 293         }
 294     }
 295
 296   free (edge);
 297   free (states1);
 298
 299   relation_transpose (&includes, ngotos);
 300 }
 301
 302
 303
 304 static void
 305 compute_FOLLOWS (void)
 306 {
 307   goto_number i;
 308
 309   relation_digraph (includes, ngotos, &F);
 310
 311   for (i = 0; i < ngotos; i++)
 312     free (includes[i]);
 313
 314   free (includes);
 315 }
 316
 317
 318 static void
 319 compute_look_ahead_tokens (void)
 320 {
 321   size_t i;
 322   goto_list *sp;
 323
 324   for (i = 0; i < nLA; i++)
 325     for (sp = lookback[i]; sp; sp = sp->next)
 326       bitset_or (LA[i], LA[i], F[sp->value]);
 327
 328   /* Free LOOKBACK. */
 329   for (i = 0; i < nLA; i++)
 330     LIST_FREE (goto_list, lookback[i]);
 331
 332   free (lookback);
 333   bitsetv_free (F);
 334 }
 335
 336
 337 /*-----------------------------------------------------.
 338 | Count the number of look-ahead tokens required for S |
 339 | (N_LOOK_AHEAD_TOKENS member).                        |
 340 `-----------------------------------------------------*/
 341
 342 static int
 343 state_look_ahead_tokens_count (state *s)
 344 {
 345   int k;
 346   int n_look_ahead_tokens = 0;
 347   reductions *rp = s->reductions;
 348   transitions *sp = s->transitions;
 349
 350   /* We need a look-ahead either to distinguish different
 351      reductions (i.e., there are two or more), or to distinguish a
 352      reduction from a shift.  Otherwise, it is straightforward,
 353      and the state is `consistent'.  */
 354   if (rp->num > 1
 355       || (rp->num == 1 && sp->num &&
 356           !TRANSITION_IS_DISABLED (sp, 0) && TRANSITION_IS_SHIFT (sp, 0)))
 357     n_look_ahead_tokens += rp->num;
 358   else
 359     s->consistent = 1;
 360
 361   for (k = 0; k < sp->num; k++)
 362     if (!TRANSITION_IS_DISABLED (sp, k) && TRANSITION_IS_ERROR (sp, k))
 363       {
 364         s->consistent = 0;
 365         break;
 366       }
 367
 368   return n_look_ahead_tokens;
 369 }
 370
 371
 372 /*-----------------------------------------------------.
 373 | Compute LA, NLA, and the look_ahead_tokens members.  |
 374 `-----------------------------------------------------*/
 375
 376 static void
 377 initialize_LA (void)
 378 {
 379   state_number i;
 380   bitsetv pLA;
 381
 382   /* Compute the total number of reductions requiring a look-ahead.  */
 383   nLA = 0;
 384   for (i = 0; i < nstates; i++)
 385     nLA += state_look_ahead_tokens_count (states[i]);
 386   /* Avoid having to special case 0.  */
 387   if (!nLA)
 388     nLA = 1;
 389
 390   pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
 391   lookback = xcalloc (nLA, sizeof *lookback);
 392
 393   /* Initialize the members LOOK_AHEAD_TOKENS for each state whose reductions
 394      require look-ahead tokens.  */
 395   for (i = 0; i < nstates; i++)
 396     {
 397       int count = state_look_ahead_tokens_count (states[i]);
 398       if (count)
 399         {
 400           states[i]->reductions->look_ahead_tokens = pLA;
 401           pLA += count;
 402         }
 403     }
 404 }
 405
 406
 407 /*----------------------------------------------.
 408 | Output the look-ahead tokens for each state.  |
 409 `----------------------------------------------*/
 410
 411 static void
 412 look_ahead_tokens_print (FILE *out)
 413 {
 414   state_number i;
 415   int j, k;
 416   fprintf (out, "Look-ahead tokens: BEGIN\n");
 417   for (i = 0; i < nstates; ++i)
 418     {
 419       reductions *reds = states[i]->reductions;
 420       bitset_iterator iter;
 421       int n_look_ahead_tokens = 0;
 422
 423       if (reds->look_ahead_tokens)
 424         for (k = 0; k < reds->num; ++k)
 425           if (reds->look_ahead_tokens[k])
 426             ++n_look_ahead_tokens;
 427
 428       fprintf (out, "State %d: %d look-ahead tokens\n",
 429                i, n_look_ahead_tokens);
 430
 431       if (reds->look_ahead_tokens)
 432         for (j = 0; j < reds->num; ++j)
 433           BITSET_FOR_EACH (iter, reds->look_ahead_tokens[j], k, 0)
 434           {
 435             fprintf (out, "   on %d (%s) -> rule %d\n",
 436                      k, symbols[k]->tag,
 437                      reds->rules[j]->number);
 438           };
 439     }
 440   fprintf (out, "Look-ahead tokens: END\n");
 441 }
 442
 443 void
 444 lalr (void)
 445 {
 446   initialize_LA ();
 447   set_goto_map ();
 448   initialize_F ();
 449   build_relations ();
 450   compute_FOLLOWS ();
 451   compute_look_ahead_tokens ();
 452
 453   if (trace_flag & trace_sets)
 454     look_ahead_tokens_print (stderr);
 455 }
 456
 457
 458 void
 459 lalr_free (void)
 460 {
 461   state_number s;
 462   for (s = 0; s < nstates; ++s)
 463     states[s]->reductions->look_ahead_tokens = NULL;
 464   bitsetv_free (LA);
 465 }