src/lalr.c

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