look.c

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

{
	SymEntry *p;
	GLA *blkstart, *blkend, *blkloopback, *start=NULL;
	require(elem!=NULL, "build_GLA_for_element: NULL tree pointer");

	if ( elem == NULL ) return NULL;
	switch ( elem->token )
	{
	    case Token :
			p = (SymEntry *) hash_get(symbols, elem->text);
			require(p!=NULL, "build_GLA_for_element: token not in sym tab");
			start = newGLANode();
			start->p1 = newGLANode();
			start->label1 = p->token_type;
			start->upper_range = elem->upper_range;
			*elem_tail = start->p1;
			break;
		case NonTerm :
			/* edge 1 points to the start of the GLA for the referenced rule.
			 * Make a new node as if it
			 * were connected, however, so that this node can be connected to the end
			 * of block node by the build BLOCK routine.
			 */
			p = (SymEntry *) hash_get(symbols, elem->text);
			if ( p==NULL || !p->defined ) {
				errNoFL(eMsg1("rule not defined: '%s'", elem->text));
				start = newGLANode();
				start->p1 = newGLANode();
				start->label1 = wild_card;
				*elem_tail = start->p1;
				break;
			}
			start = newGLANode();
			start->is_rule_ref = 1;
			start->p1 = p->start_state;
			start->label1 = epsilon;
			start->next = newGLANode();
			*elem_tail = start->next;
			/* maintain reference list for this nonterminal */
			list_add(&p->refs, start->next);
			break;
		case WILD :
			start = newGLANode();
			start->p1 = newGLANode();
			start->label1 = wild_card;
			*elem_tail = start->p1;
			break;
		case Action :
			*elem_tail = NULL;
			break;
		case PRED_OP :
			/* return o->blk */
			start = newGLANode();
			start->p1 = build_GLA_for_block(elem->down, elem_tail);
			start->label1 = epsilon;
			elem->down->start_state = start;
			/* DO NOT RETURN the block ptr because we don't want the lookahead
			 * analysis to see it.  However, the AST BLOCK node will pt to it.
			 */
			start = NULL;
			*elem_tail = NULL;
			break;
		case CLOSURE :
			/* Make a blk like this:
			 *     v---------|
			 * o-->o-->blk-->o-->o
			 *     |-------------^
			 * where the farthest left node is the start node passed in,
			 * the 2nd from the right is created here, and the 2nd from the left
			 * is a node created here.  The farthest right node is created
			 * here as the end_blk node for the CLOSURE block.  The 'p2' ptr
			 * of the blkloopback node goes back to the blkstart node.
			 */
			blkstart = newGLANode();
			blkloopback = newGLANode();
			blkend = newGLANode();
			blkstart->p1 = build_GLA_for_block(elem->down, elem_tail);
			blkstart->label1 = epsilon;
			blkstart->p2 = blkend;
			blkstart->label2 = epsilon;
			blkloopback->p1 = blkend;
			blkloopback->label1 = epsilon;
			blkloopback->p2 = blkstart;
			blkloopback->label2 = epsilon;
			(*elem_tail)->p1 = blkloopback;
			(*elem_tail)->label1 = epsilon;
			*elem_tail = blkend;
			elem->down->start_state = blkstart;
			start = newGLANode();
			start->p1 = blkstart;
			start->label1 = epsilon;
			break;
		case POS_CLOSURE :
			/* Make a blk like this:
			 * o-->o-->blk-->o-->o
			 *     ^---------|
			 * where the farthest left node is the start node passed in.
			 * The 'next' ptr of the blkstart node points to the endblk node.
			 */
			blkstart = newGLANode();
			blkloopback = newGLANode();
			blkend = newGLANode();
			blkstart->p1 = build_GLA_for_block(elem->down, elem_tail);
			blkstart->label1 = epsilon;
			/* record the end of loop for "follow" computation */
			blkstart->next = blkend;
			blkloopback->p1 = blkend;
			blkloopback->label1 = epsilon;
			blkloopback->p2 = blkstart;
			blkloopback->label2 = epsilon;
			(*elem_tail)->p1 = blkloopback;
			(*elem_tail)->label1 = epsilon;
			*elem_tail = blkend;
			elem->down->start_state = blkstart;
			start = newGLANode();
			start->p1 = blkstart;
			start->label1 = epsilon;
			break;
		case OPT :
			/* Make a blk like this:
			 * o-->o-->blk-->o
			 *     |---------^
			 * where the farthest left node is the start node passed in.
			 */
			blkstart = newGLANode();
			blkend = newGLANode();
			blkstart->p1 = build_GLA_for_block(elem->down, elem_tail);
			blkstart->label1 = epsilon;
			blkstart->p2 = blkend;
			blkstart->label2 = epsilon;
			(*elem_tail)->p1 = blkend;
			(*elem_tail)->label1 = epsilon;
			*elem_tail = (*elem_tail)->p1;
			elem->down->start_state = blkstart;
			start = newGLANode();
			start->p1 = blkstart;
			start->label1 = epsilon;
			break;
		case BLOCK :
			/* return o->blk */
			start = newGLANode();
			start->p1 = build_GLA_for_block(elem, elem_tail);
			start->label1 = epsilon;
			elem->start_state = start;
			break;
	}
	return start;
}

