Créer un compilateur/interpréteur Brainfuck

#include <fstream>
#include <array>
#include <stack>
#include <vector>
#include <cstdint>
#include <cstdio>

int main(int argc, char** argv)
{
    if(argc != 2)
    {
        return 0;
    }
    
    std::vector<char> program;
    unsigned int progPtr = 0;
    std::array<uint8_t, 30000> memory;
    memory.fill(0);
    unsigned int pointer = 0;
    std::stack<unsigned int> loops;
    
    std::ifstream file(argv[1]);
    while(!file.eof())
    {
        program.push_back(file.get());
    }
    file.close();
    
    while(progPtr < program.size())
    {
        char c = program[progPtr++];
        
        switch(c)
        {
            case '+':
                memory[pointer]++;
                break;
            case '-':
                memory[pointer]--;
                break;
            case '<':
                pointer--;
                if(pointer < 0)
                    pointer += 30000;
                break;
            case '>':
                pointer = (pointer + 1) % 30000;
                break;
            case '[':
                if(memory[pointer] == 0)
                {
                    int counter = 1;
                    while(counter > 0)
                    {
                        c = program[progPtr++];
                        if(c == '[')
                            counter++;
                        else if(c == ']')
                            counter--;
                    }
                }
                else
                {
                    loops.push(progPtr);
                }
                break;
            case ']':
                if(memory[pointer] == 0)
                {
                    loops.pop();
                }
                else
                {
                    progPtr = loops.top();
                }
                break;
            case '.':
                std::putchar(memory[pointer]);
                break;
            case ',':
                memory[pointer] = std::getchar();
                break;
            default:
                /* comment */;
        }
    }
    
    return 0;
}

#!/chemin/vers/un/interpréteur/brainfuck

________________________________________________________________________________

This is a Brainfuck interpreter written in Brainfuck⋅

Thus it requires a Brainfuck implementation to be run correctly⋅

The following assumptions are made on the Brainfuck implementation used
to run this interpreter:
  — the tape does not wrap and is initialized with zeros;
  — either negative numbers or integer wrapping is supported;
  — EOF is traduced by either −1 or the “no change” policy⋅

The specifications of the interpreted language are drawn from those of the
implementation running this interpreter; with the following alterations:
  — the tape memory is a quarter of that of this interpreter;
  — there shall be less instructions than a quarter of the number of cells
    in the interpreter’s tape;
  — there shall be less nested loops than the maximal value of a cell;
  — EOF is traduced by −1;
  — the source code follows an ASCII‐compatible charset;
  — each opening bracket must match a single closing bracket; otherwise
    an error “out of tape” will be issued if the implementation running
    this interpreter produces this kind of errors⋅
________________________________________________________________________________


structure of the tape: ( code | ptr | tmp | data )*

codes:
  −1 = “marked” rbracket (ie⋅ which has to be translated back to code 2)
   0 = end or “active” lbracket (ie⋅ beginning of a loop currently being executed)
   1 = lbracket
   2 = rbracket
   3 = rmove
   4 = lmove
   5 = dot
   6 = minus
   7 = comma
   8 = plus

LEXING

>>>>
>
-,+[-
  <+>
  >+++++++++++++[-<------->]< (91 decrementations)
  [<+> :not a lbracket
      --
      [<+> :not a rbracket
          >++++++[-<+++++>]<+ (31 incrementations)
          [<+> :not a rmove
              ++
              [<+> :not a lmove
                  ++++++++++++++
                  [<+> :not a dot
                      +
                      [<+> :not a minus
                          +
                          [<+> :not a comma
                              +
                              [<[-]> :not a plus (ie⋅ nothing)
                                  [-]<<<<
                              ]
                          ]
                      ]
                  ]
              ]
          ]
      ]
  ]
  >>>>
-,+]

rewind:
<
<<<<[<<<<]
init first cells:
+ > 0 > 0 > 0 >
_ > +

PARSING

<
[
switch instruction code:
  
“marked” rbracket?
  +
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      <+++> :set code 2 (accounting for the current parsing state)
  -]+<
  
lbracket?
  --
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
      ->+>
      [<-]<[<]> (test data=0 in tmp with ptr=0)
      <+
      {>[->>>>+<<<<]<}>>>>[[{>[->>>>+<<<<]<}>>>>]{>[->>>>+<<<<]<}>>>>]
      {>[-<<<<+>>>>]<}<<<<[{>[-<<<<+>>>>]<}<<<<]{>[->>>>+<<<<]<}>>>>-
      [+{>[-<<<<+>>>>]<}<<<<{>[-<<<<+>>>>]<}<<<<-]+ (switch position & transfer tmp)
      if data was =0:
      >[-
          <<+>> :restore code 1 for the lbracket
          + :init the nested loops counter (stored in tmp) to 1
          jump to the matching rbracket:
          [
              [->>>>+<<<<] :transfer counter
              <
              >>>>[<<<<->>>>-]+ (move right)
              >
              +<-<             :ptr=0 & counter augmented by 1
              if code≠1 → decrement counter:
              -[>>-<]>[<]<
              >>-<<            :counter restored
              if code≠2 → increment counter:
              -[>>+<]>[<]<
              ++
              >+>              :ptr=1
          ]
          <<---->> :set code −1 for a marked rbracket (accounting for the
                    current parsing state); this prevents the rbracket from
                    being evaluated during this very parsing loop 
      <->]<
      else:
      [
          <-> :mark the lbracket as active
      -]+
  -]+<
  
