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