BrainFuck

Table of Contents

UCA.png

brainfuck_code.png

1. Doxygene

BrainFuck.c

2. Introduction BrainFuck

Brainfuck est un langage de programmation minimaliste composé de 8 commandes. C’est tout. Cependant il est Turing complet et permet de faire ce que l’on veut, à condition d’être très patient et motivé.

Votre objectif est de créer un interprète Brainfuck entièrement fonctionnel. Voyons comment cela fonctionne.

Le modèle Brainfuck est composé de trois éléments :

  • Un tableau de S cellules d’un octet initialisé à 0 et indexé à partir de 0.
  • Un pointeur initialisé pour pointer sur la première cellule (index 0) du tableau.
  • Un programme composé des 8 instructions valides.

Voici les instructions :

  • > incrémente la position du pointeur.
  • < décrémente la position du pointeur.
  • + incrémente la valeur de la cellule vers laquelle pointe le pointeur.
  • - décrémente la valeur de la cellule vers laquelle pointe le pointeur.
  • . afficher la valeur de la cellule pointée, en l’interprétant comme une valeur ASCII.
  • , acceptez un entier positif d’un octet en entrée et stockez-le dans la cellule pointée.
  • [passer à l’instruction après le correspondant] si la valeur de la cellule pointée est 0.
  • ] revenir à l’instruction après le [ correspondant si la valeur de la cellule pointée est différente de 0.

3. Solution expliquée

Pour cette exercice, je crée une variable pointeur (il s’agit pas d’un vrai pointeur) et un tableau “tab” ou je vais chercher et mettre chaques commandes dans une case du tableau, et un autre tableau “memory”. Je parcours ensuite tout le tableau “tab” et j’execute l’action demandé suivant le charactère. Lorsque je rencontre un crochet ouvert je sauvegarde sa position dans un tableau à 2 dimensions afin de revenir facilement sur la bonne opération dans la boucle. 

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define M 5000

int main()
{
    int tab[M];
    int Memory[M];
    int Parenthese[M][2];
        for (int j = 0; j < M; j++) {
            Memory[j] = 0; // Assigner la valeur zéro à chaque élément
        }

    int Pointeur=0;
    int L;
    int S;
    int N;
    int j=0;
    int nbouvert=0,nbfermer=0;
    int v=0;
    int nbParenthese=0;
    scanf("%d%d%d", &L, &S, &N); fgetc(stdin);
    for (int i = 0; i < L; i++) {
        char r[1025];
        scanf("%[^\n]", r); fgetc(stdin);
        while(r[j]!='\0')
        {
            //prendre en compte que les bon charactères
            if(r[j]=='+'||r[j]=='-'||r[j]=='['||r[j]==']'||r[j]==','||r[j]=='.'||r[j]=='>'||r[j]=='<')
            {
            tab[v]=r[j];
            //compter les crochets
            if(tab[v]=='[')
            {
                nbouvert++;
                Parenthese[nbParenthese][0]=v;
                nbParenthese++;
            }
            if(tab[v]==']')
            {
                nbfermer++;
                nbParenthese--;
                Parenthese[nbParenthese][1]=v;

            }
            v++;
            }
            j++;
        }
        j=0;



    }

    //erreur de crochet
    if(nbouvert!=nbfermer){printf("SYNTAX ERROR");return 0;}
    nbParenthese=0;
    j=0;
    while(tab[j]!='\0')
    {

        if(tab[j]=='+')
        {
            Memory[Pointeur]++;
        }
        if(tab[j]=='-')
        {
            Memory[Pointeur]--;
        }
        if(tab[j]=='.')
        {
             printf("%c",Memory[Pointeur]);
        }
        if(tab[j]==',')
        {
            int c;
            scanf("%d", &c);
            Memory[Pointeur]=c;
        }
        if(tab[j]=='>')
        {
             Pointeur+=1;

        }
        if(tab[j]=='<')
        {
             Pointeur-=1;

        }
        //si crochet ouvert trouvé je stock dans un tableau a deux dimension la position de la parenthese
        if(tab[j]=='[')
        {
            Parenthese[nbParenthese][0]=j;
            nbParenthese++;

            if(Memory[Pointeur]==0)
            {
                j=Parenthese[nbParenthese][1];
                nbParenthese--;
            }

        }
        //si crochet fermer trouvé et mon pointeur est != 0 alors je reviens à l'emplacement du premier crochet
        if(tab[j]==']')
        {
            nbParenthese--;
            Parenthese[nbParenthese][1]=j;

            if(Memory[Pointeur]!=0)
            {
                j=Parenthese[nbParenthese][0];
                nbParenthese++;
            }
        }

        //types d'ereurs
        if(Pointeur<0 || Pointeur>S-1){printf("POINTER OUT OF BOUNDS");break;}
        if(Memory[Pointeur]<0 || Memory[Pointeur]>255){printf("INCORRECT VALUE");break;}

        ++j;
    };

    return 0;
}

4. Tests et exécutions

Test avec comme entrées 

gcc -Wextra -Wall -Werror BrainFuck.c
./a.out
1 4 0
++++++++++[>+++++++>++++++++++>+++<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.

voici le résultat: 

Hello World!

5. Mon programme

Mon programe en brain fuck fait un triangle de N par XN: voici l’entrée : 

gcc -Wextra -Wall -Werror BrainFuck.c
./a.out
1 4 0
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>,>++++++++++<[>>,[<<<.>>>-]<.<-]
5 5 4 3 2 1

voici le résultat:

XXXXX
XXXX
XXX
XX
X

6. solutions de la communauté

Potemkine dans son programme, il utilise des vrai pointeurs et il utilise aussi une boucle while afin de boucler sur des crochet “[]”, ceci est donc une diférente solution du problème. 

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int L;
int S;
int N;

char brnfck[102500];
int inputs[100];
int* input_ptr = inputs;

unsigned char array[100];
unsigned char* pointer = array;

int checkCount()
{
    int o_cnt = 0;
    int c_cnt = 0;

    char* ptr = brnfck;
    while (*ptr!=0 && *ptr!='\n')
    {
        if (*ptr=='[') { o_cnt++; }
        else if (*ptr==']') { c_cnt++; }
        ptr++;
    }
    if (o_cnt!=c_cnt) {
        return 0;
    }
    return 1;
}

char* getClosing(char* prgm, char* open)
{
    char* ptr = open;
    int cpt = 1;

    while (cpt!=0 && ptr-prgm<strlen(prgm)){
        ptr++;
        if (*ptr=='[') { cpt++; }
        else if (*ptr==']') { cpt--; }
    }
    if (cpt==0) {
        return ptr;
    }
    return NULL;
}

char* getOpening(char* prgm, char* close)
{
    char* ptr = close;
    int cpt = -1;

    while (cpt!=0 && ptr>prgm){
        ptr--;
        if (*ptr=='[') { cpt++; }
        else if (*ptr==']') { cpt--; }
    }
    if (cpt==0) {
        return ptr;
    }
    return NULL;
}

int checkLine()
{

    if (checkCount())
    {
        char test[102500];
        strcpy(test,brnfck);
        char* ptr = test;
        while (*ptr!=0) {
            if (*ptr=='['){
                char* close = getClosing(test, ptr);
                if (close==NULL){
                    return 0;
                } else {
                    *ptr = '(';
                    *close = ')';
                }
            } else
            if (*ptr==']'){
                return 0;
            }
            ptr++;
        }

    } else {
        return 0;
    }
    return 1;
}

void processLine()
{
    if (checkLine())
    {
        char* ptr = brnfck;
        while (*ptr!=0)
        {
            switch (*ptr) {
                case '>':
                    if (pointer+1-array>=S) {
                        printf("POINTER OUT OF BOUNDS\n");
                        return;
                    } else {
                        pointer++;
                    }
                    break;
                case '<':
                    if (pointer<=array) {
                        printf("POINTER OUT OF BOUNDS\n");
                        return;
                    } else {
                        pointer--;
                    }
                    break;
                case '+':
                    if ((int)(*pointer)<255) {
                        (*pointer)++;
                    } else {
                        printf("INCORRECT VALUE\n");
                        return;
                    }
                    break;
                case '-':
                    if (*pointer>0) {
                        (*pointer)--;
                    } else {
                        printf("INCORRECT VALUE\n");
                        return;
                    }
                    break;
                case '.':
                    printf("%c",*pointer);
                    break;
                case ',':
                    *pointer = (char)(*input_ptr & 0xFF);
                    input_ptr++;
                    break;
                case '[':
                    if (*pointer==0){
                        ptr = getClosing(brnfck, ptr);
                    }
                    break;
                case ']':
                    if (*pointer!=0){
                        ptr = getOpening(brnfck,ptr);
                    }
                    break;
                default:
                    break;
            }
            ptr ++;
        }
        printf("\n");
    } else {
        printf("SYNTAX ERROR\n");
    }
}

void fill_brnfck(char* line)
{
    char* ptr = line;
    char* b = brnfck + strlen(brnfck);

    while (*ptr!=0)
    {
        if (*ptr=='+' || *ptr=='-' || *ptr=='>' || *ptr=='<' ||
            *ptr=='[' || *ptr==']' || *ptr=='.' || *ptr==',' )
        {
            *b = *ptr;
            b++;
        }
        ptr++;
    }

}
/**
 **/
int main()
{
    memset(array,0,sizeof(array));
    memset(brnfck,0,sizeof(brnfck));

    scanf("%d%d%d", &L, &S, &N); fgetc(stdin);
    for (int i = 0; i < L; i++) {
        char r[1025];
        fgets(r, 1025, stdin);
        fill_brnfck(r);
    }
    for (int i = 0; i < N; i++) {
        scanf("%d", &(inputs[i]));
    }
    processLine();

    return 0;
}

Code de PotemKine

retour au Hub

Date: 2024-05-01

Author: CyprienJULLIEN

Created: 2024-05-02 jeu. 09:27