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
39 static char sccsid[] = "@(#)lalr.c 5.3 (Berkeley) 6/1/90";
43 #include <sys/cdefs.h>
44 __FBSDID("$FreeBSD$");
62 short *accessing_symbol;
65 reductions **reduction_table;
70 static void add_lookback_edge(int, int, int);
71 static void build_relations(void);
72 static void compute_FOLLOWS(void);
73 static void compute_lookaheads(void);
74 static void digraph(short **);
75 static void initialize_F(void);
76 static void initialize_LA(void);
77 static int map_goto(int, int);
78 static void set_accessing_symbol(void);
79 static void set_goto_map(void);
80 static void set_maxrhs(void);
81 static void set_reduction_table(void);
82 static void set_shift_table(void);
83 static void set_state_table(void);
84 static short **transpose(short **, int);
85 static void traverse(int, short **);
91 static short **includes;
92 static shorts **lookback;
94 static short *VERTICES;
101 tokensetsize = WORDSIZE(ntokens);
104 set_accessing_symbol();
106 set_reduction_table();
113 compute_lookaheads();
123 state_table = NEW2(nstates, core *);
124 for (sp = first_state; sp; sp = sp->next)
125 state_table[sp->number] = sp;
131 set_accessing_symbol()
135 accessing_symbol = NEW2(nstates, short);
136 for (sp = first_state; sp; sp = sp->next)
137 accessing_symbol[sp->number] = sp->accessing_symbol;
147 shift_table = NEW2(nstates, shifts *);
148 for (sp = first_shift; sp; sp = sp->next)
149 shift_table[sp->number] = sp;
155 set_reduction_table()
159 reduction_table = NEW2(nstates, reductions *);
160 for (rp = first_reduction; rp; rp = rp->next)
161 reduction_table[rp->number] = rp;
176 item_end = ritem + nitems;
177 for (itemp = ritem; itemp < item_end; itemp++)
185 if (length > max) max = length;
201 lookaheads = NEW2(nstates + 1, short);
204 for (i = 0; i < nstates; i++)
207 rp = reduction_table[i];
211 lookaheads[nstates] = k;
213 LA = NEW2(k * tokensetsize, unsigned);
214 LAruleno = NEW2(k, short);
215 lookback = NEW2(k, shorts *);
218 for (i = 0; i < nstates; i++)
220 rp = reduction_table[i];
223 for (j = 0; j < rp->nreds; j++)
225 LAruleno[k] = rp->rules[j];
244 goto_map = NEW2(nvars + 1, short) - ntokens;
245 temp_map = NEW2(nvars + 1, short) - ntokens;
248 for (sp = first_shift; sp; sp = sp->next)
250 for (i = sp->nshifts - 1; i >= 0; i--)
252 symbol = accessing_symbol[sp->shift[i]];
254 if (ISTOKEN(symbol)) break;
256 if (ngotos == SHRT_MAX)
257 fatal("too many gotos");
265 for (i = ntokens; i < nsyms; i++)
271 for (i = ntokens; i < nsyms; i++)
272 goto_map[i] = temp_map[i];
274 goto_map[nsyms] = ngotos;
275 temp_map[nsyms] = ngotos;
277 from_state = NEW2(ngotos, short);
278 to_state = NEW2(ngotos, short);
280 for (sp = first_shift; sp; sp = sp->next)
283 for (i = sp->nshifts - 1; i >= 0; i--)
285 state2 = sp->shift[i];
286 symbol = accessing_symbol[state2];
288 if (ISTOKEN(symbol)) break;
290 k = temp_map[symbol]++;
291 from_state[k] = state1;
292 to_state[k] = state2;
296 FREE(temp_map + ntokens);
301 /* Map_goto maps a state/symbol pair into its numeric representation. */
304 map_goto(state, symbol)
313 low = goto_map[symbol];
314 high = goto_map[symbol + 1];
319 middle = (low + high) >> 1;
320 s = from_state[middle];
348 nwords = ngotos * tokensetsize;
349 F = NEW2(nwords, unsigned);
351 reads = NEW2(ngotos, short *);
352 edge = NEW2(ngotos + 1, short);
356 for (i = 0; i < ngotos; i++)
358 stateno = to_state[i];
359 sp = shift_table[stateno];
365 for (j = 0; j < k; j++)
367 symbol = accessing_symbol[sp->shift[j]];
370 SETBIT(rowp, symbol);
375 symbol = accessing_symbol[sp->shift[j]];
376 if (nullable[symbol])
377 edge[nedges++] = map_goto(stateno, symbol);
382 reads[i] = rp = NEW2(nedges + 1, short);
384 for (j = 0; j < nedges; j++)
392 rowp += tokensetsize;
398 for (i = 0; i < ngotos; i++)
429 short **new_includes;
431 includes = NEW2(ngotos, short *);
432 edge = NEW2(ngotos + 1, short);
433 states = NEW2(maxrhs + 1, short);
435 for (i = 0; i < ngotos; i++)
438 state1 = from_state[i];
439 symbol1 = accessing_symbol[to_state[i]];
441 for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
447 for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
450 sp = shift_table[stateno];
453 for (j = 0; j < k; j++)
455 stateno = sp->shift[j];
456 if (accessing_symbol[stateno] == symbol2) break;
459 states[length++] = stateno;
462 add_lookback_edge(stateno, *rulep, i);
472 stateno = states[--length];
473 edge[nedges++] = map_goto(stateno, *rp);
474 if (nullable[*rp] && length > 0) done1 = 0;
481 includes[i] = shortp = NEW2(nedges + 1, short);
482 for (j = 0; j < nedges; j++)
488 new_includes = transpose(includes, ngotos);
490 for (i = 0; i < ngotos; i++)
496 includes = new_includes;
504 add_lookback_edge(stateno, ruleno, gotono)
505 int stateno, ruleno, gotono;
511 i = lookaheads[stateno];
512 k = lookaheads[stateno + 1];
514 while (!found && i < k)
516 if (LAruleno[i] == ruleno)
524 sp->next = lookback[i];
543 nedges = NEW2(n, short);
545 for (i = 0; i < n; i++)
555 new_R = NEW2(n, short *);
556 temp_R = NEW2(n, short *);
558 for (i = 0; i < n; i++)
563 sp = NEW2(k + 1, short);
572 for (i = 0; i < n; i++)
578 *temp_R[*sp++]++ = i;
600 unsigned *fp1, *fp2, *fp3;
605 n = lookaheads[nstates];
606 for (i = 0; i < n; i++)
608 fp3 = rowp + tokensetsize;
609 for (sp = lookback[i]; sp; sp = sp->next)
612 fp2 = F + tokensetsize * sp->value;
619 for (i = 0; i < n; i++)
620 for (sp = lookback[i]; sp; sp = next)
637 infinity = ngotos + 2;
638 INDEX = NEW2(ngotos + 1, short);
639 VERTICES = NEW2(ngotos + 1, short);
642 for (i = 0; i < ngotos; i++)
645 for (i = 0; i < ngotos; i++)
647 if (INDEX[i] == 0 && relation[i])
648 traverse(i, relation);
672 INDEX[i] = height = top;
674 base = F + i * tokensetsize;
675 fp3 = base + tokensetsize;
680 while ((j = *rp++) >= 0)
685 if (INDEX[i] > INDEX[j])
689 fp2 = F + j * tokensetsize;
696 if (INDEX[i] == height)
707 fp2 = F + j * tokensetsize;