# brainf*** interpreter/compiler

• (2 Pages)
• 1
• 2

## 28 Replies - 16482 Views - Last Post: 26 July 2013 - 09:39 AM

### #1 ishkabible

• spelling expret

Reputation: 1611
• Posts: 5,696
• Joined: 03-August 09

# brainf*** interpreter/compiler

Posted 21 March 2012 - 04:45 PM

So the challenge here is to create a program that allows brainfuck code to be run. Brainfuck is an esoteric programming language designed to be very small.

There are only 8 characters in the language. Each operates on a 'tape' or sequence of integers, usually with 30000 units allocated all set to zero.

Say 'p' is a char* pointing to sequence of N bytes all set to zero. The characters of the language do the following.

">": would be ++p it would increment the current location in the sequence
"<": would be --p the exact opposite of the above
"+": would be ++*p which would increment the value stored at the current location
"-": would be --*p which would decrement the value stored at the current location
".": would be putchar(*p) which would print the current character
",": would be *p = getchar() which would read in data from the input stream
"[": would be kinda like the beginning of a while loop, like while(*p) { it has to be matched by a "]" character that ends the loop.
"]": would be like the closing brace of a loop } so that it must be matched with "[" before it

There are many ways to implement this. You could interpret it pretty easily. You could translate it to another language like C or C++ and use that to compile it. You could make a full fledged compiler or JIT the code even!

It would be neat to add extensions to the language even. Esolang has a whole category for brainfuck derivatives, here.

I'm eager to see what you create

edit:
also, If you would like to check your work against another interpreter, Curtis Rutland wrote this a while back for his C# brainf*** challenge.

