Partage

[Atelier tous langages] Codez un interpréteur de Brainfuck

étudier, contribuer, discuter

21 août 2008 à 15:04:49

Après un peu de débat avec d'autres membres du forum, on a décidé de relancer un "Atelier multi-langages".

Le premier, improvisé, était Différents algorithmes de compression. Ça c'est très bien passé et je vous invite à aller voir le topic pour avoir une idée du but de l'exercice.

Le sujet qui a été choisi est un interpréteur de Brainfuck. Le Brainfuck est un langage de programmation très simple, très chiant à utiliser mais pour lequel il est relativement facile de coder un interpréteur. C'est à la portée même des débutants dans le domaine.

edit : je viens d'avoir un retour "oh non le BrainFuck on comprend rien". Les codes écrits en BF sont effectivement crytpiques, mais si on l'a choisi c'est parce qu'il est simple à interpréter : pas de gestion de variables, etc. Donc du point de vue de l'implémenteur (qui est le votre sur ce topic) il est simple. N'ayez pas peur, allez lire un document décrivant le langage au calme (la page wikipédia suffit largement), et ça ira très bien.

Le sujet est volontairement assez libre. Vous devez faire un programme qui lit en entrée un code Brainfuck, et qui permet de produire le résultat attendu. Plusieurs voies d'explorations sont possibles (par exemple on peut essayer de gérer un ruban infini), et on ne vous en voudra pas de faire quelque chose de simple dans un premier temps.


Il n'y a pas de règles formelles (c'est pas un concours ou quoi, pas besoin de s'inscrire, etc), mais voici quelques points de bon sens :

On veut le code, on veut tripoter



Publiez toujours la source de votre programme (normalement vous n'avez besoin de donner rien d'autre); il faudrait, dans la mesure du possible, que chacun puisse l'essayer chez soi (donc évitez les langages propriétaires, les machins pas portables du tout, etc.).

Essayez de présenter votre source de la manière la plus lisible et la plus claire possible (pas de "oh j'ai pas eu le temps de mettre des vrais noms de variables"); sinon, vous vous exposez aux commentaires du public, et ça peut vous poursuivre pendant longtemps (hein delroth ?).

Les autres participants peuvent reprendre la source, la modifier, l'améliorer, etc. On n'impose pas de licence ou quoi (et si vous précisez une licence libre elle sera respectée, enfin j'espère), mais si vous n'êtes pas prêts à vous faire tripoter, ne postez rien.


Éviter les répétitions



Si vous avez fait un programme dans votre langage préféré, mais qu'il existe déjà une proposition pour ce langage (ou un langage quasiment identique) et que le votre n'apporte visiblement rien, vous pouvez vous retenir de poster. Cherchez plutôt un aspect intéressant à explorer (une optimisation, etc.).

Le but c'est surtout d'avoir un certain nombre de versions intéressantes à comparer, et de pouvoir voir par exemple les forces ou les faiblesses de certains langages ou styles de programmation. Pas de montrer à tout le monde qu'on est le meilleur programmeur de la planète (même si c'est cool aussi).




Si vous êtes débutant, n'hésitez pas à poser des questions si vous ne comprenez pas ou n'arrivez pas à faire quelque chose.

Pour lancer le topic, voici un premier code écrit très serviablement par coucou47. C'est en PHP (on se moque pas, le but c'était que tout le monde puisse comprendre), et il n'est pas du tout optmisé, le but étant d'être clair et accessible. Je poste ici la deuxième version, mais vous pouvez trouver le tout à cette adresse. Si vous trouvez cela douloureusement commenté, c'est parce qu'on l'a forcé.

<?php
/**
 * @brief fonction qui interprete un code brainfuck
 * solution sans preprocessing
 * @param $code le code a interpreter
 */
function brainfuck_verbeux($code){
  $code_len = strlen($code);
  $mem = array();
  $indice_memoire = 0;
  for ($i=0;$i<$code_len;$i++){
    if (!isset($mem[$indice_memoire])) $mem[$indice_memoire]=0;
    else {
       // les valeurs sont comprises entre 0 et 256.
      $mem[$indice_memoire] = (256 + $mem[$indice_memoire] ) % 256;
    }
    switch($code[$i]){
      case '>': $indice_memoire++; break;
      case '<': $indice_memoire--; break;
      case '.': echo chr($mem[$indice_memoire]); break; // on affiche la valeur
      case ',': $mem[$indice_memoire]=prompt(); break;
      case '+': $mem[$indice_memoire]++; break; // on incremente la valeur
      case '-': $mem[$indice_memoire]--; break; // on decremente la valeur
      case ']':
        $n = 1; // on doit remonter $n [ en arriere
        while ($n){
          $i --; // on cherche en arriere
          if ($code[$i]==']') $n++; // si on rencontre un ], alors on attend un [ de plus
          else if ($code[$i]=='[') $n--; // si on trouve un [. alors on en attend un de moins
        } $i--; // on "jump" devant le [ correspondant.
        break;
      case '[':
        if ( $mem[$indice_memoire] == 0 ){
          $n = 1; // on doit monter $n ] en avant
          while ($n){
            $i ++;
            if ($code[$i]=='[') $n++; // si on rencontre un [, alors on attend un ] de plus
            else if ($code[$i]==']') $n--; // si on trouve un ]. alors on en attend un de moins
          } // ici, on a pas de $i-- parce-qu'on jump apres le ]
      } break;
    }
  }
}


brainfuck_verbeux(
'++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.');
brainfuck_verbeux(',>,<+>+<.>.');

?>


21 août 2008 à 15:34:13

Je viens de coder une version Python pas trop moche qui utilise des générateurs pour l'I/O du programme Brainfuck, et qui fonctionne plutôt bien :
#!/usr/bin/env python
#-*- encoding: utf-8 -*-
"""
bf.py
Brainfuck intepretor
"""

import sys

def brainfuck(code, inchan):
    """
    Read the brainfuck code from "code", input data from inchan, and yields
    output.
    """
    jumpstable = [] # List of tuples (from, dest)

    # Loop on the whole code in order to fill the jump table
    for startpos, instruction in enumerate(code):
        if instruction == '[':
            n = 1
            for offset, endinstruction in enumerate(code[startpos:]):
                if endinstruction == '[':
                    n += 1
                elif endinstruction == ']':
                    n -= 1
                    if n == 1:
                        jumpstable.append((startpos, startpos + offset))
                        break
    memory = 30000 * [0] # The memory is 30000 cases wide.
    memindex = 0 # Start at position 0

    codepos = 0 # Position in the code
    while codepos < len(code): # Main loop
        inst = code[codepos]
        if inst == '<': memindex -= 1
        elif inst == '>': memindex += 1
        elif inst == '+': memory[memindex] += 1
        elif inst == '-': memory[memindex] -= 1
        elif inst == '.': yield memory[memindex]
        elif inst == ',': memory[memindex] = inchan.next()
        elif inst == '[' and memory[memindex] == 0:
            endpos = filter(lambda (s, e): s == codepos, jumpstable)[0][1]
            codepos = endpos
        elif inst == ']':
            stpos = filter(lambda (s, e): e == codepos, jumpstable)[0][0]
            codepos = stpos - 1
        codepos += 1
        memory[memindex] = (255 if memory[memindex] < 0
                                else memory[memindex] % 256)

def stdinchan():
    """
    Read the input data from stdin. If EOF encountered, always return 0.
    """
    while True:
        try:
            yield ord(sys.stdin.read(1))
        except EOFError:
            break
    while True:
        yield 0

code = '''>++++++++++>+>+[
    [+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>[
        [-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-
            [>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>>
    ]<<<
]'''

for char in brainfuck(code, stdinchan()):
    sys.stdout.write(chr(char))
    sys.stdout.flush()

"""
Copyright (c) 2008 Pierre "wgmpgp" Bourdon <root@wgmpgp.is-a-geek.org>

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.
"""


Ça utilise d'ailleurs le fait très pratique que tableau[-1] accède à la dernière case d'un tableau en Python pour gérer les indexs négatifs ;) .
21 août 2008 à 17:10:40

Cool, j'essaierai de m'y coller ce soir...

Thierry
Admin 21 août 2008 à 17:14:38

Voici une version en C.

Elle est fonctionelle mais il reste plein de petite fioriture a faire :

La gestion d' un code mal foutu ( évité les dépassement de memoire, les boucles non fermante)

Alors deja voila le main:

main.c:
#include "brainfuck.h"

int main(void)
{

	brainfuck("++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.");
	brainfuck(",>,<+>+<.>.");

	return (0);
}


Ensuite voila brainfuck.h

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

#define FAILLURE 0
#define SUCCESS 1

/*Structure de donnée contenant la memoire de l' intérpreteur*/
typedef struct Bf_mem{
	char * memory;
	int memorySize;
	int currentMemPosition;
}Bf_mem;

/*Calcul l'espace memoire nécéssaire au programme*/
int necessaryMemorySize(char * code);
/*Initialise la structure de donnée*/
int init(char * code, Bf_mem * mem);
/*Fonction principal du module*/
int brainfuck(char * code);
/*L' interpréteur en lui meme*/
int bf_interpreteur(char * code, Bf_mem * memory);
/*Liberation de la memoire*/
void freeMem(Bf_mem * mem);


Et voila brainfuck.c
#include "brainfuck.h"

/*Fonction Principal:
Initialisation et appel de l' interpréteur
*/
int brainfuck(char * code)
{
	int r = FAILLURE;
	Bf_mem memory;

	if(init(code, &memory) == SUCCESS)
	{
		r = bf_interpreteur(code, &memory);
                                freeMem(&memory);
	}

	return (r);
}

/*L' interpréteur en lui même
TODO: Gestion d' un code mal écrie*/
int bf_interpreteur(char * code, Bf_mem * memory)
{
	unsigned int i = 0;
	int r = SUCCESS;

	for(i = 0; i < strlen(code); i++)
	{
		switch (code[i])
		{
		case '>':
			/*TODO Gestion des indices hors memoire*/
			memory->currentMemPosition++;
			break;
		case '<':
			/*TODO Gestion des indices or memoire*/
			memory->currentMemPosition--;
			break;
		case '+':
			memory->memory[memory->currentMemPosition]++;
			break;
		case '-':
			memory->memory[memory->currentMemPosition]--;
			break;
		case '.':
			putchar(memory->memory[memory->currentMemPosition]);
			break;
		case ',':
			memory->memory[memory->currentMemPosition] = getchar();
			break;
		case '[':
			/*Si la case memoire pointé est a zero on saute a son crochet fermant*/
			if(memory->memory[memory->currentMemPosition] == 0)
			{
				int numOfBrackets = 1;
				while(numOfBrackets != 0)
				{
					i++;
					if(code[i] == '[')
						numOfBrackets++;

					else if( code[i] == ']')
						numOfBrackets--;
				}
			}
			break;
		case ']':
			/*On doit remonté a son crochet ouvrant*/
			if(1)
			{
				int numOfBrackets = 1;
				while(numOfBrackets != 0)
				{
					i--;
					if(code[i] == '[')
						numOfBrackets--;

					else if( code[i] == ']')
						numOfBrackets++;
				}
				/*On passe un caractere en arriere pour retourné sur l' evaluation du caractere '['*/
				i--;
			}
			break;
		default:
			break;
		}
	}

	return (r);
}

/*initialisation de la structure memoire*/
int init(char * code, Bf_mem * mem)
{
	int r = FAILLURE;
	mem->currentMemPosition = 0;
	mem->memorySize = necessaryMemorySize(code);

	mem->memory = 0;
	mem->memory = calloc(1,mem->memorySize);

	if(mem->memory != 0)
		r = SUCCESS;

	return (r);
}

/*Retourne l'espace memoire maximal nécéssaire au programme*/

int necessaryMemorySize(char * code)
{
	unsigned int i = 0;
	int maxSize = 1;
	int tmpSize = 1;

	for( i = 0; i < strlen(code); i++)
	{
		switch(code[i])
		{
		case '>':
			tmpSize++;
			if(tmpSize > maxSize)
				maxSize++;
			break;
		case '<':
			tmpSize--;
			break;
		default: 
			break;
		}
	}

	return (maxSize);
}
void freeMem(Bf_mem * mem)
{
	mem->currentMemPosition = 0;
	mem->memorySize = 0;
	free(mem->memory);

	mem->memory = 0;
}


La fonction intéréssente etant bien sur : int bf_interpreteur(char * code, Bf_mem * memory)

Edit: Oublier la liberation de la memoire :D , Algo de calcul de l' éspace memoire
21 août 2008 à 17:50:16

J'ai aussi fait une version C, mais plus simple (et plus naïve), qui se rapproche fortement de la version PHP, donc il n'y a pas vraiment d'intérêt à la poster ici.
Par contre je vais tenter une version C++ avec une approche un peu différente.
21 août 2008 à 18:19:09

int necessaryMemorySize(char * code)
ta fonction est totalement fausse...

a part ca, c'est la traduction de mon code...
21 août 2008 à 18:33:53

Effectivement, brainfuck("<") devrait normalement faire planter ton code joliement (haha, allocation de UINT_MAX octets).
21 août 2008 à 18:41:43

Bonjour !
J’apporte moi aussi ma pièce à l’édifice. Je crois que c’est la première faites dans un langage de programmation fonctionnel, en l’occurence en Erlang. Alors pour les petites différences par rapports aux autres versions : on a ni tableaux, ni pointeurs. À la place on se sert de listes. Et plus précisement un Zipper. Le principe est très simple, on découpe une liste en 3 parties :
  1. ce qu’il y a avant le curseur
  2. le curseur
  3. ce qu’il y a après le curseur