rbracket?
  -
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
      ->+>
      [<-]<[<]> (test data=0 in tmp with ptr=0)
      <+
      {>[->>>>+<<<<]<}>>>>[[{>[->>>>+<<<<]<}>>>>]{>[->>>>+<<<<]<}>>>>]
      {>[-<<<<+>>>>]<}<<<<[{>[-<<<<+>>>>]<}<<<<]{>[->>>>+<<<<]<}>>>>-
      [+{>[-<<<<+>>>>]<}<<<<{>[-<<<<+>>>>]<}<<<<-]+ (switch position & transfer tmp)
      if data was =0:
      >[-
          <<
          - :mark the current rbracket to jump back to it
          jump to the last active lbracket:
          [
              >
              <<<<[>>>>-<<<<-]+ (move left)
              <
          ]
          + :set code 1 for a normal lbracket
          jump back to the rbracket:
          +[-
              >
              >>>>[<<<<->>>>-]+ (move right)
              <
          +]
          >>
      <->]<
      else:
      [
          <
          ++ :restore code 2 for the rbracket
          jump to the last active lbracket:
          [
              >
              <<<<[>>>>-<<<<-]+ (move left)
              <
          ]
          -- :account for the current parsing state in the lbracket’s code
          >
      -]+
  -]+<
  
rmove?
  -
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
      >>>>[<<<<->>>>-]+ (move right)
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
  -]+<
  
lmove?
  -
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
      <<<<[>>>>-<<<<-]+ (move left)
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
  -]+<
  
dot?
  -
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
      >>.<<
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
  -]+<
  
minus?
  -
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
      >>-<<
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
  -]+<
  
comma?
  -
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
      >>[-]-,<< :enforce −1 for EOF
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
  -]+<
  
plus?
  -
  [>-]>[>]< (test code=0 in ptr with tmp=0)
  [
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
      >>+<<
      >>>>[[>>>>]>>>>]<<<<[<<<<]>>>>-[+<<<<<<<<-]+ (switch position between code/data)
  -]+<
  
  ++++++++
  >
  >>>>[<<<<->>>>-]+ (move right)
  <
]

package info.kisai.brainfuck;

import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

/**
 * Interpréteur BrainFuck
 * @author SpaceFox
 */
public class BrainFuck {

  // Paramètres de la machine
  private int tailleMemoire;
  private int tailleValeur;

  // Variables
  private char[] programme;
  private StringBuilder sortie = new StringBuilder();
  private char[] memoireTab;
  private int pointeurMaxMemoire;

  private char[] programmeCompile;
  private int[] parametresCompile;

  /**
   * Constructeur unique.<br/>
   * Initialise la mémoire et les tailles maximales.
   * @param tailleMemoire la taille max de la mémoire, en cases. Aucune taille max si <code>null</code>.
   * @param tailleValeur la taille max d'une case. Aucune taille max si <code>null</code>.
   */
  public BrainFuck(Integer tailleMemoire, Integer tailleValeur) {
      if (tailleMemoire == null) {
          this.tailleMemoire = Integer.MAX_VALUE;
          initMemoire(30000); // Purement arbitraire, sera augmenté si besoin
      } else {
          this.tailleMemoire = tailleMemoire;
          initMemoire(tailleMemoire);
      }

      if (tailleValeur == null) {
          this.tailleValeur = Character.MAX_VALUE;
      } else {
          this.tailleValeur = tailleValeur;
      }
  }

  public void setProgramme(char[] programme) {
      this.programme = programme;
  }

  public void setProgramme(String programme) {
      setProgramme(programme.toCharArray());
  }

  /**
   * Pour debug. Utile pour les versions étendues (verif de la transformation).
   * @return le programme en brainfuck.
   */
  public String getProgramme() {
      return String.valueOf(programme);
  }

