⟦6fa78921f⟧

TextFile

/*
 * write goto table and parsing table out to temp file
 * to be picked up later by the optimizer
 * at this point, the tables are fit to be processed by the C parser
 */
#include "yacc.h"
#include "assert.h"
#include "action.h"

char	*actns[] = {
	"SHIFT",
	"REDUCE",
	"ACCEPT",
	"ERROR"
};

static int *uv;

go2out()
{
	register i;

	if( verbose )
		fprintf(listout, "\n\nGoto table:\n\n");
	uv = (int *)yalloc(nstates, sizeof *uv);
	rewopt();
	for(i=1; i<nnonterm; i++)
		outgo2(i);
	free(uv);
}

outgo2(n)
{
	extern yyredns, yygodef;
	int max, sno, j;
	struct sym *sp;
	struct go2n g2;


	sp = ntrmptr[n];
	for(j=0; j<sp->s_nstates; j++)
		uv[j] = 0;
	max = 0;
	for(j=0; j<sp->s_nstates; j++) {
		sno = findnt( &states[sp->s_states[j]], n+NTBASE)->ng_st;
		if( ++uv[sno] > uv[max] )
			max = sno;
	}
	yygodef += uv[max];
	g2.from = (YYGOTO<<YYACTSH) | n;
	g2.to = sp->s_nstates - uv[max] + 1;
	yyredns += g2.to;
	fwrite(&g2, sizeof g2, 1, optout);
	if( verbose )
		fprintf(listout, "%s:\n\n", ntrmptr[n]->s_name);
	for(j=0; j<sp->s_nstates; j++) {
		sno = sp->s_states[j];
		if( (g2.to=findnt(&states[sno], n+NTBASE)->ng_st) == max )
			continue;
		g2.from = sno;
		if( verbose )
			fprintf(listout, "\t%d\t%d\n",  g2.from, g2.to);
		fwrite(&g2, sizeof g2, 1, optout);
	}
	g2.from = YYOTHERS;
	g2.to = max;
	fwrite(&g2, sizeof g2, 1, optout);
	if( verbose )
		fprintf(listout, "\t.\t%d\n\n", max);
}

paout()
{
	register i;

	if( verbose )
		fprintf(listout, "\n\nParsing action table:\n\n");
	for(i=0; i<nstates; i++)
		outstate(i);
}

outstate(n)
{
	extern yydefact, yypact;
	register i, k;
	register struct state *stp;
	int size, max, errshift, pno, maxp, j, l;
	struct lset shls, rdls;
	struct actn rdact[MAXREDS], act;

	stp = &states[n];
	zerolset(&shls);
	for(i=0; i<stp->s_tgo; i++) 
		setbit(&shls, stp->s_tgos[i].tg_trm);
	max = 0;
	maxp = -1;
	for(i=k=0; i<stp->s_nred; i++) {
		pno = stp->s_reds[i].rd_prod->p_prodno;
		copylset(&rdls, stp->s_reds[i].rd_lset);
		resolve(n, i, &shls, &rdls);
		size = 0;
		for(j=first(&rdls); j>=0; j=next(&rdls, j)) {
			for(l=0; l<k; l++) 
				if( rdact[l].a_chr==j ) {
					redred(n, pno, rdact[l].a_no&YYAMASK, j);
					goto nextj; /* C needs next <var> */
				}
			bounded(l, MAXREDS, "reductions");
			rdact[k].a_chr = j;
			rdact[k++].a_no = (YYREDACT<<YYACTSH) | pno;
			size++;
		nextj:
			;
		}
		if( size>max ) {
			max = size;
			maxp = pno;
		}
	}
	if( bit(&shls, ERRNO) || maxp==0 ) /* shift on error or accept */
		maxp = -1;

	/* count total number of actions */
	size = k + lcount(&shls) + !bit(&shls,ERRNO); /* shifts+reds+default */
	if( maxp >= 0 ) {
		size -= max;
		yydefact += max;
	}
	yypact += size;
	act.a_chr = size;
	act.a_no = (YYPACTION<<YYACTSH) | n;
	if( verbose )
		fprintf(listout, "State %d (size %d):\n\n", n, size);
	fwrite(&act, sizeof act, 1, optout);

	/* now have shifts in shls redns in rdact */

	/* output shifts */
	for(j=0; j<stp->s_tgo; j++) {
		if( !bit(&shls, i = stp->s_tgos[j].tg_trm) )
			continue;
		if( i==ERRNO ) { /* will be made default */
			errshift = stp->s_tgos[j].tg_st;
			continue;
		}
		act.a_chr = i;
		act.a_no = (YYSHIFTACT<<YYACTSH) | stp->s_tgos[j].tg_st;
		wract(&act);
	}

	/* output reductions */
	for(i=0; i<k; i++) {
		if( (pno = rdact[i].a_no&YYAMASK) == maxp )
			continue;
		if( pno==0 ) /* $accept -> start $end . */
			rdact[i].a_no = YYACCEPTACT<<YYACTSH;
		wract(&rdact[i]);
	}

	/* default action */
	act.a_chr = YYOTHERS;
	if( bit(&shls, ERRNO) ) {
		act.a_no = (YYSHIFTACT<<YYACTSH) | errshift;
	} else if( maxp>=0 )
		act.a_no = YYREDACT<<YYACTSH | maxp;
	else
		act.a_no = (YYERRACT<<YYACTSH);
	wract(&act);
}

wract(actp)
register struct actn *actp;
{
	register unsigned actn;
	actn = actp->a_no>>YYACTSH;
	if( verbose ) {
		fprintf(listout, "\t%s\t%s", actp->a_chr==YYOTHERS?".":
		    trmptr[actp->a_chr]->s_name, actns[actn]);
		if( actn<=YYREDACT )
			fprintf(listout, "\t%d", actp->a_no&YYAMASK);
		fprintf(listout, "\n");
	}
	fwrite(actp, sizeof *actp, 1, optout);
}

lcount(lp)
struct lset *lp;
{
	register n, count;
	register unsigned char *ucp;
	extern unsigned char bcount[];

	count = 0;
	ucp = lp->l_bits;
	n = LSETSIZE;
	do {
		count += bcount[*ucp++];
	} while (--n);
	return(count);
}

setdiff(ld, ls)
struct lset *ld, *ls;
{
	register n;
	register unsigned char *udcp, *uscp;

	n = LSETSIZE;
	udcp = ld->l_bits;
	uscp = ls->l_bits;
	do {
		*udcp++ &= ~ *uscp++;
	} while (--n);
}

setunion(ld, ls)
struct lset *ld, *ls;
{
	register n;
	register unsigned char *udcp, *uscp;

	n = LSETSIZE;
	udcp = ld->l_bits;
	uscp = ls->l_bits;
	do {
		*udcp++ |= *uscp++;
	} while (--n);
}

setint(ld, ls)
struct lset *ld, *ls;
{
	register n;
	register unsigned char *udcp, *uscp;

	n = LSETSIZE;
	udcp = ld->l_bits;
	uscp = ls->l_bits;
	do {
		*udcp++ &= *uscp++;
	} while (--n);
}

copylset(ld, ls)
struct lset *ld, *ls;
{
	register n;
	register unsigned char *udcp, *uscp;

	n = LSETSIZE;
	udcp = ld->l_bits;
	uscp = ls->l_bits;
	do {
		*udcp++ = *uscp++;
	} while (--n);
}

zerolset(ld)
struct lset *ld;
{
	register n;
	register unsigned char *udcp;

	n = LSETSIZE;
	udcp = ld->l_bits;
	do {
		*udcp++ = 0;
	} while (--n);
}

