src/lalr.c

   1 /* Compute lookahead criteria for Bison.
   2
   3    Copyright (C) 1984, 1986, 1989, 2000-2015, 2018 Free Software
   4    Foundation, Inc.
   5
   6    This file is part of Bison, the GNU Compiler Compiler.
   7
   8    This program 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 3 of the License, or
  11    (at your option) any later version.
  12
  13    This program 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 this program.  If not, see <http://www.gnu.org/licenses/>.  */
  20
  21
  22 /* Find which rules need lookahead in each state, and which lookahead
  23    tokens they accept.  */
  24
  25 #include <config.h>
  26 #include "system.h"
  27
  28 #include <bitset.h>
  29 #include <bitsetv.h>
  30
  31 #include "LR0.h"
  32 #include "complain.h"
  33 #include "derives.h"
  34 #include "getargs.h"
  35 #include "gram.h"
  36 #include "lalr.h"
  37 #include "muscle-tab.h"
  38 #include "nullable.h"
  39 #include "reader.h"
  40 #include "relation.h"
  41 #include "symtab.h"
  42
  43 goto_number *goto_map;
  44 goto_number ngotos;
  45 state_number *from_state;
  46 state_number *to_state;
  47 bitsetv goto_follows = 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 an NLA 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 static goto_number **includes;
  67 static goto_list **lookback;
  68
  69
  70 void
  71 set_goto_map (void)
  72 {
  73   state_number s;
  74   goto_number *temp_map = xnmalloc (nvars + 1, sizeof *temp_map);
  75
  76   goto_map = xcalloc (nvars + 1, sizeof *goto_map);
  77   ngotos = 0;
  78   for (s = 0; s < nstates; ++s)
  79     {
  80       transitions *sp = states[s]->transitions;
  81       int i;
  82       for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
  83         {
  84           ngotos++;
  85
  86           /* Abort if (ngotos + 1) would overflow.  */
  87           aver (ngotos != GOTO_NUMBER_MAXIMUM);
  88
  89           goto_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
  90         }
  91     }
  92
  93   {
  94     goto_number k = 0;
  95     int i;
  96     for (i = ntokens; i < nsyms; i++)
  97       {
  98         temp_map[i - ntokens] = k;
  99         k += goto_map[i - ntokens];
 100       }
 101
 102     for (i = ntokens; i < nsyms; i++)
 103       goto_map[i - ntokens] = temp_map[i - ntokens];
 104
 105     goto_map[nsyms - ntokens] = ngotos;
 106     temp_map[nsyms - ntokens] = ngotos;
 107   }
 108
 109   from_state = xcalloc (ngotos, sizeof *from_state);
 110   to_state = xcalloc (ngotos, sizeof *to_state);
 111
 112   for (s = 0; s < nstates; ++s)
 113     {
 114       transitions *sp = states[s]->transitions;
 115       int i;
 116       for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
 117         {
 118           goto_number k = temp_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
 119           from_state[k] = s;
 120           to_state[k] = sp->states[i]->number;
 121         }
 122     }
 123
 124   free (temp_map);
 125 }
 126
 127
 128 goto_number
 129 map_goto (state_number s0, symbol_number sym)
 130 {
 131   goto_number low = goto_map[sym - ntokens];
 132   goto_number high = goto_map[sym - ntokens + 1] - 1;
 133
 134   for (;;)
 135     {
 136       goto_number middle;
 137       state_number s;
 138       aver (low <= high);
 139       middle = (low + high) / 2;
 140       s = from_state[middle];
 141       if (s == s0)
 142         return middle;
 143       else if (s < s0)
 144         low = middle + 1;
 145       else
 146         high = middle - 1;
 147     }
 148 }
 149
 150
 151 static void
 152 initialize_F (void)
 153 {
 154   goto_number **reads = xnmalloc (ngotos, sizeof *reads);
 155   goto_number *edge = xnmalloc (ngotos + 1, sizeof *edge);
 156   goto_number nedges = 0;
 157
 158   goto_number i;
 159
 160   goto_follows = bitsetv_create (ngotos, ntokens, BITSET_FIXED);
 161
 162   for (i = 0; i < ngotos; i++)
 163     {
 164       state_number stateno = to_state[i];
 165       transitions *sp = states[stateno]->transitions;
 166
 167       int j;
 168       FOR_EACH_SHIFT (sp, j)
 169         bitset_set (goto_follows[i], TRANSITION_SYMBOL (sp, j));
 170
 171       for (; j < sp->num; j++)
 172         {
 173           symbol_number sym = TRANSITION_SYMBOL (sp, j);
 174           if (nullable[sym - ntokens])
 175             edge[nedges++] = map_goto (stateno, sym);
 176         }
 177
 178       if (nedges == 0)
 179         reads[i] = NULL;
 180       else
 181         {
 182           reads[i] = xnmalloc (nedges + 1, sizeof reads[i][0]);
 183           memcpy (reads[i], edge, nedges * sizeof edge[0]);
 184           reads[i][nedges] = END_NODE;
 185           nedges = 0;
 186         }
 187     }
 188
 189   relation_digraph (reads, ngotos, &goto_follows);
 190
 191   for (i = 0; i < ngotos; i++)
 192     free (reads[i]);
 193
 194   free (reads);
 195   free (edge);
 196 }
 197
 198
 199 static void
 200 add_lookback_edge (state *s, rule *r, goto_number gotono)
 201 {
 202   int ri = state_reduction_find (s, r);
 203   goto_list *sp = xmalloc (sizeof *sp);
 204   sp->next = lookback[(s->reductions->lookahead_tokens - LA) + ri];
 205   sp->value = gotono;
 206   lookback[(s->reductions->lookahead_tokens - LA) + ri] = sp;
 207 }
 208
 209
 210
 211 static void
 212 build_relations (void)
 213 {
 214   goto_number *edge = xnmalloc (ngotos + 1, sizeof *edge);
 215   state_number *states1 = xnmalloc (ritem_longest_rhs () + 1, sizeof *states1);
 216   goto_number i;
 217
 218   includes = xnmalloc (ngotos, sizeof *includes);
 219
 220   for (i = 0; i < ngotos; i++)
 221     {
 222       int nedges = 0;
 223       symbol_number symbol1 = states[to_state[i]]->accessing_symbol;
 224       rule **rulep;
 225
 226       for (rulep = derives[symbol1 - ntokens]; *rulep; rulep++)
 227         {
 228           bool done;
 229           int length = 1;
 230           item_number const *rp;
 231           state *s = states[from_state[i]];
 232           states1[0] = s->number;
 233
 234           for (rp = (*rulep)->rhs; ! item_number_is_rule_number (*rp); rp++)
 235             {
 236               s = transitions_to (s->transitions,
 237                                   item_number_as_symbol_number (*rp));
 238               states1[length++] = s->number;
 239             }
 240
 241           if (!s->consistent)
 242             add_lookback_edge (s, *rulep, i);
 243
 244           length--;
 245           done = false;
 246           while (!done)
 247             {
 248               done = true;
 249               /* Each rhs ends in a rule number, and there is a
 250                  sentinel (ritem[-1]=0) before the first rhs, so it is safe to
 251                  decrement RP here.  */
 252               rp--;
 253               if (ISVAR (*rp))
 254                 {
 255                   /* Downcasting from item_number to symbol_number.  */
 256                   edge[nedges++] = map_goto (states1[--length],
 257                                              item_number_as_symbol_number (*rp));
 258                   if (nullable[*rp - ntokens])
 259                     done = false;
 260                 }
 261             }
 262         }
 263
 264       if (nedges == 0)
 265         includes[i] = NULL;
 266       else
 267         {
 268           int j;
 269           includes[i] = xnmalloc (nedges + 1, sizeof includes[i][0]);
 270           for (j = 0; j < nedges; j++)
 271             includes[i][j] = edge[j];
 272           includes[i][nedges] = END_NODE;
 273         }
 274     }
 275
 276   free (edge);
 277   free (states1);
 278
 279   relation_transpose (&includes, ngotos);
 280 }
 281
 282
 283
 284 static void
 285 compute_FOLLOWS (void)
 286 {
 287   goto_number i;
 288
 289   relation_digraph (includes, ngotos, &goto_follows);
 290
 291   for (i = 0; i < ngotos; i++)
 292     free (includes[i]);
 293
 294   free (includes);
 295 }
 296
 297
 298 static void
 299 compute_lookahead_tokens (void)
 300 {
 301   size_t i;
 302   goto_list *sp;
 303
 304   for (i = 0; i < nLA; i++)
 305     for (sp = lookback[i]; sp; sp = sp->next)
 306       bitset_or (LA[i], LA[i], goto_follows[sp->value]);
 307
 308   /* Free LOOKBACK. */
 309   for (i = 0; i < nLA; i++)
 310     LIST_FREE (goto_list, lookback[i]);
 311
 312   free (lookback);
 313 }
 314
 315
 316 /*----------------------------------------------------.
 317 | Count the number of lookahead tokens required for S |
 318 | (N_LOOKAHEAD_TOKENS member).                        |
 319 `----------------------------------------------------*/
 320
 321 static int
 322 state_lookahead_tokens_count (state *s, bool default_reduction_only_for_accept)
 323 {
 324   int n_lookahead_tokens = 0;
 325   reductions *rp = s->reductions;
 326   transitions *sp = s->transitions;
 327
 328   /* Transitions are only disabled during conflict resolution, and that
 329      hasn't happened yet, so there should be no need to check that
 330      transition 0 hasn't been disabled before checking if it is a shift.
 331      However, this check was performed at one time, so we leave it as an
 332      aver.  */
 333   aver (sp->num == 0 || !TRANSITION_IS_DISABLED (sp, 0));
 334
 335   /* We need a lookahead either to distinguish different reductions
 336      (i.e., there are two or more), or to distinguish a reduction from a
 337      shift.  Otherwise, it is straightforward, and the state is
 338      'consistent'.  However, do not treat a state with any reductions as
 339      consistent unless it is the accepting state (because there is never
 340      a lookahead token that makes sense there, and so no lookahead token
 341      should be read) if the user has otherwise disabled default
 342      reductions.  */
 343   if (rp->num > 1
 344       || (rp->num == 1 && sp->num && TRANSITION_IS_SHIFT (sp, 0))
 345       || (rp->num == 1 && rp->rules[0]->number != 0
 346           && default_reduction_only_for_accept))
 347     n_lookahead_tokens += rp->num;
 348   else
 349     s->consistent = 1;
 350
 351   return n_lookahead_tokens;
 352 }
 353
 354
 355 /*----------------------------------------------------.
 356 | Compute LA, NLA, and the lookahead_tokens members.  |
 357 `----------------------------------------------------*/
 358
 359 void
 360 initialize_LA (void)
 361 {
 362   state_number i;
 363   bitsetv pLA;
 364   bool default_reduction_only_for_accept;
 365   {
 366     char *default_reductions =
 367       muscle_percent_define_get ("lr.default-reduction");
 368     default_reduction_only_for_accept = STREQ (default_reductions, "accepting");
 369     free (default_reductions);
 370   }
 371
 372   /* Compute the total number of reductions requiring a lookahead.  */
 373   nLA = 0;
 374   for (i = 0; i < nstates; i++)
 375     nLA +=
 376       state_lookahead_tokens_count (states[i],
 377                                     default_reduction_only_for_accept);
 378   /* Avoid having to special case 0.  */
 379   if (!nLA)
 380     nLA = 1;
 381
 382   pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
 383
 384   /* Initialize the members LOOKAHEAD_TOKENS for each state whose reductions
 385      require lookahead tokens.  */
 386   for (i = 0; i < nstates; i++)
 387     {
 388       int count =
 389         state_lookahead_tokens_count (states[i],
 390                                       default_reduction_only_for_accept);
 391       if (count)
 392         {
 393           states[i]->reductions->lookahead_tokens = pLA;
 394           pLA += count;
 395         }
 396     }
 397 }
 398
 399
 400 /*---------------------------------------------.
 401 | Output the lookahead tokens for each state.  |
 402 `---------------------------------------------*/
 403
 404 static void
 405 lookahead_tokens_print (FILE *out)
 406 {
 407   state_number i;
 408   fprintf (out, "Lookahead tokens: BEGIN\n");
 409   for (i = 0; i < nstates; ++i)
 410     {
 411       reductions *reds = states[i]->reductions;
 412       bitset_iterator iter;
 413       int n_lookahead_tokens = 0;
 414
 415       if (reds->lookahead_tokens)
 416         {
 417           int j;
 418           for (j = 0; j < reds->num; ++j)
 419             if (reds->lookahead_tokens[j])
 420               ++n_lookahead_tokens;
 421         }
 422
 423       fprintf (out, "State %d: %d lookahead tokens\n",
 424                i, n_lookahead_tokens);
 425
 426       if (reds->lookahead_tokens)
 427         {
 428           int j, k;
 429           for (j = 0; j < reds->num; ++j)
 430             BITSET_FOR_EACH (iter, reds->lookahead_tokens[j], k, 0)
 431               fprintf (out, "   on %d (%s) -> rule %d\n",
 432                        k, symbols[k]->tag,
 433                        reds->rules[j]->number);
 434         }
 435     }
 436   fprintf (out, "Lookahead tokens: END\n");
 437 }
 438
 439 void
 440 lalr (void)
 441 {
 442   initialize_LA ();
 443   set_goto_map ();
 444   initialize_F ();
 445   lookback = xcalloc (nLA, sizeof *lookback);
 446   build_relations ();
 447   compute_FOLLOWS ();
 448   compute_lookahead_tokens ();
 449
 450   if (trace_flag & trace_sets)
 451     lookahead_tokens_print (stderr);
 452 }
 453
 454
 455 void
 456 lalr_update_state_numbers (state_number old_to_new[], state_number nstates_old)
 457 {
 458   goto_number ngotos_reachable = 0;
 459   symbol_number nonterminal = 0;
 460   aver (nsyms == nvars + ntokens);
 461   {
 462     goto_number i;
 463     for (i = 0; i < ngotos; ++i)
 464       {
 465         while (i == goto_map[nonterminal])
 466           goto_map[nonterminal++] = ngotos_reachable;
 467         /* If old_to_new[from_state[i]] = nstates_old, remove this goto
 468            entry.  */
 469         if (old_to_new[from_state[i]] != nstates_old)
 470           {
 471             /* from_state[i] is not removed, so it and thus to_state[i] are
 472                reachable, so to_state[i] != nstates_old.  */
 473             aver (old_to_new[to_state[i]] != nstates_old);
 474             from_state[ngotos_reachable] = old_to_new[from_state[i]];
 475             to_state[ngotos_reachable] = old_to_new[to_state[i]];
 476             ++ngotos_reachable;
 477           }
 478       }
 479   }
 480   while (nonterminal <= nvars)
 481     {
 482       aver (ngotos == goto_map[nonterminal]);
 483       goto_map[nonterminal++] = ngotos_reachable;
 484     }
 485   ngotos = ngotos_reachable;
 486 }
 487
 488
 489 void
 490 lalr_free (void)
 491 {
 492   state_number s;
 493   for (s = 0; s < nstates; ++s)
 494     states[s]->reductions->lookahead_tokens = NULL;
 495   bitsetv_free (LA);
 496 }