Ce qui nous permet ainsi facilement d’attendre l’élément précédent ou l’élément suivant de la liste sans avoir à tout parcourir. :) Vous verrez dans mon code que grace à la syntaxe [Tête|Queue] offerte par erlang pour représenter les listes on peut réduire ce découpage à deux listes, bref… Seulement l’utilisations de deux zippers simultanéments (un pour les instructions, un pour la mémoire) rend le code assez difficile à lire. :(

Mais voyez plutôt :
-module(brainfuck).
-export([start/1]).

start(Str) -> brainfuck([], Str, [], [0]).

brainfuck(_, [], _, _) -> ok;
brainfuck(A, B, [], C) -> brainfuck(A, B, [0], C);
brainfuck(A, B, C, []) -> brainfuck(A, B, C, [0]);
brainfuck(Prevs, [Act|Next], [CPrev|CPrevs], [CAct|CNext]) ->
    case [Act] of
	">" -> brainfuck([Act|Prevs], Next, [CAct, CPrev|CPrevs], CNext);
	"<" -> brainfuck([Act|Prevs], Next, CPrevs, [CPrev, CAct|CNext]);
	"+" -> brainfuck([Act|Prevs], Next, [CPrev|CPrevs], [(CAct + 1)|CNext]);
	"-" -> brainfuck([Act|Prevs], Next, [CPrev|CPrevs], [(CAct - 1)|CNext]);
	"." -> 
	    io:put_chars([CAct]),
	    brainfuck([Act|Prevs], Next, [CPrev|CPrevs], [CAct|CNext]);
	"," ->
	    [NewCAct|_] = io:get_line("> "),
	    brainfuck([Act|Prevs], Next, [CPrev|CPrevs], [NewCAct|CNext]);
	"[" when CAct == 0 ->
	    {A, B, C, D} = skip([Act|Prevs], Next, [CPrev|CPrevs], [CAct|CNext]),
	    brainfuck(A, B, C, D);
	"["  -> brainfuck([Act|Prevs], Next, [CPrev|CPrevs], [CAct|CNext]);
	"]" when CAct == 0 -> brainfuck([Act|Prevs], Next, [CPrev|CPrevs], [CAct|CNext]);
	"]" -> 
	    {A, B, C, D} = back(Prevs, [Act|Next], [CPrev|CPrevs], [CAct|CNext]),
	    brainfuck(A, B, C, D)
    end.

skip(_, _, _, []) -> exit("Boucle non fermée");
skip(Prevs, [Act|Next], [CPrev|CPrevs], [CAct|CNext]) ->
    case [Act] of
	"]" -> {Prevs, [Act|Next], [CPrev|CPrevs], [CAct|CNext]};
	"[" ->
	    {A, B, C, D} = skip([Act|Prevs], Next, [CPrev|CPrevs], [CAct|CNext]),
	    skip(A, B, C, D);
	_ -> skip([Act|Prevs], Next, [CPrev|CPrevs], [CAct|CNext])
    end.

back(_, _, [], _) -> exit("Boucle non fermée");
back([Prev|Prevs], [Act|Next], [CPrev|CPrevs], [CAct|CNext]) ->
    case [Prev] of
	"[" -> {[Prev|Prevs], [Act|Next], [CPrev|CPrevs], [CAct|CNext]};
	"]" ->
	    {A, B, C, D} = back([Prev|Prevs], [Act|Next], [CPrev|CPrevs], [CAct|CNext]),
	    back(A, B, C, D);
	_ -> back(Prevs, [Prev, Act|Next], [CPrev|CPrevs], [CAct|CNext])
    end.


Pour tester :
$ erl
...
1> c(brainfuck).
{ok,brainfuck}
2> brainfuck:start("votre code").

Si vous avez des questions n’hésitez ps à les poser !
21 août 2008 à 19:03:08

Intéressant la version Erlang, ça change un peu, par contre c'est effectivement assez difficile à lire.

Voilà ma version C++ :

#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;

int main(int argc, char *argv[])
{
    if (argc < 2) {
	cout << "Specifiez un code Brainfuck !" << endl;
        return -1;
    }
	
    string code = argv[1];

    vector<char> memory; //Tableau d'octets
    vector<char>::iterator memPtr = memory.begin(); //Represente le pointeur 
    vector<int> brackets(code.length()); //Correspondance des positions de '[' et ']'
    stack<char,vector<char>> bracketStack; //Pile pour stocker la position des '['

    memory.push_back(0);
    memPtr = memory.begin();
	
    //On parcourt une premiere fois le code pour noter les correspondances entre '[' et ']'
    //(a chaque [ correspond un ] et vice versa)
    for (size_t i = 0; i < code.length(); i++) {
	if (code[i] == '[')
            bracketStack.push(i);
	    if (code[i] == ']') {
		if (bracketStack.empty()) {
		    cerr << "] inattendu en position" << i << endl;
		    return 1;
		}
		else {
		    int pos = bracketStack.top(); //On cherche le '[' correspondant
		    bracketStack.pop();
		    brackets[i] = pos; //Il correspond au ']' trouvé
		    brackets[pos] = i; //et inversement
		}
	    }
	}
    if (!bracketStack.empty()) {
        cerr << "[ non fermé en position" << bracketStack.size() << endl;
        return 1;
    }

    //Deuxieme parcourt du code : execution
    for (size_t i = 0; i < code.length(); i++) {
        switch (code[i]) {
       	    case '<' : if (memPtr != memory.begin()) memPtr--; break;
	    case '>' :
                if (memPtr == memory.end() - 1) {
	            memory.push_back(0);
		    memPtr = memory.end() - 1;
		}
		else 
                    memPtr++; 
		break;
	    case '+' : (*memPtr)++; break;
            case '-' : (*memPtr)--; break;
	    case '.' : cout.put(*memPtr); break;
	    case ',' : *memPtr = cin.get(); break;
	    case '[' : if (!(*memPtr)) i = brackets[i]; break;
	    case ']' : if (*memPtr) i = brackets[i]; break;
	}
    }
    return 0;
}


Je pense que les commentaires expliquent à peu près bien.

[EDIT] Modifié le code pour gérer un tableau de taille infini.
21 août 2008 à 19:19:03

Et une version en caml, tirant partie des foncteurs.
La version est assez longue et son but est d'être modulaire.

J'ai découpé le code en plusieurs modules :
  • La structure de donnée utilisée pour stocker la mémoire
  • Le type des données
  • Le flux du code

Pour chacun de ces modules j'ai défini une interface et j'apporte une implémentation.

La mémoire


La structure de donnée utilisée pour la mémoire doit contenir plusieurs élements, et être infinie (s'aggrandissant quand il faut). De plus, elle doit garder un "pointeur" vers un élement particulier de la mémoire (la case actuelle) et permettre de déplacer ce pointeur facilement.
Voilà l'interface :
module type Memory = sig
  type 'a t
  val update : ('a -> 'a) -> 'a t -> 'a t
  val get : 'a t -> 'a
  val forward : 'a t -> 'a t
  val backward : 'a t -> 'a t
  val single : 'a -> 'a t
end

update permet de modifier l'élement qui est pointé, et single retourne une mémoire contenant un seul élément, et dont le pointeur pointe sur cet élement.

Mon implémentation repose également sur un Zipper, qui s'aggrandit en remplissant avec l'élément passé à single :
module Zipper : Memory = struct
  type 'a t = {
    before : 'a list;
    current : 'a;
    after: 'a list;
    default : 'a;
  }
  let update f ({current = a} as zipper) = {zipper with current = f a}
  let get {current = a} = a
  let forward zipper = match zipper.after with
    | [] -> { zipper with current = zipper.default; 
		before = zipper.current :: zipper.before;  }
    | t :: q -> {zipper with before = zipper.current :: zipper.before; current = t; 
		   after = q}

  let swap zipper =  { zipper with after = zipper.before; before = zipper.after }
  let backward z = swap (forward (swap z))
  let single a = {
    before = []; after = []; current = a; default = a
  }
end



Le type des données


Les données contenues dans notre mémoire doivent supporter l'incrémentation, la décrémentation, et doivent posséder un zéro(qui sert pour les boucles), ainsi que la lecture et l'écriture à l'écran :
module type Data = sig 
  type t
  val zero : t
  val incr : t -> t
  val decr : t -> t
  val print : t -> unit
  val read : unit -> t
end

L'implémentation pour les entiers :
module Int : Data = struct
  type t = int
  let incr = (+) 1 and decr x = x - 1 and zero = 0
  let print = Printf.printf "%c" |< char_of_int
  let read () = int_of_char (input_line stdin).[0]
end


Le flux de code


Le flux de code doit permettre de se déplacer aussi bien en avant qu'en arrière (pour les boucles) et doit permettre l'accès rapide à un élement courant. On retrouve quasiment les mêmes contraintes que pour le Zipper, ceci dit il y a quelques différentes : le flux est en lecture seule (pas de modification) et sa taille est fixée. Voici l'interface et son implémentation basée sur un char array :

module Stream = struct
  type 'a t = 'a array * int

  let at (array, n) = array.(n)
  let prev (array, n) = (array, n-1)
  let next (array, n) = (array, n + 1)
  let of_chan chan = 
    let buffer = Buffer.create 100 in
    let rec loop () = 
      match (try Some (input_line chan) with _ -> None) with
	| Some l -> Buffer.add_string buffer l; loop ()
	| None -> ()
    in loop ();
      let s = Buffer.contents buffer in
      (Array.init (String.length s) (String.get s), 0)

end



Here we are, nous avons nos trois modules, on peut commencer à coder l'interpréteur en lui même. Il s'agit donc d'un foncteur, paramétré avec nos trois signatures. L'implémentation est assez naïve et rejoint celle d'eelte :
module Brainfuck (Stream : Stream) (Mem : Memory) (Data : Data) = struct
  type mem = Data.t Mem.t
  type operator = 
    | Simple of (mem -> mem)
    | Complex of (char Stream.t -> mem -> (char Stream.t * mem))

  let jump move incr_char decr_char = 
    let rec aux n st = 
      if Stream.at st = incr_char then
	aux (n+1) (move st)
      else if Stream.at st = decr_char then
	if n = 1 then
	  st
	else
	  aux (n - 1) (move st) 
      else
	aux n (move st)
    in move >| aux 1 >| Stream.next

  let incr_char = '+'
  let decr_char = '-'
  let forward_char = '>'
  let backward_char = '<'
  let prompt_char = ','
  let print_char = '.'
  let jump_forward_char = '['
  let jump_backward_char = ']'
  let jump_forward st mem = 
    (if Mem.get mem = Data.zero then
      jump Stream.next jump_forward_char jump_backward_char st
    else
      Stream.next st), mem

  let jump_backward st mem =
    (if Mem.get mem <> Data.zero then
      jump Stream.prev jump_backward_char jump_forward_char st
    else
      Stream.next st), mem

  let exec = function
    | Simple f -> (fun st mem -> (Stream.next st, f mem))
    | Complex f -> f

  let operators = [
    incr_char, Simple (Mem.update Data.incr);
    decr_char, Simple (Mem.update Data.decr);
    forward_char, Simple Mem.forward;
    backward_char, Simple Mem.backward;
    prompt_char, Simple (fun mem -> Mem.update (const (Data.read ())) mem);
    print_char, Simple (fun mem -> Data.print (Mem.get mem); mem);
    jump_forward_char, Complex jump_forward;
    jump_backward_char, Complex jump_backward;
  ]
  let exec_chan chan = 
    let st = Stream.of_chan chan in
    let rec loop (st, mem) = 
      let c = Stream.at st in
	loop 
	  (try
	     (exec (List.assoc c operators) st mem)
	   with Not_found -> (Stream.next st, mem))
    in loop (st, Mem.single Data.zero)
end


Et enfin la boucle principale :
let () = 
  let module MyBrainfuckInterpreter = Brainfuck(Stream)(Zipper)(Int) in
    if Array.length Sys.argv > 1 then begin
      let fd = open_in Sys.argv.(1) in
	(try MyBrainfuckInterpreter.exec_chan fd with _ -> ());
	close_in fd
    end

Et voilà, le tour est joué :p

Le code utilise l'opérateur >| qui compose deux fonctions, dans le sens suggéré par la flèche. Son implémentation est laissée au lecteur :-°
Code pasté.
21 août 2008 à 19:29:28

'Soir,

Ma version en C, finie il y'a quelques jours (après d'autres jours de réflexion :p). Par rapport à l'autre elle fait:
> Lecture du code BF dans un fichier - Allocation Dynamique du tableau nécessaire.
> Allocation directe de la pile BF de 30 000 cases
> Elle utilise deux tableaux de correspondance ( Un pour les [ et un pour les ] ) construit une seule fois.
> Pour gérer les boucles, un troisième tableau dynamique est utilisé (enfin, réutilisé), en tant que pile.
> De fait, aucune structure n'est déclarée. Le code n'est pas non plus séparé en fonctions, j'n'en voyais pas l'utilité directe.

