Commit | Line | Data |
---|---|---|
d0fb370f | 1 | /* Compute look-ahead criteria for bison, |
3feec034 | 2 | Copyright 1984, 1986, 1989, 2000, 2001 Free Software Foundation, Inc. |
d0fb370f | 3 | |
340ef489 | 4 | This file is part of Bison, the GNU Compiler Compiler. |
d0fb370f | 5 | |
340ef489 AD |
6 | Bison is free software; you can redistribute it and/or modify |
7 | it under the terms of the GNU General Public License as published by | |
8 | the Free Software Foundation; either version 2, or (at your option) | |
9 | any later version. | |
d0fb370f | 10 | |
340ef489 AD |
11 | Bison is distributed in the hope that it will be useful, |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | GNU General Public License for more details. | |
d0fb370f | 15 | |
340ef489 AD |
16 | You should have received a copy of the GNU General Public License |
17 | along with Bison; see the file COPYING. If not, write to | |
18 | the Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |
19 | Boston, MA 02111-1307, USA. */ | |
d0fb370f RS |
20 | |
21 | ||
720d742f AD |
22 | /* Compute how to make the finite state machine deterministic; find |
23 | which rules need lookahead in each state, and which lookahead | |
340ef489 | 24 | tokens they accept. */ |
d0fb370f | 25 | |
d0fb370f | 26 | #include "system.h" |
7c6b64d0 | 27 | #include "reader.h" |
d0fb370f | 28 | #include "types.h" |
b2ca4022 | 29 | #include "LR0.h" |
ad949da9 | 30 | #include "symtab.h" |
d0fb370f | 31 | #include "gram.h" |
a0f6b076 | 32 | #include "complain.h" |
720d742f | 33 | #include "lalr.h" |
3519ec76 | 34 | #include "nullable.h" |
340ef489 | 35 | #include "derives.h" |
f67d13aa | 36 | #include "getargs.h" |
d0fb370f | 37 | |
d200e455 | 38 | /* All the decorated states, indexed by the state number. */ |
29e88316 | 39 | state_t **states = NULL; |
9703cc49 | 40 | |
d0fb370f | 41 | int tokensetsize; |
d0fb370f RS |
42 | short *LAruleno; |
43 | unsigned *LA; | |
d200e455 | 44 | size_t nLA; |
9703cc49 | 45 | |
aa2aab3c | 46 | static int ngotos; |
d0fb370f RS |
47 | short *goto_map; |
48 | short *from_state; | |
49 | short *to_state; | |
50 | ||
fe961097 | 51 | /* And for the famous F variable, which name is so descriptive that a |
ddcd5fdf AD |
52 | comment is hardly needed. <grin>. */ |
53 | static unsigned *F = NULL; | |
54 | #define F(Rule) (F + (Rule) * tokensetsize) | |
55 | ||
d0fb370f RS |
56 | static short **includes; |
57 | static shorts **lookback; | |
aa2aab3c AD |
58 | |
59 | ||
60 | /*---------------------------------------------------------------. | |
61 | | digraph & traverse. | | |
62 | | | | |
63 | | The following variables are used as common storage between the | | |
64 | | two. | | |
65 | `---------------------------------------------------------------*/ | |
66 | ||
d0fb370f RS |
67 | static short **R; |
68 | static short *INDEX; | |
69 | static short *VERTICES; | |
70 | static int top; | |
aa2aab3c | 71 | static int infinity; |
d0fb370f | 72 | |
720d742f AD |
73 | static void |
74 | traverse (int i) | |
d0fb370f | 75 | { |
720d742f | 76 | int j; |
fe961097 | 77 | size_t k; |
720d742f | 78 | int height; |
fe961097 | 79 | size_t size = F (i + 1) - F(i); |
720d742f AD |
80 | |
81 | VERTICES[++top] = i; | |
82 | INDEX[i] = height = top; | |
83 | ||
fe961097 AD |
84 | if (R[i]) |
85 | for (j = 0; R[i][j] >= 0; ++j) | |
86 | { | |
87 | if (INDEX[R[i][j]] == 0) | |
88 | traverse (R[i][j]); | |
720d742f | 89 | |
fe961097 AD |
90 | if (INDEX[i] > INDEX[R[i][j]]) |
91 | INDEX[i] = INDEX[R[i][j]]; | |
720d742f | 92 | |
fe961097 AD |
93 | for (k = 0; k < size; ++k) |
94 | F (i)[k] |= F (R[i][j])[k]; | |
95 | } | |
720d742f AD |
96 | |
97 | if (INDEX[i] == height) | |
fe961097 AD |
98 | for (;;) |
99 | { | |
100 | j = VERTICES[top--]; | |
101 | INDEX[j] = infinity; | |
720d742f | 102 | |
fe961097 AD |
103 | if (i == j) |
104 | break; | |
720d742f | 105 | |
fe961097 | 106 | for (k = 0; k < size; ++k) |
b9752825 | 107 | F (j)[k] = F (i)[k]; |
fe961097 | 108 | } |
d0fb370f RS |
109 | } |
110 | ||
111 | ||
720d742f AD |
112 | static void |
113 | digraph (short **relation) | |
114 | { | |
115 | int i; | |
116 | ||
117 | infinity = ngotos + 2; | |
d7913476 AD |
118 | INDEX = XCALLOC (short, ngotos + 1); |
119 | VERTICES = XCALLOC (short, ngotos + 1); | |
720d742f AD |
120 | top = 0; |
121 | ||
122 | R = relation; | |
123 | ||
124 | for (i = 0; i < ngotos; i++) | |
125 | INDEX[i] = 0; | |
126 | ||
127 | for (i = 0; i < ngotos; i++) | |
ddcd5fdf AD |
128 | if (INDEX[i] == 0 && R[i]) |
129 | traverse (i); | |
720d742f | 130 | |
d7913476 AD |
131 | XFREE (INDEX); |
132 | XFREE (VERTICES); | |
720d742f AD |
133 | } |
134 | ||
bb527fc2 | 135 | |
4a120d45 | 136 | static void |
d2729d44 | 137 | initialize_LA (void) |
d0fb370f | 138 | { |
720d742f AD |
139 | int i; |
140 | int j; | |
720d742f | 141 | short *np; |
d0fb370f | 142 | |
d200e455 | 143 | /* Avoid having to special case 0. */ |
a845a697 AD |
144 | if (!nLA) |
145 | nLA = 1; | |
d0fb370f | 146 | |
a845a697 AD |
147 | LA = XCALLOC (unsigned, nLA * tokensetsize); |
148 | LAruleno = XCALLOC (short, nLA); | |
149 | lookback = XCALLOC (shorts *, nLA); | |
d0fb370f RS |
150 | |
151 | np = LAruleno; | |
152 | for (i = 0; i < nstates; i++) | |
29e88316 AD |
153 | if (!states[i]->consistent) |
154 | for (j = 0; j < states[i]->reductions->nreds; j++) | |
155 | *np++ = states[i]->reductions->rules[j]; | |
d0fb370f RS |
156 | } |
157 | ||
158 | ||
4a120d45 | 159 | static void |
d2729d44 | 160 | set_goto_map (void) |
d0fb370f | 161 | { |
d0b0fefa | 162 | int state, i; |
720d742f | 163 | short *temp_map; |
d0fb370f | 164 | |
d7913476 AD |
165 | goto_map = XCALLOC (short, nvars + 1) - ntokens; |
166 | temp_map = XCALLOC (short, nvars + 1) - ntokens; | |
d0fb370f RS |
167 | |
168 | ngotos = 0; | |
7215de24 AD |
169 | for (state = 0; state < nstates; ++state) |
170 | { | |
29e88316 | 171 | shifts *sp = states[state]->shifts; |
7215de24 AD |
172 | for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i) |
173 | { | |
7215de24 AD |
174 | if (ngotos == MAXSHORT) |
175 | fatal (_("too many gotos (max %d)"), MAXSHORT); | |
d0fb370f | 176 | |
7215de24 | 177 | ngotos++; |
13ca549a | 178 | goto_map[SHIFT_SYMBOL (sp, i)]++; |
7215de24 AD |
179 | } |
180 | } | |
d0fb370f | 181 | |
d0b0fefa AD |
182 | { |
183 | int k = 0; | |
184 | for (i = ntokens; i < nsyms; i++) | |
185 | { | |
186 | temp_map[i] = k; | |
187 | k += goto_map[i]; | |
188 | } | |
d0fb370f | 189 | |
d0b0fefa AD |
190 | for (i = ntokens; i < nsyms; i++) |
191 | goto_map[i] = temp_map[i]; | |
d0fb370f | 192 | |
d0b0fefa AD |
193 | goto_map[nsyms] = ngotos; |
194 | temp_map[nsyms] = ngotos; | |
195 | } | |
d0fb370f | 196 | |
d7913476 AD |
197 | from_state = XCALLOC (short, ngotos); |
198 | to_state = XCALLOC (short, ngotos); | |
d0fb370f | 199 | |
7215de24 | 200 | for (state = 0; state < nstates; ++state) |
d0fb370f | 201 | { |
29e88316 | 202 | shifts *sp = states[state]->shifts; |
aa2aab3c | 203 | for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i) |
d0fb370f | 204 | { |
13ca549a | 205 | int k = temp_map[SHIFT_SYMBOL (sp, i)]++; |
d0b0fefa | 206 | from_state[k] = state; |
13ca549a | 207 | to_state[k] = sp->shifts[i]; |
d0fb370f RS |
208 | } |
209 | } | |
210 | ||
d7913476 | 211 | XFREE (temp_map + ntokens); |
d0fb370f RS |
212 | } |
213 | ||
214 | ||
215 | ||
43591cec AD |
216 | /*----------------------------------------------------------. |
217 | | Map a state/symbol pair into its numeric representation. | | |
218 | `----------------------------------------------------------*/ | |
d0fb370f | 219 | |
4a120d45 | 220 | static int |
d2729d44 | 221 | map_goto (int state, int symbol) |
d0fb370f | 222 | { |
720d742f AD |
223 | int high; |
224 | int low; | |
225 | int middle; | |
226 | int s; | |
d0fb370f RS |
227 | |
228 | low = goto_map[symbol]; | |
229 | high = goto_map[symbol + 1] - 1; | |
230 | ||
231 | while (low <= high) | |
232 | { | |
233 | middle = (low + high) / 2; | |
234 | s = from_state[middle]; | |
235 | if (s == state) | |
36281465 | 236 | return middle; |
d0fb370f RS |
237 | else if (s < state) |
238 | low = middle + 1; | |
239 | else | |
240 | high = middle - 1; | |
241 | } | |
242 | ||
43591cec AD |
243 | assert (0); |
244 | /* NOTREACHED */ | |
d0fb370f RS |
245 | return 0; |
246 | } | |
247 | ||
248 | ||
4a120d45 | 249 | static void |
d2729d44 | 250 | initialize_F (void) |
d0fb370f | 251 | { |
4d4f699c AD |
252 | short **reads = XCALLOC (short *, ngotos); |
253 | short *edge = XCALLOC (short, ngotos + 1); | |
254 | int nedges = 0; | |
d0fb370f | 255 | |
4d4f699c | 256 | int i; |
d0fb370f | 257 | |
4d4f699c | 258 | F = XCALLOC (unsigned, ngotos * tokensetsize); |
d0fb370f | 259 | |
d0fb370f RS |
260 | for (i = 0; i < ngotos; i++) |
261 | { | |
80a69750 | 262 | int stateno = to_state[i]; |
29e88316 | 263 | shifts *sp = states[stateno]->shifts; |
d0fb370f | 264 | |
d954473d AD |
265 | int j; |
266 | for (j = 0; j < sp->nshifts && SHIFT_IS_SHIFT (sp, j); j++) | |
13ca549a | 267 | SETBIT (F (i), SHIFT_SYMBOL (sp, j)); |
d0fb370f | 268 | |
d954473d AD |
269 | for (; j < sp->nshifts; j++) |
270 | { | |
13ca549a | 271 | int symbol = SHIFT_SYMBOL (sp, j); |
d954473d AD |
272 | if (nullable[symbol]) |
273 | edge[nedges++] = map_goto (stateno, symbol); | |
274 | } | |
a0f6b076 | 275 | |
d954473d AD |
276 | if (nedges) |
277 | { | |
278 | reads[i] = XCALLOC (short, nedges + 1); | |
279 | shortcpy (reads[i], edge, nedges); | |
280 | reads[i][nedges] = -1; | |
281 | nedges = 0; | |
d0fb370f | 282 | } |
d0fb370f RS |
283 | } |
284 | ||
720d742f | 285 | digraph (reads); |
d0fb370f RS |
286 | |
287 | for (i = 0; i < ngotos; i++) | |
ddcd5fdf | 288 | XFREE (reads[i]); |
d0fb370f | 289 | |
d7913476 AD |
290 | XFREE (reads); |
291 | XFREE (edge); | |
d0fb370f RS |
292 | } |
293 | ||
294 | ||
4a120d45 | 295 | static void |
dac3c910 | 296 | add_lookback_edge (state_t *state, int ruleno, int gotono) |
d0fb370f | 297 | { |
720d742f | 298 | int i; |
720d742f | 299 | shorts *sp; |
d0fb370f | 300 | |
dac3c910 AD |
301 | for (i = 0; i < state->nlookaheads; ++i) |
302 | if (LAruleno[state->lookaheadsp + i] == ruleno) | |
065fbd27 | 303 | break; |
d0fb370f | 304 | |
dac3c910 | 305 | assert (LAruleno[state->lookaheadsp + i] == ruleno); |
d0fb370f | 306 | |
d7913476 | 307 | sp = XCALLOC (shorts, 1); |
dac3c910 | 308 | sp->next = lookback[state->lookaheadsp + i]; |
d0fb370f | 309 | sp->value = gotono; |
dac3c910 | 310 | lookback[state->lookaheadsp + i] = sp; |
d0fb370f RS |
311 | } |
312 | ||
313 | ||
f67d13aa AD |
314 | static void |
315 | matrix_print (FILE *out, short **matrix, int n) | |
316 | { | |
317 | int i, j; | |
318 | ||
319 | for (i = 0; i < n; ++i) | |
320 | { | |
321 | fprintf (out, "%3d: ", i); | |
322 | if (matrix[i]) | |
323 | for (j = 0; matrix[i][j] != -1; ++j) | |
324 | fprintf (out, "%3d ", matrix[i][j]); | |
325 | fputc ('\n', out); | |
326 | } | |
327 | fputc ('\n', out); | |
328 | } | |
329 | ||
9887c18a AD |
330 | /*-------------------------------------------------------------------. |
331 | | Return the transpose of R_ARG, of size N. Destroy R_ARG, as it is | | |
332 | | replaced with the result. | | |
f67d13aa AD |
333 | | | |
334 | | R_ARG[I] is NULL or a -1 terminated list of numbers. | | |
335 | | | | |
336 | | RESULT[NUM] is NULL or the -1 terminated list of the I such as NUM | | |
337 | | is in R_ARG[I]. | | |
9887c18a AD |
338 | `-------------------------------------------------------------------*/ |
339 | ||
4a120d45 | 340 | static short ** |
d2729d44 | 341 | transpose (short **R_arg, int n) |
d0fb370f | 342 | { |
f67d13aa AD |
343 | /* The result. */ |
344 | short **new_R = XCALLOC (short *, n); | |
345 | /* END_R[I] -- next entry of NEW_R[I]. */ | |
346 | short **end_R = XCALLOC (short *, n); | |
347 | /* NEDGES[I] -- total size of NEW_R[I]. */ | |
348 | short *nedges = XCALLOC (short, n); | |
349 | int i, j; | |
350 | ||
351 | if (trace_flag) | |
d0fb370f | 352 | { |
f67d13aa AD |
353 | fputs ("transpose: input\n", stderr); |
354 | matrix_print (stderr, R_arg, n); | |
d0fb370f RS |
355 | } |
356 | ||
f67d13aa AD |
357 | /* Count. */ |
358 | for (i = 0; i < n; i++) | |
359 | if (R_arg[i]) | |
360 | for (j = 0; R_arg[i][j] >= 0; ++j) | |
361 | ++nedges[R_arg[i][j]]; | |
d0fb370f | 362 | |
f67d13aa | 363 | /* Allocate. */ |
d0fb370f | 364 | for (i = 0; i < n; i++) |
80a69750 AD |
365 | if (nedges[i] > 0) |
366 | { | |
367 | short *sp = XCALLOC (short, nedges[i] + 1); | |
80a69750 | 368 | sp[nedges[i]] = -1; |
f67d13aa AD |
369 | new_R[i] = sp; |
370 | end_R[i] = sp; | |
80a69750 | 371 | } |
d0fb370f | 372 | |
f67d13aa | 373 | /* Store. */ |
d0fb370f | 374 | for (i = 0; i < n; i++) |
f67d13aa AD |
375 | if (R_arg[i]) |
376 | for (j = 0; R_arg[i][j] >= 0; ++j) | |
377 | { | |
378 | *end_R[R_arg[i][j]] = i; | |
379 | ++end_R[R_arg[i][j]]; | |
380 | } | |
d0fb370f | 381 | |
f67d13aa AD |
382 | free (nedges); |
383 | free (end_R); | |
d0fb370f | 384 | |
9887c18a AD |
385 | /* Free the input: it is replaced with the result. */ |
386 | for (i = 0; i < n; i++) | |
387 | XFREE (R_arg[i]); | |
f67d13aa AD |
388 | free (R_arg); |
389 | ||
390 | if (trace_flag) | |
391 | { | |
392 | fputs ("transpose: output\n", stderr); | |
393 | matrix_print (stderr, new_R, n); | |
394 | } | |
9887c18a | 395 | |
36281465 | 396 | return new_R; |
d0fb370f RS |
397 | } |
398 | ||
399 | ||
4a120d45 | 400 | static void |
720d742f | 401 | build_relations (void) |
d0fb370f | 402 | { |
9887c18a | 403 | short *edge = XCALLOC (short, ngotos + 1); |
b9f71f19 | 404 | short *states1 = XCALLOC (short, ritem_longest_rhs () + 1); |
720d742f | 405 | int i; |
720d742f | 406 | |
d7913476 | 407 | includes = XCALLOC (short *, ngotos); |
d0fb370f RS |
408 | |
409 | for (i = 0; i < ngotos; i++) | |
410 | { | |
9887c18a | 411 | int nedges = 0; |
29e88316 | 412 | int symbol1 = states[to_state[i]]->accessing_symbol; |
9887c18a | 413 | short *rulep; |
d0fb370f | 414 | |
720d742f AD |
415 | for (rulep = derives[symbol1]; *rulep > 0; rulep++) |
416 | { | |
9887c18a | 417 | int done; |
80a69750 | 418 | int length = 1; |
9887c18a | 419 | short *rp; |
29e88316 | 420 | state_t *state = states[from_state[i]]; |
b9f71f19 | 421 | states1[0] = state->number; |
d0fb370f | 422 | |
1a2b5d37 | 423 | for (rp = &ritem[rules[*rulep].rhs]; *rp >= 0; rp++) |
720d742f | 424 | { |
dac3c910 | 425 | shifts *sp = state->shifts; |
9887c18a | 426 | int j; |
80a69750 | 427 | for (j = 0; j < sp->nshifts; j++) |
720d742f | 428 | { |
29e88316 | 429 | state = states[sp->shifts[j]]; |
dac3c910 | 430 | if (state->accessing_symbol == *rp) |
720d742f AD |
431 | break; |
432 | } | |
d0fb370f | 433 | |
b9f71f19 | 434 | states1[length++] = state->number; |
720d742f AD |
435 | } |
436 | ||
dac3c910 AD |
437 | if (!state->consistent) |
438 | add_lookback_edge (state, *rulep, i); | |
720d742f AD |
439 | |
440 | length--; | |
441 | done = 0; | |
442 | while (!done) | |
443 | { | |
444 | done = 1; | |
445 | rp--; | |
446 | /* JF added rp>=ritem && I hope to god its right! */ | |
447 | if (rp >= ritem && ISVAR (*rp)) | |
448 | { | |
b9f71f19 | 449 | edge[nedges++] = map_goto (states1[--length], *rp); |
720d742f AD |
450 | if (nullable[*rp]) |
451 | done = 0; | |
452 | } | |
453 | } | |
d0fb370f RS |
454 | } |
455 | ||
720d742f AD |
456 | if (nedges) |
457 | { | |
9887c18a | 458 | int j; |
80a69750 | 459 | includes[i] = XCALLOC (short, nedges + 1); |
720d742f | 460 | for (j = 0; j < nedges; j++) |
80a69750 AD |
461 | includes[i][j] = edge[j]; |
462 | includes[i][nedges] = -1; | |
720d742f | 463 | } |
d0fb370f RS |
464 | } |
465 | ||
d7913476 | 466 | XFREE (edge); |
b9f71f19 | 467 | XFREE (states1); |
9887c18a AD |
468 | |
469 | includes = transpose (includes, ngotos); | |
d0fb370f RS |
470 | } |
471 | ||
472 | ||
720d742f | 473 | |
4a120d45 | 474 | static void |
720d742f | 475 | compute_FOLLOWS (void) |
d0fb370f | 476 | { |
720d742f | 477 | int i; |
d0fb370f | 478 | |
720d742f | 479 | digraph (includes); |
d0fb370f RS |
480 | |
481 | for (i = 0; i < ngotos; i++) | |
ddcd5fdf | 482 | XFREE (includes[i]); |
d0fb370f | 483 | |
d7913476 | 484 | XFREE (includes); |
d0fb370f RS |
485 | } |
486 | ||
487 | ||
4a120d45 | 488 | static void |
720d742f | 489 | compute_lookaheads (void) |
d0fb370f | 490 | { |
d200e455 | 491 | size_t i; |
720d742f | 492 | shorts *sp; |
d0fb370f | 493 | |
d200e455 | 494 | for (i = 0; i < nLA; i++) |
ddcd5fdf AD |
495 | for (sp = lookback[i]; sp; sp = sp->next) |
496 | { | |
9887c18a AD |
497 | int size = LA (i + 1) - LA (i); |
498 | int j; | |
499 | for (j = 0; j < size; ++j) | |
500 | LA (i)[j] |= F (sp->value)[j]; | |
ddcd5fdf | 501 | } |
d0fb370f | 502 | |
ddcd5fdf | 503 | /* Free LOOKBACK. */ |
d200e455 | 504 | for (i = 0; i < nLA; i++) |
300f275f | 505 | LIST_FREE (shorts, lookback[i]); |
d0fb370f | 506 | |
d7913476 AD |
507 | XFREE (lookback); |
508 | XFREE (F); | |
720d742f | 509 | } |
d0fb370f | 510 | |
d0fb370f | 511 | |
5edafffd AD |
512 | /*--------------------------------------. |
513 | | Initializing the lookaheads members. | | |
514 | `--------------------------------------*/ | |
515 | ||
516 | static void | |
517 | initialize_lookaheads (void) | |
518 | { | |
519 | int i; | |
d200e455 | 520 | nLA = 0; |
5edafffd AD |
521 | for (i = 0; i < nstates; i++) |
522 | { | |
523 | int k; | |
3877f72b | 524 | int nlookaheads = 0; |
29e88316 AD |
525 | reductions *rp = states[i]->reductions; |
526 | shifts *sp = states[i]->shifts; | |
5edafffd | 527 | |
80dac38c AD |
528 | /* We need a lookahead either to distinguish different |
529 | reductions (i.e., there are two or more), or to distinguish a | |
530 | reduction from a shift. Otherwise, it is straightforward, | |
531 | and the state is `consistent'. */ | |
532 | if (rp->nreds > 1 | |
533 | || (rp->nreds == 1 && sp->nshifts && SHIFT_IS_SHIFT (sp, 0))) | |
3877f72b | 534 | nlookaheads += rp->nreds; |
5edafffd | 535 | else |
29e88316 | 536 | states[i]->consistent = 1; |
5edafffd AD |
537 | |
538 | for (k = 0; k < sp->nshifts; k++) | |
539 | if (SHIFT_IS_ERROR (sp, k)) | |
540 | { | |
29e88316 | 541 | states[i]->consistent = 0; |
5edafffd AD |
542 | break; |
543 | } | |
3877f72b | 544 | |
29e88316 AD |
545 | states[i]->nlookaheads = nlookaheads; |
546 | states[i]->lookaheadsp = nLA; | |
d200e455 | 547 | nLA += nlookaheads; |
5edafffd | 548 | } |
5edafffd AD |
549 | } |
550 | ||
7c6b64d0 AD |
551 | |
552 | /*---------------------------------------. | |
553 | | Output the lookaheads for each state. | | |
554 | `---------------------------------------*/ | |
555 | ||
556 | static void | |
557 | lookaheads_print (FILE *out) | |
558 | { | |
559 | int i, j, k; | |
560 | fprintf (out, "Lookaheads: BEGIN\n"); | |
561 | for (i = 0; i < nstates; ++i) | |
562 | { | |
563 | fprintf (out, "State %d: %d lookaheads\n", | |
29e88316 | 564 | i, states[i]->nlookaheads); |
7c6b64d0 | 565 | |
29e88316 | 566 | for (j = 0; j < states[i]->nlookaheads; ++j) |
7c6b64d0 | 567 | for (k = 0; k < ntokens; ++k) |
29e88316 | 568 | if (BITISSET (LA (states[i]->lookaheadsp + j), j)) |
7c6b64d0 | 569 | fprintf (out, " on %d (%s) -> rule %d\n", |
ad949da9 | 570 | k, symbols[k]->tag, |
29e88316 | 571 | -LAruleno[states[i]->lookaheadsp + j] - 1); |
7c6b64d0 AD |
572 | } |
573 | fprintf (out, "Lookaheads: END\n"); | |
574 | } | |
575 | ||
720d742f AD |
576 | void |
577 | lalr (void) | |
578 | { | |
579 | tokensetsize = WORDSIZE (ntokens); | |
580 | ||
5edafffd | 581 | initialize_lookaheads (); |
720d742f AD |
582 | initialize_LA (); |
583 | set_goto_map (); | |
584 | initialize_F (); | |
585 | build_relations (); | |
586 | compute_FOLLOWS (); | |
587 | compute_lookaheads (); | |
7c6b64d0 AD |
588 | |
589 | if (trace_flag) | |
590 | lookaheads_print (stderr); | |
d0fb370f | 591 | } |