  /**
   * Exécute le programme et renvoie le résultat sous forme de chaîne. Les entrées sont lues sur l'entrée passée en
   * paramètre.
   * @param entreeStream un flux d'entrée quelconque.
   * @return le résultat du programme.
   */
  public String execute(InputStream entreeStream) {

        compile();

      int longueurProgramme = programmeCompile.length;
      int iInstruction = 0;
      int pointeur = 0;
        do {
          switch (programmeCompile[iInstruction]) {
              case '+':
              case '-':
                  memoireTab[pointeur] = incrementeMemoire(pointeur, parametresCompile[iInstruction]);
                  break;
              case '>':
              case '<':
                  pointeur = incrementePointeur(pointeur, parametresCompile[iInstruction]);
                  break;
              case '0':
                  resetMemoire(pointeur);
                  break;
              case 'a':
                  addition(pointeur);
                  break;
              case 'm':
                  copie(pointeur);
                  break;
              case '.':
//                    sortie.append(getMemoireAt(pointeur));
                  System.out.print(getMemoireAt(pointeur));
                  break;
              case ',':
                  memoireTab[pointeur] = litEntree(entreeStream);
                  break;
              case '[':
                  iInstruction = sautConditionnelComp(iInstruction, pointeur);
                  break;
              case ']':
                  iInstruction = retourConditionnelComp(iInstruction, pointeur);
                  break;
              default:
                  // Autres cas --> ignorés (commentaires)
                  break;
          }
          // Pour debug
//            System.out.println(
//                    "   instruction n°" + iInstruction
//                + " " + programmeCompile[iInstruction]
//                + " (" + parametresCompile[iInstruction]
//                + ") ==> pointeur " + pointeur
//                + " --> valeur " + Integer.valueOf(memoireTab[pointeur]));

          iInstruction++;
      } while (iInstruction < longueurProgramme);

      return sortie.toString();
  }


  private void compile() {

      char[] progSansComm = preProcesseur(supprimeCommentaires());

      final int tailleProg = progSansComm.length;
      char[] progTmp = new char[tailleProg];
      int[] paramTmp = new int[tailleProg];

      // Compilation
      int iProg = 0;
      int tailleProgComp = 0;
      int compteur = 0;
      char instr;
      char instrPrec = '\u0000';

      while (iProg < tailleProg) {

          instr = progSansComm[iProg];

          // Instructions cumulables
          if (    (instr != instrPrec)
              &&  (instrPrec == '+' || instrPrec == '-' || instrPrec == '>' || instrPrec == '<')
          ) {
              progTmp[tailleProgComp] = instrPrec;
              paramTmp[tailleProgComp] = compteur;
              tailleProgComp++;
              compteur = 0;
          }

          // Instructions à ajouter direct
          if (    instr == '['|| instr == ']' || instr == '.' || instr == ','
              ||  instr == '0' || instr == 'a' || instr == 'm') {
              progTmp[tailleProgComp] = instr;
              tailleProgComp++;
              compteur = 0;
          }

          // Modif du compteur si besoin
          if (instr == '+' || instr == '>') {
              compteur++;
          }
          else if (instr == '-' || instr == '<') {
              compteur--;
          }
          instrPrec = instr;
          iProg++;
      }

      // Correspondances
      for (int iCrochetOuvrant = 0; iCrochetOuvrant < tailleProgComp; iCrochetOuvrant++) {
          if (progTmp[iCrochetOuvrant] == '[') {
              int nbCrochets = 1;
              int iCrochetFermant = iCrochetOuvrant;
              while (nbCrochets > 0) {
                  iCrochetFermant++;
                  if (progTmp[iCrochetFermant] == '[') {
                      nbCrochets++;
                  } else if(progTmp[iCrochetFermant] == ']') {
                      nbCrochets--;
                  }
              }
              // Correspondance [ --> ]
              paramTmp[iCrochetOuvrant] = iCrochetFermant;
              // Correspondance ] --> [
              paramTmp[iCrochetFermant] = iCrochetOuvrant;
          }
      }

      // Copie dans les tableaux généraux
      programmeCompile = new char[tailleProgComp];
      parametresCompile = new int[tailleProgComp];
      System.arraycopy(progTmp, 0, programmeCompile, 0, tailleProgComp);
      System.arraycopy(paramTmp, 0, parametresCompile, 0, tailleProgComp);
//        System.out.println("Taille compilée : " + tailleProgComp);
  }

  /**
   * Récupère le caractère dans la mémoire. Initialise la mémoire jusqu'à ce pointeur si besoin.
   * @param pointeur l'adresse de la case à récupérer.
   * @return le contenu de cette case.
   */
  private char getMemoireAt(int pointeur) {
      if (pointeur > pointeurMaxMemoire) {
          initMemoire(pointeur);
      }
      return memoireTab[pointeur];
  }

  /**
   * Incrémente le pointeur de manière sécurisée.
   * @param pointeur la valeur actuelle du pointeur.
   * @return <code>pointeur + 1</code> ou <code>0</code> en cas de dépassement de la taille max de la mémoire.
   */
  private int incrementePointeur(int pointeur, int i) {
      return ((pointeur + i) % tailleMemoire);
  }

