parser.c

OXCC is a multipass, interpreting C compiler with several language extensions. It generates an Archi

/* parser.c -- derived from the `LALR' parser written by Paul Mann */

#define CLASS Parser

#include <oxbow.h>

object CLASS;

instanceVars {
	PG pg;
};
#define HOWBIG 1
#define DEBUG 1

#if HOWBIG
static int maxXX_parse;
static int maxSS_parse;
static int maxSS_lex;
static int maxNS_parse;
static int maxLS_parse;
static int maxRS_parse;
#endif


/* Built in standard actions */
static void nullaction();
static void classify();
static void require();
static void doline();
static void dyntoken();

static void LoadParserPointers();

/* some imported functions */
char *strchr();
char *strrchr();
int atol();
int _strcpy(void *dst, const void *src);
void *strcpy(void *dst, const void *src);
void *strcat(void *dst, const void *src);
void *memcpy(void *dst, const void *src, int len);


/* All chunk types have the same number of bytes */

#define ASTCHUNK (pg->astchunk)
#define SYMBOLCHUNK (pg->symbolchunk)
#define TEXTCHUNK (pg->textchunk)
#define ASTSIZE (pg->astsize)


typedef struct _key
{
	unsigned long key;
	unsigned long hv;
} KEY, *KEYP;

typedef struct _psym
{/* Fits in a minimal sized AST node */
	unsigned short dat[4];		/* 8 bytes */
	KEY cat;					/* 8 bytes */
	struct _psym *next;			/* 4 bytes */
} Psym, *PsymP;

typedef struct _pbuf
{/* parser symbol table struct */
	int	size;
	void *lastbin;	/* for DelLast */
	int headbin;	/* for seq access */
	PsymP headptr;	/* ditto */
	PG *wpg;
	PsymP bins[0];
} *PbufP;

void *
NewParserSymTable(PG *pg, int size)
{
PbufP buf = callocC(pg->category, 1, size*sizeof(PsymP) + sizeof(struct _pbuf));
	buf->size = size;
	buf->wpg = pg;
	return buf;
}