resolve(sno, p, sls, rls)
int p;
struct lset *sls, *rls;
{
	register i;
	struct lset cls;
	int todo;
	struct prod *pp;
	struct sym *tsp;

	copylset(&cls, sls);
	setint(&cls, rls);
	pp = states[sno].s_reds[p].rd_prod;
	for(i=first(&cls); i>=0; i=next(&cls,i) ) { /* conflict on term i */
		tsp = trmptr[i];
		if( tsp->s_ass<=UNASSOC || pp->p_ass<=UNASSOC ) {
			shiftred(sno, pp->p_prodno, i);
			clrbit(rls, i);
			continue;
			/* conflict resolved in favour of shift */
		}
		if( pp->p_prc > tsp->s_prc )
			todo = LASSOC;
		else if( pp->p_prc < tsp->s_prc )
			todo = RASSOC;
		else
			todo = tsp->s_ass;
		switch( todo ) {
		case LASSOC: /* reduce */
			clrbit(sls, i);
			break;

		case RASSOC:
			clrbit(rls, i);
			break;

		case UNASSOC: /* non-self associating op */
			clrbit(rls, i);
			clrbit(sls, i);
			break;
		}
	}
}

shiftred(sno, pn, tok)
{
	register i;
	struct state *stp;

	stp = &states[sno];
	++nsrconf;
	if( !verbose )
		return;
	for(i=0; i<stp->s_tgo; i++)
		if( stp->s_tgos[i].tg_trm==tok )
			break;
	fprintf(listout, "State %d: Shift/Reduce conflict ", sno);
	fprintf(listout, "(shift %d, red'n %d) on %s\n",
		stp->s_tgos[i].tg_st, pn, trmptr[tok]->s_name);
}

redred(sno, pn1, pn2, tok)
{
	struct state *stp;

	stp = &states[sno];
	++nrrconf;
	if( !verbose )
		return;
	fprintf(listout, "State %d: Reduce/Reduce conflict ", sno);
	fprintf(listout, "(red'n %d, red'n %d) on %s\n",
		pn1, pn2, trmptr[tok]->s_name);
}

clrbit(lp, n)
struct lset *lp;
register n;
{
	register unsigned char *ucp;

	ucp = lp->l_bits;
	ucp[n>>LOGCHAR] &= ~( 01 << (n & (NBCHAR-1)) );
}

setbit(lp, n)
struct lset *lp;
register n;
{
	register unsigned char *ucp;

	ucp = lp->l_bits;
	ucp[n>>LOGCHAR] |= 01 << (n & (NBCHAR-1));
}

bit(lp, n)
struct lset *lp;
register n;
{
	register unsigned char *ucp;

	ucp = lp->l_bits;
	return( (ucp[n>>LOGCHAR] >> (n&(NBCHAR-1))) & 01 );
}

first(lp)
struct lset *lp;
{
	return(next(lp,-1));
}

next(lp, n)
struct lset *lp;
register n;
{
	register w;
	register unsigned char *ucp;
	extern char ltab[];

	if( ++n >= LSETSIZE*NBCHAR )
		return(-1);
	ucp = lp->l_bits;
	w = ucp[n >> LOGCHAR];
	w &= ~ ( (01 << (n&(NBCHAR-1))) - 1);
	n >>= LOGCHAR;
	while (w == 0) {
		if ( ++n >= LSETSIZE )
			return(-1);
		w = ucp[n];
	}
	return( (n<<LOGCHAR) + ltab[w] );
}

struct ntgo *
findnt(stp, nt)
register struct state *stp;
{
	register i;

	for(i=0; i<stp->s_ntgo; i++ )
		if( stp->s_ntgos[i].ng_nt==nt )
			return( &stp->s_ntgos[i] );
	yyerror(NLNO|FATAL, "oops in findnt");
}
DataMuseum.dk

Commodore CBM-900

⟦6fa78921f⟧ TextFile

Derivation

TextFile