  /**
   * Incrémente la valeur de la case mémoire de manière sécurisée.
   * @param pointeur l'adresse de la case à incrémenter.
   * @return <code>valeur + 1</code> ou <code>0</code> en cas de dépassement de la taille max d'une case.
   */
  private char incrementeMemoire(int pointeur, int i) {
      return (char) ((getMemoireAt(pointeur) + i) % tailleValeur);
  }

  /**
   * Lit un caractère sur l'entrée.<br/>
   * Un problème de lecture ne provoque pas d'erreur mais le caractère <code>0x0000</code>
   * @param entreeStream le flux d'entrée sur lequel lire le caractère.
   * @return le premier caractère de l'entrée, ou <code>0x0000</code> en cas d'erreur.
   */
  private char litEntree(InputStream entreeStream) {
      InputStreamReader entreeReader = new InputStreamReader(entreeStream);
      char[] entree = new char[1];
      try {
          entreeReader.read(entree);
      } catch (IOException e) {
          entree[0] = 0;
      }
      return entree[0];   // La seule qui existe
  }

  /**
   * Donne l'index de l'instruction suivante, selon le résultat du saut conditionnel.
   * @param iInstruction l'index de l'instruction courante.
   * @param pointeur le pointeur pour la condition
   * @return l'index de l'instruction courante si la valeur à la case indiquée par le pointeur est différente de
   * <code>0x0000</code>.<br/>
   * L'index de l'instruction suivant le crochet fermant correspondant sinon.
   */
  private int sautConditionnelComp(int iInstruction, int pointeur) {
      if (getMemoireAt(pointeur) == 0) {
          return parametresCompile[iInstruction];
      }
      return iInstruction;
  }


  /**
   * Donne l'index de l'instruction suivante, selon le résultat du saut conditionnel.
   * @param iInstruction l'index de l'instruction courante.
   * @param pointeur le pointeur pour la condition
   * @return l'index de l'instruction courante si la valeur à la case indiquée par le pointeur est égale à
   * <code>0x0000</code>.<br/>
   * L'index de l'instruction suivant le crochet ouvrant correspondant sinon.
   */
  private int retourConditionnelComp(int iInstruction, int pointeur) {
      if (getMemoireAt(pointeur) != 0) {
          return parametresCompile[iInstruction];
      }
      return iInstruction;
  }

  /**
   * Initialise la mémoire (remplissage par des 0) jusqu'à la taille indiquée.<br/>
   * Seule la partie entre la taille courante et la taille spécifiée est initialisée, pour pouvoir agrandir la mémoire
   * en cas de "mémoire infinie".<br/>
   * Cette méthode ne fait rien si la taille voulue est plus petite que la taille actuelle.
   * @param taille la taille voulue pour la mémoire.
   */
  private void initMemoire(int taille) {
      char[] newMemoireTab = new char[taille];

      if (memoireTab == null) {
          memoireTab = new char[taille];
      }
      System.arraycopy(memoireTab, 0, newMemoireTab, 0, memoireTab.length);
      // Initialisation du reste
      for (int i = memoireTab.length; i < taille; i++) {
          newMemoireTab[i] = 0;
      }
      memoireTab = newMemoireTab;
      pointeurMaxMemoire = memoireTab.length - 1;
  }

  private char[] supprimeCommentaires() {
//        System.out.println("Taille avec commentaires : " + programme.length);
      char[] tmp = new char[programme.length];
      int progTailleSansComm = 0;
      for (char c : programme) {
          if (c == '+' || c == '-' || c == '>' || c == '<'  || c == '[' || c == ']' || c == '.' || c == ',') {
              tmp[progTailleSansComm++] = c;
          }
      }
      char[] retour = new char[progTailleSansComm];
      System.arraycopy(tmp, 0, retour, 0, progTailleSansComm);
//        System.out.println("Taille sans commentaires : " + progTailleSansComm);
      return retour;
  }

  private char[] preProcesseur(char[] supprimeCommentaires) {
      String str = new String(supprimeCommentaires);
//        System.out.println("Avant préprocesseur : " + str);

      // RAZ cellule
      str = str.replaceAll("\\[-\\]", "0");
      // Addition
      str = str.replaceAll("\\[->\\+<\\]", "a");
      // Déplacement
      str = str.replaceAll(">\\[-\\]<\\[->\\+<\\]", "m");

//        System.out.println("Après préprocesseur : " + str);
      return str.toCharArray();
  }

  private void resetMemoire(int pointeur) {
      memoireTab[pointeur] = 0;
  }

  private void addition(int pointeur) {
      memoireTab[pointeur + 1] += memoireTab[pointeur];
      memoireTab[pointeur] = 0;
  }

  private void copie(int pointeur) {
      memoireTab[pointeur + 1] = memoireTab[pointeur];
      memoireTab[pointeur] = 0;
  }
}

package info.kisai.brainfuck;


/**
 *
 * @author SpaceFox
 */
public class CLI {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {

      long debut = System.currentTimeMillis();