there are also a number of interesting scripts here to work with including a quine(prints it's own source code), a prime number sieve, and 99 bottles of bear on the wall.

This post has been edited by ishkabible: 21 March 2012 - 05:00 PM

Is This A Good Question/Topic? 3

## Replies To: brainf*** interpreter/compiler

### #2 cfoley

• Cabbage

Reputation: 1889
• Posts: 3,912
• Joined: 11-December 07

## Re: brainf*** interpreter/compiler

Posted 21 March 2012 - 05:27 PM

Not C or C++ but I did write a brainfuck to VB.NET translator in Java:
http://www.dreaminco...5&#entry1447115

### #3 ishkabible

• spelling expret

Reputation: 1611
• Posts: 5,696
• Joined: 03-August 09

## Re: brainf*** interpreter/compiler

Posted 21 March 2012 - 05:55 PM

cool! Im going to go work on a C++ JITed compiler for Windows I have one in C but it's pretty bad code; I really want to re-work it.

This post has been edited by ishkabible: 21 March 2012 - 05:56 PM

• MrCupOfT

Reputation: 2197
• Posts: 9,286
• Joined: 29-May 08

## Re: brainf*** interpreter/compiler

Posted 21 March 2012 - 06:18 PM

BF -> Directly Convert BF to C++ -> Compile that C++ -> Run

Treat C++ as the Intermediate Language.

### #5 ishkabible

• spelling expret

Reputation: 1611
• Posts: 5,696
• Joined: 03-August 09

## Re: brainf*** interpreter/compiler

Posted 21 March 2012 - 06:33 PM

then it's not JITed I'm going to use the Win32 VirtualAlloc function to allocate a block of executable memory and fill it with x86 code then cast that to a function and call it.

If there is a posix function that allows you to allocate executable memory then It will be dirt easy to make this cross platform.

This post has been edited by ishkabible: 21 March 2012 - 06:34 PM

### #6 cfoley

• Cabbage

Reputation: 1889
• Posts: 3,912
• Joined: 11-December 07

## Re: brainf*** interpreter/compiler

Posted 21 March 2012 - 08:30 PM

OK, here is my effort. It's a bit crude but I'm pleased with it. I've hardly used C before, rarely used BASH and never used sed.

I'm open to suggestions for improvement, especially on initialising the array (if anyone wants to dig through the mass of characters!)

#!/bin/bash

cat $1 | sed -e 's/[^][\.,<+>-]//g' \ -e 's/+/++*p; /g' \ -e 's/-/--*p; /g' \ -e 's/>/++p; /g' \ -e 's/</--p; /g' \ -e 's/\./putchar(*p); /g' \ -e 's/,/*p = getchar(); /g' \ -e 's/\[/while(*p) { /g' \ -e 's/]/} /g' \ -e '1i\#include <stdio.h>' \ -e '1i\#include <stdlib.h>' \ -e '1i\int main() {' \ -e '1i\char *p; p = (char *)malloc(30000 * sizeof(char)); ' \ -e '1i\char *j; int i; j=p; for(i=0; i < 30000; i++) {*j = 0; ++j;} ' \ -e '$a\free(p); return 0;}' \
| gcc -x c -o runner.o -
runner.o
rm runner.o


### #7 ishkabible

• spelling expret

Reputation: 1611
• Posts: 5,696
• Joined: 03-August 09

## Re: brainf*** interpreter/compiler

Posted 21 March 2012 - 09:25 PM

Ha! That's pretty good. a compiler in bash using sed and gcc Im not very familiar with sed or bash either unfortunately but that was a preety good idea!

in the for loop you *could* move that '++j' at the end to be next to the 'i++' like so

for(i=0; i < 30000; ++i, ++j)


but that's not necessary.

### #8 cfoley

• Cabbage

Reputation: 1889
• Posts: 3,912
• Joined: 11-December 07

## Re: brainf*** interpreter/compiler

Posted 22 March 2012 - 04:04 AM

mmm that would save a bit, but I was thinking more along the lines of a shortcut for setting all the bits in a block of memory to zero. Is that always done explicitly with a loop in C?

### #9 CodeGrappler

Reputation: 41
• Posts: 120
• Joined: 29-November 10

## Re: brainf*** interpreter/compiler

Posted 22 March 2012 - 07:37 AM

cfoley, on 22 March 2012 - 04:04 AM, said:

mmm that would save a bit, but I was thinking more along the lines of a shortcut for setting all the bits in a block of memory to zero. Is that always done explicitly with a loop in C?

Generally you would use memset

### #10 baavgai

• Dreaming Coder

Reputation: 5557
• Posts: 12,249
• Joined: 16-October 07

## Re: brainf*** interpreter/compiler

Posted 22 March 2012 - 08:21 AM

cfoley, on 21 March 2012 - 10:30 PM, said:

OK, here is my effort.

I love it! I'd avoid the malloc. My first riff on what you have is this:
#!/bin/bash

#test: echo '++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.-/>-------.>+.>.' | ./bf2.bash

EXE=./runner.o

toBf() {
BUFF_SIZE=30000
cat << EOT
#include <stdio.h>
#include <stdlib.h>
int main() {
int i;
char buff[$BUFF_SIZE]; char *p = buff; for(i=0; i<$BUFF_SIZE; i++) { buff[i]=0; }
EOT
echo $LINE | sed -e 's/[^][\.,<+>-]//g' \ -e 's/+/++*p; /g' \ -e 's/-/--*p; /g' \ -e 's/>/++p; /g' \ -e 's/</--p; /g' \ -e 's/\./putchar(*p); /g' \ -e 's/,/*p = getchar(); /g' \ -e 's/\[/while(*p) { /g' \ -e 's/]/} /g' done echo -e "\treturn 0;\n}\n\n" } toBf | gcc -x c -o$EXE -
$EXE rm$EXE



I want to optimize the C code it a little, but it doesn't look like sed will let me do it. However, awk would work...

### #11 vividexstance

• D.I.C Lover

Reputation: 629
• Posts: 2,103
• Joined: 31-December 10

## Re: brainf*** interpreter/compiler

Posted 22 March 2012 - 09:18 AM

CodeGrappler, on 22 March 2012 - 10:37 AM, said:

cfoley, on 22 March 2012 - 04:04 AM, said:

mmm that would save a bit, but I was thinking more along the lines of a shortcut for setting all the bits in a block of memory to zero. Is that always done explicitly with a loop in C?

Generally you would use memset

Actually, no matter what the size of the array, if it's statically allocated you can set all elements to zero using an initializer list with 1 element:
#include <stdio.h>

#define MAX 100

int main(void)
{
int a[MAX] = { 0 };
int i;

for(i = 0; i < MAX; ++i)
printf("a[%d] = %d\n", i, a[i]);

return 0;
}



The output is the whole array with each element set to zero. Note that this only works for setting it to zero, so you couldn't use this to initialize the array with a different number.
This also works in C++. IMO this is better than making a call to memset.

This post has been edited by vividexstance: 22 March 2012 - 09:20 AM

### #12 baavgai

• Dreaming Coder

Reputation: 5557
• Posts: 12,249
• Joined: 16-October 07

## Re: brainf*** interpreter/compiler

Posted 22 March 2012 - 09:49 AM

Damn... What a bloody time sink.

Right, I figured I didn't need sed:
#!/bin/bash

EXE=./runner.o

#test: echo '++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.-/>-------.>+.>.' | ./bf2.bash

toBf() {
BUFF_SIZE=30000
cat << EOT
#include <stdio.h>
#include <stdlib.h>
int main() {
int i;
char buff[$BUFF_SIZE]; char *p = buff; for(i=0; i<$BUFF_SIZE; i++) { buff[i]=0; }
EOT
while IFS= read -r -n1 c; do
if [ "$c" == "+" ]; then echo -n "++*p; " elif [ "$c" == "-" ]; then
echo -n "--*p; "
elif [ "$c" == ">" ]; then echo -n "++p; " elif [ "$c" == "<" ]; then
echo -n "--p; "
elif [ "$c" == "." ]; then echo -n "putchar(*p); " elif [ "$c" == "," ]; then
echo -n "*p = getchar(); "
elif [ "$c" == "[" ]; then echo -n "while(*p) { " elif [ "$c" == "]" ]; then
echo -n "}"
fi
done
echo -e "\treturn 0;\n}\n\n"
}
toBf | gcc -x c -o $EXE -$EXE
rm $EXE  And, for optimizing, I worked up a repetition counter: #!/bin/bash EXE=./runner.o #test: echo '++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.-/>-------.>+.>.' | ./bf4.bash opForChar() { if [ "$#" -eq "2" ] && [ "$2" -gt "0" ]; then local c=$1
local reps=$2 if [ "$c" == "+" ]; then
echo -n "*p+=$reps;" elif [ "$c" == "-" ]; then
echo -n "*p-=$reps;" elif [ "$c" == ">" ]; then
echo -n "p+=$reps;" elif [ "$c" == "<" ]; then
echo -n "p-=$reps;" elif [ "$c" == "." ]; then
echo -n "pc(*p, $reps);" elif [ "$c" == "," ]; then
echo -n "*p = getchar();"
elif [ "$c" == "[" ]; then echo -e "\nwhile(*p) { " opForChar$c expr $reps - 1 elif [ "$c" == "]" ]; then
echo -e "\n}"
opForChar $c expr$reps - 1
fi
fi
}

toBf() {
BUFF_SIZE=30000
cat << EOT
#include <stdio.h>
#include <stdlib.h>
void pc(char ch, int n) { while(n-- > 0) { putchar(ch); } }
int main() {
char *p, buff[$BUFF_SIZE]; for(p = buff +$BUFF_SIZE - 1; p!=buff; p--) { *p=0; }
*p = 0;
EOT

LAST_CHAR='X'
CHAR_COUNT=0
while IFS= read -r -n1 c; do
if [ "$c" == "$LAST_CHAR" ]; then
CHAR_COUNT=expr $CHAR_COUNT + 1 else opForChar$LAST_CHAR $CHAR_COUNT LAST_CHAR=$c
CHAR_COUNT=1
fi
done
opForChar $LAST_CHAR$CHAR_COUNT
echo -e "\n\treturn 0;\n}\n\n"
}

toBf | gcc -x c -o $EXE -$EXE
rm \$EXE



I also took the i out, just because it was silly to do so.

### #13 CodeGrappler

Reputation: 41
• Posts: 120
• Joined: 29-November 10

## Re: brainf*** interpreter/compiler

Posted 22 March 2012 - 10:48 AM

vividexstance, on 22 March 2012 - 09:18 AM, said:

CodeGrappler, on 22 March 2012 - 10:37 AM, said:

cfoley, on 22 March 2012 - 04:04 AM, said:

mmm that would save a bit, but I was thinking more along the lines of a shortcut for setting all the bits in a block of memory to zero. Is that always done explicitly with a loop in C?

Generally you would use memset

Actually, no matter what the size of the array, if it's statically allocated you can set all elements to zero using an initializer list with 1 element:

*SNIP*

The output is the whole array with each element set to zero. Note that this only works for setting it to zero, so you couldn't use this to initialize the array with a different number.
This also works in C++. IMO this is better than making a call to memset.

I agree for a statically sized array. I should have said that instead of memset but hey.. it's a long road ahead.

### #14 ishkabible

• spelling expret

Reputation: 1611
• Posts: 5,696
• Joined: 03-August 09

## Re: brainf*** interpreter/compiler

Posted 22 March 2012 - 01:22 PM

Ok, my front end and interpreter are done; now for the challenge, a JITed backed.

### #15 Dogstopper

Reputation: 2843
• Posts: 10,919
• Joined: 15-July 08

## Re: brainf*** interpreter/compiler

Posted 23 March 2012 - 07:51 PM

I have an interpreter and compiler here on DIC, but I also wrote them in C#:
http://www.dreaminco...snippet6122.htm
http://www.dreaminco...snippet6121.htm