Building a simple Brainfuck Interpreter in C

Brainfuck is a Turing-complete language that isn't necessary designed for productive usage :)

However it is actually great to understand C pointers.

An Interpreter is a computer program that directly executes instructions.

 

 

How does Brainfuck work?

Imagine Brainfuck as an endless tape of 1 byte cells that are initialized with 0.

[0][0][0][0][0][0][0][0]

 ^

1. The ^ represents our pointer. We can move the pointer with >  (right) or  < (left)

>>  (2 cells to the right)

[0][0][0][0][0][0][0][0]

        ^

2. If we want to change the value of the cell we can use + or -

+++++++++++++++++++++++++++++++++++ (increment 35 times)

[0][0][35][0][0][0][0][0]

           ^

3. We can print an ASCII character with .

.

Output: #

.(Explanation: The corresponding ASCII character for the value of 35 is #)

 

4. We can read an ASCII charcacter with ,

>,

[0][0][35][0][0][0][0][0]

                 ^

Input: <Any ASCII character>

It will write the value of any ASCII character into that cell. For example if we input 6 it will write 54 into that cell.

[0][0][35][56][0][0][0][0]

                  ^

5. Loops are a bit tricky.

[ : If the value at the cell, where our pointer currently points to, is 0 - then skip to corresponding  ] . Otherwise execute the next instruction.

] : If the value at the cell, where our pointer currently points to, is NOT 0 - then go back to corresponding  [ . Otherwise execute the next instruction.

 

 

Writing the C program

I will use C99 and the QTCreator with MinGW 32.

 

1. First let's scaffold the structure:

 

We need the instruction itself and the length of the instruction. Nothing fancy.

 

2. Creating our tape of zeros and the first pointer:

 

I use calloc(), because calloc() zero-initializes the buffer, while malloc() leaves the memory uninitialized. Each cell has a size of 1byte.

Note that you could write char * ptr = tape since this would point to the first cell, too.

With free() we are releasing the memory again, because we don't need it anymore.

 

3. Creating pointer movement

 

We basicly need to read the instruction one by one until we reach the end.

The end of a C string is indicated with a null terminator '\0'.

 

4. Adding incrementation / decrementation of cells

 

The operator * tells us to dereference a pointer (wherever it currently points to). Another word would be indirection. Maybe you didn't notice, but we already used it at *instruction

 

5. Input / Output

 

Print the current value of the cell (with printf()) as an ASCII character. With getchar() we read user input and save the value  (ASCII value!) into the current cell.

Note: Instead of printf() you could use putchar().

 

6. Loops

 

Now things get hairy! I find it really easy if you just stick to the loop definitions and try to implement them word by word.

Let's start with [:

if (!*ptr) this is actually a short writing for if(*ptr == 0).

Ok, the value of the current cell is not 0, so skip (++instruction) until (while (loop_cnt  != 0)) you find the correspoding ] ( if (*instruction == ']')).

I've used loop_cnt because loops can be nested!

Now ] is simply the same, but we have to look if(*ptr != 0) (see definition!) and go back to (--instruction). 

 

7. Testing our solution:

 

Output:

 

 

Sweet!

Now you could go further and implement error handling such as bounds check, balance checking (for the loops) and printing out where you have a mistake in your brainfuck syntax.

 



Mahmut Jomaa is a Software Engineer from Germany.

Currently he attends university to gain more knowledge in Computer Science.


Security code Refresh