astlib.c

来自「SRI international 发布的OAA框架软件」· C语言 代码 · 共 835 行 · 第 1/2 页

}

SORAST *
#ifdef __USE_PROTOS
ast_cut_between(SORAST *a, SORAST *b)
#else
ast_cut_between(a, b)
SORAST *a,*b;
#endif
{
	SORAST *end, *ret;
	require(a!=NULL&&b!=NULL, "ast_cut_between: NULL input tree");
	/* find node pointing to b */
	for (end=a; end->ast_right!=NULL&&end->ast_right!=b; end=end->ast_right)
		{;}
	require(end->ast_right!=NULL, "ast_cut_between: a,b not connected");
	end->ast_right = NULL;	/* don't want it point to 'b' anymore */
	ret = a->ast_right;
	a->ast_right = b;
	return ret;
}

SList *
#ifdef __USE_PROTOS
ast_to_slist(SORAST *t)
#else
ast_to_slist(t)
SORAST *t;
#endif
{
	SList *list=NULL;
	SORAST *p;

	for (p=t; p!=NULL; p=p->ast_right)
	{
		slist_add(&list, p);
	}
	return list;
}

SORAST *
#ifdef __USE_PROTOS
slist_to_ast(SList *list)
#else
slist_to_ast(list)
SList *list;
#endif
{
	SORAST *t=NULL, *last=NULL;
	SList *p;

	for (p = list->next; p!=NULL; p=p->next)
	{
		SORAST *u = (SORAST *)p->elem;
		if ( last==NULL ) last = t = u;
		else { last->ast_right = u; last = u; }
	}
	return t;
}

void
#ifdef __USE_PROTOS
ast_free(SORAST *t)
#else
ast_free(t)
SORAST *t;
#endif
{
    if ( t == NULL ) return;
    ast_free( t->ast_down );
    ast_free( t->ast_right );
    free( t );
}

int
#ifdef __USE_PROTOS
ast_nsiblings(SORAST *t)
#else
ast_nsiblings(t)
SORAST *t;
#endif
{
	int n=0;

	while ( t!=NULL )
	{
		n++;
		t = t->ast_right;
	}
	return n;
}

SORAST *
#ifdef __USE_PROTOS
ast_sibling_index(SORAST *t, int i)
#else
ast_sibling_index(t,i)
SORAST *t;
int i;
#endif
{
	int j=1;
	require(i>0, "ast_sibling_index: i<=0");

	while ( t!=NULL )
	{
		if ( j==i ) return t;
		j++;
		t = t->ast_right;
	}
	return NULL;
}

static void
#ifdef __USE_PROTOS
scanast_free(ScanAST *t)
#else
scanast_free(t)
ScanAST *t;
#endif
{
    if ( t == NULL ) return;
    scanast_free( t->down );
    scanast_free( t->right );
    free( t );
}

/*
 * ast_scan
 *
 * This function is like scanf(): it attempts to match a template
 * against an input tree.  A variable number of tree pointers
 * may be set according to the '%i' labels in the template string.
 * For example:
 *
 *   ast_scan("#( 6 #(5 %1:4 %2:3) #(1 %3:3 %4:3) )",
 *            t, &w, &x, &y, &z);
 *
 * Naturally, you'd want this converted from
 *
 *	 ast_scan("#( RangeOp #(Minus %1:IConst %2:Var) #(Plus %3:Var %4Var) )",
 *			  t, &w, &x, &y, &z);
 *
 * by SORCERER.
 *
 * This function call must be done withing a SORCERER file because SORCERER
 * must convert the token references to the associated token number.
 *
 * This functions parses the template and creates trees which are then
 * matched against the input tree.  The labels are set as they are
 * encountered; hence, partial matches may leave some pointers set
 * and some NULL.  This routines initializes all argument pointers to NULL
 * at the beginning.
 *
 * This function returns the number of labels matched.
 */
int
#ifdef PCCTS_USE_STDARG
ast_scan(char *templ, SORAST *tree, ...)
#else
ast_scan(va_alist)
va_dcl
#endif
{
	va_list ap;
	ScanAST *t;
	int n, i, found=0;
	SORAST ***label_ptrs=NULL;

#ifdef PCCTS_USE_STDARG
	va_start(ap, tree);
#else
	char *templ;
	SORAST *tree;

	va_start(ap);
	templ = va_arg(ap, char *);
	tree = va_arg(ap, SORAST *);
#endif

	/* make a ScanAST tree out of the template */
	t = stringparser_parse_scanast(templ, &n);

	/* make an array out of the labels */
	if ( n>0 )
	{
		label_ptrs = (SORAST ***) calloc(n, sizeof(SORAST **));
		require(label_ptrs!=NULL, "ast_scan: out of memory");
		for (i=1; i<=n; i++)
		{
			label_ptrs[i-1] = va_arg(ap, SORAST **);
			*(label_ptrs[i-1]) = NULL;
		}
	}

	/* match the input tree against the template */
	ast_scanmatch(t, tree, label_ptrs, &found);

	scanast_free(t);
	free(label_ptrs);

	return found;
}

static ScanAST *
#ifdef __USE_PROTOS
new_scanast(int tok)
#else
new_scanast(tok)
int tok;
#endif
{
    ScanAST *p = (ScanAST *) calloc(1, sizeof(ScanAST));
    if ( p == NULL ) {fprintf(stderr, "out of mem\n"); exit(-1);}
	p->token = tok;
	return p;
}

