brainf*** interpreter/compiler

  • (2 Pages)
  • +
  • 1
  • 2

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

#1 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,710
  • Joined: 03-August 09

brainf*** interpreter/compiler

Post icon  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

For any confusions please see this Wikipedia page on the matter.

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  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2069
  • View blog
  • Posts: 4,307
  • 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
Was This Post Helpful? 1
  • +
  • -

#3 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,710
  • 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 :P 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

Was This Post Helpful? 0
  • +
  • -

#4 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2271
  • View blog
  • Posts: 9,499
  • 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.
Was This Post Helpful? 0
  • +
  • -

#5 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,710
  • Joined: 03-August 09

Re: brainf*** interpreter/compiler

Posted 21 March 2012 - 06:33 PM

then it's not JITed :P 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

Was This Post Helpful? 0
  • +
  • -

#6 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2069
  • View blog
  • Posts: 4,307
  • 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

Was This Post Helpful? 3
  • +
  • -

#7 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,710
  • 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 :P 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.
Was This Post Helpful? 1
  • +
  • -

#8 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2069
  • View blog
  • Posts: 4,307
  • 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?
Was This Post Helpful? 0
  • +
  • -

#9 CodeGrappler  Icon User is offline

  • D.I.C Head
  • member icon

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

Re: brainf*** interpreter/compiler

Posted 22 March 2012 - 07:37 AM

View Postcfoley, 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
Was This Post Helpful? 1
  • +
  • -

#10 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5931
  • View blog
  • Posts: 12,853
  • Joined: 16-October 07

Re: brainf*** interpreter/compiler

Posted 22 March 2012 - 08:21 AM

View Postcfoley, 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
	while read LINE; do
	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...
Was This Post Helpful? 0
  • +
  • -

#11 vividexstance  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 687
  • View blog
  • Posts: 2,376
  • Joined: 31-December 10

Re: brainf*** interpreter/compiler

Posted 22 March 2012 - 09:18 AM

View PostCodeGrappler, on 22 March 2012 - 10:37 AM, said:

View Postcfoley, 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

Was This Post Helpful? 3
  • +
  • -

#12 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5931
  • View blog
  • Posts: 12,853
  • Joined: 16-October 07

Re: brainf*** interpreter/compiler

Posted 22 March 2012 - 09:49 AM

Damn... What a bloody time sink. :P

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.
Was This Post Helpful? 3
  • +
  • -

#13 CodeGrappler  Icon User is offline

  • D.I.C Head
  • member icon

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

Re: brainf*** interpreter/compiler

Posted 22 March 2012 - 10:48 AM

View Postvividexstance, on 22 March 2012 - 09:18 AM, said:

View PostCodeGrappler, on 22 March 2012 - 10:37 AM, said:

View Postcfoley, 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.
Was This Post Helpful? 1
  • +
  • -

#14 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1623
  • View blog
  • Posts: 5,710
  • 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.
Was This Post Helpful? 1
  • +
  • -

#15 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2876
  • View blog
  • Posts: 11,051
  • 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
Was This Post Helpful? 1
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2