Je vous laisse découvrir :) Si vous avez des questions, n'hésitez pas. Le code est en secret pour 140 lignes à ceux que ca n'intéresserais pas. Si vous trouvez des bugs, vous pouvez aussi faire remonter :)

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

#define Debu /* Set to Debug to enter debbuging Mode */
#define StackS 30000

int main(int argc, char **argv) {

    FILE *f = NULL;
    int Stack[StackS] = {0};
    char *Bf=NULL;
    int *BStack=NULL,*FStack=NULL,*CStack=NULL;
    int SIdx = 0;
    int i=0,j=0,l=0,o=0;
    int Len = 0,NbB=0;

    if (argc < 2)
        printf("BFInt - by RedoX, 2008\n\n"\
               "Usage: ./BfInt /path/to/file\n"),exit(0); /* Aucun Fichier */
    if (!(f = fopen(argv[1], "r")))
        printf("Can't open the file %s.\n", argv[1]), exit(-1); /* Erreur */
    do {
        getc(f); /* On Lit l'char */
        Len++;  /* On Incremente la longeur */
    } while (!feof(f)); /* Tant qu'il en reste */
    Len--; /* On corrige le depassement */
    rewind(f); /* On r'vient au debut */
    Bf = malloc((unsigned)Len*sizeof(char)); /* On alloue assez d'place */
    if (!Bf) printf("Malloc Error 1.Aborting!"),exit(-1);

    for (i=0;i<Len;i++) {
        Bf[i] = (char)getc(f); /* On place le char lu dans Bf */
        if (Bf[i] == '[') { /* On compte les [ */
            NbB++; /* Compte Final */
            SIdx++; /* Verif Nb Paires de [ ] Ok */
        }
        if (Bf[i] == ']') SIdx--; /* Verif Nb paires */
    }

    if (SIdx) /* Erreur */
        printf("Unmatching Square Brackets." \
               "Sum of [ - Sum of] = %d.Aborting!\n",SIdx), exit(-1);

    BStack = malloc((unsigned)NbB*sizeof(int)); /* Stack Index des [ */
    if (!BStack) printf("Malloc Error 2.Aborting!"),exit(-1);
    FStack = malloc((unsigned)NbB*sizeof(int)); /* Stack Index des ] */
    if (!FStack) printf("Malloc Error 3.Aborting!"),exit(-1);
    CStack = malloc((unsigned)NbB*2*sizeof(int)); /* Stack Temporaire */
    if (!CStack) printf("Malloc Error 4.Aborting!"),exit(-1);

    for (i=0;i<2*NbB;i++)
        CStack[i] = -1;   /* On Init la Stack */

    i=0;
    while (i<Len) {
        if (Bf[i] == '[') {
            BStack[j] = i; /* On met l'index du [ dans la BStack */
            CStack[l] = j++; /* On l'met aussi dans la CStack */
            l += 2; /* On laisse un vide pour le ] correspondant */
        } else if (Bf[i] == ']') {
            o=l-1; /* On s'init a l'index courant -1 pour l'decalage */
            while (CStack[o] != -1) /* On remonte jusqu'au premier -1 libre*/
                o -= 2;
            CStack[o] = i; /* On y met l'index courant du ] */
        }
        i++;
    }

    for (i=0;i<NbB;i++)
        FStack[i] = CStack[1+2*i]; /* On Remplis la Stack des ] */

    for (j=0;j<NbB;j++)
        CStack[j] = 0; /* On vide la Stack pour la reutiliser */

#ifdef Debug
    for (j=0;j<NbB;j++)
        printf("J: %d B: %d F: %d - B: %c F: %c\n",
                j,BStack[j],FStack[j],Bf[BStack[j]],Bf[FStack[j]]);
    getchar();
#endif

    i=0; /* Index dans Bf */
    j=0; /* Index dans CStack */
    SIdx=0;
    while (i<Len) {
        if (Bf[i] == '+')
            Stack[SIdx]++; /* Incremente Case */
        else if (Bf[i] == '-')
            Stack[SIdx]--; /* Decremente */
        else if (Bf[i] == '>')
            SIdx++;        /* Incremente Pointeur */
        else if (Bf[i] == '<')
            SIdx--;        /* Decremente */
        if (SIdx > StackS)
            SIdx = 0;      /* Retour Index 1 */
        if (SIdx < 0)
            SIdx = StackS-1; /* Avance Dernier Index */
        else if (Bf[i] == '.') {
            putchar(Stack[SIdx]); /* Affichage case */
        } else if (Bf[i] == ',')
            Stack[SIdx] = (char)getchar(); /* Modif Case */
        else if (Bf[i] == '[') {
            o=0; /* Nombre de [ */
            l=i; /* Index pour remonter chaine */
            while (l > BStack[0]) /* avant le premier [ */
                if (Bf[l--] == '[')
                    o++; /* On compte les [ */
            CStack[j] = o; /* On Update l'index */
#ifdef Debug
            printf("\nStack, J: %d I: %d O: %d :: ",j,i,o);
            for (l=0;l<NbB;l++)
                printf("%d ",CStack[l]);
#endif
            if (Stack[SIdx] == 0) { /* Si jump */
                i = FStack[CStack[j--]]; /* On Jump au ] correspondant */
                CStack[j+1] = 0;  /*On Delete l'index courant */
            }
            j++;
        } else if (Bf[i] == ']')
            i = BStack[CStack[--j]]-1; /* On retourne au [ correspondant */
        i++;
    }
#ifdef Debug
    printf("\nLast O: %d, Last J: %d\n",o,j);
    for (j=0;j<NbB;j++)
        printf("J: %d B: %d F: %d - B: %c F: %c\n",
                j,BStack[j],FStack[j],Bf[BStack[j]],Bf[FStack[j]]);
    for (l=0;l<NbB;l++)
        printf("%d ",CStack[l]);
    getchar();
#endif

    /* On libere la memoire allouee */
    free(Bf);
    free(BStack);
    free(FStack);
    free(CStack);
    return 0;
}


