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
38 static char sccsid[] = "@(#)lalr.c 5.3 (Berkeley) 6/1/90";
55 short *accessing_symbol;
58 reductions **reduction_table;
69 static short **includes;
70 static shorts **lookback;
73 static short *VERTICES;
79 tokensetsize = WORDSIZE(ntokens);
82 set_accessing_symbol();
84 set_reduction_table();
100 state_table = NEW2(nstates, core *);
101 for (sp = first_state; sp; sp = sp->next)
102 state_table[sp->number] = sp;
107 set_accessing_symbol()
111 accessing_symbol = NEW2(nstates, short);
112 for (sp = first_state; sp; sp = sp->next)
113 accessing_symbol[sp->number] = sp->accessing_symbol;
122 shift_table = NEW2(nstates, shifts *);
123 for (sp = first_shift; sp; sp = sp->next)
124 shift_table[sp->number] = sp;
129 set_reduction_table()
131 register reductions *rp;
133 reduction_table = NEW2(nstates, reductions *);
134 for (rp = first_reduction; rp; rp = rp->next)
135 reduction_table[rp->number] = rp;
142 register short *itemp;
143 register short *item_end;
149 item_end = ritem + nitems;
150 for (itemp = ritem; itemp < item_end; itemp++)
158 if (length > max) max = length;
170 register int i, j, k;
171 register reductions *rp;
173 lookaheads = NEW2(nstates + 1, short);
176 for (i = 0; i < nstates; i++)
179 rp = reduction_table[i];
183 lookaheads[nstates] = k;
185 LA = NEW2(k * tokensetsize, unsigned);
186 LAruleno = NEW2(k, short);
187 lookback = NEW2(k, shorts *);
190 for (i = 0; i < nstates; i++)
192 rp = reduction_table[i];
195 for (j = 0; j < rp->nreds; j++)
197 LAruleno[k] = rp->rules[j];
211 register short *temp_map;
215 goto_map = NEW2(nvars + 1, short) - ntokens;
216 temp_map = NEW2(nvars + 1, short) - ntokens;
219 for (sp = first_shift; sp; sp = sp->next)
221 for (i = sp->nshifts - 1; i >= 0; i--)
223 symbol = accessing_symbol[sp->shift[i]];
225 if (ISTOKEN(symbol)) break;
227 if (ngotos == MAXSHORT)
228 fatal("too many gotos");
236 for (i = ntokens; i < nsyms; i++)
242 for (i = ntokens; i < nsyms; i++)
243 goto_map[i] = temp_map[i];
245 goto_map[nsyms] = ngotos;
246 temp_map[nsyms] = ngotos;
248 from_state = NEW2(ngotos, short);
249 to_state = NEW2(ngotos, short);
251 for (sp = first_shift; sp; sp = sp->next)
254 for (i = sp->nshifts - 1; i >= 0; i--)
256 state2 = sp->shift[i];
257 symbol = accessing_symbol[state2];
259 if (ISTOKEN(symbol)) break;
261 k = temp_map[symbol]++;
262 from_state[k] = state1;
263 to_state[k] = state2;
267 FREE(temp_map + ntokens);
272 /* Map_goto maps a state/symbol pair into its numeric representation. */
275 map_goto(state, symbol)
284 low = goto_map[symbol];
285 high = goto_map[symbol + 1];
290 middle = (low + high) >> 1;
291 s = from_state[middle];
309 register short *edge;
310 register unsigned *rowp;
312 register short **reads;
314 register int stateno;
318 nwords = ngotos * tokensetsize;
319 F = NEW2(nwords, unsigned);
321 reads = NEW2(ngotos, short *);
322 edge = NEW2(ngotos + 1, short);
326 for (i = 0; i < ngotos; i++)
328 stateno = to_state[i];
329 sp = shift_table[stateno];
335 for (j = 0; j < k; j++)
337 symbol = accessing_symbol[sp->shift[j]];
340 SETBIT(rowp, symbol);
345 symbol = accessing_symbol[sp->shift[j]];
346 if (nullable[symbol])
347 edge[nedges++] = map_goto(stateno, symbol);
352 reads[i] = rp = NEW2(nedges + 1, short);
354 for (j = 0; j < nedges; j++)
362 rowp += tokensetsize;
368 for (i = 0; i < ngotos; i++)
385 register short *rulep;
392 register int stateno;
393 register int symbol1;
394 register int symbol2;
395 register short *shortp;
396 register short *edge;
397 register short *states;
398 register short **new_includes;
400 includes = NEW2(ngotos, short *);
401 edge = NEW2(ngotos + 1, short);
402 states = NEW2(maxrhs + 1, short);
404 for (i = 0; i < ngotos; i++)
407 state1 = from_state[i];
408 symbol1 = accessing_symbol[to_state[i]];
410 for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
416 for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
419 sp = shift_table[stateno];
422 for (j = 0; j < k; j++)
424 stateno = sp->shift[j];
425 if (accessing_symbol[stateno] == symbol2) break;
428 states[length++] = stateno;
431 add_lookback_edge(stateno, *rulep, i);
441 stateno = states[--length];
442 edge[nedges++] = map_goto(stateno, *rp);
443 if (nullable[*rp] && length > 0) done = 0;
450 includes[i] = shortp = NEW2(nedges + 1, short);
451 for (j = 0; j < nedges; j++)
457 new_includes = transpose(includes, ngotos);
459 for (i = 0; i < ngotos; i++)
465 includes = new_includes;
472 add_lookback_edge(stateno, ruleno, gotono)
473 int stateno, ruleno, gotono;
479 i = lookaheads[stateno];
480 k = lookaheads[stateno + 1];
482 while (!found && i < k)
484 if (LAruleno[i] == ruleno)
492 sp->next = lookback[i];
504 register short **new_R;
505 register short **temp_R;
506 register short *nedges;
511 nedges = NEW2(n, short);
513 for (i = 0; i < n; i++)
523 new_R = NEW2(n, short *);
524 temp_R = NEW2(n, short *);
526 for (i = 0; i < n; i++)
531 sp = NEW2(k + 1, short);
540 for (i = 0; i < n; i++)
546 *temp_R[*sp++]++ = i;
566 register unsigned *fp1, *fp2, *fp3;
567 register shorts *sp, *next;
568 register unsigned *rowp;
571 n = lookaheads[nstates];
572 for (i = 0; i < n; i++)
574 fp3 = rowp + tokensetsize;
575 for (sp = lookback[i]; sp; sp = sp->next)
578 fp2 = F + tokensetsize * sp->value;
585 for (i = 0; i < n; i++)
586 for (sp = lookback[i]; sp; sp = next)
602 infinity = ngotos + 2;
603 INDEX = NEW2(ngotos + 1, short);
604 VERTICES = NEW2(ngotos + 1, short);
609 for (i = 0; i < ngotos; i++)
612 for (i = 0; i < ngotos; i++)
614 if (INDEX[i] == 0 && R[i])
627 register unsigned *fp1;
628 register unsigned *fp2;
629 register unsigned *fp3;
637 INDEX[i] = height = top;
639 base = F + i * tokensetsize;
640 fp3 = base + tokensetsize;
645 while ((j = *rp++) >= 0)
650 if (INDEX[i] > INDEX[j])
654 fp2 = F + j * tokensetsize;
661 if (INDEX[i] == height)
672 fp2 = F + j * tokensetsize;