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.5 2005/01/05 15:26:05 joerg Exp $
39 * @(#)lalr.c 5.3 (Berkeley) 6/1/90
57 short *accessing_symbol;
60 reductions **reduction_table;
65 static void add_lookback_edge(int, int, int);
66 static void build_relations(void);
67 static void compute_FOLLOWS(void);
68 static void compute_lookaheads(void);
69 static void digraph(short **);
70 static void initialize_F(void);
71 static void initialize_LA(void);
72 static int map_goto(int, int);
73 static void set_accessing_symbol(void);
74 static void set_goto_map(void);
75 static void set_maxrhs(void);
76 static void set_reduction_table(void);
77 static void set_shift_table(void);
78 static void set_state_table(void);
79 static short **transpose(short **, int);
80 static void traverse(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();
115 set_state_table(void)
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(void)
131 accessing_symbol = NEW2(nstates, short);
132 for (sp = first_state; sp; sp = sp->next)
133 accessing_symbol[sp->number] = sp->accessing_symbol;
139 set_shift_table(void)
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(void)
155 reduction_table = NEW2(nstates, reductions *);
156 for (rp = first_reduction; rp; rp = rp->next)
157 reduction_table[rp->number] = rp;
172 item_end = ritem + nitems;
173 for (itemp = ritem; itemp < item_end; itemp++)
181 if (length > max) max = length;
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];
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(int state, int symbol)
307 low = goto_map[symbol];
308 high = goto_map[symbol + 1];
313 middle = (low + high) >> 1;
314 s = from_state[middle];
342 nwords = ngotos * tokensetsize;
343 F = NEW2(nwords, unsigned);
345 reads = NEW2(ngotos, short *);
346 edge = NEW2(ngotos + 1, short);
350 for (i = 0; i < ngotos; i++)
352 stateno = to_state[i];
353 sp = shift_table[stateno];
359 for (j = 0; j < k; j++)
361 symbol = accessing_symbol[sp->shift[j]];
364 SETBIT(rowp, symbol);
369 symbol = accessing_symbol[sp->shift[j]];
370 if (nullable[symbol])
371 edge[nedges++] = map_goto(stateno, symbol);
376 reads[i] = rp = NEW2(nedges + 1, short);
378 for (j = 0; j < nedges; j++)
386 rowp += tokensetsize;
392 for (i = 0; i < ngotos; i++)
405 build_relations(void)
423 short **new_includes;
425 includes = NEW2(ngotos, short *);
426 edge = NEW2(ngotos + 1, short);
427 states = NEW2(maxrhs + 1, short);
429 for (i = 0; i < ngotos; i++)
432 state1 = from_state[i];
433 symbol1 = accessing_symbol[to_state[i]];
435 for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
441 for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
444 sp = shift_table[stateno];
447 for (j = 0; j < k; j++)
449 stateno = sp->shift[j];
450 if (accessing_symbol[stateno] == symbol2) break;
453 states[length++] = stateno;
456 add_lookback_edge(stateno, *rulep, i);
466 stateno = states[--length];
467 edge[nedges++] = map_goto(stateno, *rp);
468 if (nullable[*rp] && length > 0) done = 0;
475 includes[i] = shortp = NEW2(nedges + 1, short);
476 for (j = 0; j < nedges; j++)
482 new_includes = transpose(includes, ngotos);
484 for (i = 0; i < ngotos; i++)
490 includes = new_includes;
498 add_lookback_edge(int stateno, int ruleno, int gotono)
504 i = lookaheads[stateno];
505 k = lookaheads[stateno + 1];
507 while (!found && i < k)
509 if (LAruleno[i] == ruleno)
517 sp->next = lookback[i];
525 transpose(short **old_R, int n)
534 nedges = NEW2(n, short);
536 for (i = 0; i < n; i++)
546 new_R = NEW2(n, short *);
547 temp_R = NEW2(n, short *);
549 for (i = 0; i < n; i++)
554 sp = NEW2(k + 1, short);
563 for (i = 0; i < n; i++)
569 *temp_R[*sp++]++ = i;
581 compute_FOLLOWS(void)
588 compute_lookaheads(void)
591 unsigned *fp1, *fp2, *fp3;
596 n = lookaheads[nstates];
597 for (i = 0; i < n; i++)
599 fp3 = rowp + tokensetsize;
600 for (sp = lookback[i]; sp; sp = sp->next)
603 fp2 = F + tokensetsize * sp->value;
610 for (i = 0; i < n; i++)
611 for (sp = lookback[i]; sp; sp = next)
623 digraph(short **relation)
627 infinity = ngotos + 2;
628 INDEX = NEW2(ngotos + 1, short);
629 VERTICES = NEW2(ngotos + 1, short);
634 for (i = 0; i < ngotos; i++)
637 for (i = 0; i < ngotos; i++)
639 if (INDEX[i] == 0 && R[i])
662 INDEX[i] = height = top;
664 base = F + i * tokensetsize;
665 fp3 = base + tokensetsize;
670 while ((j = *rp++) >= 0)
675 if (INDEX[i] > INDEX[j])
679 fp2 = F + j * tokensetsize;
686 if (INDEX[i] == height)
697 fp2 = F + j * tokensetsize;