ce076d4d3c887b04f6fc082de49ea9a29b50a5ac
[bison.git] / src / lalr.c
1 /* Compute look-ahead criteria for bison,
2 Copyright 1984, 1986, 1989, 2000 Free Software Foundation, Inc.
3
4 This file is part of Bison, the GNU Compiler Compiler.
5
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.
10
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.
15
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. */
20
21
22 /* Compute how to make the finite state machine deterministic; find
23 which rules need lookahead in each state, and which lookahead
24 tokens they accept. */
25
26 #include "system.h"
27 #include "types.h"
28 #include "LR0.h"
29 #include "gram.h"
30 #include "complain.h"
31 #include "lalr.h"
32 #include "nullable.h"
33 #include "derives.h"
34
35 /* All the decorated states, indexed by the state number. Warning:
36 there is a state_TABLE in LR0.c, but it is different and static.
37 */
38 state_t *state_table = NULL;
39
40 int tokensetsize;
41 short *LAruleno;
42 unsigned *LA;
43
44 short *goto_map;
45 short *from_state;
46 short *to_state;
47
48 extern void berror PARAMS ((const char *));
49
50 static int infinity;
51 static int maxrhs;
52 static int ngotos;
53 static unsigned *F;
54 static short **includes;
55 static shorts **lookback;
56 static short **R;
57 static short *INDEX;
58 static short *VERTICES;
59 static int top;
60
61
62 static void
63 traverse (int i)
64 {
65 unsigned *fp1;
66 unsigned *fp2;
67 unsigned *fp3;
68 int j;
69 short *rp;
70
71 int height;
72 unsigned *base;
73
74 VERTICES[++top] = i;
75 INDEX[i] = height = top;
76
77 base = F + i * tokensetsize;
78 fp3 = base + tokensetsize;
79
80 rp = R[i];
81 if (rp)
82 {
83 while ((j = *rp++) >= 0)
84 {
85 if (INDEX[j] == 0)
86 traverse (j);
87
88 if (INDEX[i] > INDEX[j])
89 INDEX[i] = INDEX[j];
90
91 fp1 = base;
92 fp2 = F + j * tokensetsize;
93
94 while (fp1 < fp3)
95 *fp1++ |= *fp2++;
96 }
97 }
98
99 if (INDEX[i] == height)
100 {
101 for (;;)
102 {
103 j = VERTICES[top--];
104 INDEX[j] = infinity;
105
106 if (i == j)
107 break;
108
109 fp1 = base;
110 fp2 = F + j * tokensetsize;
111
112 while (fp1 < fp3)
113 *fp2++ = *fp1++;
114 }
115 }
116 }
117
118
119 static void
120 digraph (short **relation)
121 {
122 int i;
123
124 infinity = ngotos + 2;
125 INDEX = XCALLOC (short, ngotos + 1);
126 VERTICES = XCALLOC (short, ngotos + 1);
127 top = 0;
128
129 R = relation;
130
131 for (i = 0; i < ngotos; i++)
132 INDEX[i] = 0;
133
134 for (i = 0; i < ngotos; i++)
135 {
136 if (INDEX[i] == 0 && R[i])
137 traverse (i);
138 }
139
140 XFREE (INDEX);
141 XFREE (VERTICES);
142 }
143
144 static void
145 set_state_table (void)
146 {
147 /* NSTATES + 1 because lookahead for the pseudo state number NSTATES
148 might be used (see conflicts.c). It is too opaque for me to
149 provide a probably less hacky implementation. --akim */
150 state_table = XCALLOC (state_t, nstates + 1);
151
152 {
153 core *sp;
154 for (sp = first_state; sp; sp = sp->next)
155 {
156 state_table[sp->number].state = sp;
157 state_table[sp->number].accessing_symbol = sp->accessing_symbol;
158 }
159 }
160
161 {
162 shifts *sp;
163 for (sp = first_shift; sp; sp = sp->next)
164 state_table[sp->number].shift_table = sp;
165 }
166
167 {
168 reductions *rp;
169 for (rp = first_reduction; rp; rp = rp->next)
170 state_table[rp->number].reduction_table = rp;
171 }
172
173 /* Initializing the lookaheads members. Please note that it must be
174 performed after having set some of the other members which are
175 used below. Change with extreme caution. */
176 {
177 int i;
178 int count = 0;
179 for (i = 0; i < nstates; i++)
180 {
181 int k;
182 reductions *rp = state_table[i].reduction_table;
183 shifts *sp = state_table[i].shift_table;
184
185 state_table[i].lookaheads = count;
186
187 if (rp
188 && (rp->nreds > 1
189 || (sp && !ISVAR (state_table[sp->shifts[0]].accessing_symbol))))
190 count += rp->nreds;
191 else
192 state_table[i].consistent = 1;
193
194 if (sp)
195 for (k = 0; k < sp->nshifts; k++)
196 if (state_table[sp->shifts[k]].accessing_symbol
197 == error_token_number)
198 {
199 state_table[i].consistent = 0;
200 break;
201 }
202 }
203 state_table[nstates].lookaheads = count;
204 }
205 }
206
207
208 static void
209 set_maxrhs (void)
210 {
211 short *itemp;
212 int length;
213 int max;
214
215 length = 0;
216 max = 0;
217 for (itemp = ritem; *itemp; itemp++)
218 {
219 if (*itemp > 0)
220 {
221 length++;
222 }
223 else
224 {
225 if (length > max)
226 max = length;
227 length = 0;
228 }
229 }
230
231 maxrhs = max;
232 }
233
234
235 static void
236 initialize_LA (void)
237 {
238 int i;
239 int j;
240 short *np;
241 reductions *rp;
242
243 size_t nLA = state_table[nstates].lookaheads;
244 if (!nLA)
245 nLA = 1;
246
247 LA = XCALLOC (unsigned, nLA * tokensetsize);
248 LAruleno = XCALLOC (short, nLA);
249 lookback = XCALLOC (shorts *, nLA);
250
251 np = LAruleno;
252 for (i = 0; i < nstates; i++)
253 if (!state_table[i].consistent)
254 if ((rp = state_table[i].reduction_table))
255 for (j = 0; j < rp->nreds; j++)
256 *np++ = rp->rules[j];
257 }
258
259
260 static void
261 set_goto_map (void)
262 {
263 shifts *sp;
264 int i;
265 int symbol;
266 int k;
267 short *temp_map;
268 int state2;
269 int state1;
270
271 goto_map = XCALLOC (short, nvars + 1) - ntokens;
272 temp_map = XCALLOC (short, nvars + 1) - ntokens;
273
274 ngotos = 0;
275 for (sp = first_shift; sp; sp = sp->next)
276 {
277 for (i = sp->nshifts - 1; i >= 0; i--)
278 {
279 symbol = state_table[sp->shifts[i]].accessing_symbol;
280
281 if (ISTOKEN (symbol))
282 break;
283
284 if (ngotos == MAXSHORT)
285 fatal (_("too many gotos (max %d)"), MAXSHORT);
286
287 ngotos++;
288 goto_map[symbol]++;
289 }
290 }
291
292 k = 0;
293 for (i = ntokens; i < nsyms; i++)
294 {
295 temp_map[i] = k;
296 k += goto_map[i];
297 }
298
299 for (i = ntokens; i < nsyms; i++)
300 goto_map[i] = temp_map[i];
301
302 goto_map[nsyms] = ngotos;
303 temp_map[nsyms] = ngotos;
304
305 from_state = XCALLOC (short, ngotos);
306 to_state = XCALLOC (short, ngotos);
307
308 for (sp = first_shift; sp; sp = sp->next)
309 {
310 state1 = sp->number;
311 for (i = sp->nshifts - 1; i >= 0; i--)
312 {
313 state2 = sp->shifts[i];
314 symbol = state_table[state2].accessing_symbol;
315
316 if (ISTOKEN (symbol))
317 break;
318
319 k = temp_map[symbol]++;
320 from_state[k] = state1;
321 to_state[k] = state2;
322 }
323 }
324
325 XFREE (temp_map + ntokens);
326 }
327
328
329
330 /*----------------------------------------------------------.
331 | Map a state/symbol pair into its numeric representation. |
332 `----------------------------------------------------------*/
333
334 static int
335 map_goto (int state, int symbol)
336 {
337 int high;
338 int low;
339 int middle;
340 int s;
341
342 low = goto_map[symbol];
343 high = goto_map[symbol + 1] - 1;
344
345 while (low <= high)
346 {
347 middle = (low + high) / 2;
348 s = from_state[middle];
349 if (s == state)
350 return middle;
351 else if (s < state)
352 low = middle + 1;
353 else
354 high = middle - 1;
355 }
356
357 assert (0);
358 /* NOTREACHED */
359 return 0;
360 }
361
362
363 static void
364 initialize_F (void)
365 {
366 int i;
367 int j;
368 int k;
369 shifts *sp;
370 short *edge;
371 unsigned *rowp;
372 short *rp;
373 short **reads;
374 int nedges;
375 int stateno;
376 int symbol;
377 int nwords;
378
379 nwords = ngotos * tokensetsize;
380 F = XCALLOC (unsigned, nwords);
381
382 reads = XCALLOC (short *, ngotos);
383 edge = XCALLOC (short, ngotos + 1);
384 nedges = 0;
385
386 rowp = F;
387 for (i = 0; i < ngotos; i++)
388 {
389 stateno = to_state[i];
390 sp = state_table[stateno].shift_table;
391
392 if (sp)
393 {
394 k = sp->nshifts;
395
396 for (j = 0; j < k; j++)
397 {
398 symbol = state_table[sp->shifts[j]].accessing_symbol;
399 if (ISVAR (symbol))
400 break;
401 SETBIT (rowp, symbol);
402 }
403
404 for (; j < k; j++)
405 {
406 symbol = state_table[sp->shifts[j]].accessing_symbol;
407 if (nullable[symbol])
408 edge[nedges++] = map_goto (stateno, symbol);
409 }
410
411 if (nedges)
412 {
413 reads[i] = rp = XCALLOC (short, nedges + 1);
414
415 for (j = 0; j < nedges; j++)
416 rp[j] = edge[j];
417
418 rp[nedges] = -1;
419 nedges = 0;
420 }
421 }
422
423 rowp += tokensetsize;
424 }
425
426 digraph (reads);
427
428 for (i = 0; i < ngotos; i++)
429 {
430 if (reads[i])
431 XFREE (reads[i]);
432 }
433
434 XFREE (reads);
435 XFREE (edge);
436 }
437
438
439 static void
440 add_lookback_edge (int stateno, int ruleno, int gotono)
441 {
442 int i;
443 int k;
444 int found;
445 shorts *sp;
446
447 i = state_table[stateno].lookaheads;
448 k = state_table[stateno + 1].lookaheads;
449 found = 0;
450 while (!found && i < k)
451 {
452 if (LAruleno[i] == ruleno)
453 found = 1;
454 else
455 i++;
456 }
457
458 assert (found);
459
460 sp = XCALLOC (shorts, 1);
461 sp->next = lookback[i];
462 sp->value = gotono;
463 lookback[i] = sp;
464 }
465
466
467 static short **
468 transpose (short **R_arg, int n)
469 {
470 short **new_R;
471 short **temp_R;
472 short *nedges;
473 short *sp;
474 int i;
475 int k;
476
477 nedges = XCALLOC (short, n);
478
479 for (i = 0; i < n; i++)
480 {
481 sp = R_arg[i];
482 if (sp)
483 {
484 while (*sp >= 0)
485 nedges[*sp++]++;
486 }
487 }
488
489 new_R = XCALLOC (short *, n);
490 temp_R = XCALLOC (short *, n);
491
492 for (i = 0; i < n; i++)
493 {
494 k = nedges[i];
495 if (k > 0)
496 {
497 sp = XCALLOC (short, k + 1);
498 new_R[i] = sp;
499 temp_R[i] = sp;
500 sp[k] = -1;
501 }
502 }
503
504 XFREE (nedges);
505
506 for (i = 0; i < n; i++)
507 {
508 sp = R_arg[i];
509 if (sp)
510 {
511 while (*sp >= 0)
512 *temp_R[*sp++]++ = i;
513 }
514 }
515
516 XFREE (temp_R);
517
518 return new_R;
519 }
520
521
522 static void
523 build_relations (void)
524 {
525 int i;
526 int j;
527 int k;
528 short *rulep;
529 short *rp;
530 shifts *sp;
531 int length;
532 int nedges;
533 int done;
534 int state1;
535 int stateno;
536 int symbol1;
537 int symbol2;
538 short *shortp;
539 short *edge;
540 short *states;
541 short **new_includes;
542
543 includes = XCALLOC (short *, ngotos);
544 edge = XCALLOC (short, ngotos + 1);
545 states = XCALLOC (short, maxrhs + 1);
546
547 for (i = 0; i < ngotos; i++)
548 {
549 nedges = 0;
550 state1 = from_state[i];
551 symbol1 = state_table[to_state[i]].accessing_symbol;
552
553 for (rulep = derives[symbol1]; *rulep > 0; rulep++)
554 {
555 length = 1;
556 states[0] = state1;
557 stateno = state1;
558
559 for (rp = ritem + rrhs[*rulep]; *rp > 0; rp++)
560 {
561 symbol2 = *rp;
562 sp = state_table[stateno].shift_table;
563 k = sp->nshifts;
564
565 for (j = 0; j < k; j++)
566 {
567 stateno = sp->shifts[j];
568 if (state_table[stateno].accessing_symbol == symbol2)
569 break;
570 }
571
572 states[length++] = stateno;
573 }
574
575 if (!state_table[stateno].consistent)
576 add_lookback_edge (stateno, *rulep, i);
577
578 length--;
579 done = 0;
580 while (!done)
581 {
582 done = 1;
583 rp--;
584 /* JF added rp>=ritem && I hope to god its right! */
585 if (rp >= ritem && ISVAR (*rp))
586 {
587 stateno = states[--length];
588 edge[nedges++] = map_goto (stateno, *rp);
589 if (nullable[*rp])
590 done = 0;
591 }
592 }
593 }
594
595 if (nedges)
596 {
597 includes[i] = shortp = XCALLOC (short, nedges + 1);
598 for (j = 0; j < nedges; j++)
599 shortp[j] = edge[j];
600 shortp[nedges] = -1;
601 }
602 }
603
604 new_includes = transpose (includes, ngotos);
605
606 for (i = 0; i < ngotos; i++)
607 if (includes[i])
608 XFREE (includes[i]);
609
610 XFREE (includes);
611
612 includes = new_includes;
613
614 XFREE (edge);
615 XFREE (states);
616 }
617
618
619
620 static void
621 compute_FOLLOWS (void)
622 {
623 int i;
624
625 digraph (includes);
626
627 for (i = 0; i < ngotos; i++)
628 {
629 if (includes[i])
630 XFREE (includes[i]);
631 }
632
633 XFREE (includes);
634 }
635
636
637 static void
638 compute_lookaheads (void)
639 {
640 int i;
641 int n;
642 unsigned *fp1;
643 unsigned *fp2;
644 unsigned *fp3;
645 shorts *sp;
646 unsigned *rowp;
647 shorts *sptmp; /* JF */
648
649 rowp = LA;
650 for (i = 0; i < state_table[nstates].lookaheads; i++)
651 {
652 fp3 = rowp + tokensetsize;
653 for (sp = lookback[i]; sp; sp = sp->next)
654 {
655 fp1 = rowp;
656 fp2 = F + tokensetsize * sp->value;
657 while (fp1 < fp3)
658 *fp1++ |= *fp2++;
659 }
660
661 rowp = fp3;
662 }
663
664 for (i = 0; i < state_table[nstates].lookaheads; i++)
665 {
666 /* JF removed ref to freed storage */
667 for (sp = lookback[i]; sp; sp = sptmp)
668 {
669 sptmp = sp->next;
670 XFREE (sp);
671 }
672 }
673
674 XFREE (lookback);
675 XFREE (F);
676 }
677
678
679 void
680 lalr (void)
681 {
682 tokensetsize = WORDSIZE (ntokens);
683
684 set_state_table ();
685 set_maxrhs ();
686 initialize_LA ();
687 set_goto_map ();
688 initialize_F ();
689 build_relations ();
690 compute_FOLLOWS ();
691 compute_lookaheads ();
692 }