2 * Copyright (c) 1989 The Regents of the University of California.
5 * This code is derived from software contributed to Berkeley by
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. All advertising materials mentioning features or use of this software
17 * must display the following acknowledgement:
18 * This product includes software developed by the University of
19 * California, Berkeley and its contributors.
20 * 4. Neither the name of the University nor the names of its contributors
21 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission.
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 * $FreeBSD: src/usr.bin/yacc/lalr.c,v 1.7 1999/08/28 01:07:59 peter Exp $
37 * $DragonFly: src/usr.bin/yacc/lalr.c,v 1.2 2003/06/17 04:29:34 dillon Exp $
39 * @(#)lalr.c 5.3 (Berkeley) 6/1/90
57 short *accessing_symbol;
60 reductions **reduction_table;
65 static void add_lookback_edge __P((int, int, int));
66 static void build_relations __P((void));
67 static void compute_FOLLOWS __P((void));
68 static void compute_lookaheads __P((void));
69 static void digraph __P((short **));
70 static void initialize_F __P((void));
71 static void initialize_LA __P((void));
72 static int map_goto __P((int, int));
73 static void set_accessing_symbol __P((void));
74 static void set_goto_map __P((void));
75 static void set_maxrhs __P((void));
76 static void set_reduction_table __P((void));
77 static void set_shift_table __P((void));
78 static void set_state_table __P((void));
79 static short **transpose __P((short **, int));
80 static void traverse __P((register int));
86 static short **includes;
87 static shorts **lookback;
90 static short *VERTICES;
97 tokensetsize = WORDSIZE(ntokens);
100 set_accessing_symbol();
102 set_reduction_table();
109 compute_lookaheads();
119 state_table = NEW2(nstates, core *);
120 for (sp = first_state; sp; sp = sp->next)
121 state_table[sp->number] = sp;
127 set_accessing_symbol()
131 accessing_symbol = NEW2(nstates, short);
132 for (sp = first_state; sp; sp = sp->next)
133 accessing_symbol[sp->number] = sp->accessing_symbol;
143 shift_table = NEW2(nstates, shifts *);
144 for (sp = first_shift; sp; sp = sp->next)
145 shift_table[sp->number] = sp;
151 set_reduction_table()
153 register reductions *rp;
155 reduction_table = NEW2(nstates, reductions *);
156 for (rp = first_reduction; rp; rp = rp->next)
157 reduction_table[rp->number] = rp;
165 register short *itemp;
166 register short *item_end;
172 item_end = ritem + nitems;
173 for (itemp = ritem; itemp < item_end; itemp++)
181 if (length > max) max = length;
194 register int i, j, k;
195 register reductions *rp;
197 lookaheads = NEW2(nstates + 1, short);
200 for (i = 0; i < nstates; i++)
203 rp = reduction_table[i];
207 lookaheads[nstates] = k;
209 LA = NEW2(k * tokensetsize, unsigned);
210 LAruleno = NEW2(k, short);
211 lookback = NEW2(k, shorts *);
214 for (i = 0; i < nstates; i++)
216 rp = reduction_table[i];
219 for (j = 0; j < rp->nreds; j++)
221 LAruleno[k] = rp->rules[j];
236 register short *temp_map;
240 goto_map = NEW2(nvars + 1, short) - ntokens;
241 temp_map = NEW2(nvars + 1, short) - ntokens;
244 for (sp = first_shift; sp; sp = sp->next)
246 for (i = sp->nshifts - 1; i >= 0; i--)
248 symbol = accessing_symbol[sp->shift[i]];
250 if (ISTOKEN(symbol)) break;
252 if (ngotos == MAXSHORT)
253 fatal("too many gotos");
261 for (i = ntokens; i < nsyms; i++)
267 for (i = ntokens; i < nsyms; i++)
268 goto_map[i] = temp_map[i];
270 goto_map[nsyms] = ngotos;
271 temp_map[nsyms] = ngotos;
273 from_state = NEW2(ngotos, short);
274 to_state = NEW2(ngotos, short);
276 for (sp = first_shift; sp; sp = sp->next)
279 for (i = sp->nshifts - 1; i >= 0; i--)
281 state2 = sp->shift[i];
282 symbol = accessing_symbol[state2];
284 if (ISTOKEN(symbol)) break;
286 k = temp_map[symbol]++;
287 from_state[k] = state1;
288 to_state[k] = state2;
292 FREE(temp_map + ntokens);
297 /* Map_goto maps a state/symbol pair into its numeric representation. */
300 map_goto(state, symbol)
309 low = goto_map[symbol];
310 high = goto_map[symbol + 1];
315 middle = (low + high) >> 1;
316 s = from_state[middle];
335 register short *edge;
336 register unsigned *rowp;
338 register short **reads;
340 register int stateno;
344 nwords = ngotos * tokensetsize;
345 F = NEW2(nwords, unsigned);
347 reads = NEW2(ngotos, short *);
348 edge = NEW2(ngotos + 1, short);
352 for (i = 0; i < ngotos; i++)
354 stateno = to_state[i];
355 sp = shift_table[stateno];
361 for (j = 0; j < k; j++)
363 symbol = accessing_symbol[sp->shift[j]];
366 SETBIT(rowp, symbol);
371 symbol = accessing_symbol[sp->shift[j]];
372 if (nullable[symbol])
373 edge[nedges++] = map_goto(stateno, symbol);
378 reads[i] = rp = NEW2(nedges + 1, short);
380 for (j = 0; j < nedges; j++)
388 rowp += tokensetsize;
394 for (i = 0; i < ngotos; i++)
412 register short *rulep;
419 register int stateno;
420 register int symbol1;
421 register int symbol2;
422 register short *shortp;
423 register short *edge;
424 register short *states;
425 register short **new_includes;
427 includes = NEW2(ngotos, short *);
428 edge = NEW2(ngotos + 1, short);
429 states = NEW2(maxrhs + 1, short);
431 for (i = 0; i < ngotos; i++)
434 state1 = from_state[i];
435 symbol1 = accessing_symbol[to_state[i]];
437 for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
443 for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
446 sp = shift_table[stateno];
449 for (j = 0; j < k; j++)
451 stateno = sp->shift[j];
452 if (accessing_symbol[stateno] == symbol2) break;
455 states[length++] = stateno;
458 add_lookback_edge(stateno, *rulep, i);
468 stateno = states[--length];
469 edge[nedges++] = map_goto(stateno, *rp);
470 if (nullable[*rp] && length > 0) done = 0;
477 includes[i] = shortp = NEW2(nedges + 1, short);
478 for (j = 0; j < nedges; j++)
484 new_includes = transpose(includes, ngotos);
486 for (i = 0; i < ngotos; i++)
492 includes = new_includes;
500 add_lookback_edge(stateno, ruleno, gotono)
501 int stateno, ruleno, gotono;
507 i = lookaheads[stateno];
508 k = lookaheads[stateno + 1];
510 while (!found && i < k)
512 if (LAruleno[i] == ruleno)
520 sp->next = lookback[i];
532 register short **new_R;
533 register short **temp_R;
534 register short *nedges;
539 nedges = NEW2(n, short);
541 for (i = 0; i < n; i++)
551 new_R = NEW2(n, short *);
552 temp_R = NEW2(n, short *);
554 for (i = 0; i < n; i++)
559 sp = NEW2(k + 1, short);
568 for (i = 0; i < n; i++)
574 *temp_R[*sp++]++ = i;
596 register unsigned *fp1, *fp2, *fp3;
597 register shorts *sp, *next;
598 register unsigned *rowp;
601 n = lookaheads[nstates];
602 for (i = 0; i < n; i++)
604 fp3 = rowp + tokensetsize;
605 for (sp = lookback[i]; sp; sp = sp->next)
608 fp2 = F + tokensetsize * sp->value;
615 for (i = 0; i < n; i++)
616 for (sp = lookback[i]; sp; sp = next)
633 infinity = ngotos + 2;
634 INDEX = NEW2(ngotos + 1, short);
635 VERTICES = NEW2(ngotos + 1, short);
640 for (i = 0; i < ngotos; i++)
643 for (i = 0; i < ngotos; i++)
645 if (INDEX[i] == 0 && R[i])
659 register unsigned *fp1;
660 register unsigned *fp2;
661 register unsigned *fp3;
669 INDEX[i] = height = top;
671 base = F + i * tokensetsize;
672 fp3 = base + tokensetsize;
677 while ((j = *rp++) >= 0)
682 if (INDEX[i] > INDEX[j])
686 fp2 = F + j * tokensetsize;
693 if (INDEX[i] == height)
704 fp2 = F + j * tokensetsize;