[unix-history] / usr / src / usr.bin / yacc / lalr.c

/*
 * Copyright (c) 1989 The Regents of the University of California.
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Robert Paul Corbett.
 *
 * %sccs.include.redist.c%
 */

#ifndef lint
static char sccsid[] = "@(#)lalr.c	5.3 (Berkeley) %G%";
#endif /* not lint */

#include "defs.h"

typedef
  struct shorts
    {
      struct shorts *next;
      short value;
    }
  shorts;

int tokensetsize;
short *lookaheads;
short *LAruleno;
unsigned *LA;
short *accessing_symbol;
core **state_table;
shifts **shift_table;
reductions **reduction_table;
short *goto_map;
short *from_state;
short *to_state;

short **transpose();

static int infinity;
static int maxrhs;
static int ngotos;
static unsigned *F;
static short **includes;
static shorts **lookback;
static short **R;
static short *INDEX;
static short *VERTICES;
static int top;


lalr()
{
    tokensetsize = WORDSIZE(ntokens);

    set_state_table();
    set_accessing_symbol();
    set_shift_table();
    set_reduction_table();
    set_maxrhs();
    initialize_LA();
    set_goto_map();
    initialize_F();
    build_relations();
    compute_FOLLOWS();
    compute_lookaheads();
}


set_state_table()
{
    register core *sp;

    state_table = NEW2(nstates, core *);
    for (sp = first_state; sp; sp = sp->next)
	state_table[sp->number] = sp;
}


set_accessing_symbol()
{
    register core *sp;

    accessing_symbol = NEW2(nstates, short);
    for (sp = first_state; sp; sp = sp->next)
	accessing_symbol[sp->number] = sp->accessing_symbol;
}


set_shift_table()
{
    register shifts *sp;

    shift_table = NEW2(nstates, shifts *);
    for (sp = first_shift; sp; sp = sp->next)
	shift_table[sp->number] = sp;
}


set_reduction_table()
{
    register reductions *rp;

    reduction_table = NEW2(nstates, reductions *);
    for (rp = first_reduction; rp; rp = rp->next)
	reduction_table[rp->number] = rp;
}


set_maxrhs()
{
  register short *itemp;
  register short *item_end;
  register int length;
  register int max;

  length = 0;
  max = 0;
  item_end = ritem + nitems;
  for (itemp = ritem; itemp < item_end; itemp++)
    {
      if (*itemp >= 0)
	{
	  length++;
	}
      else
	{
	  if (length > max) max = length;
	  length = 0;
	}
    }

  maxrhs = max;
}


initialize_LA()
{
  register int i, j, k;
  register reductions *rp;

  lookaheads = NEW2(nstates + 1, short);

  k = 0;
  for (i = 0; i < nstates; i++)
    {
      lookaheads[i] = k;
      rp = reduction_table[i];
      if (rp)
	k += rp->nreds;
    }
  lookaheads[nstates] = k;

  LA = NEW2(k * tokensetsize, unsigned);
  LAruleno = NEW2(k, short);
  lookback = NEW2(k, shorts *);

  k = 0;
  for (i = 0; i < nstates; i++)
    {
      rp = reduction_table[i];
      if (rp)
	{
	  for (j = 0; j < rp->nreds; j++)
	    {
	      LAruleno[k] = rp->rules[j];
	      k++;
	    }
	}
    }
}


set_goto_map()
{
  register shifts *sp;
  register int i;
  register int symbol;
  register int k;
  register short *temp_map;
  register int state2;
  register int state1;

  goto_map = NEW2(nvars + 1, short) - ntokens;
  temp_map = NEW2(nvars + 1, short) - ntokens;

  ngotos = 0;
  for (sp = first_shift; sp; sp = sp->next)
    {
      for (i = sp->nshifts - 1; i >= 0; i--)
	{
	  symbol = accessing_symbol[sp->shift[i]];

	  if (ISTOKEN(symbol)) break;

	  if (ngotos == MAXSHORT)
	    fatal("too many gotos");

	  ngotos++;
	  goto_map[symbol]++;
        }
    }

  k = 0;
  for (i = ntokens; i < nsyms; i++)
    {
      temp_map[i] = k;
      k += goto_map[i];
    }

  for (i = ntokens; i < nsyms; i++)
    goto_map[i] = temp_map[i];

  goto_map[nsyms] = ngotos;
  temp_map[nsyms] = ngotos;

  from_state = NEW2(ngotos, short);
  to_state = NEW2(ngotos, short);

  for (sp = first_shift; sp; sp = sp->next)
    {
      state1 = sp->number;
      for (i = sp->nshifts - 1; i >= 0; i--)
	{
	  state2 = sp->shift[i];
	  symbol = accessing_symbol[state2];

	  if (ISTOKEN(symbol)) break;

	  k = temp_map[symbol]++;
	  from_state[k] = state1;
	  to_state[k] = state2;
	}
    }

  FREE(temp_map + ntokens);
}


