BrainFuck compiler

brainfuck.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

/*
>   becomes     ++p;
<   becomes     --p;
+   becomes     ++*p;
-   becomes     --*p;
.   becomes     putchar(*p);
,   becomes     *p = getchar();
[   becomes     while (*p) {
]   becomes     }
*/

#define INCP '>'
#define DECP '<'
#define INCV '+'
#define DECV '-'
#define PUTC '.'
#define GETC ','
#define WHLA '['
#define WHLZ ']'
#define BF_LENGTH 1024

typedef struct BFInstruction {
    char type;
    struct BFInstruction *prev;
    struct BFInstruction *next;
} BFInstruction;

typedef struct BFProgram {
    BFInstruction *head;
    BFInstruction *tail;
    unsigned long instr_count;
    int error;
} BFProgram;

typedef struct BFState {
    char tape[BF_LENGTH];
    int tape_index;
    int tape_size;
} BFState;

BFProgram* bf_compile(FILE* fin)
{
    int cmd, bracket=0;
    BFProgram *prog = calloc(sizeof(BFProgram), 1);
    if (NULL==prog) return NULL;
    while ((cmd=fgetc(fin))!=EOF) {
        if (cmd != INCP && cmd != DECP &&
            cmd != INCV && cmd != DECV &&
            cmd != PUTC && cmd != GETC &&
            cmd != WHLA && cmd != WHLZ)
            continue;
        if (WHLA == cmd)
            ++bracket;
        else if (WHLZ == cmd && --bracket<0) {
            prog->error = 2; // unbalanced brackets
            return prog;
        }
        BFInstruction *bfi = calloc(sizeof(BFInstruction), 1);
        if (bfi == NULL) {
            prog->error = 1; // calloc error
            return prog;
        }
        bfi->type = cmd;
        if (prog->tail == NULL) {
            prog->head = prog->tail = bfi;
        } else {
            bfi->prev = prog->tail;
            prog->tail->next = bfi;
            prog->tail = bfi;
        }
    }
    if (bracket) prog->error = 2;
    return prog;
}

BFInstruction * _execute(BFProgram* prog, BFInstruction *start, BFState *stat)
{
    BFInstruction * i;
    while (NULL != start) {
        switch (start->type) {
            case INCP: assert(++stat->tape_index < stat->tape_size); break;
            case DECP: assert(--stat->tape_index > -1); break;
            case INCV: ++stat->tape[stat->tape_index]; break;
            case DECV: --stat->tape[stat->tape_index]; break;
            case GETC: stat->tape[stat->tape_index] = (char)getchar(); break;
            case PUTC: putchar(stat->tape[stat->tape_index]); break;
            case WHLA:
                while (stat->tape[stat->tape_index]) {
                    i = _execute(prog, start->next, stat); // i should be WHLZ
                }
                if (NULL == i) {
                    fprintf(stderr, "Unexpected EOF");
                    abort();
                }
                if (WHLZ != i->type) {
                    fprintf(stderr, "Unexpected cmd: %c\n", i->type);
                    abort();
                }
                start = i->next;
                continue;
            case WHLZ:
                return start; // return at ]
            default:
                fprintf(stderr, "Illegal cmd: %c\n", start->type);
                abort();
        }
        start = start->next;
    }
    return NULL;
}

int bf_execute(BFProgram *prog, BFState *stat)
{
    _execute(prog, prog->head, stat);
    return 0;
}

int bf_dump(BFProgram *prog, FILE* fout)
{
    if (NULL == prog) return -1;
    BFInstruction * i;
    i = prog->head;
    while (NULL != i) {
        fputc(i->type, fout);
        i = i->next;
    }
    return 0;
}

int main(int argc, char* argv[])
{
    if (argc<2) {
        fprintf(stderr, "Usage: %s file.bf\n", argv[0]);
        return 1;
    }
    FILE * fp = fopen(argv[1], "r");
    if (NULL == fp) {
        perror("fopen");
        return 2;
    }
    BFState bfs;
    BFProgram *prog;
    memset(&bfs, 0, sizeof(bfs));
    bfs.tape_size = BF_LENGTH;

    prog = bf_compile(fp);
    if (NULL == prog) {
        fprintf(stderr, "Cannot compile\n");
        return 1;
    }
    if (0 != prog->error) {
        fprintf(stderr, "compile error: %d\n", prog->error);
        return 2;
    }
    bf_dump(prog, stdout);
    printf("\n");
    bf_execute(prog, &bfs);
    printf("\n");
    return 0;
}