#include #define ADD_CONST 1 #define ADD_VAR 2 #define PUT 3 #define GET 4 #define CLR 5 #define LOOP 6 #define MALLOC(T) (T*)malloc(sizeof(T)) typedef struct bf_com_T { int var ; int kind ; union { struct { int val ; } add ; struct { int from ; int factor ; } ass ; struct { int shift ; struct bf_com_T *coms ; } loop ; } c ; struct bf_com_T *next ; } bf_com_t ; #define S_VAL 1 #define S_BOOL 2 #define S_ALL_CLR 3 typedef struct var_state_T { int var ; int state ; int val ; int cleared ; struct var_state_T *next ; } var_state_t ; void var_add( var_state_t **ref_states, int var, int val ) { while( (*ref_states) != NULL && (*ref_states)->state != S_ALL_CLR && (*ref_states)->var < var ) ref_states = &(*ref_states)->next ; if ( (*ref_states)->state != S_ALL_CLR && (*ref_states)->var == var ) { if ( (*ref_states)->state == S_VAL ) (*ref_states)->val += val ; else { ref_states = &(*ref_states)->next ; } } } var_state_t shift( var_state_t states, int shift ) { } char *cur ; void parse( int at_var, bf_com_t **ref_com_p, int *shift ) { int cur_var = at_var ; while ( *cur ) { switch( *cur ) { case '+': case '-': { int val = 0 ; for( ; *cur == '+' || *cur == '-'; cur++ ) val += *cur == '+' ? 1 : -1 ; if ( val != 0 ) { bf_com_t *new = MALLOC(bf_com_t) ; new->var = cur_var ; new->kind = ADD_CONST ; new->next = NULL ; new->c.add.val = val ; *ref_com_p = new ; ref_com_p = &(new->next) ; } } break ; case '<': cur_var-- ; cur++ ; break ; case '>': cur_var++ ; cur++ ; break ; case '.': { bf_com_t *new = MALLOC(bf_com_t) ; new->var = cur_var ; new->kind = PUT ; new->next = NULL ; *ref_com_p = new ; ref_com_p = &(new->next) ; } cur++ ; break ; case ',': { bf_com_t *new = MALLOC(bf_com_t) ; new->var = cur_var ; new->kind = GET ; new->next = NULL ; *ref_com_p = new ; ref_com_p = &(new->next) ; } cur++ ; break ; case '[': { int s = 1; int m = 0; int mval = 0; int vars[30]; int added[30]; int nr_vars = 0; int succ = 1; for ( s = 1; cur[s] == '+' || cur[s] == '-' || cur[s] == '<' || cur[s] == '>' ; s++ ) { if ( cur[s] == '<' ) m-- ; else if ( cur[s] == '>' ) m++ ; else if ( m == 0 ) mval += cur[s] == '+' ? 1 : -1 ; else { int i ; for ( i = 0; i < nr_vars && m != vars[ i ]; i++ ) ; if ( i == nr_vars ) { vars[i] = m ; added[i] = 0 ; nr_vars++ ; } added[i] += cur[s] == '+' ? 1 : -1 ; } } if ( cur[s] == ']' && m == 0 && mval == -1 ) { int i ; for ( i = 0; i < nr_vars; i++ ) if ( added[i] != 0 ) { bf_com_t *new = MALLOC(bf_com_t) ; new->var = cur_var + vars[i] ; new->kind = ADD_VAR ; new->next = NULL ; new->c.ass.from = cur_var ; new->c.ass.factor = added[i] ; *ref_com_p = new ; ref_com_p = &(new->next) ; } { bf_com_t *new = MALLOC(bf_com_t) ; new->var = cur_var ; new->kind = CLR ; new->next = NULL ; *ref_com_p = new ; ref_com_p = &(new->next) ; } cur += s + 1; } else { bf_com_t *new = MALLOC(bf_com_t) ; new->var = cur_var ; new->kind = LOOP ; new->next = NULL ; *ref_com_p = new ; ref_com_p = &(new->next) ; cur++ ; parse( cur_var, &(new->c.loop.coms), &(new->c.loop.shift) ) ; } } break ; case ']': *shift = cur_var - at_var ; cur++ ; return ; default: *shift = 0 ; return ; } } } int trace = 0 ; int a[10000] , *p ; void execute( int depth, bf_com_t *coms ) ; void run( bf_com_t *program ) { p = a ; execute( 0, program ) ; } void execute( int depth, bf_com_t *coms ) { for ( ; coms != NULL; coms = coms->next ) { int var = coms->var ; switch( coms->kind ) { case ADD_CONST: if ( trace ) if ( coms->c.add.val > 1 ) printf( "%*.*sp[%d] += %d\n", depth, depth, "", var, coms->c.add.val ) ; else if ( coms->c.add.val == 1 ) printf( "%*.*sp[%d]++\n", depth, depth, "", var ) ; else if ( coms->c.add.val < -1 ) printf( "%*.*sp[%d] -= %d\n", depth, depth, "", var, -coms->c.add.val ) ; else if ( coms->c.add.val == -1 ) printf( "%*.*sp[%d]--\n", depth, depth, "", var ) ; p[var] += coms->c.add.val ; break ; case PUT: fputc( p[var], stdout ) ; fflush( stdout ); break ; case GET: p[var] = fgetc( stdin ); break ; case CLR: if ( trace ) printf( "%*.*sp[%d] = 0\n", depth, depth, "", var ) ; p[var] = 0; break ; case ADD_VAR: if ( trace ) if ( coms->c.ass.factor == 1 ) printf( "%*.*sp[%d] += p[%d]\n", depth, depth, "", var, coms->c.ass.from ) ; else if ( coms->c.ass.factor == -1 ) printf( "%*.*sp[%d] -= p[%d]\n", depth, depth, "", var, coms->c.ass.factor, coms->c.ass.from ) ; else if ( coms->c.ass.factor > 0 ) printf( "%*.*sp[%d] += %d * p[%d]\n", depth, depth, "", var, coms->c.ass.factor, coms->c.ass.from ) ; else if ( coms->c.ass.factor < 0 ) printf( "%*.*sp[%d] -= %d * p[%d]\n", depth, depth, "", var, -coms->c.ass.factor, coms->c.ass.from ) ; p[var] += coms->c.ass.factor * p[coms->c.ass.from] ; break ; case LOOP: if ( trace ) printf( "%*.*sloop p[%d]\n", depth, depth, "", var ) ; while( p[var] ) { execute( depth + 1, coms->c.loop.coms ) ; if ( trace ) if ( coms->c.loop.shift > 0 ) printf( "%*.*s p += %d\n", depth, depth, "", coms->c.loop.shift ) ; else if ( coms->c.loop.shift < 0 ) printf( "%*.*s p -= %d\n", depth, depth, "", -coms->c.loop.shift ) ; p += coms->c.loop.shift ; } break ; default: printf( "/*ERROR*/\n") ; } } } void unparse_to_c( int depth, bf_com_t *coms ) ; void generate_c_code( bf_com_t *program ) { printf( "#include \n" "\n" "main()\n" "{\n" " int a[10000] , *p, i ;\n" " for (i = 0; i < 10000 ; i++ )\n" " a[i] = 0 ;\n" "\n" " p = a ;\n" "\n" ) ; unparse_to_c( 1, program ) ; printf( "}\n" ) ; } void unparse_to_c( int depth, bf_com_t *coms ) { for ( ; coms != NULL; coms = coms->next ) { int var = coms->var ; switch( coms->kind ) { case ADD_CONST: { int val = coms->c.add.val ; if ( val == 1 ) printf("%*.*sp[%d]++;\n", depth, depth, "", var) ; else if ( val == -1 ) printf("%*.*sp[%d]--;\n", depth, depth, "", var) ; else if ( val > 0 ) printf("%*.*sp[%d] += %d;\n", depth, depth, "", var, val) ; else if ( val < 0 ) printf("%*.*sp[%d] -= %d;\n", depth, depth, "", var, -val) ; } break ; case PUT: printf("%*.*sfputc( p[%d], stdout ) ; fflush( stdout );\n", depth, depth, "", var) ; break ; case GET: printf("%*.*sp[%d] = fgetc( stdin );\n", depth, depth, "", var) ; break ; case CLR: printf("%*.*sp[%d] = 0;\n", depth, depth, "", var) ; break ; case ADD_VAR: { int factor = coms->c.ass.factor ; int from = coms->c.ass.from ; if ( factor == 1 ) printf("%*.*sp[%d] += p[%d];\n", depth, depth, "", var, from); else if ( factor == -1 ) printf("%*.*sp[%d] -= p[%d];\n", depth, depth, "", var, from); else if ( factor > 0 ) printf("%*.*sp[%d] += %d * p[%d];\n", depth, depth, "", var, factor, from ); else if ( factor < 0 ) printf("%*.*sp[%d] -= %d * p[%d];\n", depth, depth, "", var, -factor, from ); } break ; case LOOP: printf("%*.*swhile( p[%d] ) {\n", depth, depth, "", var) ; unparse_to_c( depth + 2, coms->c.loop.coms ) ; if ( coms->c.loop.shift == 1 ) printf("%*.*s p++;\n", depth, depth, "") ; else if ( coms->c.loop.shift == -1 ) printf("%*.*s p--;\n", depth, depth, "") ; else if ( coms->c.loop.shift > 0 ) printf("%*.*s p += %d;\n", depth, depth, "", coms->c.loop.shift) ; else if ( coms->c.loop.shift < 0 ) printf("%*.*s p -= %d;\n", depth, depth, "", -coms->c.loop.shift) ; printf("%*.*s}\n", depth, depth, "") ; break ; default: printf( "/*ERROR*/\n") ; } } } void main( int argc, char *argv[] ) { char buffer[10000] ; int buf_end = 0 ; char ch ; int depth = 2 ; bf_com_t *program = NULL ; int shift = 0 ; #define RUN 1 #define CTOC 2 #define COUNT 3 int mode = RUN ; FILE *fin = stdin ; /* parse input arguments */ { int i ; for ( i = 1; i < argc; i++ ) if ( strcmp( argv[i], "-r" ) == 0 ) mode = RUN ; else if ( strcmp( argv[i], "-t" ) == 0 ) trace = 1 ; else if ( strcmp( argv[i], "-2c" ) == 0 ) mode = CTOC ; else if ( strcmp( argv[i], "-C" ) == 0 ) mode = COUNT ; else fin = fopen( argv[i], "r" ) ; } if ( fin == NULL ) return ; ch = (char)fgetc( fin ) ; while ( !feof( fin ) ) { if ( ch == '+' || ch == '-' || ch == '<' || ch == '>' || ch == '.' || ch == ',' || ch == '[' || ch == ']' ) buffer[ buf_end++ ] = ch ; ch = (char)fgetc( fin ) ; } buffer[ buf_end ] = '\0' ; cur = buffer ; parse( 0, &program, &shift ) ; switch ( mode ) { case RUN: run( program ) ; break ; case CTOC: generate_c_code( program ) ; break ; case COUNT: run( program ) ; printf( "%d\n", a[0] ) ; break ; } }