/*  Map_goto maps a state/symbol pair into its numeric representation.	*/

int
map_goto(state, symbol)
int state;
int symbol;
{
    register int high;
    register int low;
    register int middle;
    register int s;

    low = goto_map[symbol];
    high = goto_map[symbol + 1];

    for (;;)
    {
	assert(low <= high);
	middle = (low + high) >> 1;
	s = from_state[middle];
	if (s == state)
	    return (middle);
	else if (s < state)
	    low = middle + 1;
	else
	    high = middle - 1;
    }
}


initialize_F()
{
  register int i;
  register int j;
  register int k;
  register shifts *sp;
  register short *edge;
  register unsigned *rowp;
  register short *rp;
  register short **reads;
  register int nedges;
  register int stateno;
  register int symbol;
  register int nwords;

  nwords = ngotos * tokensetsize;
  F = NEW2(nwords, unsigned);

  reads = NEW2(ngotos, short *);
  edge = NEW2(ngotos + 1, short);
  nedges = 0;

  rowp = F;
  for (i = 0; i < ngotos; i++)
    {
      stateno = to_state[i];
      sp = shift_table[stateno];

      if (sp)
	{
	  k = sp->nshifts;

	  for (j = 0; j < k; j++)
	    {
	      symbol = accessing_symbol[sp->shift[j]];
	      if (ISVAR(symbol))
		break;
	      SETBIT(rowp, symbol);
	    }

	  for (; j < k; j++)
	    {
	      symbol = accessing_symbol[sp->shift[j]];
	      if (nullable[symbol])
		edge[nedges++] = map_goto(stateno, symbol);
	    }
	
	  if (nedges)
	    {
	      reads[i] = rp = NEW2(nedges + 1, short);

	      for (j = 0; j < nedges; j++)
		rp[j] = edge[j];

	      rp[nedges] = -1;
	      nedges = 0;
	    }
	}

      rowp += tokensetsize;
    }

  SETBIT(F, 0);
  digraph(reads);

  for (i = 0; i < ngotos; i++)
    {
      if (reads[i])
	FREE(reads[i]);
    }

  FREE(reads);
  FREE(edge);
}


build_relations()
{
  register int i;
  register int j;
  register int k;
  register short *rulep;
  register short *rp;
  register shifts *sp;
  register int length;
  register int nedges;
  register int done;
  register int state1;
  register int stateno;
  register int symbol1;
  register int symbol2;
  register short *shortp;
  register short *edge;
  register short *states;
  register short **new_includes;

  includes = NEW2(ngotos, short *);
  edge = NEW2(ngotos + 1, short);
  states = NEW2(maxrhs + 1, short);

  for (i = 0; i < ngotos; i++)
    {
      nedges = 0;
      state1 = from_state[i];
      symbol1 = accessing_symbol[to_state[i]];

      for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
	{
	  length = 1;
	  states[0] = state1;
	  stateno = state1;

	  for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
	    {
	      symbol2 = *rp;
	      sp = shift_table[stateno];
	      k = sp->nshifts;

	      for (j = 0; j < k; j++)
		{
		  stateno = sp->shift[j];
		  if (accessing_symbol[stateno] == symbol2) break;
		}

	      states[length++] = stateno;
	    }

	  add_lookback_edge(stateno, *rulep, i);

	  length--;
	  done = 0;
	  while (!done)
	    {
	      done = 1;
	      rp--;
	      if (ISVAR(*rp))
		{
		  stateno = states[--length];
		  edge[nedges++] = map_goto(stateno, *rp);
		  if (nullable[*rp] && length > 0) done = 0;
		}
	    }
	}

      if (nedges)
	{
	  includes[i] = shortp = NEW2(nedges + 1, short);
	  for (j = 0; j < nedges; j++)
	    shortp[j] = edge[j];
	  shortp[nedges] = -1;
	}
    }

  new_includes = transpose(includes, ngotos);

  for (i = 0; i < ngotos; i++)
    if (includes[i])
      FREE(includes[i]);

  FREE(includes);

  includes = new_includes;

  FREE(edge);
  FREE(states);
}


add_lookback_edge(stateno, ruleno, gotono)
int stateno, ruleno, gotono;
{
    register int i, k;
    register int found;
    register shorts *sp;

    i = lookaheads[stateno];
    k = lookaheads[stateno + 1];
    found = 0;
    while (!found && i < k)
    {
	if (LAruleno[i] == ruleno)
	    found = 1;
	else
	    ++i;
    }
    assert(found);

    sp = NEW(shorts);
    sp->next = lookback[i];
    sp->value = gotono;
    lookback[i] = sp;
}


short **
transpose(R, n)
short **R;
int n;
{
  register short **new_R;
  register short **temp_R;
  register short *nedges;
  register short *sp;
  register int i;
  register int k;

  nedges = NEW2(n, short);

  for (i = 0; i < n; i++)
    {
      sp = R[i];
      if (sp)
	{
	  while (*sp >= 0)
	    nedges[*sp++]++;
	}
    }

  new_R = NEW2(n, short *);
  temp_R = NEW2(n, short *);

  for (i = 0; i < n; i++)
    {
      k = nedges[i];
      if (k > 0)
	{
	  sp = NEW2(k + 1, short);
	  new_R[i] = sp;
	  temp_R[i] = sp;
	  sp[k] = -1;
	}
    }

  FREE(nedges);

  for (i = 0; i < n; i++)
    {
      sp = R[i];
      if (sp)
	{
	  while (*sp >= 0)
	    *temp_R[*sp++]++ = i;
	}
    }

  FREE(temp_R);

  return (new_R);
}


compute_FOLLOWS()
{
  digraph(includes);
}


compute_lookaheads()
{
  register int i, n;
  register unsigned *fp1, *fp2, *fp3;
  register shorts *sp, *next;
  register unsigned *rowp;

  rowp = LA;
  n = lookaheads[nstates];
  for (i = 0; i < n; i++)
    {
      fp3 = rowp + tokensetsize;
      for (sp = lookback[i]; sp; sp = sp->next)
	{
	  fp1 = rowp;
	  fp2 = F + tokensetsize * sp->value;
	  while (fp1 < fp3)
	    *fp1++ |= *fp2++;
	}
      rowp = fp3;
    }

  for (i = 0; i < n; i++)
    for (sp = lookback[i]; sp; sp = next)
      {
        next = sp->next;
        FREE(sp);
      }

  FREE(lookback);
  FREE(F);
}


digraph(relation)
short **relation;
{
  register int i;

  infinity = ngotos + 2;
  INDEX = NEW2(ngotos + 1, short);
  VERTICES = NEW2(ngotos + 1, short);
  top = 0;

  R = relation;

  for (i = 0; i < ngotos; i++)
    INDEX[i] = 0;

  for (i = 0; i < ngotos; i++)
    {
      if (INDEX[i] == 0 && R[i])
	traverse(i);
    }

  FREE(INDEX);
  FREE(VERTICES);
}


traverse(i)
register int i;
{
  register unsigned *fp1;
  register unsigned *fp2;
  register unsigned *fp3;
  register int j;
  register short *rp;

  int height;
  unsigned *base;

  VERTICES[++top] = i;
  INDEX[i] = height = top;

  base = F + i * tokensetsize;
  fp3 = base + tokensetsize;

  rp = R[i];
  if (rp)
    {
      while ((j = *rp++) >= 0)
	{
	  if (INDEX[j] == 0)
	    traverse(j);

	  if (INDEX[i] > INDEX[j])
	    INDEX[i] = INDEX[j];

	  fp1 = base;
	  fp2 = F + j * tokensetsize;

	  while (fp1 < fp3)
	    *fp1++ |= *fp2++;
	}
    }

  if (INDEX[i] == height)
    {
      for (;;)
	{
	  j = VERTICES[top--];
	  INDEX[j] = infinity;

	  if (i == j)
	    break;

	  fp1 = base;
	  fp2 = F + j * tokensetsize;

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