state.cc

来自「This is a resource based on j2me embedde」· CC 代码 · 共 654 行 · 第 1/2 页

 * generalize_symbol is the inner loop: once we've found a full match
 * we pass the incurred cost and the lhs symbol to generalize_symbol,
 * which constructs items and looks them up. minselect_generalize
 * is the outer loop.
 */

static inline void
generalize_symbol( symbol *s, int cost_so_far, item_costset * Newset )
{

	Newset->cost_union( s->get_closure(), cost_so_far );
}

static item_costset
itemset_minselect_generalize( const item_costset & Input )
{
	item_cost cost;
	item_costset_iterator Ilist;
	item olditem;
	item_table *t = Input.pattab();
	item_costset result(t);

	Ilist = Input;
	result = Input.copy();
	while( ( olditem = Ilist.next( &cost ) ) != item_none ){
		if ( t->item_subpart(olditem) == item_table::fullmatch ){
			/* found a full match. 
			 * find all the places the lhs symbol
			 * appear in any rule, and consider
			 * adding those partial matches to 
			 * Inew.
			 */
			cost += t->item_rule( olditem )->principle_cost();
			generalize_symbol(
				    t->item_rule( olditem )->lhs(),
				    cost,
				    &result );
		}
	}
	return result;
}

/* "combine" function for empty state */
state *
state::null_state( item_table* itp )
{
	if (nullstate==0){
		nullstate = state::newstate( item_costset(itp), 0 );
		assert( nullstate->number == NULL_STATE );
	}
	return nullstate;
}

/* "combine" function for leaves */
state *
state::combine( terminal_symbol *s )
{
	item_costset tempa;
	state * v;
	tempa = allmatch( s );
	v = state::newstate( tempa, s );
	// tempa is not ours to destruct.
	// it belongs to s.
	return v;
}

/* "combine" function for unary operators */
state *
state::combine( unary_symbol *s, unsigned l_stateno )
{
	item_costset tempa;

	tempa = s->lhs_sets.get( l_stateno );
	if ( tempa.is_empty() )
		return nullstate;
	return state::newstate( tempa, s );
	// tempa is not ours to destruct.
	// it belongs to s.
}

/* "combine" function for binary operators */
state *
state::combine( binary_symbol *s, unsigned l_stateno, unsigned r_stateno )
{
	item_costset tempa, tempb, tempc;
	state * v;
	tempa = s->lhs_sets.get( l_stateno );
	if ( tempa.is_empty() )
		return nullstate;
	// tempa is not ours to destruct.
	// it belongs to s.
	tempb = s->rhs_sets.get( r_stateno );
	if ( tempb.is_empty() )
		return nullstate;
	// tempb is not ours to destruct, or to intersect into.
	// it belongs to s.
	tempc = tempb.copy();
	tempc.cost_intersect( tempa, 0);
	v = state::newstate( tempc, s );
	tempc.destruct();
	return v;
}

/*
 *  Stuff for making new states. States are kept in a pool, which is
 *  an array of linked lists of states. The array is indexed by some
 *  function of the state. We'll first try the rule number of the
 * first item on the itemset. Since itemsets are sorted by something
 * (rule number?) the first one should always be the same for two
 * itemsets that are the same.
 * We'll also keep a statelist of states in ascending numerical order.
 */

class statelist allstates; // the list of all states in ascending order.
class state * nullstate = 0;

static unsigned nlists = 0;
static state ** statelists = 0;

class state *
state::newstate( const item_costset & ilist, const symbol * syp )
{
	item_costset_iterator iter;
	item_costset	temp_set;
	item ip;
	item_cost c;
	int ruleno;
	state * sp;
	/*
	 * compare this state with all that have gone before.
	 */
	// getting the first rule number is suprizingly awkward.
	temp_set = itemset_trim( ilist );
	iter = temp_set;
	ip = iter.next( &c );
	ruleno = (ip==item_none) ? 0 : temp_set.pattab()->item_rule( ip )->ruleno();
	if (nlists== 0){
		// first time through
		nlists = all_rules.n()+1; // 0th state is null!!
		statelists = (state **)calloc( nlists, sizeof(state *) );
		assert(statelists!=0);
	} else {
		// look for preexisting state.
		sp = statelists[ ruleno ];
		while (sp != 0){
			if (item_costset_equal( sp->core ,  temp_set ) ){
				temp_set.destruct();
				return sp;
			} else {
				sp = sp->next;
			}
		}

	}
	// No such state currently exists. Make up a new one.
	sp = new state;
	sp->number = allstates.n();
	sp->core = temp_set;
	sp->symp = syp;
	sp->rules_to_use = 0;
	temp_set = itemset_minselect_generalize( sp->core );
	sp->items = itemset_trim( temp_set );
	temp_set.destruct();
	// put new state on lists.
	sp->next = statelists[ ruleno ];
	statelists[ ruleno ] = sp;
	allstates.add( sp );
	// debug printing
	if (DEBUG(NSTATES) ){
		printf("New state: #%d has %d core, %d total items\n",
		    sp->number, sp->core.n(), sp->items.n() );
		fflush(stdout);
	}
	if (DEBUG(DUMPTABLES) ){
		sp->print( verbose );
		fflush(stdout);
	}

	return sp;
}