Si vous voulez un p'tit détail, pas forcément plus clair que le code, vous pouvez jetter un oeil ici : http://plume.redox.ws/?17-and-counting

'nne soirée,
RedoX
21 août 2008 à 19:53:10

Je sais, il y a beaucoup de code en C, mais vu qu'aucun ne montre la véritable beauté du C, je vais poster le miens.

Je l'ai codé il y a bien un an et demi, et pas dans le but d'un atelier quelconque donc j'ai mis des tests de sureté
( malloc != NULL, fopen != NULL, etc). On peut lire un fichier bf et obtenir l'input d'un autre fichier ou de stdin.

La mémoire est un tableau, qui grossit de 256 si besoin est.
Les conditions sont géré par une pile qui garde l'index de la condition entrante ( '[' ) pour pouvoir y revenir au niveau du ']'.
C'est du C ANSI.

Ah, et j'ai codé ça pour moi il y a longtemps, donc il y a peu de commentaires, et ils sont en anglais.

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

#define MAPSTEP 256

struct world {
    unsigned char *map;
    size_t size;
    unsigned char *p;
    struct stack *cond;
};

struct stack {
    struct stack *prev;
    int value;
};

static void grow(struct world *, int);
static void cond_add(struct world *, int);
static void cond_del(struct world *);

static inline void *xmalloc(size_t);
static inline FILE *xfopen(const char *);

