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
set_goto_map(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
map_goto(state_number s0,symbol_number sym)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
initialize_F(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
add_lookback_edge(state * s,rule * r,goto_number gotono)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
build_relations(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
compute_FOLLOWS(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
compute_look_ahead_tokens(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
state_look_ahead_tokens_count(state * s)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
initialize_LA(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
look_ahead_tokens_print(FILE * out)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
lalr(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
lalr_free(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