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
Si ptr < 0 ou ptr >= memSize :
- Afficher « POINTER OUT OF BOUNDS »
- Fin fonction
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 de in
- [ : 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.