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