int
main(int argc, char *argv[])
{
    long len, i;
    FILE *fpin, *fpget;
    char *p;
    int c;
    struct world w;

    memset(&w, 0, sizeof w);

    if (argc >= 3) {
        fpin = xfopen(argv[1]);
        fpget = xfopen(argv[2]);
    } else if (argc == 2) {
        fpin = xfopen(argv[1]);
        fpget = stdin;
    } else {
        fpin = stdin;
        fpget = stdin;
    }

    fseek(fpin, 0, SEEK_END);
    len = ftell(fpin); /* get the length of the script */

    if (len == -1) {
        fprintf(stderr, "Nothing to read, exiting\n");
        return EXIT_FAILURE;
    }

    fseek(fpin, 0, SEEK_SET);
    p = xmalloc(len * sizeof *p);
    for (i = 0; i < len; i++) {
        c = getc(fpin);
        if (c == EOF) { /* something really weird append. We quit cleanly */
            fprintf(stderr, "EOF received but not expected. Exit.\n");
            free(p);
            return EXIT_FAILURE;
        }
        p[i] = (unsigned char) c;
    }

    /* allocate the map */
    grow(&w, 1);
    w.p = w.map;
    /* now we execute the code */
    for (i = 0; i < len; i++) {
        switch(p[i]) {
        case '>':
            w.p++;
            if (w.p > &w.map[w.size - 1]) /* grow the map */
                grow(&w, 1);
            break;
        case '<':
            if (w.p > w.map)
                w.p--;
            else /* grow the map */
                grow(&w, 0);
            break;
        case '+':
            if (255 == (*w.p))
                *w.p = 0;
            else
                (*w.p)++;
            break;
        case '-':
            if (0 == (*w.p))
                *w.p = 255;
            else
                (*w.p)--;
            break;
        case '.':
            putchar((int) (*w.p));
            break;
        case ',':
            (*w.p) = (unsigned char) getc(fpget);
            break;
        case '[':
            if (0 == (*w.p)) { /* skip the code between [] */
                int k = 1;

                while (k && i < w.size) {
                    i++;
                    if (p[i] == '[')
                        k++;
                    else if (p[i] == ']')
                        k--;
                }
            } else
                cond_add(&w, i);
            break;
        case ']':
            if (!w.cond)
                break;
            if (0 != (*w.p)) /* jump back to the matching [ */
                i = w.cond->value;
            else
                cond_del(&w);
            break;
        default:
            break;
        }
    }
    while (w.cond) {
        fprintf(stderr, "%s: carac %d: No matching ']'\n",
                (argc < 2) ? "stdin" : argv[1], w.cond->value);
        /* print the context 5 lignes before and after */
        for (i = (w.cond->value < 5) ? 0 : w.cond->value - 5;
             i < w.cond->value + 5 && i < w.size; i++)
            putchar(p[i]);
        cond_del(&w);
    }

    free(w.map);
    free(p);

    fclose(fpget);
    fclose(fpin);

    return EXIT_SUCCESS;
}

static void
grow(struct world *w, int after)
{
    size_t oldsize = w->size;

    w->size += MAPSTEP;
    w->map = realloc(w->map, w->size * sizeof *w->map);

    if (after) {
        memset(&w->map[oldsize], 0, MAPSTEP * sizeof *w->map);
        w->p = &w->map[oldsize];
    } else { /* move the old map in the new map's end */
        memmove(&w->map[MAPSTEP], w->map, oldsize);
        memset(w->map, 0, MAPSTEP * sizeof *w->map);
        w->p = &w->map[w->size - oldsize - 1];
    }
}

static void
cond_add(struct world *w, int val)
{
    struct stack *s;

    s = xmalloc(sizeof *s);
    s->prev = w->cond;
    s->value = val;
    w->cond = s;
}

static void
cond_del(struct world *w)
{
    struct stack *s;

    if (w->cond) {
        s = w->cond;
        w->cond = s->prev;
        free(s);
    }
}

static inline void *
xmalloc(size_t n)
{
    void *p;

    p = malloc(n);
    if (!p) {
        fprintf(stderr, "Can't allow more memory. Exiting...\n");
        exit(EXIT_FAILURE);
    }

    return p;
}

static inline FILE *
xfopen(const char *file)
{
    FILE *fp;

    fp = fopen(file, "r");
    if (!fp) {
        perror(file);
        exit(EXIT_FAILURE);
    }

    return fp;
}
21 août 2008 à 20:29:57

Dark-Side : comment tu gères une mémoire circulaire avec un zipper ?
21 août 2008 à 20:45:31

Citation : bluestorm

Dark-Side : comment tu gères une mémoire circulaire avec un zipper ?


Elle est pas circulaire, elle est infinie (du moins je ne trouve pas de meilleur dénomination).
En fait l'idée c'est que quand j'arrive au bout de la mémoire je rajoute des cases, c'est d'ailleurs à ça que servent les deux premières clauses de la « fonction brainfuck/4 ». :)
21 août 2008 à 20:49:25

Un code C++ ayant déjà été proposé, je tiens quand même à apporter ma pierre à l'édifice. Voici un compilateur BF écrit en BF.

>>>+++++[>+++++++++<-]>[>+>>+>>+>>+>>++>>++>>+>>+[<<]>-]+++++[>+++>>+++<
<<-]>++>>>>->>+>>+>>+++>>-->>>,+[>>>+++++++++++[<++++++++++++>-]<++[>>[>
]+[<]<-]>+++++++++++[<+++++++++++>-]<++++++[>>[+>]<[<]<-]<+++++[>+++++[>
>++++>+++>----->++>>----->---->+++>>---->++>---->-->-->+++>>----->+++>--
-->->+++>----->---->----->>----->----->>----->+++++>++++>++>>----->-->--
-->>----->++>----->-->---->>----->++>---->-->----->----->---->----->----
->---->>----->+>----->+++>++>---->+++>---->---->+++>>----->-->+++++>----
->++>----->+++>---->-->---->>+++++>+>----->+++>++>----->-->+++>----->---
->-->+>---->--->++++>>----->>+++>----->+++>---->>++++>----->+++>---->->+
++>+>+++++>>--->+>----->----->>--->+>----->----->>--->++>----->----->>--
->++>----->++++>++++>>--->+++>----->+++>+++[<]<-]>
>++>++>+>-->+>+>++>->->>++>-->>++>-->+>+>++>++>->>++>++>+>+>>++>+>+>-->+
>-->+>+>-->+>->+>+>>-->-->->+>+>-->>>++>++>+>>-->+>+>-->++>>++>-->++>++>
++>->->+>>-->+>++>+>++>++>-->-->->-->-->++>>++>+>++>-->+>-->>-->>++>-->-
>++>+>->+>++>++>+>++>+>++>++>->>-->>+>+>-->+>+>+>+>++>+>+>+>+>++>+>+>+>+
>->+>->->+>+>->+>++>++[<]<<-]>>
>+>>-->-->+>-->++>>>->-->->>>->>-->-->+>-->+>->>->++>+>->+>-->-->+>-->++
>-->-->->>>->++>-->+>>+>->->>+>->>->+>++>+>-->->>-->-->->-->+>++>>>+>>--
>++>-->++++++
>-->+>-->+>->>->>-->-->>>->-->->++>+>+>+>++>>+>+>++>+>-->+>+>++>
+>-->+>-->-->-->>+>++>+>->->+>++>->->->+>++>->->->++>++>-->->->->++>++>-
>->+>+[<]>[------.++++++>]<[[-]<]+++++++++++[<++++++++++++>-]<+[>>[>]+[<
]<-]>+++++++++++[<+++++++++++>-]<++++++[>>[+>]<[<]<-]<+++++[>+++++[>
>+>----->---->+++>>++++>----->->->+>----->-->+>+++>--->+++>+++>++++>++++
+>++>>--->----->->->-->-->->--->+++>-->+>+>+>+++++>--->+++>++>-->++++>>+
++++>-->++++>>+++++>--->++++>----->+++>-->----->+++>>+++++>+>+++>+>+>->-
>-->----->++++>>+++++>----->>+++++>----->+>----->->->----->++++>---->---
->---->----->+++>>----->+++>----->>++>---->+++>---->----->+++>----->----
->+++++>++>+>++++>+>+++>--->+++>--->+++>+++++>++>+++>----->----->>-->>--
--->----->>----->+++>--->----->+++>-->----->+++>>----->+++>->----->>++++
>----->+>+++++[<]<-]>
>-->++>++>->->>>-->-->-->>++>-->++>->+>++>++>->+>->->>-->>++>++>-->+>+>-
>->->-->->+>->>-->-->-->>-->->->>+>->+>->>+>+>->-->-->>->->->-->++>>>++>
-->+>++>>+>-->++>-->>>>-->++>-->++>-->+>+>>++>+>+>++>->-->+>-->>>->>-->>
-->+>->++>+>->->>-->+>+>+>-->+>+>+>->+>-->++>+>-->++>+>->++>+>->++>+>++>
+>>-->--[<]<<-]>>
>+>>++>>>-->->+>>++>->->++>-->+>++>++>+>>-->->>->++>-->-->->->->->-->++>
++>++>-->->>>-->++>++>++>-->-->++>-->>-->>>>+>-->>->++>+>++>++>++>++>-->
++>++>->++>>->>>++>-->++>-->++>++>++>->++>>>>-->+>>+>->>->->+>-->++>++>+
+++++++>+
+>++>+>++>++>+>>->>+>-->-->+>->+>>+>-->-->->+>-->+>->->-->->-->++>->->--
>->->+>->++>-[<]<[<]>[------.++++++>]----.----------.>[------.++++++>]<[
[-]<]<<<[-[[>+<<-<<-<<-<<-<<-<<-<<-<<->>>>>>>>>>>>>>>-]<[<<]>>[>-[>>-<<+
]>]>+++++++++[-[>+<-]>>+<[<+>-[->+<<-]>>[>]<<]>-[>+<-<+>]>>+<[<+>-[->+<<
-]>>[>]<<]>-[>+<-<->]<<[>->>-<<<-]>[.[+]]>>[<<<->>>+[-]]<<<+<<[>>[>>++++
+++<<-]>>+<<<<-]>>[-]++++++[>+++++++++++<-]>+<<[>++++++++++[>+++++++++++
+++<-]>++<<-[>>+++++<<-[>>[-]+++++++<<-]]]>>>[<+>-]<.[-]<<<]<<<[<<+<<+<<
+<<+<<+<<+<<+<<+>>>>>>>>>>>>>>>>-]<],+]]++++++++[>+++++>++++<<-]>+[<++++
+>-]<.>>.


Il n'est pas de moi. Il vient d'ici : http://esoteric.sange.fi/brainfuck/bf-source/prog/
Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
21 août 2008 à 20:57:19

J'ai rédigé une autre implémentation en OCaml. À la différence de celle d'asmanur, elle utilise un parseur (ce qui simplifie grandement le code) et va un peu plus loin que la simple interprétation (avec un prototype de compilateur pour brainfuck).

Comme le texte est un peu long, je l'ai mis sur internet : Implémentation d'un Brainfuck en OCaml. À priori, le programme est suffisamment commenté pour être lisible par quelqu'un qui ne connaît pas l'OCaml (à ce stade, c'est même du literate programming :-° ). Si vous avez des suggestions ou des remarques en tout genre, merci de me le faire savoir :) .
21 août 2008 à 20:58:17

C'est là qu'on voit pourquoi ce langage s'appelle Brainfuck...
Anonyme
21 août 2008 à 21:01:38

Comme le lien de lastsseldon est intéressant, je me permets de le redonner afin qu'il ne passe pas inaperçu dans le reste du topic.

http://lasts.no-ip.org/brainfuck.html

De rien, lasts.
Ton agent de presse qui t'aime.
21 août 2008 à 21:59:47

Dark-Side : comment tu gères une mémoire circulaire avec un zipper ?
21 août 2008 à 22:36:05

une version assez marrante en C:

gcc brainfuck.c --pedantic --ansi -O2 -O3 -Wall
valgrind ./a.out -c helloworld.bf

elle passe valgrind, -Wall --pedantic et --ansi sans probleme apparent.

pour lancer un programme :

./a.out -c fichier_source

on peut faire -o fichier output pour rediriger la sortie
on peut faire -i fichier input pour rediriger l'entree


#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <getopt.h>



#define BOUCLE_ERROR 1
#define MALLOC_ERROR 2
#define READING_ERROR 3
#define OPT_ERROR 4

#define F_DEBUG  1
/* stack */
struct stack {
  struct stack *prev;
  int content;
};

struct stack * newStack(){
  struct stack *s = malloc(sizeof(struct stack));
  if (!s){
    fputs("malloc error\n", stderr);
    exit(MALLOC_ERROR);
  }
  return s;
}

void stack_push(struct stack **s, int content){
  struct stack *s2 = newStack();
  s2->prev = *s;
  s2->content = content;
  *s=s2;
}

int stack_pop(struct stack **s){
  struct stack *s2 = (*s);
  int c = s2->content;
  *s=s2->prev;
  free(s2);
  return c;
}

/* liste doublement chainee */
struct mem {
  struct mem *prev, *next;
  unsigned char content;
};

struct mem * newMem(){
  struct mem *m = malloc(sizeof(struct mem));
  if (!m){
    fputs("malloc error\n", stderr);
    exit(MALLOC_ERROR);
  }
  m->prev = NULL;
  m->next = NULL;
  m->content = 0;
  return m;
}

void link_listes(struct mem * prev, struct mem *next){
  prev->next = next;
  next->prev = prev;
}

struct mem * prev(struct mem *m){
  struct mem *p;
  if (m->prev) return m->prev;
  p = newMem();
  link_listes(p, m);
  return p;
}

struct mem * next(struct mem *m){
  struct mem *n;
  if (m->next) return m->next;
  n = newMem();
  link_listes(m, n);
  return n;
}

void freeMem(struct mem *m){
  struct mem *m2, *m3;
  m3=m->next;
  while (m3){
    m2 = m3->next;
    free(m3);
    m3 = m2;
  }
  m3=m->prev;
  while (m3){
    m2 = m3->prev;
    free(m3);
    m3 = m2;
  }
  free(m);
}


int brainfuck(char * code, int len, int flags, FILE *out, FILE * in){
  int i, j;
  struct mem *m = newMem();
  struct stack *s = newStack();
  int * jmps;
  jmps = malloc(len * sizeof(int));
  if (!jmps){
    freeMem(m);
    fputs("malloc error\n", stderr);
    exit(MALLOC_ERROR);
  }
  s->content = -1;
  for(i=0;i<len;i++){
    if (code[i]=='['){
      stack_push(&s, i);
    }else if(code[i]==']'){
      j=stack_pop(&s);
      if ( j == -1 ) return BOUCLE_ERROR;
      jmps[i]=j-1; jmps[j]=i;
    }
  }
  if ( s->content != -1 ) return BOUCLE_ERROR;
  free(s);
  for(i=0;i<len;i++){
    if (flags & F_DEBUG) fprintf(out, "\t %c %d\n", code[i], i);
    switch(code[i]){
      case 0: goto fin;
      case '+': m->content++; break;
      case '-': m->content--; break;
      case '<': m = prev(m); break;
      case '>': m = next(m); break;
      case '.': fputc(m->content, out); break;
      case ',': m->content = fgetc(in); break;
      case '[': if (m->content) break;
        case ']': i=jmps[i]; break;
    }
  }
  fin:
  freeMem(m);
  free(jmps);
  return 0;
}

int main(int argc, char **argv){

  int flags = 0;
  int c;
  FILE *out = stdout;
  FILE *in = stdin;
  FILE *code = NULL;
  size_t length;
  int err;
  char * content;
  while ( (c=getopt(argc, argv, "do:i:c:")) != -1 ){
    switch (c){
      case 'd':
        flags = flags | F_DEBUG;
        break;
      case 'o':
        out = fopen(optarg, "w");
        if (out == NULL){
          fprintf(stderr, "output error (%s)\n", optarg);
          return READING_ERROR;
        }
        break;
      case 'i':
        in = fopen(optarg, "r");
        if (in == NULL){
          fprintf(stderr, "input error (%s)\n", optarg);
          return READING_ERROR;
        }
        break;
      case 'c':
        code = fopen(optarg, "r");
        break;
      case '?':
        if (isprint (optopt))
          fprintf (stderr, "Unknown option `-%c'.\n", optopt);
        else
          fprintf (stderr, "Unknown option character `\\x%x'.\n", optopt);
        return OPT_ERROR;
      default:
        abort ();
    }
  }
  if (code == NULL){
    fputs("code file error\n", stderr);
    exit(1);
  }
  fseek(code, 0, SEEK_END);
  length=ftell(code);
  content=malloc(length);
  if (!content){
    fputs("malloc error\n", stderr);
    return MALLOC_ERROR;
  }
  fseek(code, 0, SEEK_SET);
  c = fread (content,1,length,code);
  fclose(code);
  if (c != length) {
    fputs("Reading error\n", stderr);
    return READING_ERROR;
  }
  if ( (err=brainfuck(content, length, flags, out, in)) ){
    fprintf(stderr, "erreur (%d)\n", err);
    return err;
  }
  free(content);
  return 0;
}
21 août 2008 à 23:09:05

Citation : bluestorm

Dark-Side : comment tu gères une mémoire circulaire avec un zipper ?


Elle est pas circulaire, elle est infinie (du moins je ne trouve pas de meilleur dénomination).
En fait l'idée c'est que quand j'arrive au bout de la mémoire je rajoute des cases, c'est d'ailleurs à ça que servent les deux premières clauses de la « fonction brainfuck/4 ». :)

Une impression de déjà vu ? Mais non vous vous faites des idées.
22 août 2008 à 0:01:01

Hey hey ! Super topic !

Bon, j'ai fait une version Ruby qui n'est rien de plus qu'une pâle copie de la version PHP (avec moins de "$"...). Comme ça n'a que peu d'intérêt, je la colle .

Edit : version buggée. Nouvelle version ici.

J'ai essayé de voir s'il y avait moyen d'avoir une approche OO là-dessus, mais j'avoue ne pas être arrivé à quelque chose d'acceptable (quel intérêt de plus sur un code aussi court ?). Ce qui est intéressant par contre c'est qu'on constate une réelle différence entre les versions procédurales et les versions fonctionnelles.

L'article de Lasts me paraît aussi très enrichissant.

PS : dis donc Dark, comment tu gères une mémoire circulaire avec un zipper ?

Encore bravo pour le topic les gars !
22 août 2008 à 0:18:01

Bonjour à tous,

Désolé, je ne suis pas capable de faire quelque chose, je n'ai pas le niveau. En revanche, il y a un code que je n'arrive pas à faire fonctionner ou j'ai mal compris un truc, ce qui est fort possible. C'est le code Python de wgmpgp.

À wgmpgp : Que doit-il se passer une fois qu'on a lancé le script en ligne de commande. Personnellement, j'ai des nombres grandissant qui s'affichent indéfiniment. J'imagine que ce n'est pas le comportement voulu pour un interpréteur, non ?

Merci d'avance.
22 août 2008 à 0:28:46

Citation : sisco

Bonjour à tous,

Désolé, je ne suis pas capable de faire quelque chose, je n'ai pas le niveau. En revanche, il y a un code que je n'arrive pas à faire fonctionner ou j'ai mal compris un truc, ce qui est fort possible. C'est le code Python de wgmpgp.

À wgmpgp : Que doit-il se passer une fois qu'on a lancé le script en ligne de commande. Personnellement, j'ai des nombres grandissant qui s'affichent indéfiniment. J'imagine que ce n'est pas le comportement voulu pour un interpréteur, non ?

Merci d'avance.


Sisi, le code Brainfuck interprété affiche la suite de Fibonacci. C'est tout à fait voulu.
22 août 2008 à 0:31:36

Ah mille excuses. Charge à moi de changer le contenu de variable code pour qu'elle fasse autre chose (mettre un "Hello World" par exemple). C'est bien ça ?

Merci pour la réponse rapide.
22 août 2008 à 0:33:18

Exactement. J'aurais pu lire le code depuis un fichier ou depuis stdin, mais j'ai choisi la solution de facilité, a.k.a. le code en dur dans le script (en même temps, ça rajoute pas non plus une complexité extrème de lire depuis un fichier).
22 août 2008 à 0:36:25

euh... la gestion des options, c'est un truc assez chiant au final...
22 août 2008 à 0:37:53

Ok merci. J'ai juste un petit souci en mettant le code du "Hello world".

C'est bien ceci, non ? Chez moi, ça plante... [edit] Soyons précis : si je remplace le contenu de la variable code par ce qui est ci-dessous dans le code bf.py, ça plante.

code = '''++++++++++
[                 
   >+++++++>++++++++++>+++>+<<<<-
]
                 
>++.                     
>+.                     
+++++++.                
.                         
+++.                      
>++.                      
<<+++++++++++++++.        
>.                        
+++.                      
------.                   
--------.                 
>+.                       
>.      
]'''
22 août 2008 à 0:57:49

Bah... en même temps ton code est pas valide. T'as une fin de boucle louche à la dernière ligne, qui correspond à aucun début de boucle.
22 août 2008 à 1:01:12

Mais oui ! Quel idiot je suis. Je ne sais pas ce que j'ai fichu.

C'est bon ça marche impeccable. Merci encore et désolé d'avoir mis en cause injustement ton code python. :)

A+

Edit

Pour plus de lisibilité voici le code correct d'un "Hello World! en BrainFuck :
++++++++++
[                 
   >+++++++>++++++++++>+++>+<<<<-
]
                 
>++.                     
>+.                     
+++++++.                
.                         
+++.                      
>++.                      
<<+++++++++++++++.        
>.                        
+++.                      
------.                   
--------.                 
>+.                       
>.
</span>

[Atelier tous langages] Codez un interpréteur de Brainfuck

× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
  • Editeur
  • Markdown