cmethod vobject
New(object self, char *language, int astsize)
{
void *lfile;
char lodname[200];
char filename[40];
char *cp;
PTABLE *pp;
LTABLE *lp;
long *symbase;
char *symptr;
char buf[100];
Item item;
int i;
object instance;
PG *pg;
int oldload = 0;
AstP fnode;

	if(IsaClass(self))
		instance  = cSuper(gNew)(self);
	else {
		instance = self;
	}
	pg = (PG *)ivPtr(instance);
	pg->category = NewMallocCategory();

	strcpy(pg->language, language);
	strcpy(filename, language);
	strcat(filename, ".lod");

	if((cf_find_file("oxlib.cff", lodname)))
	{/* The archive file */
		strcat(lodname, "/language/");
		strcat(lodname, filename);
	} else {
		pg->errors = 1;
		return instance;
	}
	if(cfqget(MEMTEMP, filename, strlen(filename), &item, 8) == FOUND)
	{/* Parser tables for this language have been loaded earlier */
		pg->lod_table = item.a1;
		oldload = 1;
	}
	else
	{/* Load the parser tables for this language */
		if((lfile = cfopen(lodname, F_STAT, NULL)))
		{
		int size;
			size = cfseek(lfile, 0, S_END);
			pg->lod_table = malloc(size);
			cfseek(lfile, 0, S_SET);
			cfread(lfile, pg->lod_table, size);
			cfclose(lfile);
			item.item = 0;
			item.a1 = pg->lod_table;
			cfinsert(MEMTEMP, filename, strlen(filename), &item);
		}
		else {
			pg->errors = 2;
			return instance;
		}
	}

	/* using the size of the caller's AST node, compute suitable chunks */

	if(astsize < sizeof(AST_NODE))
		astsize = sizeof(AST_NODE);

	if(astsize & 3)
		astsize += 4-(astsize&3);

	ASTCHUNK = 8184/astsize;
	TEXTCHUNK = ASTCHUNK * astsize;
	SYMBOLCHUNK = TEXTCHUNK / 4;
	ASTSIZE = astsize;
	
	/* Parser table init */
	pg->ptab = callocC(pg->category, 1, sizeof(PTABLE));	
	pp = pg->ptab;
	pp->pg = pg;
	LoadParserPointers(pp, pg->lod_table, 1);
	pp->linksize = SYMBOLCHUNK;
	pp->link = callocC(pg->category, 1, SYMBOLCHUNK*sizeof(void*));


	/* Lexer table init */
	pg->ltab = callocC(pg->category, 1, sizeof(LTABLE));
	lp = pg->ltab;
	lp->pg = pg;
	LoadParserPointers(lp, (LODTABLE *)(((char *)pg->lod_table) + pg->lod_table->next), 0);

	/* Action pointers, applies to both parser and lexer */
	pg->n_actions = lp->n_actions;	/* lexer has the best action count */
	pg->ACTIONS = (PACTIONS)lp->ACTIONS;
	pg->ACTIONSTRINGS = lp->ACTIONSTRINGS;

	/* Allocate the initial ast space */
	pg->pat.free = callocC(pg->category, 1, ASTCHUNK*astsize);	
	pg->pat.freecnt = pg->pat.cnt = ASTCHUNK;
	fnode = pg->pat.free;
	for(i = 0; i < ASTCHUNK-1; ++i)
	{
		fnode->down = (AstP)(((char*)fnode)+ASTSIZE);
		fnode = fnode->down;
	}

	/* Allocate and initialize the parser symbol table */
	PARSERSYMBOLS = callocC(pg->category, 1, SYMBOLCHUNK*sizeof(PARSER_SYMBOL));
	pg->symhandle = NewParserSymTable(pg, 2003);

	/* Allocate and initialize the first text accumulation chunk */
	pg->chunkbase = callocC(pg->category, 1, TEXTCHUNK);
	pg->chunkend = pg->chunkbase+TEXTCHUNK-1;
	pg->symbase = pg->chunkbase+4;
	pg->symend = pg->symbase;

	/* Enter all the terminal symbols of the grammar */
	symbase = pp->G_symbol;
	symptr = (char *)symbase;

	for(i = 0; i < pp->n_terms; ++i)
	{
		NewParserSymbol(pg, symptr+symbase[i]);
	}

	/* Set the values for the automatic node ids */
	{
	int	symnum = -1;
	int symval;
	int subsym = 0;
	char *cp = NULL;
		for(i = 0; i < pp->n_rules; ++i)
		{
		long *vp;	/* assume callers node ids are sizeof(long) */
			if(pp->PL[i] & PL_MAKENODE)
			{
				if(pp->Head[i] != symnum)
				{
					subsym = 0;
					symnum = pp->Head[i];
					cp = symptr + symbase[symnum];
				}
				/* e.g. _cInitDeclarator_0 */
				cfsprintf(buf, "_%s%s_%d", pg->language, cp, subsym);

				/* use dynamic linker here */
				symval = (symnum<<6) | subsym;
				if((vp = oxlink_find_bare_symb(buf)) != NULL)
				{/* vp is now the address of the symbol in caller memory */
					*vp = symval;  /* caller defined a global symbol he wants */
				}
				++subsym;
			}
		}
	}
	/* Set up the function pointers for actions */
	if(!oldload)
	{/* THIS WOULD WORK WITHOUT TESTING FOR 'oldload', just saving time */
	PACTIONS pa = pg->ACTIONS;
	char *cp;
	int mask;
	int j;

		for(i = 0; i < pg->n_actions; ++i, ++pa)
		{
		/* 
			pa->func is initially set to an offset into ACTIONSTRINGS 
					convert it into a function pointer
		*/
			cp = pg->ACTIONSTRINGS + (int)pa->func; /* funcname is first entry */
			if(!strcmp(cp, "classify"))
				pa->func = classify;
			else if(!strcmp(cp, "require"))
				pa->func = require;
			else if(!strcmp(cp, "doline"))
				pa->func = doline;
			else if(!strcmp(cp, "dyntoken"))
				pa->func = dyntoken;
			else
			{/* Concoct the real user action name and find the function */
				/* e.g. _dosomething_ada_ */
				cfsprintf(buf, "_%s_%s_", cp, pg->language);
				if((pa->func = oxlink_find_bare_func(buf)) == NULL)
				{/* Not already in core */
					if((pa->func = oxlink_load_bare_symb(buf, 1)) == NULL)
					{/* And can't load it from the archive, punt to nothing */
						pa->func = nullaction;
					}
				}
			}
			/* 
				Set up the args:
				arg[0] contains a bitmask in the high order 16 bits
					and argcnt in the low 16 bits 
			*/
			mask = (pa->args[0] & 0xffff0000) >> 16;
			pa->args[0] &= 0x0000ffff;
			for(j = 1; j <= pa->args[0]; ++j)
			{
				if(mask & 1)
				{/* This arg is really a pointer to a string */
					pa->args[j] += (int)pg->ACTIONSTRINGS;
				}
				mask >>= 1;
			}
		}
	}
	/* Set a few constants */
	pg->parsecnt = 2;
	pg->ROOT = 0;
	pg->root = 0;
	pg->line_numb = 1;
	pg->line_char = 0;
#if HOWBIG
	maxXX_parse = 
		maxSS_parse =
			maxSS_lex =
				maxNS_parse =
					maxLS_parse = 
						maxRS_parse = 0;
#endif
	return instance;
}
imethod void
Dispose(object self)
{
PG *pg = (PG *)ivPtr(self);

	freecat(pg->category);
	super(gDispose)(self);
}


