Really add m4sugar to the repo.
[bison.git] / src / lalr.c
CommitLineData
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 39state_t **states = NULL;
9703cc49 40
d0fb370f 41int tokensetsize;
d0fb370f
RS
42short *LAruleno;
43unsigned *LA;
d200e455 44size_t nLA;
9703cc49 45
aa2aab3c 46static int ngotos;
d0fb370f
RS
47short *goto_map;
48short *from_state;
49short *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>. */
53static unsigned *F = NULL;
54#define F(Rule) (F + (Rule) * tokensetsize)
55
d0fb370f
RS
56static short **includes;
57static 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
67static short **R;
68static short *INDEX;
69static short *VERTICES;
70static int top;
aa2aab3c 71static int infinity;
d0fb370f 72
720d742f
AD
73static void
74traverse (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
112static void
113digraph (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 136static void
d2729d44 137initialize_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 159static void
d2729d44 160set_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 220static int
d2729d44 221map_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 249static void
d2729d44 250initialize_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 295static void
dac3c910 296add_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
314static void
315matrix_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 340static short **
d2729d44 341transpose (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 400static void
720d742f 401build_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 474static void
720d742f 475compute_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 488static void
720d742f 489compute_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
516static void
517initialize_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
556static void
557lookaheads_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
576void
577lalr (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}