BrainFuck – Language Worthy The Name

Today we dive into the world of a programming language that still baffles every programmer despite being so easy. Yes! I am talking about BrainFuck (the programming language that can never be discussed in public). From the beginning, I should warn you that it has no practical use (yet) but could still be a great exercise into the world of parsing or computer science.

Despite being completely useless for programming, it was still fun to build the parser for the language. So in this article, I will guide you through the notations and mechanisms of BrainFuck.

Operations

BrainFuck only has 8 operations to deal with the programming world.

Operator Meaning
 +  Increase the value by 1 at current position (byte)
 –  Decrease the value by 1 at current position (byte)
 >  Increment the data pointer to point to next position (byte)
 < Decrement the data pointer to point to previous position (byte)
 ,  Input 1 byte of info and store at current position
 .  Output 1 byte of info stored at current position
 [  Looping Instruction – If current byte is not zero then execute the commands between the opening and closing braces otherwise skip.
 ]  Closing loop operator – if the value is not zero then go back to the matching opening braces and execute again.

Actually that’s all you need to build your own BrainFuck parser. Before we jump into the actual parser, I wish to show some examples of BrainFuck programs to better understand the parsing process.

Examples

Let’s just start with the easy ones and make our way up.

Printing from 10 to 1

++++++++++[.-]

The first ten + operations would result in 10 at position 1. Then the loop executes until it hits 0 which consists of printing the value and decrementing the value.

Multiplying 5 with 3

+++[>+++++<-]

The first three + operations would result in 3 at position 1. Then the loop executes until it hits 0. The loop move to the right one position and add 5 each time and then moves back and decrement the counter. The program would work assuming that each position has initially 0 as its value.

Printing “Hello World!”

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

Before we jump into the code, I want to show you the ASCII values of each character we are using.

Character ASCII Value
 H  72
 e  101
 l  108
 o  111
 W  87
 r  114
 d  100
 !  33

Wikipedia provides a good explanation to why this piece of code prints “Hello World!”.

Parsing

I will show you how to build the parser (if you haven’t figured it out by yourself yet) in psuedocode. I leave the implementations for your favorite language to you.

Building the world

The parser would work in a virtual world of sequential bits. So an array of integers would work for us.

Define Integer Array[100] world = {0}
Define String input = BrainFuck program
Define Integer length = input length
Define Integer position = 1

Define an array of size N (100 in my case) and initialize it with 0. Also input is the actual program we will be parsing. Position would be our pointer in the array.

Moving to the horizon

We will start at position 1 and move sequentially towards the end unless hit by a loop.

For i := 1 to length do

Handling the operators

// Handling the + operator
If input[i] = '+' Then
    // Increment the value at position
    world[position] := world[position] + 1
End If

// Handling the - operator
If input[i] = '-' Then
    // Decrement the value at position
    world[position] := world[position] - 1
End If

// Handling the > operator
If input[i] = '>' Then
    // Point to next position
    position := position + 1
End If

// Handling the < operator
If input[i] = '<' Then
    // Point to previous position
    position := position - 1
End If

// Handling the . operator
If input[i] = '.' Then
   Print world[position]
End If

// Handling the , operator
If input[i] = ',' Then
    // Take 1 byte input
    world[position] := 1 byte input
End If

// Handling the [ operator
If input[i] = '[' Then
    // handle the case when current value is zero
    If world[position] = 0 Then
        Move right until hits matching ] operator
    End If
End If

// Handling the ] operator
If input[i] = ']' Then
    // Handle the case when current value is not zero
    If world[position] != 0 Then
        Move left until hits matching [ operator
    End If
End If

Unfortunately neither one of us can publish this in our CV or even tell our friends. With this I bid farewell. Have a nice day!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s