What the Brainfuck !
Page web ISIMA
Documentation
Fichier .org source
Défi de programmation - What the Brainfuck !

1. Introduction
Le but de cet exercice est d’écrire un interpréteur pour le langage Brainfuck.
Brainfuck est un langage ésotérique, dans lequel on nous donne accès à un bloc mémoire (de taille donnée), un pointeur vers une adresse mémoire et des opérations de base suivantes :
Symbole | Action |
---|---|
> |
Incrémente la position du pointeur |
< |
Décrémente la position du pointeur |
+ |
Ajoute 1 à la case mémoire pointée |
- |
Enlève 1 à la case mémoire pointée |
. |
Affiche la valeur de la case pointée (en tant que caracère ASCII) |
, |
Prend un nombre entier en entrée et le stocke dans la case pointée |
[ |
Passe à l’instruction après le ] correspondant si la case pointée vaut 0 |
] |
Retourne à l’instruction après le [ correspondant si la case pointée ne vaut pas 0 |
Exemple de Hello world en Brainfuck :
++++++++++[>+++++++>++++++++++>+++<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.
2. Approche utilisée
2.1. Description synoptique
Mon approche a été simplement de parcourir les caractères du programme donné et d’en exécuter l’action correspondante.
2.2. Algorithme
Fonction eval
:
Prend en paramètre une program
à évaluer, les inputs
, la memory
du prorgramme et memSize
la taille de la mémoire.
i
, ptr
, in
: des entiers initialisés à 0
Tant que program[i] != ’\0’ :
- Si memory[ptr] < 0 ou memory[ptr] > 255 :
- Afficher « INCORRECT VALUE »
- Fin fonction
- Afficher « INCORRECT VALUE »
- Si ptr < 0 ou ptr >= memSize :
- Afficher « POINTER OUT OF BOUNDS »
- Fin fonction
- Afficher « POINTER OUT OF BOUNDS »
- Selon program[i] :
>
: Incrémentation de ptr<
: Décrémentation de ptr+
: Incrémentation de memory[ptr]-
: Décrémentation de memory[ptr].
: Afficher memory[ptr],
: memory[ptr] = inputs[in], incrémentation dein
[
: Si memory[ptr] = 0, alors incrémenter i jusqu’au ] correspondant]
: Si memory[ptr] != 0, alors décrémenter i jusqu’au [ correspondant
- Incrémenter i
Fonction principale :
program
, inputs
: paramètres donnés par l’exercice
memory
: liste d’entier de taille S
donnée
Si il n’y a pas autant de ’[’ que de ’]’ dans program
:
- Afficher « SYNTAX ERROR »
- Fin fonction
eval(program, inputs, memory, S)
3. Résolution
/** * @file brainfuck.c * @brief Résolution de Brainfuck * @author Rémi SCHIRRA * @version 1.0 * @date 14 avril 2024 */ #include <stdlib.h> #include <stdio.h> #include <string.h> /** * @brief Vérifie la syntaxe du programme donné * @param program Le programme à vérifier * @return 1 si la syntaxe des crochets n'est pas correcte, 0 sinon */ int syntaxCheck(char *program) { int balance = 0; int i = 0; while (program[i] != '\0') { if (program[i] == '[') ++balance; if (program[i] == ']') --balance; ++i; } return balance != 0; } /** * @brief Evalue le programme, pour chaque caractères, exécute l'action associée. * @param program Le programme à évaluer * @param inputs Les entrées utilisateur du programme * @param memory La mémoire du programme * @param memSize La taille de la mémoire */ void eval(char *program, int *inputs, int *memory, int memSize) { int i = 0, ptr = 0, in = 0; while (program[i] != '\0') { if (memory[ptr] < 0 || memory[ptr] > 255) { printf("INCORRECT VALUE"); return; } if (ptr < 0 || ptr >= memSize) { printf("POINTER OUT OF BOUNDS"); return; } switch (program[i]) { case '>': ++ptr; break; case '<': --ptr; break; case '+': ++memory[ptr]; break; case '-': --memory[ptr]; break; case '.': printf("%c", memory[ptr]); break; case ',': memory[ptr] = inputs[in]; ++in; break; case '[': if (memory[ptr] == 0) { int skips = 1; ++i; while (skips) { switch (program[i]) { case '[': ++skips; break; case ']': --skips; break; } ++i; } } break; case ']': if (memory[ptr] != 0) { int skips = 1; --i; while (skips) { switch (program[i]) { case ']': ++skips; break; case '[': --skips; break; } --i; } } break; } ++i; } } int main() { int L, S, N; int *memory, *inputs; char *program; scanf("%d%d%d", &L, &S, &N); fgetc(stdin); memory = malloc(S * sizeof(int)); inputs = malloc(N * sizeof(int)); program = malloc(1025 * L * sizeof(char*)); for (int i=0; i<L; ++i) { char r[1025]; scanf("%[^\n]", r); fgetc(stdin); strcat(program, r); } for (int i=0; i<N; ++i) { scanf("%d", &inputs[i]); } if (syntaxCheck(program)) { printf("SYNTAX ERROR"); return 1; } eval(program, inputs, memory, S); return 0; }
4. Exemple d’utilisation
Voici l’exemple d’une addition en Brainfuck :
,>,[-<+>]<.
Pour fonctionner, ce programme prend 2 entiers en entrée (notés a et b) puis boucle jusqu’à ce que b soit égal à 0, en décrémentant b et incrémentant a. On affiche enfin a.
Par exemple, avec comme entrée !
(valeur ASCII 33) et &
(valeur ASCII 38), on obtient bien G, qui a pour valeur ASCII 71 (33 + 38 = 71).
5. Comparaison avec une autre solution
A partir de cette solution externe :
#include <stdlib.h> #include <stdio.h> #include <string.h> enum { noerr, oob, iv }; char errormsg[][22] = { "", "POINTER OUT OF BOUNDS", "INCORRECT VALUE" }; int L, S, I; int ip = 0, dp = 0, sp = 0, ia = 0; int ram[100] = {0}, inputs[100], stack[100]; char code[102500] = "", answer[1025] = ""; int left() { dp--; return dp >= 0 ? 0 : oob; } int right() { dp++; return dp < S ? 0 : oob; } int plus() { ram[dp]++; return ram[dp] < 0x100 ? 0 : iv; } int minus() { ram[dp]--; return ram[dp] >= 0 ? 0 : iv; } int dot() { strncat( answer, (char *)&ram[dp], 1); return 0; } int comma() { ram[dp] = inputs[--ia]; return 0; } int lbr() { if(ram[dp]) stack[sp++]=ip; else ip=strchr(&code[ip],']') - code; return 0; } int rbr() { if(ram[dp]) ip=stack[sp-1]; else sp--; return 0; } int nop() { return 0; } int main() { int (*cpu[256])(void); for( int i = 0; i < 256; i++ ) cpu[i] = nop; cpu['<'] = left; cpu['>'] = right; cpu['+'] = plus; cpu['-'] = minus; cpu['.'] = dot; cpu[','] = comma; cpu['['] = lbr; cpu[']'] = rbr; scanf("%d%d%d", &L, &S, &I); fgetc(stdin); for (int i = 0; i < L; i++) { char r[1025]; fgets(r, 1025, stdin); strcat( code, r ); } for (int i = 0; i < I; i++) scanf("%d", &inputs[ia++]); int syntax_error = 0; for( int i = 0; i < strlen(code); i++ ) { syntax_error += (code[i]=='[') - (code[i]==']'); if( syntax_error < 0) break; } if( syntax_error ) { puts( "SYNTAX ERROR" ); exit( 3 ); } while( ip < strlen(code) ) { int fault = cpu[code[ip]](); if( fault ) { puts( errormsg[fault] ); exit(fault); } ip++; } puts( answer ); return 0; }
Ce programme propose également une lecture caractère par caractère. Néanmoins, j’ai apprécié la manière d’assigner chaque caractère clé à une fonction spécifique.
6. Bilan
Le problème a été simple à comprendre, et à résoudre. J’ai rencontré des difficultés sur la gestion de boucles, mais après réflexion j’ai pu résoudre cette problématique.