BrainFuck Interpreter

Hiho,

ich hatte gerade etwas Luft und bin da mal über BrainFuck gestolpert.
Dazu habe ich dann gleich mal einen Interpreter geschrieben.


	private int[] map;
	private int ptr;

	public BrainFuck() {

	}

	public void parse(String aCode) {
		
		map = new int[100];
		ptr = 0;
		
		parseBF(aCode);
	}
	
	private void parseBF(String aCode) {

		char[] code = aCode.toCharArray();
		int pos = 0;

		while (pos < code.length) {

			switch (code[aPos]) {

				case '+' : { map[ptr]++; break;	}
				case '-' : { map[ptr]--; break;	}
				case '>' : { ptr++;	break; }
				case '<' : { ptr--;	break; }
				case '.' : { System.out.print((char)map[ptr]); break; }
				case ',' : { readInput(); break; }
				case '[' : { pos += runLoop(getLoopCode(aCode, pos)); break; }
			}
			pos++;
		}
	}

	private void readInput() {

		try {
			BufferedReader bin = new BufferedReader(new InputStreamReader(
					System.in));

			System.out.println("Input: ");
			map[ptr] = Integer.parseInt(bin.readLine());
		}
		catch (Exception ex) {

			ex.printStackTrace();
			System.exit(1);
		}
	}

	private String getLoopCode(String aCode, int aPos) {

		String erg = aCode.substring(aPos);

		erg = erg.substring(1, erg.indexOf(']'));

		return erg;
	}

	private int runLoop(String aCode) {

		while (map[ptr] != 0) {

			parseBF(aCode);
		}
		
		return aCode.length() + 1;
	}
}```

Verwendung:

BrainFuck bf = new BrainFuck();

bf.parse("++++++++++[>+++++++>++++++++++>++++++++++++>+<<<<-]>++++.>—.>–.<.>>.");

bf.parse("++++++++++[>+++++++>++++++++++>+++>+<<<<-]"
+">++.>+.+++++++…+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.");


Das gibt einmal "Java" und einmal "Hello World!" aus.

Known Bugs: keine Unterstützung für geschachtelte Schleifen.

Nuja vielleicht braucht es mal jemand! :D

bye Saxony

Jetzt fehlen noch Cow 99 Bottles of Beer | Language Cow und Whitespace 99 Bottles of Beer | Language Whitespace :smiley: Und… wenn du es schaffst, einen Interpreter für Shakespeare 99 Bottles of Beer | Language Shakespeare zu schreiben: Respekt :stuck_out_tongue_winking_eye:

Hiho,

ich habe nun mal BrainFuck um Funtionen erweitert:

bf.parse("F1([-]>[-]>[-]<<++++++++++[>+++++++>+++++<<-]>.>-.)F1()F1()F1()");

Die Funtion F1 gibt ihren Namen aus. Das BF Programm gibt also dreimal F1 aus.

bf.parse("F1(>+++++<)F2(>>+++++++<<)main(++++++++++[F1()F2()-]>.>.)main()");

Diese Progg gibt 2F aus. :wink:

bf.parse("mul2(>++[<[>>++<<-]>-]>.)main(+++++mul2())main()");

Multipliziert Zelle 1 mit 2. In diesem Beispiel kommt also 10 raus!

Das mit Cow und WhiteSpaces ist auch recht interessant. Ebenso Ook - was aber im Endeffekt nur eine Substitution des BF Syntaxes ist.

Shakespeare wird bestimmt zu aufwändig um es mal in der KaffeePause zu machen - da war der BF Interpreter ja der reinste Kindergeburtstag! :slight_smile:

[edit]
Das Dumme ist nur, dass ich leider kein BrainFuck kann. Meine BF Codes sind alles Abwandlungen des Hello World Beispieles von Wikipedia. Wer den Interpreter also mal ordentlich testen will, sollte dies tun - und FeedBack geben! :slight_smile:
[/edit]

bye Saxony

An einem Cow-Interpreter sitze ich gerade(nachdem Hinweis von Marco13), hab gestern mal angefangen aber zu wenig Zeit gehabt da wirklich was zu erreichen. Parser hab ich schon, der executer fehlt noch. Werde mal schauen wann ich die Tage nochmal Zeit finde weiter zu machen. :slight_smile:

Gut Schuß
VuuRWerK :wink:

Edit: Shakespeare hab ich mir auch mal angeschaut, dafür aber einen Interpreter zu schreiben wäre sehr aufwändig. Sollte ich das mit Cow auf die Reihe bekommen, werde ich mir auch mal Whitespace anschauen, das ist ebenfalls sehr spaßig. Allerdings hat der Erfinder von Whitespace seine VM und Interpreter in Haskell geschrieben … :o)

Hiho,

neben geschachtelten Schleifen beherrscht mein BF Interpreter nun auch Rekursion:

bf.parse("rekursion([->+<rekursion()])main(+++++rekursion()>.)main()");

Das Beispiel oben in Pseudocode:


rekursion() {
    if(zelle1 != 0) {

        zelle1--;
        zelle2++;
        rekursion();
    }
}

main() {

    zelle1 = 5;
    rekursion();
    print(zelle2);
}

Langsam erschließt sich mir BF. :slight_smile:

Leider ist der Interpreter immer noch knapp 150 Zeilen lang - mal schauen was da noch geht!

bye Saxony

Hiho,

nuja wer es mal braucht, hier der Code von meinem BF Interpreter. Erweitert um Funktionen mit Rekursion und geschachtelten Schleifen/Funktionen.

Mit etwa 120 Zeilen auch einigermaßen schlank. :wink:

public class BrainFuck {

	private int[] map;
	private int ptr;
	private boolean run;
	private HashMap<String, String> functions;

	public void parse(String aCode) {
		
		functions = new HashMap<String, String>();
		map = new int[30000];
		ptr = 0;
		run = false;
		parseCode(aCode);
	}
	
	private void parseCode(String aCode) {

		char[] code = aCode.toCharArray();		
		int pos = -1;

		while (++pos < code.length) {

			switch (code[pos]) {

				case '+' : { ++map[ptr]; break;	}
				case '-' : { --map[ptr]; break;	}
				case '>' : { ++ptr;	break; }
				case '<' : { --ptr;	break; }
				case '.' : { System.out.print((char)map[ptr]); break; }
				case ',' : { readInput(); break; }
				case '[' : { pos += runLoop(getLoopCode(aCode, pos));	break; }
				default : { pos += runFunction(getFunctionCode(aCode, pos)); break; }
			}
		}
	}

	private void readInput() {

		try {
			BufferedReader bin = new BufferedReader(new InputStreamReader(
					System.in));

			System.out.println("Input: ");
			map[ptr] = Integer.parseInt(bin.readLine());
		}
		catch (Exception ex) {

			ex.printStackTrace();
			System.exit(1);
		}
	}

	private String getFunctionCode(String aCode, int aPos) {

		run = false;		
		String erg = aCode.substring(aPos);
		String name = erg.substring(0, erg.indexOf('('));
		
		if(functions.containsKey(name)) {
			
			run = true;			
			return name;
		}
		
		String code = getInlineCode(erg.substring(name.length()), '(', ')');				
		functions.put(name, code);

		return name;
	}
	
	private String getLoopCode(String aCode, int aPos) {

		return getInlineCode(aCode.substring(aPos), '[', ']');
	}
	
	private int runFunction(String aName) {
		
		String code = functions.get(aName);
		
		if (run) {
			
			parseCode(code);			
			return aName.length() + 1;
		}
		
		return code.length() + aName.length() + 1;
	}
	
	private int runLoop(String aCode) {

		while (map[ptr] != 0) {

			parseCode(aCode);
		}
		
		return aCode.length() + 1;
	}
	
	private String getInlineCode(String aCode, char aOpen, char aClose) {
		
		int cOpen = 1, cClose = 0, closePos = 0;
		char[] findEnd = aCode.substring(aCode.indexOf(aOpen) + 1).toCharArray();
		
		while(cOpen != cClose) {
			
			if(findEnd[closePos] == aOpen) cOpen++;
			if(findEnd[closePos] == aClose) cClose++;
			closePos++;
		}
		
		return aCode.substring(1, closePos);
	}
}

bye Saxony

Hiho,

ich habe nun mal den Interpreter noch um ein paar Optimierungen erweitert.

Folgen von Befehlen bewirken nun einmalige Aktionen und nicht immer ±1.

++++ Addiert nun 4 zur aktuellen Zelle und nicht +1+1+1+1

Schiebt den Zeiger nun um 4 Werte nach vorn und nicht +1+1+1+1
analoges für - und <.

Zusätzlich wird die Schleife [-] nun direkt als Nullstzung der aktuellen Zelle optimiert. Steht in der aktuellen Zelle nämlich 1000 wird 1000 -1 geloopt - nuja nun nicht mehr. Zellen auf null setzen dauert nun immer gleich lange egal welcher Inhalt sich darin befindet. :wink:

private void parseCode(String aCode) {

		char[] code = aCode.toCharArray();		
		int pos = -1;

		while (++pos < code.length) {

			switch (code[pos]) {

				case '+' : { pos += optimizeCode(aCode, pos, '+'); break; }
				case '-' : { pos += optimizeCode(aCode, pos, '-'); break; }
				case '>' : { pos += optimizeCode(aCode, pos, '>'); break; }
				case '<' : { pos += optimizeCode(aCode, pos, '<'); break; }
				case '.' : { System.out.print((char)map[ptr]); break; }
				case ',' : { readInput(); break; }
				case '[' : { pos += runLoop(getLoopCode(aCode, pos));	break; }
				default : { pos += runFunction(getFunctionCode(aCode, pos)); break; }
			}
		}
	}

private int runLoop(String aCode) {

		if ("-".equals(aCode)) { map[ptr] = 0; return 2; }
		
		while (map[ptr] != 0) {

			parseCode(aCode);
		}
		
		return aCode.length() + 1;
	}

private int optimizeCode(String aCode, int aPos, char aCmd) {
		
		char[] code = aCode.substring(aPos).toCharArray();
		int i = 0;
		
		while((++i < code.length) && (code** == aCmd)) {}
		
		switch (aCmd) {
			
			case '+' : { map[ptr] += i; break; }
			case '-' : { map[ptr] -= i; break; }
			case '>' : { ptr += i; break; }
			case '<' : { ptr -= i; break; }
		}
		
		return --i;
	}

bye Saxony

Hiho,

ich habe den BF Interpreter nun soweit folgendes zu fressen :slight_smile:

/ My First BrainFuck Programm /

/ prints Hello World to StdOut /
print_Hello_World (
	
	/ Fill the cells /
	++++++++++[>+++++++>++++++++++>+++>+<<<<-]
	/ Print out the cells /
	>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.
)

/ define Main /
main (

	/ Run the Hello World Function /
	print_Hello_World()
)

/ Run main /
main()

Hmm hier im Forum fehlen BF-Code-Tags! :wink:

Hierfür war genau ein Zeile zusätzlich nötig:

parseCode(aCode.replaceAll("\\s", "").replaceAll("[/]{1}[^/]*[/]{1}", ""));

Naja auf dem Stand (~150 Zeilen) lass ich den Interpreter nun erst einmal und kümmer mich nun um Zufallssprachen Generierung.

Dinge die mir noch einfallen würden:

import von anderen .bf SourceFiles
Methoden mit „Parameter“

#otherCode.bf


add_5_to_cell(

	+++++
)

main(

	add_5_to_cell(<<<)
	/ run function from otherCode.bf /
	defined_in_otherCode()
)

[edit]
Vielleicht aber noch ne klitzekleine IDE dazu. Schau mer mal! :wink:
[/edit]

bye Saxony

Ich nutz den Thread mal, um auf meinen BrainFucker aufmerksam zu machen :smiley:

Den Source für den Interpreter kann ich auch zur Verfügung stellen. Müsst ich aber auch erst raussuchen und ist imho nicht ganz so schön, wie der von Saxony :frowning: .