fatbase

lalr.c (11006B)

---

 /*	$OpenBSD: lalr.c,v 1.17 2014/05/17 15:19:17 chl Exp $	*/
 /*	$NetBSD: lalr.c,v 1.4 1996/03/19 03:21:33 jtc Exp $	*/
 
 /*
  * 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.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  * 3. Neither the name of the University nor the names of its contributors
  *    may be used to endorse or promote products derived from this software
  *    without specific prior written permission.
  *
  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  */
 
 #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();
 void set_state_table(void);
 void set_accessing_symbol(void);
 void set_shift_table(void);
 void set_reduction_table(void);
 void set_maxrhs(void);
 void initialize_LA(void);
 void set_goto_map(void);
 void initialize_F(void);
 void build_relations(void);
 void compute_FOLLOWS(void);
 void compute_lookaheads(void);
 int map_goto(int, int);
 void digraph(short **);
 void add_lookback_edge(int, int, int);
 void traverse(int);
 
 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;
 
 void
 lalr(void)
 {
 	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();
 	free_derives();
 	free_nullable();
 }
 
 
 void
 set_state_table(void)
 {
 	core *sp;
 
 	state_table = NEW2(nstates, core *);
 	for (sp = first_state; sp; sp = sp->next)
 		state_table[sp->number] = sp;
 }
 
 
 void
 set_accessing_symbol(void)
 {
 	core *sp;
 
 	accessing_symbol = NEW2(nstates, short);
 	for (sp = first_state; sp; sp = sp->next)
 		accessing_symbol[sp->number] = sp->accessing_symbol;
 }
 
 
 void
 set_shift_table(void)
 {
 	shifts *sp;
 
 	shift_table = NEW2(nstates, shifts *);
 	for (sp = first_shift; sp; sp = sp->next)
 		shift_table[sp->number] = sp;
 }
 
 
 void
 set_reduction_table(void)
 {
 	reductions *rp;
 
 	reduction_table = NEW2(nstates, reductions *);
 	for (rp = first_reduction; rp; rp = rp->next)
 		reduction_table[rp->number] = rp;
 }
 
 
 void
 set_maxrhs(void)
 {
 	short *itemp, *item_end;
 	int length, 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;
 }
 
 
 void
 initialize_LA(void)
 {
 	int i, j, k;
 	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++;
 			}
 		}
 	}
 }
 
 void
 set_goto_map(void)
 {
 	shifts *sp;
 	int i, k, symbol;
 	int state1, state2;
 	short *temp_map;
 
 	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(int state, int symbol)
 {
 	int high, low, middle, 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;
 	}
 }
 
 
 void
 initialize_F(void)
 {
 	int i, j, k;
 	shifts *sp;
 	short *edge, *rp, **reads;
 	unsigned int *rowp;
 	int nedges, stateno, symbol, 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);
 }
 
 
 void
 build_relations(void)
 {
 	int i, j, k;
 	short *rulep, *rp;
 	shifts *sp;
 	int length, nedges, done;
 	int state1, stateno, symbol1, symbol2;
 	short *shortp, *edge, *states;
 	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);
 }
 
 void
 add_lookback_edge(int stateno, int ruleno, int gotono)
 {
 	int i, k, found;
 	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(short **R, int n)
 {
 	short **new_R, **temp_R, *nedges, *sp;
 	int i, 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);
 }
 
 
 void
 compute_FOLLOWS(void)
 {
 	digraph(includes);
 }
 
 void
 compute_lookaheads(void)
 {
 	int i, n;
 	unsigned int *fp1, *fp2, *fp3;
 	shorts *sp, *next;
 	unsigned int *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);
 }
 
 void
 digraph(short **relation)
 {
 	int i;
 
 	infinity = ngotos + 2;
 	INDEX = NEW2(ngotos + 1, short);
 	VERTICES = NEW2(ngotos + 1, short);
 	top = 0;
 	R = relation;
 
 	memset(INDEX, 0, ngotos * sizeof(short));
 	for (i = 0; i < ngotos; i++)
 		if (R[i])
 			traverse(i);
 
 	free(INDEX);
 	free(VERTICES);
 }
 
 
 void
 traverse(int i)
 {
 	unsigned int *base, *fp1, *fp2, *fp3;
 	int j, height;
 	short *rp;
 
 	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++;
 		}
 	}
 }