void
#ifdef __USE_PROTOS
build_follow_links( GLA *end_of_rule, ListNode *refs )
#else
build_follow_links( end_of_rule, refs )
GLA *end_of_rule;
ListNode *refs;
#endif
{
	ListNode *p;
	GLA *f, *prev, *first=NULL;
	require(end_of_rule!=NULL, "build_follow_links: NULL tree pointer");

	if ( refs == NULL )	/* no ref list, must be start symbol */
	{
		/* append a '$' link to the end_input node */
		end_of_rule->p1 = end_node;
		end_of_rule->label1 = end_of_input;
		return;
	}

	/* the refs list is a list of GLA nodes that follow references to
	 * the rule associated with 'end_of_rule'.
	 */
	prev = NULL;
	for (p = refs->next; p!=NULL; p=p->next)
	{
		f = newGLANode();
		f->p1 = (GLA *)p->elem;
		f->label1 = epsilon;
		/* connect new follow link into downward list */
		if ( prev!=NULL )
		{
			prev->p2 = f;
			prev->label2 = epsilon;
		}
		else
		{
			first = f;
		}
		prev = f;
	}

	/* connect end of rule to follow list */
	end_of_rule->p1 = first;
	end_of_rule->label1 = epsilon;
}

void
#ifdef __USE_PROTOS
dump_GLAs( AST *rules )
#else
dump_GLAs( rules )
AST *rules;
#endif
{
	AST *r;
	SymEntry *s;
	require(rules!=NULL, "dump_GLAs: NULL rules pointer");

	fprintf(stderr,"\n");
	for (r=rules; r!=NULL; r=r->right)
	{
		s = (SymEntry *) hash_get(symbols, r->text);
		require(s!=NULL, "build_GLA: sym tab broken");
		dump_GLA( s->start_state );
		fprintf(stderr,"\n");
	}
}

/* Can only dump GLA's for BNF for the moment */
void
#ifdef __USE_PROTOS
dump_GLA( GLA *q )
#else
dump_GLA( q )
GLA *q;
#endif
{
    GLA *prod, *p;

    fprintf(stderr,"o-->");
    for (prod=q->p1; prod!=NULL; prod=prod->p2)
    {
        fprintf(stderr,"o");

        for (p = prod; p->p1!=NULL;)
        {
            if ( p->visited ) break;
            p->visited = 1;

            if ( p->label1 > 0 && p->label1!=epsilon )
            {
                fprintf(stderr,"--%s-->o", token_dict[p->label1]);
                p = p->p1;
                if ( p->label1 == end_of_input ) break;
			}
            else if ( p->next!=NULL )
            {
                /*fprintf(stderr,"-%d-^  o", p->context); */
                fprintf(stderr,"---^  o");
                p = p->next;
			}
            else
            {
                fprintf(stderr,"----->o");
                p = p->p1;
			}
		}
        fprintf(stderr,"\n");
        if ( prod->p2!=NULL ) fprintf(stderr,"    |\n    ");
	}
}

/*
 * Compare each alt of a BLOCK against every other to determine
 * whether or not any tokens predict more than one alt.
 */
void
#ifdef __USE_PROTOS
test_block_consistency( AST *blk, int block_type )
#else
test_block_consistency( blk, block_type )
AST *blk;
int block_type;
#endif
{
	AST *t;
	set in_common;
	GLA *alt1, *alt2, *start;
	int i1, i2;
	require(blk!=NULL&&blk->token==BLOCK,
			"test_BLOCK_consistency: NULL or invalid block");

	t = blk->down;
	require(t!=NULL&&t->token==ALT,
			"test_BLOCK_consistency: invalid AST structure");
	require(blk->start_state!=NULL,
			"test_BLOCK_consistency: no GLA structure for block");

	start = blk->start_state->p1;
	for (alt1=start,i1=1; alt1!=NULL; alt1=alt1->p2,i1++, t=t->right)
	{
		require(!set_nil(alt1->lookahead), "test_BLOCK_consistency: invalid lookahead set");
		for (alt2=alt1->p2,i2=i1+1; alt2!=NULL; alt2=alt2->p2,i2++)
		{
			in_common = set_and(alt1->lookahead, alt2->lookahead);
			if ( !set_nil(in_common) )
			{
				fprintf(stderr, ErrHdr, FileStr[t->file], t->line);
				fprintf(stderr, " warning: alts %d and %d of (...) nondeterministic upon ",
						i1, i2);
				set_fprint(stderr, in_common);
				fprintf(stderr, "\n");
			}
			set_free(in_common);
		}
	}

	if ( block_type == OPT || block_type == CLOSURE )
	{
		/* test optional alt against all regular alts */
		t = blk->down;
		for (alt1=blk->start_state->p1,i1=1; alt1!=NULL; alt1=alt1->p2,i1++, t=t->right)
		{
			in_common = set_and(alt1->lookahead, blk->start_state->lookahead);
			if ( !set_nil(in_common) )
			{
				fprintf(stderr, ErrHdr, FileStr[t->file], t->line);
				fprintf(stderr, " warning: alt %d and optional branch of %s nondeterministic upon ",
						i1, block_type==OPT?"{...}":"(...)*");
				set_fprint(stderr, in_common);
				fprintf(stderr, "\n");
			}
			set_free(in_common);
		}
	}
}

static GLA *
#ifdef __USE_PROTOS
newGLANode(void)
#else
newGLANode()
#endif
{
	GLA *p;

	p = (GLA *) calloc(1, sizeof(GLA));
	require(p!=NULL, "newGLANode: can't alloc memory");
	p->in_rule = CurRule;
	return p;
}