static unsigned short bitlist[16] = {
			0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
			0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000, 0x8000
	};
#define BITSET(a,b,c) ( a[b+(c>>4)] & bitlist[c&0xf] )

static int
do_parse (PTABLE *ptab)
{
short i, x;
short *r;
short rule;
unsigned base;
short state;
int token;
short stacktop, *SS;
PG *pg;
int rulesize;
int debug;
int xx;
AstP *link;
int lexindx;

/* NESTED SUBROUTINE Make AST node and/or call semantic action. */

static void attach ()
{
int k, i, j;
AstP np, lp, p;
int rulesize;
AstP newnode;
int savxx;
short *pxx;

	rulesize = ptab->PL[rule] & 0x000f;
	if(rulesize == 15)
		rulesize = -1;

	ptab->NS -= rulesize;         /* Reduce the stack.        */
	ptab->LS -= rulesize;

	for (k=0,np=0,i=rulesize; i >= 0; i--) /* Look at each tail spot.  */
	{
		if (ptab->NS[i])    /* If node pointer there.   */
		{
		int xxx;
			k++;							/* Active node marker.  */
			p = ptab->NS[i];				/* Last node in chain */
			xxx = ptab->LS[i];

			if (np)							/* If one waiting.          */
			{
				lp = link[xxx];
				lp->down = np;				/* Connect last to next.    */
				link[xxx] = link[savxx];	/* Move link */
#if DEBUG
if(debug)cfprintf("Parse: Set DOWN at %x to %x\n", lp, np);
#endif
			}
			np = p;							/* Get this ones address.    */
			savxx = xxx;
		}
	}
	if (ptab->PL [rule] & PL_MAKENODE)
	{
	  newnode = NewAstNode(pg,(ptab->Head[rule]<<6)|(rule-ptab->rBase[rule]),0);
		if(!pg->ROOT)
			pg->ROOT = newnode;

		if (k > 0)
		{/* Make branch */
			newnode->right = np;            /* Pointer to child.        */
			newnode->fileno = (unsigned char)pg->line_file; /* current file */
			newnode->colno = (unsigned char)pg->line_char; /* column of text */
			newnode->lineno = (unsigned short)pg->line_numb;/* Line number. */
			if (np == pg->ROOT) {
				pg->ROOT = newnode; /* Root points to parent.   */
#if DEBUG
if(debug)cfprintf("Parse: Reset ROOT to %x\n", newnode);
#endif
			}
#if DEBUG
if(debug)cfprintf("Parse: New Branch at %x %s_%d  right=%x down=%x\n",
	newnode,GetH_symbol(pg, ptab->Head[rule]),rule-ptab->rBase[rule],np, newnode->down);
#endif
		}
		else
		{/* Make leaf */
		int lookback = (pg->LSP-lexindx)&3;
			newnode->Tindx = pg->L_stack[lookback+1];	/* Terminal type */
			newnode->symb = pg->L_stack[lookback];		/* Symnum */
			newnode->fileno = (unsigned char)pg->line_file; /* current file */
			newnode->colno = (unsigned char)pg->line_char; /* column of text */
			newnode->lineno = (unsigned short)pg->line_numb;/* Line number. */
#if DEBUG
if(debug)cfprintf("Parse: New Leaf at %x %s_%d right=%x down=%x\n", 
	newnode,GetH_symbol(pg, ptab->Head[rule]),rule-ptab->rBase[rule], newnode->right, newnode->down);
#endif
		}

		/* Prevent the unconstrained growth of the link array */
		for(pxx = ptab->LStop, xx = 0; pxx <= ptab->LS; ++pxx)
		{
			if(*pxx > xx)
				xx = *pxx;
		}

		if(++xx == ptab->linksize)
		{/* Extend the link array */
			ptab->linksize += SYMBOLCHUNK;
			link = reallocC(pg->category, link, ptab->linksize*sizeof(int));
			ptab->link = link;
		}
		np = newnode; 
		link[xx] = np;
	}
	*(ptab->NS) = np;
	*(ptab->LS) = xx;

#if HOWBIG
	if(xx > maxXX_parse)
		maxXX_parse = xx;
#endif

/* Call actions for a rule */
	if (ptab->PL [rule] & PL_ACTION)        /* Call action?             */
	{
	PACTIONS ap = &pg->ACTIONS[(ptab->PL[rule]>>7)&511];
#if DEBUG
if(debug)cfprintf("Parse: Call Action for rule:%d\n", rule);
#endif
		ptab->node = np;