      /*
       * Test BrainFuck
       */
      BrainFuck bf = new BrainFuck(30000, 65536);

      bf.setProgramme("++++++++++[ >+++++++>+++++++        +++>+++>+<<<<-]>++.>+.+++    ++++..+++.>++.<<+++++++++++++++.> .+++.------         .-        -------.>+.>.");

      String sortie = bf.execute(System.in);
      System.out.println(sortie);
      System.out.println("Temps : " + (System.currentTimeMillis() - debut) + " ms");
    }

}

#include <fstream>
#include <array>
#include <stack>
#include <vector>
#include <cstdint>
#include <cstdio>

int main(int argc, char** argv)
{
    if(argc != 2)
    {
        return 0;
    }
    
    std::vector<char> program;
    
    std::ifstream file(argv[1]);
    while(!file.eof())
    {
        program.push_back(file.get());
    }
    file.close();
    
    std::ofstream output("output.asm");
    output << "section .data\n"
            << "buffer: times 30000 db 0\n"
            << "\n"
            << "section .text\n"
            << "    global _main\n"
            << "    extern _putchar\n"
            << "\n"
            << "_main:\n"
            << "    mov ecx, 0\n";
    
    std::vector<std::pair<char, int>> instructions;
    for(char c : program)
    {
        switch(c)
        {
            // smashable instructions
            case '+':
            case '-':
            case '<':
            case '>':
                if(instructions.size() > 0 && instructions.back().first == c)
                    instructions.back().second++;
                else
                    instructions.push_back(std::make_pair(c, 1));
                break;
            // non-smashable instructions
            case '[':
            case ']':
            case '.':
            case ',':
                instructions.push_back(std::make_pair(c, 1));
                break;
            default:
                /* comment */;
        }
    }
    
    int loopCount = 0;
    std::stack<int> currentLoops;
    for(auto const & pair : instructions)
    {
        switch(pair.first)
        {
            case '+':
                if(pair.second == 1)
                    output << "    inc byte [buffer+ecx]\n";
                else
                    output << "    add byte [buffer+ecx], " << pair.second << "\n";
                break;
            case '-':
                if(pair.second == 1)
                    output << "    dec byte [buffer+ecx]\n";
                else
                    output << "    sub byte [buffer+ecx], " << pair.second << "\n";
                break;
            case '<':
                if(pair.second == 1)
                    output << "    dec ecx\n";
                else
                    output << "    sub ecx, " << pair.second << "\n";
                break;
            case '>':
                if(pair.second == 1)
                    output << "    inc ecx\n";
                else
                    output << "    add ecx, " << pair.second << "\n";
                break;
            case '[':
                output << "    cmp byte [buffer+ecx], 0\n";
                output << "    je .loopend" << loopCount << "\n";
                output << " .loopstart" << loopCount << ":\n";
                currentLoops.push(loopCount);
                loopCount++;
                break;
            case ']':
                output << "    cmp byte [buffer+ecx], 0\n";
                output << "    jne .loopstart" << currentLoops.top() << "\n";
                output << " .loopend" << currentLoops.top() << ":\n";
                currentLoops.pop();
                break;
            case '.':
                output << "    push ecx\n";
                output << "    push dword [buffer+ecx]\n";
                output << "    call _putchar\n";
                output << "    add esp, 4\n";
                output << "    pop ecx\n";
                break;
            case ',':
                output << "    push ecx\n";
                output << "    call _putchar\n";
                output << "    mov byte [buffer+ecx], eax\n";
                output << "    pop ecx\n";
                break;
            default:
                /* comment */;
        }
    }
    output << "    ret\n";
    output.close();
    
    return 0;
}

section .data
buffer: times 30000 db 0

section .text
    global _main
    extern _putchar

_main:
    mov ecx, 0
    add byte [buffer+ecx], 10
    cmp byte [buffer+ecx], 0
    je .loopend0
 .loopstart0:
    inc ecx
    add byte [buffer+ecx], 7
    inc ecx
    add byte [buffer+ecx], 10
    inc ecx
    add byte [buffer+ecx], 3
    inc ecx
    inc byte [buffer+ecx]
    sub ecx, 4
    dec byte [buffer+ecx]
    cmp byte [buffer+ecx], 0
    jne .loopstart0
 .loopend0:
    inc ecx
    add byte [buffer+ecx], 2
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    inc ecx
    inc byte [buffer+ecx]
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    add byte [buffer+ecx], 7
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    add byte [buffer+ecx], 3
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    inc ecx
    add byte [buffer+ecx], 2
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    sub ecx, 2
    add byte [buffer+ecx], 15
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    inc ecx
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    add byte [buffer+ecx], 3
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    sub byte [buffer+ecx], 6
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    sub byte [buffer+ecx], 8
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    inc ecx
    inc byte [buffer+ecx]
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    inc ecx
    push ecx
    push dword [buffer+ecx]
    call _putchar
    add esp, 4
    pop ecx
    ret

