compress.cc

This is a resource based on j2me embedded,if you dont understand,you can connection with me .

	while ( ( sp = sl_i.next() ) != 0 ){
		switch ( sp->type() ){
		case symbol::unaryop:
			n = compress_unary_transition(
			    (unary_symbol *) sp,
			    bool_temp
			);
			if (DEBUG(COMPRESS) && n != 0 ){
			    printf("Compressed %d transitions from unary %s\n",
				n, sp->name() );
			}
			n_sum += n;
			break;
		case symbol::binaryop:
			n = compress_binary_transition_row(
			    (binary_symbol *) sp,
			    bool_temp
			);
			if (DEBUG(COMPRESS) && n != 0 ){
			    printf("Compressed %d rows from binary %s\n",
				    n, sp->name() );
			}
			n_sum += n;
			n = compress_binary_transition_col(
			    (binary_symbol *) sp,
			    bool_temp
			);
			if (DEBUG(COMPRESS) && n != 0 ){
			    printf("Compressed %d cols from binary %s\n",
				    n, sp->name() );
			}
			n_sum += n;
			break;
		}
	}

	free( bool_temp );
	return n_sum;
}

/*
 * Detecting redundant states is easier than it sounds.
 * All you really need to do is make sure that they always
 * mean the same thing. This means looking at the transition
 * maps to see if they map to the same entry/row/column.
 * Also, make sure they represent the same full matches of the
 * same rules, if any. After all, we need them to cause the same
 * semantic actions.
 */

static int
are_states_redundant( state * s1, state * s2 )
{
	int * r1, * r2;
	int n_r;
	int sn1, sn2;
	symbollist_iterator sym_i;
	symbol * symp;

	// first, compare production semantics.
	n_r = nonterminal_symbols.n();
	if ( s1->rules_to_use == 0 )
		s1->use_rules();
	r1 = s1->rules_to_use;
	if ( s2->rules_to_use == 0 )
		s2->use_rules();
	r2 = s2->rules_to_use;
	while( n_r -- > 0 ){
		if (*(r1++) != *(r2++) )
			return 0; // immediate difference
	}
	// ok, so they use all the same rules.
	// but do the act the same in the transition tables??
	sn1 = s1->number;
	sn2 = s2->number;
	sym_i = all_symbols;
	while ( ( symp = sym_i.next() ) != 0 ){
		switch ( symp->type() ){
		case symbol::binaryop:
			if (symp->rhs_map[sn1] != symp->rhs_map[sn2] )
				return 0; // don't map the same.
			// FALL THRU
		case symbol::unaryop:
			if (symp->lhs_map[sn1] != symp->lhs_map[sn2] )
				return 0; // don't map the same.
			break;
		}
	}
	//
	// they have the same rules.
	// they make the same transitions.
	// they are the same.
	return 1;
}

static void
whack_state_list( const int * renumber_vector )
{
	int new_number;
	state * sp;
	statelist_iterator sli;
	statelist new_list;

	// renumber_vector is here just for sanity check.
	sli = allstates;
	new_number = 0;
	while( (sp = sli.next() ) != 0 ){
		if ( sp->is_active() ){
			// renumber and put on new list.
			assert( new_number == renumber_vector[ sp->number ] );
			sp->number = new_number;
			new_number += 1;
			new_list.add( sp );
		}
		// else: we could reap dead states but DO NOT.
	}
	// REPLACE OLD LIST WITH NEW
	allstates.destruct();
	allstates = new_list;

}

static void
renumber_transition_vector(
	register stateno *svector,
	register int max_subscript,
	register const int * renumber_vector )
{
	register int i;

	for( i = 0; i <= max_subscript ; i ++ ){
		svector[i] = renumber_vector[ svector[i] ];
	}
}

static void
renumber_unary_transition(
	unary_transition * usp,
	register const int * renumber_vector )
{

	renumber_transition_vector(
	    usp->state,
	    usp->max_stateno(),
	    renumber_vector );
}