static void
ambiguous_state( state * stp, symbol * goal_p )
{
	item_costset_iterator c_i;
	item pc;
	item_cost cst;
	item_table *t;
	int firstrule = -1;
	wordlist example;

	fprintf( stderr, "Warning: grammar is ambiguous (state %d)\n", stp->number );
	fprintf( stderr, "	cannot tell which of these rules to use to get a %s:\n", 
		 goal_p->name() );
	c_i = stp->items;
	t = stp->items.pattab();

	while( (pc = c_i.next( &cst ) ) != item_none ){
		if ( t->item_isfullmatch( pc ) 
		    && t->item_rule( pc )->lhs() == goal_p ){
			fputs("\t", stderr);
			t->item_rule( pc )->print(stderr, false);
			if (firstrule < 0 )
				firstrule = t->item_rule( pc )->ruleno();
		}
	}
	example = invert_state( stp );
	fprintf( stderr,"\texample ambiguous input tree: ");
	print_wordlist( &example, stderr );
	example.destruct();

	fprintf( stderr, "\nUsing rule %d\n\n", firstrule );
}

/*
 * Compute the rules_to_use vector.
 */
void
state::use_rules()
{
	int *   rp;     // the output vector, of length nonterms.n().
	int nfullmatch;
	symbol *sp;
	symbollist_iterator s_iter;
	item   pc;
	item_table *  t;
	item_costset_iterator i_iter;
	item_cost     cst;

	rules_to_use = (int *) malloc( nonterminal_symbols.n() * sizeof(int) );
	assert( rules_to_use != 0 );
	rp = rules_to_use;

	s_iter = nonterminal_symbols;
	while ( (sp = s_iter.next() ) != 0) {
		// for all goals...
		nfullmatch = 0;
		i_iter = items;
		t = items.pattab();
		while ( (pc = i_iter.next(&cst) ) != item_none ){
			// find a full match resulting in that goal.
			if ( t->item_rule(pc)->lhs() == sp
			  && t->item_isfullmatch(pc) ){
				// and record its rule number
				if (nfullmatch == 0 ){
					*(rp++ ) =
					    t->item_rule(pc)->ruleno();
					t->item_rule(pc)->set_reached(true);
				} else{
					ambiguous_state( this, sp );
				}
				nfullmatch += 1;
			}
		}
		if ( nfullmatch == 0 ){
			*(rp++ ) = 0 ; // oops.
		}
	}
}

/*
 * print out a state, print out all states.
 */

void
state::print(int verbose, FILE * out)
{
	fprintf( out, "%d core: (", number );
	core.print(out);
	fprintf(out, ")\n");
	if (verbose >= 2 ){
		// print closure set.
		fprintf(out, "%d closure: (", number );
		items.print(out);
		fprintf(out, ")\n");
	}

}

void
printstates(int print_closure_sets)
{
	statelist_iterator s_i;
	state *sp;
	s_i = allstates;
	printf("\nSTATES:\n");
	while( (sp = s_i.next() ) != 0){
		sp->print(!print_closure_sets);
	}
	fflush(stdout);
}

void
printstateinversion()
{
	statelist_iterator s_i;
	state *sp;
	wordlist example;
	static int maxprinted=-1;
	int stateno;

	s_i = allstates;
	fflush(stderr);
	printf("\nSTATE INPUT EXAMPLES:\n");
	while( (sp = s_i.next() ) != 0){
		stateno = sp->number;
		if ( stateno <= maxprinted ) 
			continue;
		example = invert_state( sp );
		printf( "state %d example input tree:\n\t", stateno );
		print_wordlist( &example, stdout );
		example.destruct();
		printf("\n");
	}
	maxprinted = stateno;
	fflush(stdout);
}

// find the state (if there is one) that has zero items
// useful for folding with other states during compression

int
find_error_state(void)
{
	return NULL_STATE;
}