import Data.Char

main = do
   code <- readFile "mandelbrot.bf"
   putStr $ bf code mem [] "" ""

mem = (repeat 0, 0, repeat 0)

bf :: String -> ([Int], Int, [Int]) -> [String] -> String -> String -> String
bf [] _ _ out _ = reverse out
bf c@(tc:qc) mem@(l@(tl:ql), cur, r@(tr:qr)) b out inp =
   case tc of
       '+' -> bf qc (l, cur+1, r) b out inp
       '-' -> bf qc (l, cur-1, r) b out inp
       '<' -> bf qc (ql, tl, cur:r) b out inp
       '>' -> bf qc (cur:l, tr, qr) b out inp
       '[' ->
           if cur == 0 then
               bf (skipb c 0) mem b out inp
           else
               bf qc mem (qc:b) out inp
       ']' ->
           if cur == 0 then
               bf qc mem (tail b) out inp
           else
               bf (head b) mem b out inp
       '.' -> bf qc mem b ((chr cur):out) inp
       ',' -> bf qc (l, ord (head inp), r) b out (tail inp)
       _   -> bf qc mem b out inp

skipb [] _ = []
skipb (t:q) n
   | n == 0 = q
   | t == '[' = skipb q (n+1)
   | t == ']' = skipb q (n-1)
   | otherwise = skipb q n

type optimization_token =
  MoveAdd of int * int
(* AddTo n m ajoute m fois la valeur de la cellule courante à la cellule de distance n *)
 | AddTo of int * int

type token = 
   Add of int
 | Move of int
 | Print
 | Read
 | Assign of int
 | Loop of token list
 | Macro of optimization_token

let string_of_t (ops : token) : string =
 let open Printf in
 let rec to_string indent = function
   | Move x -> sprintf "%sMove(%d)" indent x
   | Add i -> sprintf "%sAdd(%d)" indent i
   | Print -> sprintf "%sPrint" indent
   | Read -> sprintf "%sRead" indent
   | Assign x -> sprintf "%sAssign(%d)" indent x
   | Loop nodes ->
       sprintf "%sLoop <<\n%s\n%sLoop >>"
         indent
         (String.concat "\n" (List.map (to_string ("| "^indent)) nodes))
         indent
   | Macro (MoveAdd (x,y)) -> sprintf "%sMoveAdd(%d, %d)" indent x y
   | Macro (AddTo (x,y)) -> sprintf "%sAddTo (%d, %d)" indent x y
 in to_string "" ops