static void
renumber_binary_transition(
	binary_transition * bsp,
	register const int * renumber_vector )
{
	int i;
	int max_ro_no = bsp->row_max_stateno();
	int max_col_no = bsp->col_max_stateno();
	binary_transition_row * rowvec = bsp->state;

	for( i = 0; i <= max_ro_no ; i ++ ){
		renumber_transition_vector(
		    rowvec[i].state, max_col_no, renumber_vector );
	}
}

static void
renumber_statemap(
	register statemap * smp,
	register const char * delvector,
	int new_state_max,
	int old_state_max )
{
	statemap newmap;
	register stateno old_i, new_i;
	register stateno oldmax;
	// if state numbers are changing, then
	// map ordinates are, too. Deal with it.
	newmap.grow( new_state_max );
	oldmax = smp->max_ordinate();
	for( old_i = 0, new_i = 0 ; old_i <= oldmax ; old_i++ ){
		if ( ! delvector[ old_i ] ){
			// keep a state.
			newmap.new_mapping( new_i, (*smp)[ old_i ] );
			new_i += 1;
		}
	}
	assert( new_i == new_state_max+1 );
	assert( old_i <= old_state_max+1 );
	smp->destruct();
	*smp = newmap;

}

static void
renumber_transitions(
	const int * renumber_vector,
	const char * delvector,
	int new_state_max,
	int old_state_max )
{
	symbollist_iterator  sl_i;
	symbol * sp;

	sl_i = all_symbols;
	while ( ( sp = sl_i.next() ) != 0 ){
		switch ( sp->type() ){
		case symbol::unaryop:
			renumber_unary_transition(
			    ((unary_symbol *) sp)->transitions,
			    renumber_vector
			);
			renumber_statemap(
			    & sp->lhs_map, delvector, new_state_max, old_state_max );
			break;
		case symbol::binaryop:
			renumber_binary_transition(
			    ((binary_symbol *) sp)->transitions,
			    renumber_vector
			);
			renumber_statemap(
			    & sp->rhs_map, delvector, new_state_max, old_state_max );
			renumber_statemap(
			    & sp->lhs_map, delvector, new_state_max, old_state_max );
			break;
		case symbol::terminal: {
			// the easy case.
			leaf_transition * ltp = ((terminal_symbol *)sp)->transitions;
			ltp->state = renumber_vector[ ltp->state ];
			break;
		    }
		}
	}

}

static int
delete_redundant_states()
{
	statelist_iterator a, b;
	state * q, *r;
	int n_states = allstates.n();
	int * renumber_vector = (int *)malloc( n_states*sizeof(int) );
	int delvector_size= n_states*sizeof(char);
	char * delvector = (char *)malloc( delvector_size );
	int new_state_number;
	int n_redundant = 0;
	int i;

	/*
	 * delvector : an entry per state.
	 *	0 =>still active
	 *	1 =>deactivated, will be removed.
	 * This is redundant with is_active() information in the state
	 * table, but is more convenient for us.
	 *
	 * renumber_vector: an entry per state.
	 *	indexed by old state number, gives new state number.
	 *	for use when whacking transition tables.
	 */
	a = allstates;
	memset( delvector, 0, delvector_size );

	new_state_number = 0;
	while( ( q = a.next() ) != 0 ){
		if ( ! q->is_active() ) continue;
		assert( delvector[ q->number ] == 0 );

		renumber_vector[ q->number ] = new_state_number;
		b = a; // copy iterator state.
		while ( ( r = b.next() ) != 0 ){
			if ( r == q ) continue; // oops.
			if ( ! r->is_active() ) continue; // more oops.
			assert( delvector[ r->number ] == 0 );

			if ( are_states_redundant( q, r ) ){
				if (DEBUG(COMPRESS)){
				    printf("Redundant states %d and %d detected\n",
					q->number, r->number );
				}
				delvector[ r->number ] = 1;
				assert ( q->number < r->number ); // this matters
				renumber_vector[ r->number ] = new_state_number;
				r->deactivate();
				n_redundant ++;
			}
		}
		new_state_number += 1;
	}
	/*
	 * An example is wanted here. Let us say that we had 9 states,
	 * and have found that state 4 is redundant with state 2, and
	 * that state 7 is redundant with state 5. Notice that the above
	 * assertion of ( q->number < r->number ) ensures us that we delete
	 * the HIGHER numbered redundant state. This is what our data look
	 * like in this case:
	 *
	 * i 			0  1  2  3  4  5  6  7  8
	 * delvector[i]		0  0  0  0  1  0  0  1  0
	 * renumber_vector[i]	0  1  2  3  2  4  5  4  6
	 * 
	 * Notice in this case that renumber_vector[7] gives the NEW state
	 * number (4) corresponding to the redundant state (was 5).
	 */

	if ( n_redundant == 0 ){
		// boring: didn't find anything redundant
		free( (char *)delvector );
		free( (char *)renumber_vector );
		return 0;
	}

	/*
	 * Just to be really sure that things look as we expect ....
	 */
	new_state_number = -1;
	for ( i = 0; i < n_states; i ++ ){
		if ( delvector[i] ){
			assert( renumber_vector[i] <= new_state_number );
		} else {
			assert( renumber_vector[i] == ++new_state_number );
		}
	}

	/*
	 * Delete deactivated states from the state table.
	 * and renumber the survivors.
	 * We don't really need to do this, but I feel uncomfortable
	 * leaving inactive states in the table.
	 */
	whack_state_list( renumber_vector );

	/*
	 * Now for the big work: traverse ALL the transition tables,
	 * renumbering ALL the state numbers.
	 */
	renumber_transitions( renumber_vector, delvector, allstates.n()-1, n_states-1 );

	// done
	free( (char *)delvector );
	free( (char *)renumber_vector );

	if ( n_redundant != 0 )
		delete_inversion_info();
	return n_redundant;
}

// DEBUG
extern void print_transition_tables(
    const char * statetype,
    FILE *output,
    FILE *data );
// DEBUG
int
compress_output()
{
	int n_states = 0;
	int n;
	// DEBUG
	int iterno;
	if ( uncompress!= 0 ) return 0;

	iterno = 1;
	// DEBUG
	if (DEBUG(COMPRESS) && DEBUG(DUMPTABLES)){
		printf("Before compress_transition\n" );
		print_transition_tables( "INT", stdout, stdout );
	}
	// DEBUG
	while( compress_transitions()){
		// DEBUG
		if (DEBUG(COMPRESS) && DEBUG(DUMPTABLES)){
			printf("After compress_transition #%d\n", iterno );
			print_transition_tables( "INT", stdout, stdout );
		}
		// DEBUG
		n = delete_redundant_states();
		// DEBUG
		if ( n != 0 ){
			if (DEBUG(COMPRESS) && DEBUG(DUMPTABLES)){
			    printf("After delete_redundant_states #%d\n", iterno );
			    print_transition_tables( "INT", stdout, stdout );
			}
		}
		// DEBUG
		n_states += n;
		if ( n == 0 ) break;
		iterno += 1;
	}
	if ( n_states != 0 && DEBUG(DUMPTABLES) )
		printstates(0);
	if (error_folding){
		symbollist_iterator  sl_i;
		symbol * sp;

		sl_i = all_symbols;
		while ( ( sp = sl_i.next() ) != 0 ){
			switch ( sp->type() ){
			case symbol::unaryop:
				error_compress_unary_transition( (unary_symbol *) sp );
				break;
			case symbol::binaryop:
				error_compress_binary_transition( (binary_symbol *) sp );
				break;
			}
		}
	}
	return n_states;
}