2012年5月4日金曜日

bf処理系、Cで構文木(?)作るバージョン

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

bf2c.pyでトランスレータはおもしろくないことが分かっていたので、解析してtreeを作らせた。ほぼlispのcons対。

include 
#include 
#include 


/*
 *  http://en.wikipedia.org/wiki/Brainfuck
 */

char* helloworld_expected = "Hello World!\n";
char* helloworld = "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.";


/* 
 *  http://codegolf.com/competition/run/8/2
 */

char* another_expected = "Just another brainfuck hacker.";
char* another = 
  "+++[>+++++<-]>[>+>+++>+>++>+++++>++<[++<]>---]>->-.[>++>+<<--]>--.--.+.>>>++.<<"
  ".<------.+.+++++.>>-.<++++.<--.>>>.<<---.<.-->-.>+.[+++++.---<]>>[.--->]<<.<+.+"
  "+.++>+++[.<][.]<++.";


char memory[30000];
char *data = memory;
char *tape= 0;

typedef struct TAst Ast;

union UValue {
  char uChar;
  Ast *uAst;
};

typedef union UValue Value;

struct TAst {
  Ast* fNext;
  int fType;
  Value fValue;
};


int debug = 0;

Ast* make_node(Ast* parent){
  Ast* ast;
  ast = malloc(sizeof(Ast));
  if(parent){
    parent->fNext = ast;
  }

  if(debug)
    printf("makde ast node %p (parent %p)\n", ast, parent);//->fValue.uAst);
  return ast;
}

Ast* parse(char** p){
  Ast* root;
  Ast* head;
  Ast* n;
  char* sub;

  root = make_node(0);
  root->fNext = 0;
  root->fType = 0;
  head = root;

  while (**p){
    switch(**p){
      case '[':
        n = make_node(head);
        (*p)++; //consume [
        n->fNext = 0;
        n->fType = 0;
        n->fValue.uAst = parse(p);
        head = n;
        break;
      case ']': 
        // ] will be consumed after return, in '[' case.
        return root->fNext;
      default:
        n = make_node(head);
        n->fNext = 0;
        n->fType = 1;
        n->fValue.uChar = **p;
        head = n;
        break;
    }
    (*p)++;
  }
  return root->fNext;
}

void print_ast(Ast *ast, int indent){
  int i;
  
  while(ast){
    if (ast->fType){
      for(i=0; i< indent; i++){
        printf(" ");
      }
      printf("%c\n", ast->fValue.uChar);
    }else{
      for(i=0; i< indent; i++){
        printf(" ");
      }
      printf("Entered %p \n", ast->fValue.uAst);
      print_ast(ast->fValue.uAst, indent+2);
    }
    ast = ast->fNext;
  }
}


void run(Ast *ast){
  while (ast){
    if(debug)
      printf("%i, %i, %i, %i, %i\n", memory[0], memory[1], memory[2], memory[3], memory[4]);
    if (ast->fType){
      if(debug)
        printf("processing %c\n", ast->fValue.uChar);
      switch (ast->fValue.uChar){
        case '>':
          /* increment the data pointer (to point to the next cell to the right). */
          data++;
          break;
    
        case '<':
          /* decrement the data pointer (to point to the next cell to the left). */
          data--;
          break;
    
        case '+':
          /* increment (increase by one) the byte at the data pointer. */
          (*data)+=1;
          break;
    
        case '-':
          /* decrement (decrease by one) the byte at the data pointer. */
          (*data)-=1;
          break;
          
        case '.':
          /* output the byte at the data pointer as an ASCII encoded character.*/
          if(debug)
            printf("%i", *data);
          printf("%c", *data);
          break;
    
        case ',':
          /* accept one byte of input, storing its value in the byte at the data pointer. */
          /* not implemented */
          break;
        default:
          break;
      }
    }else{
      if(debug)
        printf("handling subtree, %p\n", ast->fValue.uAst);
      /* subtree from []*/
      /* If the byte at the data pointer is zero, jump it forward to the command after the matching ] command*. */
      /* if the byte at the data pointer is nonzero, jump it back to the command after the matching [ command*. */
      while(*data){
        run(ast->fValue.uAst);
      }
    }
    ast = ast->fNext;
  };
}


int main(arg, argv){
  Ast* ast;
  char* tape;
  //tape = helloworld;
  tape = another;
  ast = parse(&tape);
  if(debug){
    printf("============================\n");
    print_ast(ast,0);
    printf("============================\n");
  }

  run(ast);
  return 0;
}
     

0 件のコメント: