Programmation Brainfuck/Compilateurs et interpréteurs

Un livre de Wikilivres.
Aller à la navigation Aller à la recherche


Compilation en C[modifier | modifier le wikicode]

Les programmes Brainfuck peuvent être traduits en C en utilisant les substitutions suivantes, en considérant que ptr est du type char*:

Brainfuck C
> ++ptr;
< --ptr;
+ ++*ptr;
- --*ptr;
. putchar(*ptr);
, *ptr = getchar();
[ while (*ptr) {
] }

Le programme en C ci-dessous génère un code source en C à partir d'un programme source en Brainfuck. Cependant, le programme généré a une limite de taille mémoire, et le débordement de pointeur n'est pas vérifié.

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

#define DEFAULT_DATA_SIZE 1024

void printHeader(unsigned int data_size)
{
	printf("#include <stdio.h>\n");
	printf("#include <stdlib.h>\n\n");
	printf("unsigned char octets[%d];\n", data_size);
	printf("unsigned char *ptr;\n\n");
	printf("int main()\n");
	printf("{\n");
	printf("\tptr = octets + %d;\n", data_size/2); /* Pointeur au milieu */
	return;
}

void printFooter()
{
	printf("\n\treturn 0;\n}\n");
	return;
}

int main()
{
	unsigned int data_size = DEFAULT_DATA_SIZE;
	int c;
	printHeader(data_size);
	while ((c = getchar()) != EOF)
	{
		switch(c)
		{
			case '>': printf("\tptr++;\n"); break;
			case '<': printf("\tptr--;\n"); break;
			case '+': printf("\t(*ptr)++;\n"); break;
			case '-': printf("\t(*ptr)--;\n"); break;
			case '.': printf("\tputchar(*ptr);\n"); break;
			case ',': printf("\t*ptr = getchar();\n"); break;
			case '[': printf("\twhile (*ptr)\n{\n"); break;
			case ']': printf("\t}\n"); break;
		}
	}
	printFooter();
	return 0;
}

Interpréteur en Javascript[modifier | modifier le wikicode]

Le code source ci-dessous est un interpréteur du langage Brainfuck. Il effectue une précompilation facilitant l'interprétation du code, en particulier pour les sauts d'instruction pour éviter de rechercher le caractère crochet correspondant. Il a la particularité d'autoriser tous les mouvements de pointeur de données, en allouant et décalant le buffer de données quand nécessaire. La seule limite étant la capacité mémoire du système.

function SyntaxErrorException(message, index)
{
   this.message = message;
   this.index = index;
}

class Brainfuck
{
	// Runtime data and input
	bf_data = []; // Data area
	bf_index = 0; // Data pointer
	ip = 0;       // Instruction Pointer (IP)
	input=[];     // Input data
	o_in = 0;     // Offset in input buffer

	// Compilation
	target_ip = []; // Target IP for [ and ]
	prog = '';      // Current program

	constructor(prog, input)
	{
		if (input!==undefined) this.input = input;
		this.compile(prog);
	}
	resetinput()
	{
		this.input = []
		this.o_in = 0
	}
	addinput(input)
	{
		if (input!==undefined && input!==null)
		{
			if (Array.isArray(input))
				this.input = this.input.concat(input)
			else if (typeof(input)==='number')
				this.input = this.input.concat([input])
			else if (typeof(input)==='string')
				this.input = this.input.concat(Object.assign([], input).map(v=>v.charCodeAt(0)))
		}
	}
	compile(prog)
	{
		this.ip = 0;
		this.prog = prog;
		var stack = [];
		var target_ip = [];
		for(var i=0;i<prog.length;i++)
		{
			var c = prog.charAt(i);
			switch(c)
			{
				case '[': stack.push(i); break;
				case ']':
					if (stack.length<=0) throw new SyntaxErrorException("ERROR ]", i);
					var n = stack.pop();
					target_ip[i] = n+1;
					target_ip[n] = i+1;
					break;
				default: target_ip[i] = 0;
			}
		}
		if (stack.length>0) throw new SyntaxErrorException("ERROR [", i);
		this.target_ip = target_ip;
	}
	reset()
	{
		this.bf_data=[];
		this.bf_index=0;
		this.ip = 0;
	}
	make()
	{
		if (this.bf_index<0)
		{
			let ar = [];
			while (this.bf_index<0) { ar.push(0); this.bf_index++; }
			this.bf_data = ar.concat(this.bf_data);
		}
		else if (this.bf_index>=this.bf_data.length)
		{
			while (this.bf_index>=this.bf_data.length) this.bf_data.push(0);
		}
	}
	get current()
	{
		this.make();
		return this.bf_data[this.bf_index];
	}
	set current(value)
	{
		this.make();
		this.bf_data[this.bf_index] = value;
	}
	execute(maxsteps)
	{
		if (maxsteps===undefined) maxsteps = 10000;
		var output = [];
		var ip = this.ip;
		var target_ip = this.target_ip;
		var prog = this.prog
		while (ip<prog.length)
		{
			if (--maxsteps<0) break;
			var c = prog.charAt(ip++);
			switch(c)
			{
			case '[': if (this.current==0) ip=target_ip[ip-1]; break;
			case ']': if (this.current!=0) ip=target_ip[ip-1]; break;
			case '+': this.current = this.current + 1; break;
			case '-': this.current = this.current - 1; break;
			case '>': this.bf_index++; break;
			case '<': this.bf_index--; break;
			case ',': this.current = (this.o_in>=this.input.length) ? 0 : this.input[this.o_in++]; break;
			case '.': output.push(this.current); break;
			default: // ignore comment
			}
		}
		this.ip = ip;
		return output;
	}
	// Retourne la sortie sous forme d'une chaîne de caractères.
	run(maxsteps)
	{
		return this.execute(maxsteps).map(v => String.fromCharCode(v)).join('')
	}
	// Retourne la sortie sous forme d'un tableau de nombres.
	runnum(maxsteps)
	{
		return this.execute(maxsteps)
	}
}

L'exemple ci-dessous montre comment utiliser la classe :

new Brainfuck('++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.').run()
// Retourne "Hello World!\n"

L'interpréteur permet de spécifier les données à lire, soit au constructeur, soit au fur et à mesure par exécution pas à pas :

// Boucle de 4 itérations (7 instructions par itération + 5 initiales)
var prog = new Brainfuck('++++[>,+.<-]');

prog.addinput([10,40]);
res = prog.runnum(19); // les 2 premières itérations
// Tableau de résultat : [11,41]

prog.addinput(20);
res = res.concat(prog.runnum(7)); // itération suivante
// Tableau de résultat : [11,41,21]

prog.addinput(50);
res = res.concat(prog.runnum(7)); // itération suivante
// Tableau de résultat : [11,41,21,51]

prog.addinput(90);
res = res.concat(prog.runnum(7)); // itération suivante ?
// Tableau de résultat : [11,41,21,51] inchangé car les 4 itérations sont passées.

prog.reset();      // Remise à zéro de l'exécution
res = res.concat(prog.runnum(12)); // initialisation et première itération
// Tableau de résultat : [11,41,21,51,91]

Optimisations[modifier | modifier le wikicode]

Certaines optimisations sont possibles :

  • Regrouper plusieurs instructions d'incrémentation ou décrémentation + - en une instruction de synthèse ajoutant directement la valeur voulue,
  • Même principe pour les instructions de déplacement du pointeur de données < >,
  • Supprimer certaines séquences d'instructions qui s'annulent :
    • +-
    • <>
    • ...
  • Pré-calculer la position du crochet correspondant de chaque paire de la boucle (comme dans l'interpréteur en Javascript de la section précédente),
  • Pour un interpréteur : retirer tous les caractères ignorés (commentaire),
  • ...