1e643f0c2Sbostic /*
2e643f0c2Sbostic * Copyright (c) 1989 The Regents of the University of California.
3e643f0c2Sbostic * All rights reserved.
4e643f0c2Sbostic *
5e643f0c2Sbostic * This code is derived from software contributed to Berkeley by
6e643f0c2Sbostic * Robert Paul Corbett.
7e643f0c2Sbostic *
8*ea70a0c4Sbostic * %sccs.include.redist.c%
9e643f0c2Sbostic */
10e643f0c2Sbostic
11e643f0c2Sbostic #ifndef lint
12*ea70a0c4Sbostic static char sccsid[] = "@(#)lalr.c 5.3 (Berkeley) 06/01/90";
13e643f0c2Sbostic #endif /* not lint */
14e643f0c2Sbostic
15e643f0c2Sbostic #include "defs.h"
16e643f0c2Sbostic
17e643f0c2Sbostic typedef
18e643f0c2Sbostic struct shorts
19e643f0c2Sbostic {
20e643f0c2Sbostic struct shorts *next;
21e643f0c2Sbostic short value;
22e643f0c2Sbostic }
23e643f0c2Sbostic shorts;
24e643f0c2Sbostic
25e643f0c2Sbostic int tokensetsize;
26e643f0c2Sbostic short *lookaheads;
27e643f0c2Sbostic short *LAruleno;
28e643f0c2Sbostic unsigned *LA;
29e643f0c2Sbostic short *accessing_symbol;
30e643f0c2Sbostic core **state_table;
31e643f0c2Sbostic shifts **shift_table;
32e643f0c2Sbostic reductions **reduction_table;
33e643f0c2Sbostic short *goto_map;
34e643f0c2Sbostic short *from_state;
35e643f0c2Sbostic short *to_state;
36e643f0c2Sbostic
37e643f0c2Sbostic short **transpose();
38e643f0c2Sbostic
39e643f0c2Sbostic static int infinity;
40e643f0c2Sbostic static int maxrhs;
41e643f0c2Sbostic static int ngotos;
42e643f0c2Sbostic static unsigned *F;
43e643f0c2Sbostic static short **includes;
44e643f0c2Sbostic static shorts **lookback;
45e643f0c2Sbostic static short **R;
46e643f0c2Sbostic static short *INDEX;
47e643f0c2Sbostic static short *VERTICES;
48e643f0c2Sbostic static int top;
49e643f0c2Sbostic
50e643f0c2Sbostic
lalr()51e643f0c2Sbostic lalr()
52e643f0c2Sbostic {
53e643f0c2Sbostic tokensetsize = WORDSIZE(ntokens);
54e643f0c2Sbostic
55e643f0c2Sbostic set_state_table();
56e643f0c2Sbostic set_accessing_symbol();
57e643f0c2Sbostic set_shift_table();
58e643f0c2Sbostic set_reduction_table();
59e643f0c2Sbostic set_maxrhs();
60e643f0c2Sbostic initialize_LA();
61e643f0c2Sbostic set_goto_map();
62e643f0c2Sbostic initialize_F();
63e643f0c2Sbostic build_relations();
64e643f0c2Sbostic compute_FOLLOWS();
65e643f0c2Sbostic compute_lookaheads();
66e643f0c2Sbostic }
67e643f0c2Sbostic
68e643f0c2Sbostic
69e643f0c2Sbostic
set_state_table()70e643f0c2Sbostic set_state_table()
71e643f0c2Sbostic {
72e643f0c2Sbostic register core *sp;
73e643f0c2Sbostic
74e643f0c2Sbostic state_table = NEW2(nstates, core *);
75e643f0c2Sbostic for (sp = first_state; sp; sp = sp->next)
76e643f0c2Sbostic state_table[sp->number] = sp;
77e643f0c2Sbostic }
78e643f0c2Sbostic
79e643f0c2Sbostic
80e643f0c2Sbostic
set_accessing_symbol()81e643f0c2Sbostic set_accessing_symbol()
82e643f0c2Sbostic {
83e643f0c2Sbostic register core *sp;
84e643f0c2Sbostic
85e643f0c2Sbostic accessing_symbol = NEW2(nstates, short);
86e643f0c2Sbostic for (sp = first_state; sp; sp = sp->next)
87e643f0c2Sbostic accessing_symbol[sp->number] = sp->accessing_symbol;
88e643f0c2Sbostic }
89e643f0c2Sbostic
90e643f0c2Sbostic
91e643f0c2Sbostic
set_shift_table()92e643f0c2Sbostic set_shift_table()
93e643f0c2Sbostic {
94e643f0c2Sbostic register shifts *sp;
95e643f0c2Sbostic
96e643f0c2Sbostic shift_table = NEW2(nstates, shifts *);
97e643f0c2Sbostic for (sp = first_shift; sp; sp = sp->next)
98e643f0c2Sbostic shift_table[sp->number] = sp;
99e643f0c2Sbostic }
100e643f0c2Sbostic
101e643f0c2Sbostic
102e643f0c2Sbostic
set_reduction_table()103e643f0c2Sbostic set_reduction_table()
104e643f0c2Sbostic {
105e643f0c2Sbostic register reductions *rp;
106e643f0c2Sbostic
107e643f0c2Sbostic reduction_table = NEW2(nstates, reductions *);
108e643f0c2Sbostic for (rp = first_reduction; rp; rp = rp->next)
109e643f0c2Sbostic reduction_table[rp->number] = rp;
110e643f0c2Sbostic }
111e643f0c2Sbostic
112e643f0c2Sbostic
113e643f0c2Sbostic
set_maxrhs()114e643f0c2Sbostic set_maxrhs()
115e643f0c2Sbostic {
116e643f0c2Sbostic register short *itemp;
117e643f0c2Sbostic register short *item_end;
118e643f0c2Sbostic register int length;
119e643f0c2Sbostic register int max;
120e643f0c2Sbostic
121e643f0c2Sbostic length = 0;
122e643f0c2Sbostic max = 0;
123e643f0c2Sbostic item_end = ritem + nitems;
124e643f0c2Sbostic for (itemp = ritem; itemp < item_end; itemp++)
125e643f0c2Sbostic {
126e643f0c2Sbostic if (*itemp >= 0)
127e643f0c2Sbostic {
128e643f0c2Sbostic length++;
129e643f0c2Sbostic }
130e643f0c2Sbostic else
131e643f0c2Sbostic {
132e643f0c2Sbostic if (length > max) max = length;
133e643f0c2Sbostic length = 0;
134e643f0c2Sbostic }
135e643f0c2Sbostic }
136e643f0c2Sbostic
137e643f0c2Sbostic maxrhs = max;
138e643f0c2Sbostic }
139e643f0c2Sbostic
140e643f0c2Sbostic
141e643f0c2Sbostic
initialize_LA()142e643f0c2Sbostic initialize_LA()
143e643f0c2Sbostic {
144e643f0c2Sbostic register int i, j, k;
145e643f0c2Sbostic register reductions *rp;
146e643f0c2Sbostic
147e643f0c2Sbostic lookaheads = NEW2(nstates + 1, short);
148e643f0c2Sbostic
149e643f0c2Sbostic k = 0;
150e643f0c2Sbostic for (i = 0; i < nstates; i++)
151e643f0c2Sbostic {
152e643f0c2Sbostic lookaheads[i] = k;
153e643f0c2Sbostic rp = reduction_table[i];
154e643f0c2Sbostic if (rp)
155e643f0c2Sbostic k += rp->nreds;
156e643f0c2Sbostic }
157e643f0c2Sbostic lookaheads[nstates] = k;
158e643f0c2Sbostic
159e643f0c2Sbostic LA = NEW2(k * tokensetsize, unsigned);
160e643f0c2Sbostic LAruleno = NEW2(k, short);
161e643f0c2Sbostic lookback = NEW2(k, shorts *);
162e643f0c2Sbostic
163e643f0c2Sbostic k = 0;
164e643f0c2Sbostic for (i = 0; i < nstates; i++)
165e643f0c2Sbostic {
166e643f0c2Sbostic rp = reduction_table[i];
167e643f0c2Sbostic if (rp)
168e643f0c2Sbostic {
169e643f0c2Sbostic for (j = 0; j < rp->nreds; j++)
170e643f0c2Sbostic {
171e643f0c2Sbostic LAruleno[k] = rp->rules[j];
172e643f0c2Sbostic k++;
173e643f0c2Sbostic }
174e643f0c2Sbostic }
175e643f0c2Sbostic }
176e643f0c2Sbostic }
177e643f0c2Sbostic
178e643f0c2Sbostic
set_goto_map()179e643f0c2Sbostic set_goto_map()
180e643f0c2Sbostic {
181e643f0c2Sbostic register shifts *sp;
182e643f0c2Sbostic register int i;
183e643f0c2Sbostic register int symbol;
184e643f0c2Sbostic register int k;
185e643f0c2Sbostic register short *temp_map;
186e643f0c2Sbostic register int state2;
187e643f0c2Sbostic register int state1;
188e643f0c2Sbostic
189e643f0c2Sbostic goto_map = NEW2(nvars + 1, short) - ntokens;
190e643f0c2Sbostic temp_map = NEW2(nvars + 1, short) - ntokens;
191e643f0c2Sbostic
192e643f0c2Sbostic ngotos = 0;
193e643f0c2Sbostic for (sp = first_shift; sp; sp = sp->next)
194e643f0c2Sbostic {
195e643f0c2Sbostic for (i = sp->nshifts - 1; i >= 0; i--)
196e643f0c2Sbostic {
197e643f0c2Sbostic symbol = accessing_symbol[sp->shift[i]];
198e643f0c2Sbostic
199e643f0c2Sbostic if (ISTOKEN(symbol)) break;
200e643f0c2Sbostic
201e643f0c2Sbostic if (ngotos == MAXSHORT)
202e643f0c2Sbostic fatal("too many gotos");
203e643f0c2Sbostic
204e643f0c2Sbostic ngotos++;
205e643f0c2Sbostic goto_map[symbol]++;
206e643f0c2Sbostic }
207e643f0c2Sbostic }
208e643f0c2Sbostic
209e643f0c2Sbostic k = 0;
210e643f0c2Sbostic for (i = ntokens; i < nsyms; i++)
211e643f0c2Sbostic {
212e643f0c2Sbostic temp_map[i] = k;
213e643f0c2Sbostic k += goto_map[i];
214e643f0c2Sbostic }
215e643f0c2Sbostic
216e643f0c2Sbostic for (i = ntokens; i < nsyms; i++)
217e643f0c2Sbostic goto_map[i] = temp_map[i];
218e643f0c2Sbostic
219e643f0c2Sbostic goto_map[nsyms] = ngotos;
220e643f0c2Sbostic temp_map[nsyms] = ngotos;
221e643f0c2Sbostic
222e643f0c2Sbostic from_state = NEW2(ngotos, short);
223e643f0c2Sbostic to_state = NEW2(ngotos, short);
224e643f0c2Sbostic
225e643f0c2Sbostic for (sp = first_shift; sp; sp = sp->next)
226e643f0c2Sbostic {
227e643f0c2Sbostic state1 = sp->number;
228e643f0c2Sbostic for (i = sp->nshifts - 1; i >= 0; i--)
229e643f0c2Sbostic {
230e643f0c2Sbostic state2 = sp->shift[i];
231e643f0c2Sbostic symbol = accessing_symbol[state2];
232e643f0c2Sbostic
233e643f0c2Sbostic if (ISTOKEN(symbol)) break;
234e643f0c2Sbostic
235e643f0c2Sbostic k = temp_map[symbol]++;
236e643f0c2Sbostic from_state[k] = state1;
237e643f0c2Sbostic to_state[k] = state2;
238e643f0c2Sbostic }
239e643f0c2Sbostic }
240e643f0c2Sbostic
241e643f0c2Sbostic FREE(temp_map + ntokens);
242e643f0c2Sbostic }
243e643f0c2Sbostic
244e643f0c2Sbostic
245e643f0c2Sbostic
246e643f0c2Sbostic /* Map_goto maps a state/symbol pair into its numeric representation. */
247e643f0c2Sbostic
248e643f0c2Sbostic int
map_goto(state,symbol)249e643f0c2Sbostic map_goto(state, symbol)
250e643f0c2Sbostic int state;
251e643f0c2Sbostic int symbol;
252e643f0c2Sbostic {
253e643f0c2Sbostic register int high;
254e643f0c2Sbostic register int low;
255e643f0c2Sbostic register int middle;
256e643f0c2Sbostic register int s;
257e643f0c2Sbostic
258e643f0c2Sbostic low = goto_map[symbol];
259e643f0c2Sbostic high = goto_map[symbol + 1];
260e643f0c2Sbostic
261e643f0c2Sbostic for (;;)
262e643f0c2Sbostic {
263e643f0c2Sbostic assert(low <= high);
264e643f0c2Sbostic middle = (low + high) >> 1;
265e643f0c2Sbostic s = from_state[middle];
266e643f0c2Sbostic if (s == state)
267e643f0c2Sbostic return (middle);
268e643f0c2Sbostic else if (s < state)
269e643f0c2Sbostic low = middle + 1;
270e643f0c2Sbostic else
271e643f0c2Sbostic high = middle - 1;
272e643f0c2Sbostic }
273e643f0c2Sbostic }
274e643f0c2Sbostic
275e643f0c2Sbostic
276e643f0c2Sbostic
initialize_F()277e643f0c2Sbostic initialize_F()
278e643f0c2Sbostic {
279e643f0c2Sbostic register int i;
280e643f0c2Sbostic register int j;
281e643f0c2Sbostic register int k;
282e643f0c2Sbostic register shifts *sp;
283e643f0c2Sbostic register short *edge;
284e643f0c2Sbostic register unsigned *rowp;
285e643f0c2Sbostic register short *rp;
286e643f0c2Sbostic register short **reads;
287e643f0c2Sbostic register int nedges;
288e643f0c2Sbostic register int stateno;
289e643f0c2Sbostic register int symbol;
290e643f0c2Sbostic register int nwords;
291e643f0c2Sbostic
292e643f0c2Sbostic nwords = ngotos * tokensetsize;
293e643f0c2Sbostic F = NEW2(nwords, unsigned);
294e643f0c2Sbostic
295e643f0c2Sbostic reads = NEW2(ngotos, short *);
296e643f0c2Sbostic edge = NEW2(ngotos + 1, short);
297e643f0c2Sbostic nedges = 0;
298e643f0c2Sbostic
299e643f0c2Sbostic rowp = F;
300e643f0c2Sbostic for (i = 0; i < ngotos; i++)
301e643f0c2Sbostic {
302e643f0c2Sbostic stateno = to_state[i];
303e643f0c2Sbostic sp = shift_table[stateno];
304e643f0c2Sbostic
305e643f0c2Sbostic if (sp)
306e643f0c2Sbostic {
307e643f0c2Sbostic k = sp->nshifts;
308e643f0c2Sbostic
309e643f0c2Sbostic for (j = 0; j < k; j++)
310e643f0c2Sbostic {
311e643f0c2Sbostic symbol = accessing_symbol[sp->shift[j]];
312e643f0c2Sbostic if (ISVAR(symbol))
313e643f0c2Sbostic break;
314e643f0c2Sbostic SETBIT(rowp, symbol);
315e643f0c2Sbostic }
316e643f0c2Sbostic
317e643f0c2Sbostic for (; j < k; j++)
318e643f0c2Sbostic {
319e643f0c2Sbostic symbol = accessing_symbol[sp->shift[j]];
320e643f0c2Sbostic if (nullable[symbol])
321e643f0c2Sbostic edge[nedges++] = map_goto(stateno, symbol);
322e643f0c2Sbostic }
323e643f0c2Sbostic
324e643f0c2Sbostic if (nedges)
325e643f0c2Sbostic {
326e643f0c2Sbostic reads[i] = rp = NEW2(nedges + 1, short);
327e643f0c2Sbostic
328e643f0c2Sbostic for (j = 0; j < nedges; j++)
329e643f0c2Sbostic rp[j] = edge[j];
330e643f0c2Sbostic
331e643f0c2Sbostic rp[nedges] = -1;
332e643f0c2Sbostic nedges = 0;
333e643f0c2Sbostic }
334e643f0c2Sbostic }
335e643f0c2Sbostic
336e643f0c2Sbostic rowp += tokensetsize;
337e643f0c2Sbostic }
338e643f0c2Sbostic
339e643f0c2Sbostic SETBIT(F, 0);
340e643f0c2Sbostic digraph(reads);
341e643f0c2Sbostic
342e643f0c2Sbostic for (i = 0; i < ngotos; i++)
343e643f0c2Sbostic {
344e643f0c2Sbostic if (reads[i])
345e643f0c2Sbostic FREE(reads[i]);
346e643f0c2Sbostic }
347e643f0c2Sbostic
348e643f0c2Sbostic FREE(reads);
349e643f0c2Sbostic FREE(edge);
350e643f0c2Sbostic }
351e643f0c2Sbostic
352e643f0c2Sbostic
353e643f0c2Sbostic
build_relations()354e643f0c2Sbostic build_relations()
355e643f0c2Sbostic {
356e643f0c2Sbostic register int i;
357e643f0c2Sbostic register int j;
358e643f0c2Sbostic register int k;
359e643f0c2Sbostic register short *rulep;
360e643f0c2Sbostic register short *rp;
361e643f0c2Sbostic register shifts *sp;
362e643f0c2Sbostic register int length;
363e643f0c2Sbostic register int nedges;
364e643f0c2Sbostic register int done;
365e643f0c2Sbostic register int state1;
366e643f0c2Sbostic register int stateno;
367e643f0c2Sbostic register int symbol1;
368e643f0c2Sbostic register int symbol2;
369e643f0c2Sbostic register short *shortp;
370e643f0c2Sbostic register short *edge;
371e643f0c2Sbostic register short *states;
372e643f0c2Sbostic register short **new_includes;
373e643f0c2Sbostic
374e643f0c2Sbostic includes = NEW2(ngotos, short *);
375e643f0c2Sbostic edge = NEW2(ngotos + 1, short);
376e643f0c2Sbostic states = NEW2(maxrhs + 1, short);
377e643f0c2Sbostic
378e643f0c2Sbostic for (i = 0; i < ngotos; i++)
379e643f0c2Sbostic {
380e643f0c2Sbostic nedges = 0;
381e643f0c2Sbostic state1 = from_state[i];
382e643f0c2Sbostic symbol1 = accessing_symbol[to_state[i]];
383e643f0c2Sbostic
384e643f0c2Sbostic for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
385e643f0c2Sbostic {
386e643f0c2Sbostic length = 1;
387e643f0c2Sbostic states[0] = state1;
388e643f0c2Sbostic stateno = state1;
389e643f0c2Sbostic
390e643f0c2Sbostic for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
391e643f0c2Sbostic {
392e643f0c2Sbostic symbol2 = *rp;
393e643f0c2Sbostic sp = shift_table[stateno];
394e643f0c2Sbostic k = sp->nshifts;
395e643f0c2Sbostic
396e643f0c2Sbostic for (j = 0; j < k; j++)
397e643f0c2Sbostic {
398e643f0c2Sbostic stateno = sp->shift[j];
399e643f0c2Sbostic if (accessing_symbol[stateno] == symbol2) break;
400e643f0c2Sbostic }
401e643f0c2Sbostic
402e643f0c2Sbostic states[length++] = stateno;
403e643f0c2Sbostic }
404e643f0c2Sbostic
405e643f0c2Sbostic add_lookback_edge(stateno, *rulep, i);
406e643f0c2Sbostic
407e643f0c2Sbostic length--;
408e643f0c2Sbostic done = 0;
409e643f0c2Sbostic while (!done)
410e643f0c2Sbostic {
411e643f0c2Sbostic done = 1;
412e643f0c2Sbostic rp--;
413e643f0c2Sbostic if (ISVAR(*rp))
414e643f0c2Sbostic {
415e643f0c2Sbostic stateno = states[--length];
416e643f0c2Sbostic edge[nedges++] = map_goto(stateno, *rp);
417e643f0c2Sbostic if (nullable[*rp] && length > 0) done = 0;
418e643f0c2Sbostic }
419e643f0c2Sbostic }
420e643f0c2Sbostic }
421e643f0c2Sbostic
422e643f0c2Sbostic if (nedges)
423e643f0c2Sbostic {
424e643f0c2Sbostic includes[i] = shortp = NEW2(nedges + 1, short);
425e643f0c2Sbostic for (j = 0; j < nedges; j++)
426e643f0c2Sbostic shortp[j] = edge[j];
427e643f0c2Sbostic shortp[nedges] = -1;
428e643f0c2Sbostic }
429e643f0c2Sbostic }
430e643f0c2Sbostic
431e643f0c2Sbostic new_includes = transpose(includes, ngotos);
432e643f0c2Sbostic
433e643f0c2Sbostic for (i = 0; i < ngotos; i++)
43430ee30f7Sbostic if (includes[i])
435e643f0c2Sbostic FREE(includes[i]);
436e643f0c2Sbostic
437e643f0c2Sbostic FREE(includes);
438e643f0c2Sbostic
439e643f0c2Sbostic includes = new_includes;
440e643f0c2Sbostic
441e643f0c2Sbostic FREE(edge);
442e643f0c2Sbostic FREE(states);
443e643f0c2Sbostic }
444e643f0c2Sbostic
445e643f0c2Sbostic
add_lookback_edge(stateno,ruleno,gotono)446e643f0c2Sbostic add_lookback_edge(stateno, ruleno, gotono)
447e643f0c2Sbostic int stateno, ruleno, gotono;
448e643f0c2Sbostic {
449e643f0c2Sbostic register int i, k;
450e643f0c2Sbostic register int found;
451e643f0c2Sbostic register shorts *sp;
452e643f0c2Sbostic
453e643f0c2Sbostic i = lookaheads[stateno];
454e643f0c2Sbostic k = lookaheads[stateno + 1];
455e643f0c2Sbostic found = 0;
456e643f0c2Sbostic while (!found && i < k)
457e643f0c2Sbostic {
458e643f0c2Sbostic if (LAruleno[i] == ruleno)
459e643f0c2Sbostic found = 1;
460e643f0c2Sbostic else
461e643f0c2Sbostic ++i;
462e643f0c2Sbostic }
463e643f0c2Sbostic assert(found);
464e643f0c2Sbostic
465e643f0c2Sbostic sp = NEW(shorts);
466e643f0c2Sbostic sp->next = lookback[i];
467e643f0c2Sbostic sp->value = gotono;
468e643f0c2Sbostic lookback[i] = sp;
469e643f0c2Sbostic }
470e643f0c2Sbostic
471e643f0c2Sbostic
472e643f0c2Sbostic
473e643f0c2Sbostic short **
transpose(R,n)474e643f0c2Sbostic transpose(R, n)
475e643f0c2Sbostic short **R;
476e643f0c2Sbostic int n;
477e643f0c2Sbostic {
478e643f0c2Sbostic register short **new_R;
479e643f0c2Sbostic register short **temp_R;
480e643f0c2Sbostic register short *nedges;
481e643f0c2Sbostic register short *sp;
482e643f0c2Sbostic register int i;
483e643f0c2Sbostic register int k;
484e643f0c2Sbostic
485e643f0c2Sbostic nedges = NEW2(n, short);
486e643f0c2Sbostic
487e643f0c2Sbostic for (i = 0; i < n; i++)
488e643f0c2Sbostic {
489e643f0c2Sbostic sp = R[i];
490e643f0c2Sbostic if (sp)
491e643f0c2Sbostic {
492e643f0c2Sbostic while (*sp >= 0)
493e643f0c2Sbostic nedges[*sp++]++;
494e643f0c2Sbostic }
495e643f0c2Sbostic }
496e643f0c2Sbostic
497e643f0c2Sbostic new_R = NEW2(n, short *);
498e643f0c2Sbostic temp_R = NEW2(n, short *);
499e643f0c2Sbostic
500e643f0c2Sbostic for (i = 0; i < n; i++)
501e643f0c2Sbostic {
502e643f0c2Sbostic k = nedges[i];
503e643f0c2Sbostic if (k > 0)
504e643f0c2Sbostic {
505e643f0c2Sbostic sp = NEW2(k + 1, short);
506e643f0c2Sbostic new_R[i] = sp;
507e643f0c2Sbostic temp_R[i] = sp;
508e643f0c2Sbostic sp[k] = -1;
509e643f0c2Sbostic }
510e643f0c2Sbostic }
511e643f0c2Sbostic
512e643f0c2Sbostic FREE(nedges);
513e643f0c2Sbostic
514e643f0c2Sbostic for (i = 0; i < n; i++)
515e643f0c2Sbostic {
516e643f0c2Sbostic sp = R[i];
517e643f0c2Sbostic if (sp)
518e643f0c2Sbostic {
519e643f0c2Sbostic while (*sp >= 0)
520e643f0c2Sbostic *temp_R[*sp++]++ = i;
521e643f0c2Sbostic }
522e643f0c2Sbostic }
523e643f0c2Sbostic
524e643f0c2Sbostic FREE(temp_R);
525e643f0c2Sbostic
526e643f0c2Sbostic return (new_R);
527e643f0c2Sbostic }
528e643f0c2Sbostic
529e643f0c2Sbostic
530e643f0c2Sbostic
compute_FOLLOWS()531e643f0c2Sbostic compute_FOLLOWS()
532e643f0c2Sbostic {
533e643f0c2Sbostic digraph(includes);
534e643f0c2Sbostic }
535e643f0c2Sbostic
536e643f0c2Sbostic
compute_lookaheads()537e643f0c2Sbostic compute_lookaheads()
538e643f0c2Sbostic {
539e643f0c2Sbostic register int i, n;
540e643f0c2Sbostic register unsigned *fp1, *fp2, *fp3;
54130ee30f7Sbostic register shorts *sp, *next;
542e643f0c2Sbostic register unsigned *rowp;
543e643f0c2Sbostic
544e643f0c2Sbostic rowp = LA;
545e643f0c2Sbostic n = lookaheads[nstates];
546e643f0c2Sbostic for (i = 0; i < n; i++)
547e643f0c2Sbostic {
548e643f0c2Sbostic fp3 = rowp + tokensetsize;
549e643f0c2Sbostic for (sp = lookback[i]; sp; sp = sp->next)
550e643f0c2Sbostic {
551e643f0c2Sbostic fp1 = rowp;
552e643f0c2Sbostic fp2 = F + tokensetsize * sp->value;
553e643f0c2Sbostic while (fp1 < fp3)
554e643f0c2Sbostic *fp1++ |= *fp2++;
555e643f0c2Sbostic }
556e643f0c2Sbostic rowp = fp3;
557e643f0c2Sbostic }
558e643f0c2Sbostic
559e643f0c2Sbostic for (i = 0; i < n; i++)
56030ee30f7Sbostic for (sp = lookback[i]; sp; sp = next)
56130ee30f7Sbostic {
56230ee30f7Sbostic next = sp->next;
563e643f0c2Sbostic FREE(sp);
56430ee30f7Sbostic }
565e643f0c2Sbostic
566e643f0c2Sbostic FREE(lookback);
567e643f0c2Sbostic FREE(F);
568e643f0c2Sbostic }
569e643f0c2Sbostic
570e643f0c2Sbostic
digraph(relation)571e643f0c2Sbostic digraph(relation)
572e643f0c2Sbostic short **relation;
573e643f0c2Sbostic {
574e643f0c2Sbostic register int i;
575e643f0c2Sbostic
576e643f0c2Sbostic infinity = ngotos + 2;
577e643f0c2Sbostic INDEX = NEW2(ngotos + 1, short);
578e643f0c2Sbostic VERTICES = NEW2(ngotos + 1, short);
579e643f0c2Sbostic top = 0;
580e643f0c2Sbostic
581e643f0c2Sbostic R = relation;
582e643f0c2Sbostic
583e643f0c2Sbostic for (i = 0; i < ngotos; i++)
584e643f0c2Sbostic INDEX[i] = 0;
585e643f0c2Sbostic
586e643f0c2Sbostic for (i = 0; i < ngotos; i++)
587e643f0c2Sbostic {
588e643f0c2Sbostic if (INDEX[i] == 0 && R[i])
589e643f0c2Sbostic traverse(i);
590e643f0c2Sbostic }
591e643f0c2Sbostic
592e643f0c2Sbostic FREE(INDEX);
593e643f0c2Sbostic FREE(VERTICES);
594e643f0c2Sbostic }
595e643f0c2Sbostic
596e643f0c2Sbostic
597e643f0c2Sbostic
traverse(i)598e643f0c2Sbostic traverse(i)
599e643f0c2Sbostic register int i;
600e643f0c2Sbostic {
601e643f0c2Sbostic register unsigned *fp1;
602e643f0c2Sbostic register unsigned *fp2;
603e643f0c2Sbostic register unsigned *fp3;
604e643f0c2Sbostic register int j;
605e643f0c2Sbostic register short *rp;
606e643f0c2Sbostic
607e643f0c2Sbostic int height;
608e643f0c2Sbostic unsigned *base;
609e643f0c2Sbostic
610e643f0c2Sbostic VERTICES[++top] = i;
611e643f0c2Sbostic INDEX[i] = height = top;
612e643f0c2Sbostic
613e643f0c2Sbostic base = F + i * tokensetsize;
614e643f0c2Sbostic fp3 = base + tokensetsize;
615e643f0c2Sbostic
616e643f0c2Sbostic rp = R[i];
617e643f0c2Sbostic if (rp)
618e643f0c2Sbostic {
619e643f0c2Sbostic while ((j = *rp++) >= 0)
620e643f0c2Sbostic {
621e643f0c2Sbostic if (INDEX[j] == 0)
622e643f0c2Sbostic traverse(j);
623e643f0c2Sbostic
624e643f0c2Sbostic if (INDEX[i] > INDEX[j])
625e643f0c2Sbostic INDEX[i] = INDEX[j];
626e643f0c2Sbostic
627e643f0c2Sbostic fp1 = base;
628e643f0c2Sbostic fp2 = F + j * tokensetsize;
629e643f0c2Sbostic
630e643f0c2Sbostic while (fp1 < fp3)
631e643f0c2Sbostic *fp1++ |= *fp2++;
632e643f0c2Sbostic }
633e643f0c2Sbostic }
634e643f0c2Sbostic
635e643f0c2Sbostic if (INDEX[i] == height)
636e643f0c2Sbostic {
637e643f0c2Sbostic for (;;)
638e643f0c2Sbostic {
639e643f0c2Sbostic j = VERTICES[top--];
640e643f0c2Sbostic INDEX[j] = infinity;
641e643f0c2Sbostic
642e643f0c2Sbostic if (i == j)
643e643f0c2Sbostic break;
644e643f0c2Sbostic
645e643f0c2Sbostic fp1 = base;
646e643f0c2Sbostic fp2 = F + j * tokensetsize;
647e643f0c2Sbostic
648e643f0c2Sbostic while (fp1 < fp3)
649e643f0c2Sbostic *fp2++ = *fp1++;
650e643f0c2Sbostic }
651e643f0c2Sbostic }
652e643f0c2Sbostic }
653