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