(* Afin d’implémenter une mémoire circulaire (faute d’avoir une mémoire 
  infinie :-() *)
let rec new_pos (key : int) (p : int) (len : int) : int =
 if (p + key) >= 0 then (p + key) mod len
 else len + (p+key) mod len

(* optimiser les boucles dans lesquelles la somme des mouvements égale zéro, où la cellule de départ de 
boucle est décrémentée de -1 et qui ne contiennent que des instructions Move et Add. *)
let optimize_simple_loop (instruction : token) : token list =
 let rec aux (content : token list) (count_move : int) : token list =
   match content with
   | [] -> Assign 0 :: []
   (* On ignore les incrémentations sur la cellule d’entrée de la boucle, que l’on remet à
     zéro à la fin (voir deux lignes plus haut). *)
   | Macro(MoveAdd (x, y)) :: xs when x + count_move = 0 -> aux xs 0
   | Add x :: xs -> aux xs 0
   | Macro(MoveAdd (x, y)) :: xs -> Macro(AddTo (count_move + x, y)) :: aux xs(count_move + x)
   | Move x :: xs -> aux xs (count_move + x)
   
   | other :: xs -> failwith ( string_of_t (other) ^ "optimize_simple_loop isnt applied to a simple-loop statement")
 in match instruction with
    | Loop xs -> aux xs 0
    | _  -> failwith "optimize_simple_loop isnt applied to a loop statement"

let is_simple_loop (instruction : token) : bool =
 let rec aux (content : token list) (count_move : int) (count_add : int) =
   match content with
  | [] -> count_move = 0 && count_add = (-1)
   (* count_add permet de compter le nombre le nombre d’incrémentations qui sont faites
      sur la cellule d’entrée de la boucle *)
   | Macro(MoveAdd (x, y)) :: xs when x + count_move = 0 -> aux xs 0 (count_add + y)
   (* Un Add x isolé est forcément devant toute instruction < ou >, on est donc sur 
      la cellule d’entrée de la boucle *)
   | Add x :: xs -> aux xs 0 (count_add + x)
   | Macro(MoveAdd (x, y)) :: xs -> aux xs (count_move + x) count_add
   | Move x :: xs -> aux xs (count_move + x) count_add
   | _ -> false
 in match instruction with
    | Loop content -> aux content 0 0
    | _ -> false

let rec optimize (instructions : token list) : token list =
 match instructions with
 | [] -> []
 | Move x :: Add y :: xs -> Macro(MoveAdd (x, y)) :: optimize xs
 | Loop xs :: ys -> 
   let min_optimized = Loop (optimize xs) in
   if is_simple_loop min_optimized then (optimize_simple_loop min_optimized) @ optimize ys (* pas joli joli :/ *)
   else min_optimized :: optimize ys
 | Assign 0 :: Add x :: xs -> Assign x :: optimize xs
 | other :: xs -> other :: optimize xs

let len = 30000
let memory = Array.make len 0
let cursor = ref 0
let rec eval (program : token list) : unit =
 let aux' = function
   | Macro(MoveAdd (x, y)) -> cursor := new_pos x !cursor len; memory.(!cursor) <- memory.(!cursor) + y;
   | Move x -> cursor := new_pos x !cursor len
   | Add x -> memory.(!cursor) <- memory.(!cursor) + x
   | Print -> print_char (Char.chr memory.(!cursor))
   | Read -> let c = Scanf.scanf " %c" (fun x -> x) in memory.(!cursor) <- Char.code c
   | Assign x -> memory.(!cursor) <- x;
   | Macro(AddTo (x, y)) -> let i = new_pos x !cursor len in memory.(i) <- memory.(i) + y * memory.(!cursor);
   | Loop ys -> while memory.(!cursor) <> 0 do eval ys done
 in List.iter aux' program

let parse (channel : in_channel) : token list =
 let rec parse_increments (stream : char Stream.t) (acc : int) : char Stream.t * int =
   match stream with parser
   | [< ''+'; r >] -> parse_increments r (acc + 1)
   | [< ''-'; r >] -> parse_increments r (acc - 1)
   | [< 'l; r >] -> ([< 'l; r >], acc)
   | [< >] -> ([< >], acc) in
 let rec parse_movements (stream : char Stream.t) (acc : int) : char Stream.t * int =
   match stream with parser
   | [< ''>'; r >] -> parse_movements r (acc + 1)
   | [< ''<'; r >] -> parse_movements r (acc - 1)
   | [< 'l; r >] -> ([< 'l; r >], acc)
   | [< >] -> ([< >], acc) in
 let rec aux (stream : char Stream.t) : token list =
   match stream with parser
   | [< ''+'; r >] -> let (s, n) = parse_increments r 1 in Add n :: aux s 
   | [< ''-'; r >] -> let (s, n) = parse_increments r (-1) in Add n :: aux s 
   | [< ''>'; r >] -> let (s, n) = parse_movements r 1 in Move n :: aux s
   | [< ''<'; r >] -> let (s, n) = parse_movements r (-1) in Move n :: aux s
   | [< ''.'; r >] -> Print :: aux r
   | [< '','; r >] -> Read :: aux r
   | [< ''['; r >] ->    
     let content = aux r in 
     if content = [Add (-1)] then Assign 0 :: aux r else Loop content :: aux r
   | [< '']'; r >] -> []
   | [< 'l; r >] -> aux r
   | [< >] -> []
 in aux (Stream.of_channel channel)

let _ = 
 let tokens = parse (open_in Sys.argv.(1)) in 
 let optimized = optimize tokens in
(* List.iter (fun x -> print_endline(string_of_t x)) optimized; *) (*afficher l’ast*)
 eval optimized

import Control.Monad.Trans.State.Lazy
import Data.Char
import Data.List
import Control.Monad.Trans.Class
import Control.Monad

type Zip a = ([a],[a])

type BF = StateT (Zip Int) IO ()

currentlyPointed = head . snd

next :: BF
next = modify $ \(l, x:xs) -> (x:l, xs)

prev :: BF
prev = modify $ \(x:xs, l) -> (xs, x:l)

incr :: BF
incr = modify $ \(l, x:xs) -> (l, (x+1):xs)

decr :: BF
decr = modify $ \(l, x:xs) -> (l, (x-1):xs)

output = do s <-get
            lift (putChar . chr . currentlyPointed $ s)
            put s
                          

input :: BF 
input = do (l, _:xs) <- get
           inp <- lift $ (liftM ord) getChar
           put (l, inp:xs)

  
loop :: BF -> BF
loop code = do s <- get
               if currentlyPointed s == 0 then put s else code >> (loop code)


runBF code = evalStateT code (repeat 0, repeat 0)

main = do runBF codeBF

codeBF = do
  input
  loop $ do decr
            incr
            decr
  output
  next
  incr
  prev

#include <cassert>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <iterator>
#include <array>
#include <stdexcept>
#include <map>

using str_citer = std::string::const_iterator;
using jumps = std::map<str_citer, str_citer>;

/* 
   Returns : true if c is a BF instruction false otherwise
   Exception : noexcept
*/   
inline bool is_an_inst(char c) noexcept {
  return c == '+' || c == '-' || c == '>' || c == '<' || 
         c == '.' || c == ',' || c == '[' || c == ']';
}

str_citer compute_jumps(std::string const& prg, str_citer start, jumps& from_to, jumps& to_from);
void extract_program(std::ifstream& ifs, std::string& program);
void interpret(std::string const& program, jumps const& from_to, jumps const& to_from) noexcept;

int main(int argc, char* argv[]){
  if(argc != 2)
    throw std::invalid_argument{ "use : ./exec file_name" };

  std::ifstream ifs{ argv[1], std::ios::in };
  //warning ! remaining exception : std::string allocation (x2)
  if(!ifs) throw std::runtime_error{ std::string{ argv[1] } + " does not exists" };

  //at this point :
  // - ifs is valid
  
  std::string prg{};
  extract_program(ifs, prg);

  //at this point :
  // - ifs is not valid anymore
  // - prg is a pure BF program
  
  jumps from_to, to_from;
  //exception : unmatched ]
  if(compute_jumps(prg, std::begin(prg), from_to, to_from) != std::end(prg))
    throw std::runtime_error{ "This program is not valid (unbalanced braces)." };
  
  //at this point :
  // - prg is a pure BF program
  // - from_to contains jumps from [ to ] and no occurrence of std::end(prg)
  // - to_from contains jumps from ] to [ and no occurrence of std::end(prg)

  interpret(prg, from_to, to_from);

  return 0;
}

/*
  Pre  : - ifs valid
  Post : - prg is pure BF
         - ifs is not valid anymore
  Exceptions : - IO exceptions on getline (unlikely)
               - allocation exception on program += and line allocation
               - remove_if cannot raise exception here
               - clear is noexcept
               - resize should not allocate (size is inferior)
*/
void extract_program(std::ifstream& ifs, std::string& program){
  using std::begin;
  using std::end;

  program.clear();
  for(std::string line{}; getline(ifs, line); ) program += line;

  //we only keep BF instructions
  auto e = std::remove_if(begin(program), end(program), [](char c){ return !is_an_inst(c); });

  //remove final moved characters
  program.resize(e - begin(program));
}

/*
  Pre  : - prg is pure BF
         - std::begin(prg) <= it <= std::end(prg)
  Post : - from_to contains jumps from [ to ] * and no occurrence of std::end(prg)
         - to_from contains jumps from ] to [ * and no occurrence of std::end(prg)
         * between Pre(it) and Return value
  Returns : - iterator to ] or std::end(prg) (if this last happens in a rec call it is an error)
  Exceptions : - runtime_error (parsing)
               - allocation error on inserting in the map
               - recursive call exceptions
*/
str_citer compute_jumps(std::string const& prg, str_citer it, jumps& from_to, jumps& to_from)
{
  //invariant : - std::begin(prg) <= it <= std::end(prg)
  //            - from_to and to_from contains all visited jumps
  while(it != std::end(prg)){
    if(*it == '['){
      str_citer begin { it };
      it = compute_jumps(prg, it+1, from_to, to_from);

      //exception : unmatched [
      if(it == std::end(prg))
        throw std::runtime_error{ "This program is not valid (unbalanced braces)." };

      assert(begin != std::end(prg)); //obvious
      assert(it    != std::end(prg)); //obvious

      //guarantee : from_to an to_from does not contain std::end(prg)
      from_to[begin] = it;
      to_from[it]    = begin;
    }
    else if(*it == ']') return it;
    
    ++it;
  }

  return std::end(prg);
}

/*
  Pre : - prg is a pure BF program
        - from_to contains jumps from [ to ] and no occurrence of std::end(prg)
        - to_from contains jumps from ] to [ and no occurrence of std::end(prg)
  Post: - nothing special : standard output as been updated with output
  Exceptions : noexcept
*/
void interpret(std::string const& program, jumps const& from_to, jumps const& to_from) noexcept{
  using std::begin;
  using std::end;

  std::array<char, 30000> data;
  data.fill(0);
  decltype(data)::iterator dp { begin(data) };

  str_citer pc { begin(program) };

  // Invariant : - std::begin(program) <= pc <= std::end(program) (== causes end loop)
  //             - std::begin(data)    <= dp <  std::end(program)
  while(pc != end(program)){
    char const byte { *dp };
    
    switch(*pc){
    case '+': ++(*dp); break;
    case '-': --(*dp); break;
    case '>': ++dp;    break;
    case '<': --dp;    break;
    case '.': std::cout<<byte; break;
    case ',': *dp = static_cast<char>(getchar()); break;
    case '[': if(!*dp)    pc = (*from_to.find(pc)).second; break;
    case ']': if( *dp)  pc = (*to_from.find(pc)).second; break;
    default : assert(false && "Something really bad happened");
    }
    if(dp == end(data)) dp = begin(data);

    ++pc;
  }
}