pcctsast.cpp

来自「本工具提供一个词法分析器和语法分析器的集成开发环境」· C++ 代码 · 共 663 行 · 第 1/2 页

/*
 * PCCTSAST.C
 *
 * SOFTWARE RIGHTS
 *
 * We reserve no LEGAL rights to SORCERER -- SORCERER is in the public
 * domain.  An individual or company may do whatever they wish with
 * source code distributed with SORCERER or the code generated by
 * SORCERER, including the incorporation of SORCERER, or its output, into
 * commerical software.
 *
 * We encourage users to develop software with SORCERER.  However, we do
 * ask that credit is given to us for developing SORCERER.  By "credit",
 * we mean that if you incorporate our source code into one of your
 * programs (commercial product, research project, or otherwise) that you
 * acknowledge this fact somewhere in the documentation, research report,
 * etc...  If you like SORCERER and have developed a nice tool with the
 * output, please mention that you developed it using SORCERER.  In
 * addition, we ask that this header remain intact in our source code.
 * As long as these guidelines are kept, we expect to continue enhancing
 * this system and expect to make other tools available as they are
 * completed.
 *
 * SORCERER 1.00B14 and ANTLR 1.33
 * Terence Parr
 * Parr Research Corporation
 * AHPCRC, University of Minnesota
 * 1992-1998
 */

#define ANTLR_SUPPORT_CODE

#include "pcctscfg.h"

#include "PCCTSAST.h"
#include PCCTS_STDARG_H

PCCTS_NAMESPACE_STD

#include <ctype.h>

//#include "SList.h"

               /* String Scanning/Parsing Stuff */

char *PCCTS_AST::scan_token_tbl[] = {
	"invalid",	/*	0 */
	"LPAREN",	/*	1 */
	"RPAREN",	/*	2 */
	"PERCENT",	/*	3 */
	"INT",		/*	4 */
	"COLON",	/*	5 */
	"POUND",	/*	6 */
	"PERIOD",	/*	7 */
};

void PCCTS_AST::
addChild(PCCTS_AST *t)
{
	if ( t==NULL ) return;
	PCCTS_AST *s = down();
	if ( s!=NULL )
	{
		while ( s->right()!=NULL ) s = s->right();
		s->setRight(t);
	}
	else
		this->setDown(t);
}

void PCCTS_AST::
lisp(FILE *f)
{
	if ( down() != NULL ) fprintf(f," (");
	lisp_action(f);
	if ( down()!=NULL ) down()->lisp(f);
	if ( down() != NULL ) fprintf(f," )");
	if ( right()!=NULL ) right()->lisp(f);
}

/* build a tree (root child1 child2 ... NULL)
 * If root is NULL, simply make the children siblings and return ptr
 * to 1st sibling (child1).  If root is not single node, return NULL.
 *
 * Siblings that are actually sibling lists themselves are handled
 * correctly.  For example #( NULL, #( NULL, A, B, C), D) results
 * in the tree ( NULL A B C D ).
 *
 * Requires at least two parameters with the last one being NULL.  If
 * both are NULL, return NULL.
 *
 * The down() and right() down/right pointers are used to make the tree.
 */
PCCTS_AST *PCCTS_AST::
make(PCCTS_AST *rt, ...)
{
	va_list ap;
	register PCCTS_AST *child, *sibling=NULL, *tail, *w;
	PCCTS_AST *root;

	va_start(ap, rt);
	root = rt;

	if ( root != NULL )
		if ( root->down() != NULL ) return NULL;
	child = va_arg(ap, PCCTS_AST *);
	while ( child != NULL )
	{
		/* find end of child */
		for (w=child; w->right()!=NULL; w=w->right()) {;}
		if ( sibling == NULL ) {sibling = child; tail = w;}
		else {tail->setRight(child); tail = w;}
		child = va_arg(ap, PCCTS_AST *);
	}
	if ( root==NULL ) root = sibling;
	else root->setDown(sibling);
	va_end(ap);
	return root;
}

/* The following push and pop routines are only used by ast_find_all() */

void PCCTS_AST::
_push(PCCTS_AST **st, int *sp, PCCTS_AST *e)
{
	(*sp)--;
	require((*sp)>=0, "stack overflow");
	st[(*sp)] = e;
}

PCCTS_AST *PCCTS_AST::
_pop(PCCTS_AST **st, int *sp)
{
	PCCTS_AST *e = st[*sp];
	(*sp)++;
	require((*sp)<=MaxTreeStackDepth, "stack underflow");
	return e;
}

/* Find all occurrences of u in t.
 * 'cursor' must be initialized to 't'.  It eventually
 * returns NULL when no more occurrences of 'u' are found.
 */