static ScanAST *
#ifdef __USE_PROTOS
stringparser_parse_scanast(char *templ, int *num_labels)
#else
stringparser_parse_scanast(templ, num_labels)
char *templ;
int *num_labels;
#endif
{
	StringLexer lex;
	StringParser parser;
	ScanAST *t;

	stringlexer_init(&lex, templ);
	stringparser_init(&parser, &lex);
	t = stringparser_parse_tree(&parser);
	*num_labels = parser.num_labels;
	return t;
}

static void
#ifdef __USE_PROTOS
stringparser_match(StringParser *parser, int token)
#else
stringparser_match(parser, token)
StringParser *parser;
int token;
#endif
{
	if ( parser->token != token ) sorcerer_panic("bad tree in ast_scan()");
}

/*
 * Match a tree of the form:
 *		(root child1 child2 ... childn)
 * or,
 *		node
 *
 * where the elements are integers or labeled integers.
 */
static ScanAST *
#ifdef __USE_PROTOS
stringparser_parse_tree(StringParser *parser)
#else
stringparser_parse_tree(parser)
StringParser *parser;
#endif
{
	ScanAST *t=NULL, *root, *child, *last = NULL;

	if ( parser->token != POUND )
	{
		return stringparser_parse_element(parser);
	}
	stringparser_match(parser,POUND);
	parser->token = stringscan_gettok(parser->lexer);
	stringparser_match(parser,LPAREN);
	parser->token = stringscan_gettok(parser->lexer);
	root = stringparser_parse_element(parser);
	while ( parser->token != RPAREN )
	{
		child = stringparser_parse_element(parser);
		if ( t==NULL ) { t = child; last = t; }
		else { last->right = child; last = child; }
	}
	stringparser_match(parser,RPAREN);
	parser->token = stringscan_gettok(parser->lexer);
	root->down = t;
	return root;
}

static ScanAST *
#ifdef __USE_PROTOS
stringparser_parse_element(StringParser *parser)
#else
stringparser_parse_element(parser)
StringParser *parser;
#endif
{
	static char ebuf[100];
	int label = 0;

	if ( parser->token == POUND )
	{
		return stringparser_parse_tree(parser);
	}
	if ( parser->token == PERCENT )
	{
		parser->token = stringscan_gettok(parser->lexer);
		stringparser_match(parser,INT);
		label = atoi(parser->lexer->text);
		parser->num_labels++;
		if ( label==0 ) sorcerer_panic("%%0 is an invalid label");
		parser->token = stringscan_gettok(parser->lexer);
		stringparser_match(parser,COLON);
		parser->token = stringscan_gettok(parser->lexer);
		/* can label tokens and wildcards */
		if ( parser->token != INT && parser->token != PERIOD )
			sorcerer_panic("can only label tokens");
	}
	if ( parser->token == INT )
	{
		ScanAST *p = new_scanast(atoi(parser->lexer->text));
		parser->token = stringscan_gettok(parser->lexer);
		p->label_num = label;
		return p;
	}
	if ( parser->token == PERIOD )
	{
		ScanAST *p = new_scanast(0);	/* token of 0 is wildcard */
		parser->token = stringscan_gettok(parser->lexer);
		p->label_num = label;
		return p;
	}
	sprintf(ebuf, "mismatch token in ast_scan(): %s", scan_token_str(parser->token));
	sorcerer_panic(ebuf);
    return NULL; /* MR20 make -Wall happy */
}

static void
#ifdef __USE_PROTOS
stringparser_init(StringParser *parser, StringLexer *input)
#else
stringparser_init(parser, input)
StringParser *parser;
StringLexer *input;
#endif
{
	parser->lexer = input;
	parser->token = stringscan_gettok(parser->lexer);
	parser->num_labels = 0;
}

static void
#ifdef __USE_PROTOS
stringlexer_init(StringLexer *scanner, char *input)
#else
stringlexer_init(scanner, input)
StringLexer *scanner;
char *input;
#endif
{
	scanner->text[0]='\0';
	scanner->input = input;
	scanner->p = input;
	stringscan_advance(scanner);
}

static void
#ifdef __USE_PROTOS
stringscan_advance(StringLexer *scanner)
#else
stringscan_advance(scanner)
StringLexer *scanner;
#endif
{
	if ( *(scanner->p) == '\0' ) scanner->c = StringScanEOF;
	scanner->c = *(scanner->p)++;
}

static int
#ifdef __USE_PROTOS
stringscan_gettok(StringLexer *scanner)
#else
stringscan_gettok(scanner)
StringLexer *scanner;
#endif
{
	char *index = &scanner->text[0];
	static char ebuf[100];

	while ( isspace(scanner->c) ) { stringscan_advance(scanner); }
	if ( isdigit(scanner->c) )
	{
		int tok = INT;
		while ( isdigit(scanner->c) ) {
			*index++ = scanner->c;
			stringscan_advance(scanner);
		}
		*index = '\0';
		return tok;
	}
	switch ( scanner->c )
	{
		case '#' : stringscan_advance(scanner); return POUND;
		case '(' : stringscan_advance(scanner); return LPAREN;
		case ')' : stringscan_advance(scanner); return RPAREN;
		case '%' : stringscan_advance(scanner); return PERCENT;
		case ':' : stringscan_advance(scanner); return COLON;
		case '.' : stringscan_advance(scanner); return PERIOD;
		case '\0' : return StringScanEOF;
		case StringScanEOF : return StringScanEOF;
		default  :
			sprintf(ebuf, "invalid char in ast_scan: '%c'", scanner->c);
			sorcerer_panic(ebuf);
            return 0; /* MR20 Make -Wall happy */
	}
}