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