PCCTS_AST *PCCTS_AST::
ast_find_all(PCCTS_AST *u, PCCTS_AST **cursor)
{
	PCCTS_AST *sib;
	static PCCTS_AST *template_stack[MaxTreeStackDepth];
	static int tsp = MaxTreeStackDepth;
	static int nesting = 0;

	if ( *cursor == NULL ) return NULL;
	if ( *cursor!=this ) sib = *cursor;
	else {
		/* else, first time--start at top of template 't' */
		tsp = MaxTreeStackDepth;
		sib = this;
		/* bottom of stack is always a NULL--"cookie" indicates "done" */
		_push(template_stack, &tsp, NULL);
	}

keep_looking:
	if ( sib==NULL )	/* hit end of sibling list */
	{
		sib = _pop(template_stack, &tsp);
		if ( sib == NULL ) { *cursor = NULL; return NULL; }
	}

	if ( sib->type() != u->type() )
	{
		/* look for another match */
		if ( sib->down()!=NULL )
		{
			if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
			sib=sib->down();
			goto keep_looking;
		}
		/* nothing below to try, try next sibling */
		sib=sib->right();
		goto keep_looking;
	}

	/* found a matching root node, try to match what's below */
	if ( match_partial(sib, u) )
	{
		/* record sibling cursor so we can pick up next from there */
		if ( sib->down()!=NULL )
		{
			if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
			*cursor = sib->down();
		}
		else if ( sib->right()!=NULL ) *cursor = sib->right();
		else *cursor = _pop(template_stack, &tsp);
		return sib;
	}

	/* no match, keep searching */
	if ( sib->down()!=NULL )
	{
		if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
		sib=sib->down();
	}
	else sib = sib->right();	/* else, try to right if zip below */
	goto keep_looking;
}

/* are two trees exactly alike? */
int PCCTS_AST::
match(PCCTS_AST *u)
{
	PCCTS_AST *t = this;
	PCCTS_AST *sib;

	if ( u==NULL ) return 0;

	for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right())
	{
		if ( sib->type() != u->type() ) return 0;
		if ( sib->down()!=NULL )
			if ( !sib->down()->match(u->down()) ) return 0;
	}
	return 1;
}

/* Is 'u' a subtree of 't' beginning at the root? */
int PCCTS_AST::
match_partial(PCCTS_AST *t, PCCTS_AST *u)
{
	PCCTS_AST *sib;

	if ( u==NULL ) return 1;
	if ( t==NULL ) if ( u!=NULL ) return 0; else return 1;

	for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right())
	{
		if ( sib->type() != u->type() ) return 0;
		if ( sib->down()!=NULL )
			if ( !match_partial(sib->down(), u->down()) ) return 0;
	}
	return 1;
}

/* Walk the template tree 't' (matching against 'this'), filling in the
 * 'labels' array, and setting 'n' according to how many labels were matched.
 */
int PCCTS_AST::
scanmatch(ScanAST *t, PCCTS_AST **labels[], int *n)
{
	ScanAST *sib;
	PCCTS_AST *u = this;

	if ( u==NULL ) return 0;

	for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right())
	{
		/* make sure tokens match; token of '0' means wildcard match */
		if ( sib->type() != u->type() && sib->type()!=0 ) return 0;
		/* we have a matched token here; set label pointers if exists */
		if ( sib->label_num>0 )
		{
			require(labels!=NULL, "label found in template, but no array of labels");
			(*n)++;
			*(labels[sib->label_num-1]) = u;
		}
		/* match what's below if something there and current node is not wildcard */
		if ( sib->down()!=NULL && sib->type()!=0 )
		{
			if ( sib->down()==NULL ) if ( u->down()!=NULL ) return 0; else return 1;
			if ( !u->down()->scanmatch(sib->down(), labels, n) ) return 0;
		}
	}
	return 1;
}

void PCCTS_AST::
insert_after(PCCTS_AST *b)
{
	PCCTS_AST *end;
	if ( b==NULL ) return;
	/* find end of b's child list */
	for (end=b; end->right()!=NULL; end=end->right()) {;}
	end->setRight(this->right());
	this->setRight(b);
}

void PCCTS_AST::
append(PCCTS_AST *b)
{
	PCCTS_AST *end;
	require(b!=NULL, "append: NULL input tree");
	/* find end of child list */
	for (end=this; end->right()!=NULL; end=end->right()) {;}
	end->setRight(b);
}

PCCTS_AST *PCCTS_AST::
tail()
{
	PCCTS_AST *end;
	/* find end of child list */
	for (end=this; end->right()!=NULL; end=end->right()) {;}
	return end;
}

PCCTS_AST *PCCTS_AST::
bottom()
{
	PCCTS_AST *end;
	/* find end of child list */
	for (end=this; end->down()!=NULL; end=end->down()) {;}
	return end;
}

PCCTS_AST *PCCTS_AST::
cut_between(PCCTS_AST *a, PCCTS_AST *b)
{
	PCCTS_AST *end, *ret;
	if (a==NULL||b==NULL) return NULL;
	/* find node pointing to b */
	for (end=a; end->right()!=NULL&&end->right()!=b; end=end->right())
		{;}
	if (end->right()==NULL) return NULL; //ast_cut_between: a,b not connected
	end->setRight(NULL);	/* don't want it point to 'b' anymore */
	ret = a->right();
	a->setRight(b);
	return ret;
}

#ifdef NOT_YET
SList *PCCTS_AST::
to_slist()
{