Créer un compilateur/interpréteur Brainfuck

Tous langages

a marqué ce sujet comme résolu.

Hello,

j'avais un peu de temps libre, alors j'ai codé un interpréteur en Lua. Il n'y a aucune optimisation et le seul prétraitement du code est de constituer une table des positions des crochets. Les exemples fonctionnent (mais évidemment, comme il n'y a rien d'optimisé, Mandelbrot prend un bon moment ^^ ).

Je voulais faire le code le plus simple possible, et du coup j'ai construit une table qui permet d'interpréter le code Brainfuck en assimilant chaque instruction à un pointeur sur fonction (les commentaires étant liés à une fonction neutre grâce à la métatable).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
bf={ptr = 1,
    pos = 0,
    code = '',
    ['>'] = function () bf.ptr = bf.ptr+1 end,
    ['<'] = function () bf.ptr = bf.ptr-1 end,
    ['+'] = function () bf[bf.ptr] = bf[bf.ptr]+1 end,
    ['-'] = function () bf[bf.ptr] = bf[bf.ptr]-1 end,
    ['.'] = function () io.write(string.char(bf[bf.ptr])) end,
    [','] = function () bf[bf.ptr] = string.byte(io.read()) end,
    ['['] = function () if bf[bf.ptr]==0 then bf.pos=bf.lEnd[bf.pos] end end;
    [']'] = function () if bf[bf.ptr]~=0 then bf.pos=bf.lBeg[bf.pos] end end;

    setCode = function (userCode)
        bf.code = userCode
        local posOp = {}
        bf.lEnd = {}
        bf.lBeg = {}
        for i = 1, #bf.code do
            c = bf.code:sub(i,i)
            if c=='[' then posOp[1+#posOp]=i
            elseif c==']' then
                if #posOp == 0 then error('Missing [')
                else
                    bf.lEnd[posOp[#posOp]] = i
                    bf.lBeg[i] = posOp[#posOp]
                    posOp[#posOp] = nil
                end
            end
        end
        if #posOp~=0 then error('Missing ]') end
    end,

    execute = function () 
        while bf.pos<=#bf.code do
            bf.pos = bf.pos+1
            bf[bf.code:sub(bf.pos, bf.pos)]()
        end
    end,}

setmetatable(bf, {__index = function (t, k)
        return type(k)=='string' and function () end or 0
    end})

local file = arg[1]
local code = [[++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>
               ++.<<+++++++++++++++.>.+++.------.--------.>+.>.]]
if file then
    local f = io.open(file, "r")
    code = f:read("*all")
    f:close()
end
bf.setCode(code)
bf.execute()

Depuis mon dernier post où j'avais fait un interpréteur simple (et limité) en Haskell, j'ai pas mal bossé sur un "compilateur" brainfuck -> c++ qui optimise bien le code au passage.

La compilation se fait en 5 passes :

  • La première chose qui est faite est la transformation du code brainfuck en un arbre d'exécution qui contient des nœuds Set, Move, Put, Get, While et If. Au passage, les instructions similaires sont rassemblés et les déplacements se propagent jusqu'au premier while rencontré.
    • Set permet d'affecter une expression à une case
    • Move permet de déplacer le pointeur
    • Put permet d'afficher le résultat d'une expression
    • Get récupère le caractère suivant de l'entrée standard et le place dans une case arbitraire
    • While effectue une liste d'instruction tant qu'une case arbitraire est non nulle
    • If effectue une liste d'instruction si une case arbitraire est nulle
  • La deuxième étape consiste à faire des optimisations simples sur les boucles. Les boucles stables (sans déplacement) qui contiennent exactement une instruction qui diminue de 1 l'index de boucle et autrement uniquement des Set qui ajoutent/suppriment une constante à une case ou qui affectent sont optimisés avec des multiplications. Par exemple [>+>>>++<--<<<-] devient p[1] = p[1] + p[0]; p[4] = p[4] + 2*p[0]; p[3] = p[3] - 2*p[0]; p[0] = 0. Notez que ça inclue aussi les remises à zéro.
  • La troisième étape consiste simplement à propager les déplacement de manière un peu plus poussée qu'à la première étape puisqu'elle déplace aussi les boucles p += 5; while(p[0] != 0) {p[2] = 0; p += 6;} devient while(p[5] != 0) {p[7] = 0; p+= 6} p += 5;. On se retrouve alors avec des Move uniquement à la fin des boucles et nul part ailleurs. Je ne l'ai pas fait à la première étape pour la simplifier et parce que le code ne s'y prêtait pas.
  • La quatrième est largement plus complexe et risque de se complexifier par le suite. C'est la propagation des constantes et la suppression de certaines instructions inutiles qui apparaissent. Au début, on sait que toutes les cases sont nulles. Ensuite, toutes les variables dont on connait la valeur sont remplacés dans les expressions rencontrés jusqu'à ce qu'elle change de valeur. De même, lorsque l'on rentre dans une boucle, on supprime toutes les constantes enregistré (elle peuvent être modifié dans le boucle) et à la sortie de la boucle, on enregistre que l'index est nul. Au passage, si une boucle a un index nul, on supprime la boucle et si l'index est nul à la fin de la boucle, on transforme la boucle en if. Pour les if, si l'index est constant non nul, on sort le contenu du if.
  • La cinquième étape est simplement la transformation de l'arbre d'exécution en c++.

A priori, aucune de mes optimisation ne cassent le code et j'ai vérifié le comportement sur plusieurs programmes brainfuck (mandelbrot, mandelbrot-titannic, hanoi, hello, …).

J'ai encore un certain nombre d'idée d'optimisations possibles, notamment la fusion des constantes pré-boucle et post-boucle pour éviter qu'une boucle qui touche à 2 cases bloque la propagation de plein de constantes. Il faudrait aussi que la détection de boucles optimisables à l'étape 2 soit meilleur. J'essayerait aussi de grouper les instructions Put si le contenu est constant. D'ailleurs, si quelqu'un a une bonne solution pour détecter les caractères spéciaux (genre ESC, \n et autres) histoire de ne pas les inclure directement dans une string sans problème, je suis preneur.

Voici le code :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
import System.Environment
import System.IO
import System.Process
import Data.List
import Data.Char
import qualified Data.Map as Map

data Instr = Set Int Expr | Move Int | Get Int | Put Expr | While Int [Instr] | If Int [Instr] deriving (Show, Eq)
data Expr = Const Int | Var Int | Sum [Expr] | Product [Expr] deriving Eq

instance Show Expr where
   show (Const i) = show i
   show (Var i) = "p[" ++ show i ++ "]"
   show (Sum l) = intercalate " + " . map show $ l
   show (Product l) = intercalate "*" . map (\e -> if isSum e then "(" ++ show e ++ ")" else show e) $ l
       where isSum (Sum _) = True
             isSum _ = False
   showsPrec _ a = (\e -> (show a) ++ e)

main = do
   (file:_) <- getArgs
   bf <- readFile (file ++ ".bf")
   if checkBrackets bf then do
       writeFile (file ++ ".cpp") $ toCpp . constPropagate (\e -> Const 0) Map.empty . movePropagate 0 . optimize . compile $ bf
       _ <- system ("g++ -O3 -o " ++ file ++ " " ++ file ++ ".cpp -std=c++11")
       return ()
   else
       putStrLn "Erreur de crochets"

checkBrackets :: String -> Bool
checkBrackets s =
   aux s 0
   where aux [] n = n == 0
         aux (t:q) n =
           if t == '[' then
               aux q (n+1)
           else if t == ']' then
               n > 0 && aux q (n-1)
           else
               aux q n

compile :: String -> [Instr]
compile s =
   reverse $ aux s [[]] 0
   where aux [] [c] i = c
         aux (t:q) (st:sq) i = case t of
             '+' -> aux q ((insert (Set i (Sum [Var i, Const 1])) st):sq) i
             '-' -> aux q ((insert (Set i (Sum [Var i, Const (-1)])) st):sq) i
             '<' -> aux q (st:sq) (i-1)
             '>' -> aux q (st:sq) (i+1)
             ',' -> aux q ((Get i:st):sq) i
             '.' -> aux q ((Put (Var i):st):sq) i
             '[' -> aux q ([]:(insert (Move i) st):sq) 0
             ']' -> aux q ((While 0 (reverse . insert (Move i) $ st):head sq):tail sq) 0
             _ -> aux q (st:sq) i
         insert (Move 0) s = s
         insert (Move i) s = Move i:s
         insert (Set i e) [] = [Set i e]
         insert (Set i sum) (t:q) =
             case t of
                 Set i2 sum2 ->
                     if i2 == i then
                         Set i (normalize $ replace i sum sum2):q
                     else
                         t:insert (Set i sum) q
                 Get i2 ->
                     if i == i2 then
                         Set i sum:Get i2:q
                     else
                         Get i2:insert (Set i sum) q
                 Put sum2 ->
                     if dependOn i sum2 then
                         Set i sum:Put sum2:q
                     else
                         Put sum2:insert (Set i sum) q
                 _ ->
                     Set i sum:t:q

optimize :: [Instr] -> [Instr]
optimize [] = []
optimize (While 0 l:q) =
   if isOptimizableWhile l' then
       map (\(Set i (Sum [Var _, Const c])) -> Set i (normalize $ Sum [Var i, Product [Const c, Var 0]])) nonSet0 ++ [Set 0 (Const 0)] ++ optimize q
   else
       While 0 l':optimize q
   where l' = optimize l
         (set0, nonSet0) = partition (\e -> case e of Set 0 _ -> True; _ -> False) l
         isOptimizableWhile l = all (\e -> case e of Set i expr -> (case expr of Sum [Var n, Const _] -> n == i; _ -> False) || i == 0; _ -> False) l &&
                                length set0 == 1 &&
                                head set0 == Set 0 (Sum [Var 0, Const (-1)])
optimize (t:q) = t:optimize q

replace :: Int -> Expr -> Expr -> Expr
replace i _ (Const n) = Const n
replace i e (Var n) =
   if n == i then
       e
   else
       Var n
replace i e (Product l) = Product (map (replace i e) l)
replace i e (Sum l) = Sum (map (replace i e) l)

replaceBy :: (Int -> Expr) -> Expr -> Expr
replaceBy f (Const n) = Const n
replaceBy f (Var n) = f n
replaceBy f (Sum l) = Sum (map (replaceBy f) l)
replaceBy f (Product l) = Product (map (replaceBy f) l)

dependOn :: Int -> Expr -> Bool
dependOn _ (Const n) = False
dependOn i (Var n) = n == i
dependOn i (Product l) = any (dependOn i) l
dependOn i (Sum l) = any (dependOn i) l

normalize :: Expr -> Expr
normalize (Const n) = Const n
normalize (Var n) = Var n
normalize (Sum []) = Const 0
normalize (Sum [e]) = e
normalize (Sum l) =
   let (sums, nonSums) = partition (\e -> case e of Sum _ -> True; _ -> False) . map normalize $ l
       l' = nonSums ++ foldl (\r (Sum l) -> l ++ r) [] sums
       (l'', c) = foldl (\(l, c) e -> case e of Const n -> (l, c+n); _ -> (e:l, c)) ([], 0) l' in
           if c == 0 then
               case length l'' of
                   0 -> Const 0
                   1 -> head l''
                   _ -> Sum l''
           else
               if length l'' == 0 then
                   Const c
               else
                   Sum (l'' ++ [Const c])
normalize (Product []) = Const 1
normalize (Product [e]) = e
normalize (Product l) =
   let (prods, nonProds) = partition (\e -> case e of Product _ -> True; _ -> False) . map normalize $ l
       l' = nonProds ++ foldl (\r (Product l) -> l ++ r) [] prods
       (l'', c) = foldl (\(l, c) e -> case e of Const n -> (l, c*n); _ -> (e:l, c)) ([], 1) l' in
           if c == 0 then
               Const 0
           else if c == 1 then
               case length l'' of
                   0 -> Const 1
                   1 -> head l''
                   _ -> Product l''
           else
               if length l'' == 0 then
                   Const c
               else
                   Product (Const c:l'')

movePropagate :: Int -> [Instr] -> [Instr]
movePropagate i [] =
   if i == 0 then
       []
   else
       [Move i]
movePropagate m (t:q) =
   case t of
       Set i e -> Set (i+m) (decale m e):movePropagate m q
       Move i -> movePropagate (i+m) q
       Get i -> Get (i+m):movePropagate m q
       Put e -> Put (decale m e):movePropagate m q
       While i l ->
           if m == 0 then
               While i (movePropagate 0 l):movePropagate m q
           else
               While (i+m) (decaleInstr m l):movePropagate m q
   where decale i (Const n) = Const n
         decale i (Var n) = Var (n+i)
         decale i (Sum l) = Sum (map (decale i) l)
         decale i (Product l) = Product (map (decale i) l)
         decaleInstr i l =
             let l' = movePropagate i l in
                 case last l' of
                     Move i' ->
                         if i'-i == 0 then
                             init l'
                         else
                             (init l') ++ [Move (i'-i)]
                     _ ->
                         if i == 0 then
                             l'
                         else 
                             l' ++ [Move (-i)]

constPropagate :: (Int -> Expr) -> Map.Map Int Int -> [Instr] -> [Instr]
constPropagate f m l =
   fst $ aux f m l
   where aux :: (Int -> Expr) -> Map.Map Int Int -> [Instr] -> ([Instr], Map.Map Int Int)
         aux _ m [] = (map (\(i, n) -> Set i (Const n)) . Map.assocs $ m, m)
         aux f m (Set i (Const n):q) = aux (\e -> if e == i then Const n else f e) (Map.insert i n m) q
         aux f m (Set i e:q) =
             case e' of
                 Const n -> aux (\e -> if e == i then e' else f e) (Map.insert i n m) q
                 _ -> next (Set i e') $ aux (\e -> if e == i then Var e else f e) (Map.delete i m) q
             where e' = normalize $ replaceBy f e
         aux f m (Move i:q) =
             next (Move i) $ aux (\e -> case f (e+i) of Const n -> Const n; Var _ -> Var e) (Map.mapKeysMonotonic ((+) (-i)) m) q
         aux f m (Put e:q) =
             next (Put $ replaceBy f e) $ aux f m q
         aux f m (Get i:q) =
             next (Get i) $ aux (\e -> if e == i then Var e else f e) (Map.delete i m) q
         aux f m (While i l:q) =
             case f i of
                 Const 0 -> aux f m q
                 _ ->
                     if stable l' && Map.lookup i m' == Just 0 then
                         case f i of
                             Const n -> aux f m (l'++q)
                             _ -> (deb ++ (If i $ constPropagate f m l'):auxq, auxm)
                     else
                         (deb ++ (While i l'):auxq, auxm)
                     where (l', m') = aux (\e -> Var e) Map.empty l
                           stable = foldl (\r e -> r && case e of Move i -> i == 0; While _ l -> stable l; If _ l -> stable l; _ -> True) True
                           (auxq, auxm) = aux (\e -> if e == i then Const 0 else Var e) Map.empty q
                           deb = constPropagate (\n -> Const n) m []
         next instr (q, m) = (instr:q, m)

toCpp :: [Instr] -> String
toCpp i =
   "#include <iostream>\n#include <chrono>\nint main(int argc, char **argv) {\n" ++
   "unsigned char tab[30000];\nunsigned char *p = tab;\nfor(int i=0; i<30000; i++) tab[i] = 0;\n" ++
   "auto t1 = std::chrono::system_clock::now();\n" ++ 
   (aux i) ++
   "auto t2 = std::chrono::system_clock::now();\n" ++
   "std::chrono::duration<double, std::ratio<1, 1000>> dur = t2-t1;\n" ++
   "std::cout << \"Time : \" << dur.count() << \" ms\" << std::endl;\n" ++
   "return 0;\n}"
   where aux = (foldr (++) "") . map (\e -> case e of
                                               Set i s -> "p[" ++ show i ++ "] = " ++ show s ++ ";\n"
                                               Move n -> "p += " ++ show n ++ ";\n"
                                               Get i -> "std::cin >> p[" ++ show i ++ "];\n"
                                               Put (Const 10) -> "std::cout << '\\n';\n"
                                               Put (Const n) -> "std::cout << '" ++ chr n:"';\n"
                                               Put s -> "std::cout << " ++ show s ++ ";\n"
                                               While i l -> "while(p[" ++ show i ++ "] != 0) {\n" ++ aux l ++ "}\n"
                                               If i l -> "if(p[" ++ show i ++ "] != 0) {\n" ++ aux l ++ "}\n"
                                               )

Au niveau perf, vu que ça sort des exécutables optimisés par gcc en plus, c'est vraiment rapide :

Un des gros problème des mandelbrot, c'est l'omniprésence des boucles non stables, ce que donne du code très difficile à optimiser avec juste une analyse statique (voir impossible). Au contraire, hanoi est un nid à absurdité : j'ai déjà vu des [code][-] par exemple. Beaucoup de boucles sont présente alors que l'index est toujours nul. Et c'est loin d'être les seuls choses facilement optimisables, donc c'est l'exemple parfait pour chercher des optimisations à faire.

+2 -0

@[@dri1] Sympa les metatables! Je ne connaissais pas trop le Lua. Je découvre

@Berdes Bon, il va falloir que je me mette au Haskell!

Impressionnant en tout cas! En comparaison il me manque les étapes 3, 4 et 5. Par contre je ne suis pas certain de saisir l'intérêt de l'étape 3, car à priori elle ne change ni la complexité ni la taille du code. J'ai l'impression de rater quelque chose car je ne comprends pas l'exemple que tu donnes non plus :)

Sinon pour la 5ème étape de mon côté, plutôt que de générer du C++ je pensais faire du JIT. Je regarde actuellement du côté de libjit issue du projet DotGNU (LGPL), xbyak (header only :o) et bien sur de la LLVM. Si d'autres personnes se penchent sur du JIT quelles bibliothèques comptez-vous utiliser?

J'ai mis l'exemple de l'étape 3 au format C++. En fait, c'est surtout utile dans les cas où il y a move; while; move; while; move… Ça permet de réduire le nombre de move (plus qu'un seul move à la fin) donc ça améliore les pref, mais surtout ça améliore la lisibilité du code (ce qui aide beaucoup pour chercher les éléments optimisables).

Tu pourrais nous donner un ordre d'idée des temps de compils aussi (de génération du code C++ puis de leur compilation) ?

En fait c'est, je pense, toute la différence entre un interpréteur et un compilateur car perso il y a certaines optimisations que je n'ai pas implémentés (ou viré) car trop longue vis a vis du temps gagné.

Je viens de faire quelques tests de comparaison en performance. Tout le tableau est au format compilation (s) +exécution (ms ou s) :

Fichier sans optimisation -O0 -O0 -O1 -O2 -O3 sans optimisation -O3
hello 0.38s + 0ms 0.37s + 0ms 0.38s + 0ms 0.37s + 0ms 0.37s + 0ms 0.39s + 0ms
hanoi 2.4s + 5.2s 1.1s + 80ms 1.67s + 27ms 2.5s + 6ms 2.6s + 8ms 24s + 65ms
mandelbrot 0.78s + 4.4s 0.65s + 3.6s 1.1s + 1.2s 1.8s + 1.3s 1.9s + 1.3s 3.2s + 1.6s
mandelbrot-titannic 0.74s + 118s 0.65s + 95s 1.1s + 34s 1.8s + 34s 1.9s + 34s 3.1s + 43s

Sans optimisation veut dire que je n'ai effectué que les passes 1 et 5 (toutes deux nécessaires). Cela permet de voir l'impact de mes optimisations. On voit nettement que j'arrive à faire des optimisations que ne fait pas gcc, même avec -03 (ce qui est plutôt encourageant). Le temps de compilation a un impact très clair.

On remarquera quand même que hanoi est très nettement optimisable puisque mes optimisations (sans gcc) font passer de 5.2s à 80ms. Le temps de compilation est aussi fortement influencé par mes optimisations : en effet, tout ce que je fais provoque une diminution du nombre d'instructions. hanoi passe de 14753 lignes de c++ à 4825, ce qui a l'air de beaucoup aider gcc (la compilation passe de 24s à 2.6s en -O3).

En revanche, sur les deux mandelbrot, j'ai beaucoup moins d'impact, ce qui se comprend par le fait que je n'optimise quasiment rien quand j'arrive sur des boucles non stables (ce qui forme la base des mandelbrot).

Hello !

Bon, bien évidemment, mon immonde bazar du début était complètement inutilisable, puisqu'il ne prennait pas en compte les boucles.

Je suis donc parti sur autre chose : un interpréteur BF écrit en assembleur. Et bien, ça a été un peu long à débogguer (j'ai voulu faire trop optimisé, résultat j'ai loupé des cas) au niveau des boucles, mais ça marche !

Le code ici:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
format ELF executable 3

entry start

segment readable writeable
cell db 1024 dup(0)
filename db 'prog.bf'
instru db 100000 dup(0)
msg_end db 0xA

segment readable executable

start:

; = Read BF source code =

; === Open the file ===
  mov eax, 5
  mov ebx, filename
  xor ecx, ecx
  xor edx, edx
  int 0x80

; === Read the file ===
  mov eax, 3
  mov ebx, 3
  mov ecx, instru
  mov edx, 100000
  int 0x80

; = Go to the interpreter =
  mov ecx, 1
  mov edi, cell
  mov esi, instru
  jmp bf_i

bf_sub:
; inc byte [edi]
  sub byte [edi], 1
  jmp instru_inc

bf_cell_dec:
  dec edi
  jmp instru_inc

bf_cell_inc:
  inc edi
  jmp instru_inc

bf_add:
; inc byte [edi]
  add byte [edi], 1

instru_inc:
  inc esi

bf_i:
  cmp byte [esi], ']'
  je bf_loop_pop

  cmp byte [esi], '['
  je bf_loop_push

; Skip the loop in case we are on a 0 cell
  jcxz instru_inc

  cmp byte [esi], '+'
  je bf_add

  cmp byte [esi], '-'
  je bf_sub

  cmp byte [esi], '>'
  je bf_cell_inc

  cmp byte [esi], '<'
  je bf_cell_dec

  cmp byte [esi], ','
  je bf_in

  cmp byte [esi], '.'
  je bf_out

  cmp byte [esi], 0
  je endprog

; Something that's not BF ==> never mind.
  jmp instru_inc

bf_out:
  mov eax, 4
  mov ebx, 1
  mov ecx, edi
  mov edx, 1
  int 0x80

  mov ecx, 1
  jmp instru_inc

bf_in:
  mov eax, 3
  mov ebx, 0
  mov ecx, edi
  mov edx, 1
  int 0x80

  mov ecx, 1
  jmp instru_inc

bf_loop_push:
  push esi
  push ecx
  cmp byte [edi], 0
  setne cl
  jmp instru_inc

bf_loop_pop:
  pop ecx
  cmp byte [edi], 0
  je no_pop
  pop esi
  jmp bf_i

no_pop:
  pop eax
  jmp instru_inc

endprog:
  mov eax, 4
  mov ebx, 1
  mov ecx, msg_end
  mov edx, 1
  int 0x80
  mov eax, 1
  xor ebx, ebx
  int 0x80

Le tout est donc en appel système direct, donc utilisable uniquement sous linux. Par contre, c'est théoriquement directement utilisable sous un i386. Il faut obligatoirement utiliser fasm puisqu'il n'y a aucune section, donc le linker va être perdu.

Il me sort Mandelbrot en environ 23s, donc il y a encore du boulot à faire.

Il marche de la façon suivante:

  • edi pointe sur les cases BF (limité à 1Ko pour essayer de rester en L1)
  • esi pointe sur le code source BF (limité à une valeur bizarre pour essayer de rester en L3)

A chaque instruction, esi est donc incrémenté : on avance d'une case, donc d'une instruction. Quand on rentre dans une boucle, on stocke l'adresse de la case courante dans la pile, comme ça à la fin de boucle il n'y a plus qu'à dépiler le pointeur et on est repartit. Si la boucle doit être ignorée, elle est "échappée" en mettant ecx à 0 (d'où un petit jcxz et un setne cl), après avoir poussée la valeur précédente d'ecx dans la pile, ce qui permet de gérer les boucles imbriquées.

Il n'y a donc aucune sorte d'optimisation sur les boucles.

Pour les curieux, le programme en lui-même fait 1.4Ko, c'est le tableau d'instructions qui prend tout le reste de la place.

EDIT : le msg_end, c'est un LF pour terminer le programme de façon propre

EDIT 2: Important pour l'utiliser (une fois assemblé) vous devez mettre votre code bf dans le répertoire courant (par exemple celui qui contient l'interpréteur) dans le fichier prog.bf (cette constante est contenue dans la variable filename). Il ne prend aucun argument. J'ai fait ça en attendant de savoir gérer correctement les arguments de taille variables.

EDIT 3: Ce qui est optimisable. Parce que même si les précédents interpréteurs sortaient mandelbrot en environ 20s, on peut faire encore quelques petites choses en assembleur:

  • remplacer les add et sub des '+' et '-' par des inc et dec (moins d'opérandes = moins de temps de prélecture avant saut = quelques cycles d'économisés). Actuellement j'ai un problème terrible avec les inc et dec (que je ne comprends pas d'ailleurs) qui fait que je suis obligé de passer par des add et sub
  • diminer le nombre de saut:

Pour les non-initiés au langage, tout ce qui commence par 'j' est un saut, comme par exemple:

  • jne
  • je
  • jcxz
  • jmp

Sauf qu'en x86, un saut prend énormément de temps. Une addition ou une soustraction prennent 2 cycles. Un comparaison avec une opérande mémoire 4 (si ma mémoire est bonne). Un saut, c'est minimum 7. Et encore, parce qu'il y a une prélecture automatique de l'instruction suivante, qui ne peut se faire que s'il n'y a pas de rupture de séquence. Un saut, c'est une rupture de séquence, donc il est obligé de prendre du temps en plus pour lire la première instructions (les autres bénéficeront de la prélecture automatique), et plus cette instruction a "d'arguments", plus la lecture prend du temps.

  • dans le cas ou j'en aurais oublié, quelques optimisations introduites tardivement sur les x86, tel que la "parallélisation" des opérations sur les registres, ainsi que certaines micro-optimisations (je n'en connait aucune à part le xor pour mettre à 0)

EDIT 4 : Modification mineure. Au programme : déplacement de certaines procédures, suppression d'un jump pour '+', écriture d'un align 4 pour le début de l'interpréteur.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
format ELF executable 3

entry start

segment readable writeable
cell db 1024 dup(0)
filename db 'prog.bf'
instru db 100001 dup(0)
msg_end db 0xA

segment readable executable

start:

; = Read BF source code =

; === Open the file ===
  mov eax, 5
  mov ebx, filename
  xor ecx, ecx
  xor edx, edx
  int 0x80

; === Read the file ===
  mov eax, 3
  mov ebx, 3
  mov ecx, instru
  mov edx, 100000
  int 0x80

; = Go to the interpreter =
  mov ecx, 1
  mov edi, cell
  mov esi, instru
  jmp bf_i

bf_sub:
  align 4
  sub byte [edi], 1
  jmp instru_inc

bf_cell_dec:
  dec edi
  jmp instru_inc

bf_add:
  add byte [edi], 1
  dec edi

bf_cell_inc:
  inc edi

instru_inc:
  inc esi

bf_i:
  cmp byte [esi], ']'
  je bf_loop_pop

  cmp byte [esi], '['
  je bf_loop_push

; Skip the loop in case we are on a 0 cell
; jcxz instru_inc
  cmp ecx, 0
  je instru_inc

  cmp byte [esi], '+'
  je bf_add

  cmp byte [esi], '-'
  je bf_sub

  cmp byte [esi], '>'
  je bf_cell_inc

  cmp byte [esi], '<'
  je bf_cell_dec

  cmp byte [esi], ','
  je bf_in

  cmp byte [esi], '.'
  je bf_out

  cmp byte [esi], 0
  je endprog

; Something that's not BF ==> never mind.
  jmp instru_inc

bf_out:
  mov eax, 4
  mov ebx, 1
  mov ecx, edi
  mov edx, 1
  int 0x80

  mov ecx, 1
  jmp instru_inc

bf_loop_push:
  push esi
  push ecx
  cmp byte [edi], 0
  setne cl
  jmp instru_inc


bf_loop_pop:
  pop ecx
  cmp byte [edi], 0
  je no_pop
; cmove eax, [esp]
  pop esi
; cmovne esi, [esp]
; add esp, 4
; je instru_inc
  jmp bf_i

no_pop:
  pop eax
  jmp instru_inc

bf_in:
  mov eax, 3
  xor ebx, ebx
  mov ecx, edi
  mov edx, 1
  int 0x80

  mov ecx, 1
  jmp instru_inc

endprog:
  mov eax, 4
  mov ebx, 1
  mov ecx, msg_end
  mov edx, 1
  int 0x80

  mov eax, 1
  xor ebx, ebx
  int 0x80

Mandelbrot en 21.75s, notamment par le remplacement de jcxz (censé être optimisé …) par un combo cmp-je, comme pour le reste.

+0 -0

Et voici ma réalisation en C++ (Eh oui, une de plus!)

Le code BrainFuck est convertit en C++.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int varpos=0,i=0;

int main(int argc,char* argv[])
{
    ifstream file("main.brainfuck");
    ofstream out("bmain.cpp");
    if(file&&out)
    {
        file.seekg(0, ios::end);
        int filesize;
        filesize = file.tellg();

        file.seekg(0, ios::beg);

        string data1 = "";

        out << "#include <iostream>\n#include <stdio.h>\n#include <conio.h>\n#include <string>\nint main(){\n//initialisation\nint var[30000]={0};int k=0;\n//programme\n";

        char car;
        file.get(car);
        while(file.tellg()<=filesize&&file.tellg()>=0)
        {
            switch(car)
            {
                case '+':
                    i=0;
                    while(car=='+')
                    {
                        i++;
                        file.get(car);
                    }
                    out << "var[k]+=" << i << ";\n";
                    break;

                case '-':
                    i=0;
                    while(car=='-')
                    {
                        i++;
                        file.get(car);
                    }
                    out << "var[k]-=" << i << ";\n";
                    break;

                case '<':
                    i=0;
                    while(car=='<')
                    {
                        i++;
                        file.get(car);
                    }
                    out << "k-=" << i << ";\n";
                    break;

                case '>':
                    i=0;
                    while(car=='>')
                    {
                        i++;
                        file.get(car);
                    }
                    out << "k+=" << i << ";\n";
                    break;

                case '[':
                    out << "while(var[k]!=0)\n{\n";
                    file.get(car);
                    break;

                case ']':
                    out << "}\n";
                    file.get(car);
                    break;

                case ',':
                    out << "getch(var[k]);\n";
                    out << "printf(\"%c\",var[k]);\n";
                    file.get(car);
                    break;

                case '.':
                    out << "printf(\"%c\",var[k]);\n";
                    file.get(car);
                    break;

                default:
                    file.get(car);
            }
        }
        out << "std::cout << std::endl << std::endl;system(\"PAUSE\");}";
    }
    else
    {
        cout << "pas de donnees disponibles" << endl;
    }
}

Et une version en rust, une ! Contrairement au lien ci-dessus, mon code n'optimise presque rien, et se content d'interpréter l'entrée au fur et à mesure. La seul petite optimisation est le stockage des paires de [] au lieu de les rechercher à chaque fois.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
use std::io;
use std::io::prelude::*;
use std::fs::File;
use std::char;
use std::env;
use std::fmt;
use std::error;

const MEMORY: usize = 30000;

#[derive(Debug)]
enum Error {
    IoError(io::Error),
    OverflowError,
    UnderflowError,
    NotASCIIPrint,
    UnmatchedBrackets,
}

impl From<io::Error> for Error {
    fn from(error: io::Error) -> Error {
        Error::IoError(error)
    }
}

impl fmt::Display for Error {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            &Error::IoError(ref err) => err.fmt(f),
            _ => write!(f, "{}", error::Error::description(self))
        }
    }
}

impl error::Error for Error {
    fn description(&self) -> &str {
        match self {
            &Error::IoError(ref err) => err.description(),
            &Error::OverflowError => "Pointer overflow",
            &Error::UnderflowError => "Pointer underflow",
            &Error::NotASCIIPrint => "Trying to print outside of ASCII range",
            &Error::UnmatchedBrackets => "Unmatched squared brackets"
        }
    }
}

/******************************************************************************/

/// A Brainfuck processor
struct BFProcessor {
    cells: [u8; MEMORY],
    ptr: usize,
}

impl BFProcessor {
    pub fn new() -> BFProcessor {
        BFProcessor{cells: [0; MEMORY], ptr: 0}
    }

    /// `+` : Increments the value at the current cell by one.
    pub fn increment(&mut self) -> Result<(), Error> {
        self.cells[self.ptr] += 1;
        Ok(())
    }

    /// `-` : Decrements the value at the current cell by one.
    pub fn decrement(&mut self) -> Result<(), Error> {
        self.cells[self.ptr] -= 1;
        Ok(())
    }

    /// `>` : Moves the data pointer to the next cell (cell on the right).
    pub fn move_right(&mut self) -> Result<(), Error> {
        if self.ptr == MEMORY-1 {
            return Err(Error::OverflowError);
        }
        self.ptr += 1;
        Ok(())
    }

    /// `<` : Moves the data pointer to the previous cell (cell on the left).
    pub fn move_left(&mut self) -> Result<(), Error> {
        if self.ptr == 0 {
            return Err(Error::UnderflowError);
        }
        self.ptr -= 1;
        Ok(())
    }

    /// `.` : Prints the ASCII value at the current cell (i.e. 65 = 'A').
    pub fn print(&self) -> Result<(), Error> {
        match char::from_u32(self.cells[self.ptr] as u32) {
            Some(p) => print!("{}", p),
            None => return Err(Error::NotASCIIPrint)
        }
        Ok(())
    }

    /// `,` : Reads a single input character into the current cell.
    pub fn read(&mut self) -> Result<(), Error> {
        let stdin = io::stdin();
        let mut input = stdin.take(1);
        let mut buffer = Vec::new();
        try!(input.read_to_end(&mut buffer));
        self.cells[self.ptr] = buffer[0];
        Ok(())
    }

    /// Is the current cell null ?
    pub fn current_is_null(&self) -> bool {
        self.cells[self.ptr] == 0
    }
}

/******************************************************************************/

/// Keeping track of opening and closing brackets
#[derive(Clone, Copy)]
struct BracketPair {
    /// Index of the opening bracket
    pub open: usize,
    /// Index of the closing bracket
    pub close: usize
}

/// A Brainfuck program
struct BFProgram {
    /// Program to execute
    program: Vec<char>,
    /// brackets pairing
    brackets: Vec<BracketPair>,
    /// Current state in the program
    state: usize,
}

impl BFProgram {
    pub fn new(program: Vec<char>) -> Result<BFProgram, Error> {
        let brackets = try!(BFProgram::validate(&program));
        Ok(BFProgram{
            program: program,
            brackets: brackets,
            state: 0
        })
    }

    /// Get current instruction
    pub fn get(&self) -> char {
        self.program[self.state]
    }

    /// Change state to next instruction
    pub fn next(&mut self) {
        self.state += 1;
    }

    /// Change state to previous instruction
    pub fn previous(&mut self) {
        self.state -= 1;
    }

    /// Is the program finished yet?
    pub fn done(&self) -> bool {
        self.state == self.program.len()
    }

    /// Change state to the bracket corresponding to the current instruction.
    pub fn goto_bracket(&mut self) {
        let pair = self.get_current_pair();
        if self.get() == '[' {
            self.state = pair.close;
        } else {
            self.state = pair.open;
        }
    }

    fn get_current_pair(&self) -> BracketPair {
        assert!(self.get() == '[' || self.get() == ']');
        for pair in self.brackets.iter() {
            if pair.open == self.state || pair.close == self.state {
                return pair.clone();
            }
        }
        unreachable!();
    }

    /// Validate the brackets pairing in the program, and return the list of
    /// brackets or an error.
    fn validate(program: &Vec<char>) -> Result<Vec<BracketPair>, Error> {
        let mut opening = Vec::new();
        let mut pairs = Vec::new();
        for (i, c) in program.iter().enumerate() {
            match *c {
                '[' => {
                    opening.push(i);
                }
                ']' => {
                    let open = opening.pop().unwrap();
                    pairs.push(BracketPair{open: open, close: i});
                }
                _ => {}
            }
        }
        if opening.len() == 0 {
            return Ok(pairs);
        } else {
            return Err(Error::UnmatchedBrackets);
        }
    }
}

/******************************************************************************/

/// Representing a full Brainfuck computer
struct BFComputer {
    /// Processor to use
    processor: BFProcessor,
    /// Program to execute
    program: BFProgram,
}

impl BFComputer {
    pub fn new(program: String) -> Result<BFComputer, Error> {
        let program = try!(BFProgram::new(program.chars().collect()));
        Ok(BFComputer{
            program: program,
            processor: BFProcessor::new(),
        })
    }

    pub fn run(&mut self) -> Result<(), Error> {
        while !self.program.done() {
            let c = self.program.get();
            match c {
                '>' => try!(self.processor.move_right()),
                '<' => try!(self.processor.move_left()),
                '+' => try!(self.processor.increment()),
                '-' => try!(self.processor.decrement()),
                '.' => try!(self.processor.print()),
                ',' => try!(self.processor.read()),
                '[' => self.open_bracket(),
                ']' => self.close_bracket(),
                _ => {}
            }
            self.program.next();
        }
        Ok(())
    }

    /// Handle opening bracket
    fn open_bracket(&mut self) {
        if self.processor.current_is_null() {
            self.program.goto_bracket();
            self.program.previous();
        }
    }

    /// Handle closing bracket
    fn close_bracket(&mut self) {
        if !self.processor.current_is_null() {
            self.program.goto_bracket();
            self.program.previous();
        }
    }
}

fn read_input<'a, S>(path: S) -> String where S: Into<&'a str> {
    let path = path.into();
    let mut file = File::open(path).ok()
                    .expect(& format!("Could not open the file at '{}'", path));
    let mut buffer = String::new();
    file.read_to_string(&mut buffer).ok()
                    .expect(& format!("Could not read the file at '{}'", path));
    return buffer;
}

fn usage() {
    let argv: Vec<String> = env::args().collect();
    println!("Usage: {} program.bf", argv[0]);
}

fn main() {
    let argv: Vec<String> = env::args().collect();

    let program: String;
    if argv.len() > 1 {
        program = read_input(&*argv[1]);
    } else {
        return usage();
    }

    let mut computer = BFComputer::new((program)).unwrap();
    computer.run().unwrap();
}

Le Mandelbrot sort en 336s, avec rustc -O brainfuck.rs.

+0 -0

Bonjour,

C'est moi ou il n'y a pas d’interpréteurs BF qui aident a débugger le BF ?

Pour info, j'en ai fait un en C++, déjà posté sur OC, si cela intéresse quelqu'un je le poste ici,

Je crée un fichier qui décrit pas a pas l'exécution et l'état de la mémoire, du pointeur et les commentaires du code BF, en regroupant les codes répétitifs.

Pour info, je réfléchit a faire un compilateur code HP25 vers BF…

Il suffit d'ajouter des affichages de la mémoire à chaque instruction… c'est ce que j'ai fait, je l'ai peut-être trop poussé mais cela m'a bien aidé a comprendre des codes trouvés ça et là…

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
#include <cstdlib>  // pour system("PAUSE"); à la fin
#include <iostream> // pour cout / cin
#include <fstream>  // ifstream, open, get, ofstream...
#include <vector>   // pour la table du language
#include <stack>    // Pile LIFO des retours de boucle
#include <iomanip>  // std::setw
#include <sstream>  // ostringstream

using namespace std;

// conversion valeur vers string trouvé sur internet
template<typename T>
string to_string( const T & Value ) {
    ostringstream oss; // utiliser un flux de sortie pour créer la chaîne
    oss << Value;      // écrire la valeur dans le flux
    return oss.str();  // renvoyer une string
}

// conversion valeur vers string trouvé sur internet
// revue pour changer les char en int et formater la valeur sur i caractères
string int_to_string_setw( const unsigned int & Value , unsigned int i) {
    ostringstream oss;       // utiliser un flux de sortie pour créer la chaîne
    oss << setw(i) << Value; // écrire la valeur dans le flux, formatée avec setw
    return oss.str();        // renvoyer une string
}

// Literale string, également trouvée sur un forum, inutile en C++14 je crois
string operator "" _s(const char *str, std::size_t len)
{ return {str, len}; }

typedef vector<char> typeTable; // Type de conteneur de la table du language

class Execution{

public:
    Execution() : tableDeBase(30000), nbBoucleAIgnorer(0) {i = tableDeBase.begin();}
// gestion du fichier
    bool ouvreFichier(string sNomF) {
        iFichier.open(sNomF.c_str(), ios::in | ios::binary); // tentative d'ouverture du fichier en lecture,
        return iFichier; // revoie vrai si l'ouverture s'est bien passée, faux sinon.
    }
    bool get(char & q) {return iFichier.get(q);}
// mode ou on passe les boucles parcequ'une avait 0 en entrée
    bool modeIgnorerboucle() {return nbBoucleAIgnorer;}
// vérification qu'il ne reste pas de boucle ouverte a la fin
    bool testDeFin() {return (!entreeBoucle.empty() || nbBoucleAIgnorer);}
// traitement du caractère suivant du fichier
    bool fonctionnementNormal(char l);
    void rechercheLaSortieDeBoucle(char l);

// 2 fonctions pour fournir les fichiers BFdebog en chaine de texte
// position du caractère étudié dans le fichier (tellg)
    const string pasFichier() {return int_to_string_setw(iFichier.tellg(), 5);}
// Représentation de la mémoire ou table de base du language BF
    const string memoire()const{
        static typeTable::iterator iMax = i;      // première case inutilisée
        if (i == iMax) iMax++;                    // Si une nouvelle case est utilisée, on incrémente iMax
        string memoire = "";
        for (auto p = tableDeBase.cbegin(); p!=iMax; p++) { // boucle sur les cases memoires utilisées
            memoire += int_to_string_setw(*p, 3); // ajout à la chaine, formaté sur trois caractère
            if (p == i) memoire += "+";           // un signe + marque le pointeur du langage
            else memoire +="|";                   // sinon, une barre verticale sépare les valeurs
        }
        return memoire;
    }
protected:

// Traitement normal des boucles
    void entreeBoucleNormale() {
        if (*i == 0) nbBoucleAIgnorer++;      // si on pointe sur 0, on passe en mode de recherche de la sortie de boucle.
        else entreeBoucle.push(iFichier.tellg()); // sinon, on ajoute la position en cours dans la pile de pointeur de boucle
    }
    bool sortieBoucleNormale() {
        if (entreeBoucle.empty()) return false;   // si la liste est vide, on retourne faux pour sortir du fichier
        if (*i == 0) entreeBoucle.pop();          // si 0 en sortie, on se debarrasse du point d'entrée
        else  iFichier.seekg(entreeBoucle.top()); // sinon, on lit le point d'entrée dans la pile pour y aller
        return true;
    }

// Variables du language BF
    typeTable tableDeBase;             // Table de base
    typeTable::iterator i;             // Pointeur sur la table
// Variables de gestion des boucles
    stack<streampos> entreeBoucle;     // liste des pointeurs d'entrée de boucle
    unsigned int nbBoucleAIgnorer = 0; // variable pour ignorer les boucles avec 0 en entrée
// fichier a éxécuter
    ifstream iFichier;
};

// traitement du fichier de debogage du programme BF
class debog {
public:
// debogage inactif par defaut,
// le flus etant "true" tant que rien n'y a été envoyé sans succès, je n'ai rien trouvé de mieux que "BFdebog << endl;"
    debog(Execution * a) : debogActif(false), debogstr(""), debogNb(0), exe(a),
                           nbOldl(0), oldl('$'), oldTellg("      ") {BFdebog << endl;}

// Fonction enregistrant a chaque tour les parametres du langage
void unTourDebog(char l){
    if (l == '$') debogActif = !debogActif; // Le debogage est activé / desactivé par le caractère $ ajouté au code BF
    else if (debogActif) {
// crée un nouveau fichier de sortie, soit au premier appel soit quand la taille dépasse 4Mio
        if (!BFdebog || BFdebog.tellp() > 4194304) ouvreFichierDebog();
// calcul de la chaine de sortie au fur et a mesure,
        if ("<>+-[].,"_s.find(l) < 9)     // cas d'un caractère du langage
            ligneDebog(l);
        else {                            // Les caractères autre que ceux du langage, et hors caractères spéciaux
            unsigned int intl = l;        // parceque l >+ ' ' vire les caractères accentués
            if (intl >= 32) debogstr +=l; // sont ajoutés a la chaine pour que les remarques correspondent a l'instruction
            oldl = '$';                   // et on force l'affichage de la chaine au prochain caractère du langage
}   }   }
protected:

// ouverture du fichier BFdebog000 ou 000 est le numero du fichier
    void ouvreFichierDebog(){
        if (BFdebog) BFdebog.close(); // si on est pas au premier appel, on ferme le fichier encours,
        debogNb++;                    // incrément du numero de fichier
        string debogNom = "00" + to_string(debogNb); // calcul du nom de fichier
        debogNom = "BFdebog" + debogNom.substr(debogNom.size()-3,3) + ".txt";
        BFdebog.open(debogNom);                      // et ouverture du fichier
    }

// creation de la ligne du fichier BFdebog correspondant a une instructions BF
void ligneDebog( char l) {
    if (l == oldl || nbOldl >= 99) nbOldl++; // on compte des caractères identiques consécutifs
    else { // mais si le caractère a changé, ou est répété plus de 99 fois
// s'il y a eu répétition, on ajoute la quantité et le point de départ dans la chaine
        if (nbOldl > 1) debogstr.replace(0, 15, oldTellg + "-" + debogstr.substr(6,6) + int_to_string_setw(nbOldl, 2) + "x");
// on envoie la chaine vers le fichier de sortie
        BFdebog << debogstr << endl;
// et on remet les variables de détection aux nouvelles valeurs
        nbOldl = 1;
        oldl = l;
        oldTellg = exe->pasFichier();
    }
// Création de la chaine de sortie a chaque caractère pour avoir l'état de la memoire avec le dernier en cas de répétition
// avec des espaces pour inserer les données en cas de repetition
    debogstr = "      " + exe->pasFichier() + "|   " + to_string(l) + "|" + exe->memoire();
}
// variables
    bool debogActif;      //
    ofstream BFdebog;     // flux du fichier de sortie
    string debogstr;      // chaine de sortie, ligne suivante du fichier BFdebog
    unsigned int debogNb; // numero du fichier de sortie en cours
    Execution * exe;      // lien vers le fichier exécuté
    unsigned int nbOldl;  // nombre de caractères identiques consécutifs
    char oldl;            // Operation précédente pour regrouper les opérations identiques
    string oldTellg;      // Première position du caractère répété
};

// 2 fonctions de traitement d'un caractère du fichier.
// fonctionnement normal
bool Execution::fonctionnementNormal(char l){
    switch (l) {
// Instructions de déplacement du pointeur BF, quand on arrive a un bout de la table on repart de l'autre bout
        case '<': if (i == tableDeBase.begin()) i = tableDeBase.end(); i--; break;
        case '>': i++; if (i == tableDeBase.end()) i = tableDeBase.begin(); break;
// Instructions de dé/incrémentation de la valeur pointée
        case '+': (*i)++; break;
        case '-': (*i)--; break;
// Instructions d'entrée/sortie de la valeur pointée
        case '.': cout << *i; break;
        case ',': cin >> *i; break;
// Boucles
        case '[': entreeBoucleNormale(); break;
        case ']':
            if(sortieBoucleNormale()) break;
            cout << "\nerreur ] sans [\n";       // sortie de boucle a renvoyé faux, on a une erreur a signaler
            return false;                        // et on renvoie faux pour sortir du fichier
        default : break; // pas sur que cette ligne serve a quelque chose mais c'etait dans mon cours de C++
    }
    static debog deb( this);
    deb.unTourDebog(l); // fonction de debogage du fichier BF, ici parcequ'on ne debogue que le fonctionnement normal
    return true;
}

void Execution::rechercheLaSortieDeBoucle(char l){
    switch (l) {                             // On recherche la sortie de boucle en ignorant tout sauf les [ et les ]
        case '[': nbBoucleAIgnorer++; break; // On compte les entrées de boucle imbriquées dans la boucle a ignorer
        case ']': nbBoucleAIgnorer--; break; // pour chaque entréee de boucle imbriquée, on ignore une sortie de boucle
        default : break;
}   }         // Et quand on rencontre la bonne sortie, le nombre de boucles a ignorer est a 0 donc on repasse en mode normal

int main(int nNumberOfArgs, char* pszArgs[]) {
    cout << "INTERPRETEUR BRAINF." << endl;
    string cNomFich = "";
    if (nNumberOfArgs > 1) cNomFich = pszArgs[1];      // nom du fichier transmi par l'appel de main
// un objet Execution contient toutes les variables necessaires a l'execution d'un fichier BF, gestion du fichier comprise
    Execution a;
    if (a.ouvreFichier(cNomFich)) {                    // on ouvre le fichier, rend vrai si l'ouverture réussi
        char l;                                        // Caractère a traiter
        while (a.get(l))                               // Tant que le fichier revoie un caractere, on le traite
            if (a.modeIgnorerboucle())                 // S'il y a des boucles a ignorer, CàD entrée avec 0
                a.rechercheLaSortieDeBoucle(l);        // on cherche la sortie de boucle,
            else                                       // s'il n'y a pas de boucles a ignorer on suit le traitement normal
                if (!a.fonctionnementNormal(l)) break; // en cas d'erreur revoie false, donc on sort de la boucle
        if (a.testDeFin()) cout << "\nerreur, [ sans ]"; // s'il reste des entrées de boucle après la fin du fichier
    }
    else cout << "Probleme a l'ouverture du fichier " << cNomFich ; // Si le fichier est illisible/introuvable,
    cout << endl;
    system("PAUSE");
    return 0;
}

Par exemple, le fameux code de la Suite de Fibonacci

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
$
> première case reste a 0 pour marquer la fin de l'affichage du nombre
++++++++++ 10 = code de retour a la ligne
>+ un chiffre est sur 3 cases la première garde le dernier chiffre affiché a 1 au départ
>+ la seconde case d'un chiffre marque qu'il éxiste et sert de compteur pour l'affichage et de case de transfert pour le calcul
[ Debut affichage d'un nombre[ Debut affichage d'un chiffre $
+++++[>++++++++<-]>$. chiffre plus 48 donne le code d'affichage$
<++++++[>--------<-]$+ fin d'affichage d'un chiffre 
<<< decallage vers le chiffre suivant
] fin d'affichage d'un nombre
>. retour a la ligne 
>>[$[-]$ mise a zero 2nde case du chiffre
<$[>+<-]$>Transfert 1ere case vers 2nde
>$[<<+>+>-]$<Ajout 3eme case (chiffre affiché) dans 1ere et 2nde 
puis transfert 2nde vers 3eme jusqu'a 9
[$>+<-$1[$>+<-$2[$>+<-$3[$>+<-$4[$>+<-$5[$>+<-$6[$>+<-$7[$>+<-$8[$>+<-$9
[ si on dépasse 9
$>[-]$ mise à 0
>+>+ incrément du chiffre suivant pour la retenue et de sa seconde case pour le créer si nécéssaire
<<<-retour au chiffre
$[>+<-]$ et fin du transfert 2nd case vers 3ème
]]]]]]]]]]+>>> on passe au calcul du chiffre suivant
]<<<retour au dernier chiffre pour lancer l'affichage]

donne :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
          4|   >|  0|  0+ première case reste a 0 pour marquer la fin de l'affichage du nombre
   76-   85|10x+|  0| 10+ 10 = code de retour a la ligne
        119|   >|  0| 10|  0+
        120|   +|  0| 10|  1+ un chiffre est sur 3 cases la première garde le dernier chiffre affiché a 1 au départ
        209|   >|  0| 10|  1|  0+
        210|   +|  0| 10|  1|  1+ la seconde case d'un chiffre marque qu'il éxiste et sert de compteur pour l'affichage et de case de transfert pour le calcul
        338|   [|  0| 10|  1|  1+ Debut affichage d'un nombre
        367|   [|  0| 10|  1|  1+ Debut affichage d'un chiffre 
        421|   .|  0| 10|  1|  0| 48+ chiffre plus 48 donne le code d'affichage
        488|   +|  0| 10|  1|  1+  0| fin d'affichage d'un chiffre 
  521-  523| 3x<|  0+ 10|  1|  1|  0| decallage vers le chiffre suivant
        560|   ]|  0+ 10|  1|  1|  0| fin d'affichage d'un nombre
        591|   >|  0| 10+  1|  1|  0|
        592|   .|  0| 10+  1|  1|  0| retour a la ligne 
  614-  615| 2x>|  0| 10|  1|  1+  0|
        616|   [|  0| 10|  1|  1+  0| mise a zero 2nde case du chiffre
        657|   <|  0| 10|  1+  0|  0|
        666|   >|  0| 10|  0|  1+  0|Transfert 1ere case vers 2nde
        698|   >|  0| 10|  0|  1|  0+
        710|   <|  0| 10|  0|  1+  0|Ajout 3eme case (chiffre affiché) dans 1ere et 2nde puis transfert 2nde vers 3eme jusqu'a 9
        806|   [|  0| 10|  0|  1+  0|1
        814|   [|  0| 10|  0|  0+  1|
       1098|   ]|  0| 10|  0|  0+  1|
       1099|   +|  0| 10|  0|  1+  1|
 1100- 1102| 3x>|  0| 10|  0|  1|  1|  0|  0+ on passe au calcul du chiffre suivant
       1143|   ]|  0| 10|  0|  1|  1|  0|  0+
 1144- 1146| 3x<|  0| 10|  0|  1+  1|  0|  0|retour au dernier chiffre pour lancer l'affichage
        338|   ]|  0| 10|  0|  1+  1|  0|  0| Debut affichage d'un nombre

J'avais, il y a quelques temps, réalisé un convertisseur BF->JS en PHP (histoire de bien faire le plus sale possible), qui évidemment met 3 plombes à exécuter l'algo de test :p.

Il est testable à cette adresse : http://fayedu39.1s.fr/brainfuck/brainfuck-sa.php

Et pour ce qui est des sources :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
var p=0;
var m=[0];
function disp(t) {
  if(t=="\n")
      t="<br/>";
  document.getElementById("out").innerHTML+=t;
}
window.onload=function(){
  <?php
      if(isset($_POST["brainfuck"]) && !empty($_POST["brainfuck"])) {
          $i=0;
          while($i<=strlen($_POST["brainfuck"])) {
              switch($_POST["brainfuck"][$i]) {
                  case '+':
                      echo('m[p]++;if(m[p]>255) m[p]=0;');
                  break;
                  case '-':
                      echo('m[p]--;if(m[p]<0) m[p]=255;');
                  break;
                  case '<':
                      echo('p--;if(p<0) p=30000;if(!m[p]) m[p]=0;');
                  break;
                  case '>':
                      echo('p++;if(p>=30000) p=0;if(!m[p]) m[p]=0;');
                  break;
                  case '.':
                      echo('disp(String.fromCharCode(m[p]));');
                  break;
                  case ',':
                      echo('m[p]=prompt(",");m[p]=m[p].charCodeAt(0);');
                  break;
                  case '[':
                      echo('while(m[p]) {');
                  break;
                  case ']':
                      echo('}');
                  break;
              }
              echo("\n");
              $i++;
          }
      }
  ?>
}

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte