Partage

[Exercices] Venez vous entraîner !

Ce mois: Parseur de fonctions mathématiques

21 juin 2011 à 17:42:38

pour faire que l'on puisse utiliser ce language dans du C++, il est possible d'implémenter à la manière du mot clé asm ?
par exemple :
befunge
{
>v
^<
}


enfin c'est qu'un exemple, mais se serai possible ?
21 juin 2011 à 17:49:57

Du inline befunge en C++ ? :p
Non je ne pense pas...
21 juin 2011 à 18:12:11

dommage se serai parfait ...
Anonyme
21 juin 2011 à 18:33:00

Directement, je sais pas (macros ?), mais y'aurais moyen de rajouter un petit préprocesseur qui remplacerais ça par un appel de fonction à l’interpréteur...
21 juin 2011 à 18:42:01

Personnellement, comme j'ai implémenté en fonction, en c++11 (pour la simplicité de l'expression) il faudrait appeller comme ça :
befunge({
">v",
"^<"
});

Et, en restant dans le c++ classique :
matrix m;
m.push_back(">v");
m.push_back("^<");
befunge(m);

(vous m'avourez que c'est moins élégant. ^^ )
Sachant qu'il faudrait simplement ajouter un paramètre stack, pour pouvoir récupérer le résultat si le befunge n'interagit pas directement avec l'utilisateur, ou bien pour passer des paramètres au programme.

Pour les macros, je ne pense pas que ce soit possible.
Anonyme
21 juin 2011 à 19:10:18

Rôôôhhh, du calme !

On ne va pas s'engueuler sur les normes, etc.
Libre à vous de choisir la norme qui vous plaît, on est ici pour laisser cours à son imagination, et pour "créer" un fungoïde...

Faites chacun ce que bon vous semble, et envoyez-le moi à la fin, en spécifiant ce que vous supportez comme syntaxe... ;)

Personnellement, vous avez vu que j'ai "créé" la mienne (de syntaxe) :

A à F : différentes piles
G à Z : téléporteurs
a à z : fonctions/variables, définies par l'interpréteur...
'(', ')', '[', ']', '{', '}', '=', ';', ''' : encore non définies par moi, mais pourquoi par des 'rotations', des 'demi-tours' ou des conditions spéciales ?
21 juin 2011 à 19:45:22

@Equinoxe : je crois que je vais laisser tomber le concept pour le moment (2D ça suffit amplement), je suis juste content d'avoir réussi à montrer que c'était possible :)
Je vais plutôt me concentrer sur ma version des fonctions :
et oui, encore des fichiers ! On peux même mettre des namespaces (les dossiers) !

Edit : @youyou : c'est tout à fait possible. Je regarde ça ;)
21 juin 2011 à 19:56:16

Bonne chance. :)

Je dois avouer que je m'en suis retourné à ma bibliothèque d'algorithme génétique (cf. wikipédia pour plus de détails), et que, du coup, j'ai arrêté mon interpréteur. Mais je commence à me demander si je ne vais pas coder un interpréteur BF en befunge. =D

Edit de précision, avant d'être pris au mot : C'est une blague
21 juin 2011 à 19:57:48

Citation : Equinoxe

Bonne chance. :)

Je dois avouer que je m'en suis retourné à ma bibliothèque d'algorithme génétique (cf. wikipédia pour plus de détails), et que, du coup, j'ai arrêté mon interpréteur. Mais je commence à me demander si je ne vais pas coder un interpréteur BF en befunge. =D

Edit de précision, avant d'être pris au mot : C'est une blague


Ben, manque juste la gestion d'écriture/lecture des fichiers pour ça :D !
21 juin 2011 à 19:59:06

Même pas, on peut prendre le fichier BF sur l'entrée standard en stockant ça dans un bout du programme befunge, et ensuite on redirige l'entrée standard vers le programme befunge. ^^

Finalement, peut-être que je vais essayer. :D
21 juin 2011 à 20:11:44

Lol, c'est comme si tu t'essayais à faire un interpréteur d'ASM en BF, c'est à se tirer une balle dans le pied !
21 juin 2011 à 23:01:19

Bah nan. :p
J'ai déjà implémenté les opérateurs < ; > ; + et -. ^^
Par contre, on n'a que 100 cases dans le tableau, la flemme de faire une ligne de 30000 cases dans mon fichier, vu que mon interpréteur refuse les put en dehors de la taille du fichier. :)

Edit : Et je viens d'implémenter le . et la , ... :D
Reste les crochets. Souhaitez-moi bonne chance. :-°
Au moins, ce sera une jolie réalisation de l'exercice BF. ^^

Re-Edit : Finalement (5 secondes plus tard) j'ai la flemme, et surtout je viens de voir l'heure. Bonne nuit.
22 juin 2011 à 2:18:27

Les crochets passent comme une lettre à la poste. Il suffit de travailler avec un delta et non pas un énuméré de direction (c'est certes possible avec des enums, mais guère joli).
Une fois le test mycose.b98 passé en entier, j'aurais un truc en C++11 à vous filer -- je remplace les switch par des lambdas => c'est plus concis, et dans l'absolu cela permet de reprogrammer les correspondances car dynamique.
C++: Blog|FAQ C++ dvpz|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS| Bons livres sur le C++| PS: Je ne réponds pas aux questions techniques par MP.
22 juin 2011 à 10:51:01

Citation : lmghs

Les crochets passent comme une lettre à la poste. Il suffit de travailler avec un delta et non pas un énuméré de direction (c'est certes possible avec des enums, mais guère joli).
Une fois le test mycose.b98 passé en entier, j'aurais un truc en C++11 à vous filer -- je remplace les switch par des lambdas => c'est plus concis, et dans l'absolu cela permet de reprogrammer les correspondances car dynamique.


Si tu parles de ce que fait Equinoxe, sache qu'il fait un interpréteur de Brainfuck en befunge :-° .
Sinon, pour ta 2e phrase, ça donne quoi en français ?
22 juin 2011 à 11:09:55

Je suis tombé sur une batterie de tests pour tester les commandes: http://users.tkk.fi/~mniemenm/befunge/mycology.html (c'est essentiellement du befunge 98, mais c'est pas mal pour éprouver les trucs très moyennement documentés)

Pour le [, je n'avais effectivement pas compris. Au temps pour moi.
C++: Blog|FAQ C++ dvpz|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS| Bons livres sur le C++| PS: Je ne réponds pas aux questions techniques par MP.
22 juin 2011 à 13:30:16

J'ai essayé de télécharger la suite de test pour la lancer, mais il se trouve qu'elle contient une erreur dans le premier test proposé.
En effet, il est marqué "should reflect" ; alors que l'interpréteur befunge ne doit pas "rebondir" contre les bords, mais plutot aller de l'autre côté : "A Befunge-93 program is treated as an 80x25 torus (a page which wraps around on the edges) of ASCII text.".
Et, en befunge-98, il me semble qu'il est demandé d'effectuer un backtracking, pour que le pointeur revienne au même endroit qu'avant.

Du coup, le premier test contient une erreur (boucle infinie). Je dois avouer que je ne continuerai pas à tester mon interpréteur.

Et, pour la direction, l'avantage d'un enum-like, c'est que ça permet de faire direction = c une fois qu'on a testé que c est bien une flèche.

Edit : Finalement j'ai lancé mycology.b98. Il ne me donne que des "good" au befunge-93 ; et aussi en partie au b98 ("wraparound works" ? C'est une erreur imho, je n'ai pas implémenté de backtracking, ou bien il s'est implémenté tout seul ? o_O ). Par contre, forcément, il fail au "a doesn't push 10" ; puisque j'ai implémenté les 6 piles qu'on peut changer par abcdef. :)
22 juin 2011 à 14:34:10

reflect, c'est "r" qui fait faire demi-tour il me semble.

Pour l'énum, j'avais fais comme ça aussi au départ. Puis finalement pour traiter les cas de delta non unitaire (cf. p.ex. la cmd 'j':Jump Forward/98) je suis passé à l'approche addition de vecteurs, ce qui simplifie énormément les mouvements (je n'ai plus un seul switch dans l'interpréteur).
C++: Blog|FAQ C++ dvpz|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS| Bons livres sur le C++| PS: Je ne réponds pas aux questions techniques par MP.
22 juin 2011 à 14:48:05

Moi je n'ai jamais eu un seul switch dans mon interpréteur...
25 juin 2011 à 22:49:05

J'ai fini l'interpréteur BF en befunge !
Le code (et celui qui me dit que ça manque de commentaires je le trucide) :
v            BF = Pointeur BF ; I = Instruction ; T = Valeur tableau ; T* = Pointeur tableau
                     
                     
             ==== On lit le BF sur l'entree standard ====

>101pv       On met 1 en (0, 1) : c'est la pos du prochain caractere du prog BF
>  v <
   >  ~:   v On pousse deux fois l'entree utilisateur sur la pile
   v  "E"  < On pousse le caractere E ; pour EOF ; fin du BF
   -         On pousse la difference. Ce sera 0 si ils sont egaux, 1 sinon
  v_v        On compare donc les deux
v   <        On a atteint un E : le programme BF est termine
# >v         On a un nouveau caractere du programme BF
   >01g    v On met sur la pile la position du dernier carac BF (en 0, 1) pour savoir ou placer le nouveau
#
^p10+1g10p1< On place le caractere BF au bon endroit, on incremente la valeur (0, 1), et on gere un autre caractere
$            On retire le 'E' inutile de la pile

             ==== Maintenant, on initialise le tableau BF. ====

> 0        v On commence par placer 0 sur la pile : c'est notre position ou on s'arrete
v     +1   < On passe a la position suivante
> :0\2p   v  Et on met 0 dans la position
v -**554: <  On compare la position a 100 (le nombre de cases du tableau BF)
>          | Si c'est different (donc position < 100) on remonte
v          < Sinon, on a initialise le tableau !

$            ==== Et finalement on execute le BF ! ====

> 0 102p   v On commence par placer le pointeur BF sur la pile et le pointeur tableau en (0, 2)
v      +1  < On passe a l'instruction suivante
>:01g`v      On compare avec la longueur du BF
     v_v     La comparaison
     @       On a fini : on est arrivé au bout du programme
v      <     Ou bien on execute l'instruction
>:1gv        On recupere l'instruction : (BF, I)
 v  <
 >"<"-v      Si c'est "<"
     v_v     On essaie
v    <       Ce n'est pas ca. On teste le suivant                                                                                                                                                          
 v     <     C'est ca. On execute                                                                                                                                                                          
 >02g  v     On recupere la position du pointeur tableau                                                                                                                                                   
 v  -1 <     On la diminue                                                                                                                                                                                 
 >02p      ^ On le sauvegarde, et on revient.                                                                                                                                                              
>:1gv        On recupere l'instruction : (BF, I)                                                                                                                                                           
 v  <                                                                                                                                                                                                      
 >">"-v      Si c'est ">"                                                                                                                                                                                  
     v_v     On essaie                                                                                                                                                                                     
v    <       Ce n'est pas ca. On teste le suivant                                                                                                                                                          
 v     <     C'est ca. On execute                                                                                                                                                                          
 >02g  v     On recupere la position du pointeur tableau                                                                                                                                                   
 v  +1 <     On l'augmente
 >02p      ^ On la sauvegarde, et on revient.
>:1gv        On recupere l'instruction : (BF, I)
 v  <
 >"+"-v      Si c'est "+"
     v_v     On essaie
v    <       Ce n'est pas ca. On teste le suivant
 v     <     C'est ca. On execute
 >02g: v     On recupere la position du pointeur tableau en double
 v  g2 <     On recupere la valeur de la case
 > 1+\ v     On l'augmente et on inverse les positions
 v  p2 <     On la sauvegarde
 >         ^ Et on revient.
>:1gv        On recupere l'instruction : (BF, I)
 v  <
 >"-"-v      Si c'est "-"
     v_v     On essaie
v    <       Ce n'est pas ca. On teste le suivant
 v     <     C'est ca. On execute
 >02g: v     On recupere la position du pointeur tableau en double
 v  g2 <     On recupere la valeur de la case
 > 1-\ v     On la diminue
 v  p2 <     On la sauvegarde
 >         ^ Et on revient.
>:1gv        On recupere l'instruction : (BF, I)
 v  <
 >"."-v      Si c'est "."
     v_v     On essaie
v    <       Ce n'est pas ca. On teste le suivant
 v     <     C'est ca. On execute
 >02g  v     On recupere la position du pointeur tableau
 v g2  <     On recupere la valeur de la case
 > ,       ^ Et on l'affiche, et on revient.
>:1gv        On recupere l'instruction : (BF, I)
 v  <
 >","-v      Si c'est ","
     v_v     On essaie
v    <       Ce n'est pas ca. On teste le suivant
 v     <     C'est ca. On execute
 >~02g v     On recupere l'entree et la position ou la placer
 v  p2 <     On la place
 >         ^ Et on revient.
>:1gv        On recupere l'instruction : (BF, I)
 v  <
 >"["-v      Si c'est "["
     v_v     On essaie
v    <       Ce n'est pas ca. On arrete
 v     <     C'est ca. On execute : (BF)
 >02g  v     On recupere la position du pointeur tableau : (BF, T*)
  vg2  <     On recupere la valeur de la case : (BF, T)
 v_v         On teste la valeur de la case : (BF)
 >         ^ La valeur n'est pas a 0. On passe a l'instruction suivante (BF)
 v <         La valeur est a 0. On cherche le "]" correspondant : (BF)
 >  1\    v  On a actuellement 1 "[" ouvert ; on recupere le pointeur BF : (N, BF)
  v:\+1   <  On passe a la case suivante : (BF, N, N)
 v_v         Si on a 0 "[" ouvert : (BF, N)
   >  $1-  ^ C'est le cas. On passe a la suite (en retirant 1 au pointeur BF pour eviter de sauter le caractere qui suit "]") : (BF)
 \           Ce n'est pas le cas. : (N, BF)
 >:1g    v   On recupere l'instruction : (N, BF, I)
   v-"]":<   Si c'est "]" : (N, BF, I, ?)
  v_v        On essaie : (N, BF, I)
 v< >$\1-\^  C'est "]". On va donc diminuer N et aller a la case suivante : (N, BF)
 >$:1g   v   Ce n'est pas "]". On regarde si c'est "[" : (N, BF)
   v-"[" <   Si c'est "[" : (N, BF, ?)
  v_v        On essaie : (N, BF)
  >       ^  Ce n'est pas ca. On passe au caractere suivant : (N, BF)
    > \1+\^  C'est ca. On augmente le compteur de profondeur et on passe au caractere suivant : (N, BF)
>:1gv        On recupere l'instruction : (BF, I)
 v  <
 >"]"-v      Si c'est "]"
     v_v     On essaie
     >     ^ Ce n'est pas ca. On arrete
 v     <     C'est ca. On execute : (BF)
 >02g  v     On recupere la position du pointeur tableau : (BF, T*)
  vg2  <     On recupere la valeur de la case : (BF, T)
 v_v         On teste la valeur de la case : (BF)
   >       ^ La valeur n'est pas a 0. On passe a l'instruction suivante (BF)
             La valeur est a 0. On cherche le "[" correspondant : (BF)
 >  1\    v  On a actuellement 1 "]" ouvert ; on recupere le pointeur BF : (N, BF)
  v:\-1   <  On passe a la case precedente : (BF, N, N)
 v_v         Si on a 0 "]" ouvert : (BF, N)
   >  $1+  ^ C'est le cas. On passe a la suite (en ajoutant 1 au pointeur BF pour eviter de reconsiderer le "[") : (BF)
 \           Ce n'est pas le cas. : (N, BF)
 >:1g    v   On recupere l'instruction : (N, BF, I)
   v-"[":<   Si c'est "[" : (N, BF, I, ?)
  v_v        On essaie : (N, BF, I)
 v< >$\1-\^  C'est "[". On va donc diminuer N et aller a la case precedente : (N, BF)
 >$:1g   v   Ce n'est pas "[". On regarde si c'est "]" : (N, BF)
   v-"]" <   Si c'est "]" : (N, BF, ?)
  v_v        On essaie : (N, BF)
  >       ^  Ce n'est pas ca. On passe au caractere suivant : (N, BF)
    > \1+\^  C'est ca. On augmente le compteur de profondeur et on passe au caractere suivant : (N, BF)

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.E

interpreteur_befunge bf.bef < hw.bf


Et la sortie attendue :
Hello World!

(Bien évidemment !)

A noter : un caractère "E" est nécessaire pour indiquer la fin du BF. Tout caractère subséquent au E sera envoyé comme input au BF. Et, enfin, il est à noter que le wrap-around aux 30000 caractères n'est pas implémenté, et qu'un dépassement des 30000 se traduit donc par une écriture en-dehors.

En pratique, les positions particulières :
- Premier caractère de la 2ème ligne : nombre de caractères du code BF
- Reste de la 2ème ligne : Le code BF
- Premier caractère de la 3ème ligne : position du pointeur sur le tableau BF
- Reste de la 3ème ligne : Le tableau BF
- Valeur la plus basse sur la pile : Le pointeur instruction BF

Enfin, il est à noter que seuls les éléments [0..99] du tableau BF sont actuellement remis à 0. Ceci peut se corriger à la ligne 24, en augmentant la valeur placée par "5*5*4" ; en ajoutant d'autres facteurs par exemple.

Vous pourrez me dire ce que vous en pensez ? :)
26 juin 2011 à 9:36:42

Tu devrais le poster dans [Atelier tous langages] Codez votre interpréteur brainfuck. Le sujet accepte de revivre sans trop de réticences. Il y a pleins d'optimisations qui sont indiquées sur ce sujet.
26 juin 2011 à 11:02:30

Le boulot de malade !
Et beh !
Bravo à toi !
26 juin 2011 à 14:01:14

Merci. Pour les optimisations, je pense que ce serait un peu du suicide que d'essayer de les coder en befunge, par contre. Surtout sachant qu'il tourne déjà relativement vite : mon interpréteur befunge + le hello world > moins d'une seconde :
$ time ./exec bf.bef < input 
Hello World!

real    0m0.010s
user    0m0.003s
sys     0m0.003s

Donc je n'ai pas forcément extrèmement besoin d'optimisations - mais, de toute façon, c'est surtout pour m'amuser.

J'ai donc posté sur le topic pointé ; mon message est accessible ici. :)
26 juin 2011 à 14:03:30

Sympa l'exercice Befunge, je me suis codé un petit interpréteur en C++11, comme ça je découvre un peu. :p

Du coup je me suis un peu amusé avec les lambda (seulement pour les opérations mathématiques pour l'instant), j'utilise une liste de pointeur sur Instruction (avec une méthode action) de façon dynamique comme ça plus tard on peut imaginer passer à la volée en mode bf98.

Un petit exemple :
struct PushX : public Instruction
{
    PushX(const unsigned int &number) : Instruction(' '), m_number(-1)
    {
        ostringstream oss;
        oss << number;
        character = oss.str()[0];
        if (number < 10) // otherwise invalid
            m_number = number;
    }

    void action(ProgramMap &program)
    {
        if (m_number >= 0) // otherwise invalid
            program.pushStack(m_number);
    }

    private:
        int m_number;
};


Et derrière une simple boucle suffit :
// Push instructions : '0' -> '9'
    for (unsigned int i = 0; i < 10; i++)
        m_instructions.push_back(new PushX(i));


:)

Equinoxe > Code de malade, respect!!!


EDIT : Pas bête la std::map youyou, j'y avais même pas pensé! Faut dire que j'ai fait à l'arrache au début, mais je voir si je peux pas changer c'est mieux ^^
Anonyme
26 juin 2011 à 15:14:54

Perso, j'ai préférer une std::map<char, Instruction>. Ça évite de faire la recherche toi même, et c'est plus efficace si tu ne range pas ton vector/list ;)

26 juin 2011 à 17:17:07

Personnellement je me suis servi de ça :
std::map<char, void (ScriptInterpretor::*)()> m_com;

ça évite de créer des classes à tire-larigot...

Edit : le lien vers le code source de mon interpréteur pour ceux que ça intéresse : http://www.mediafire.com/?m9bdk4061fp5nur
26 juin 2011 à 19:59:35

Pourquoi une struct plutôt qu'une class pierreyoda ?
26 juin 2011 à 20:05:59

@rom1504: C'est pareil. La différence est sur l'accessibilité par défaut. Dans son cas ca lui évite d'écrire un "public :" (et potentiellement 2, celui de l'héritage est superflux dans son cas).
FaQ : Fr | En 1 2 | C++11 | Template || Blog : Deloget | C++|Boost--Dev | C++Next | GotW || Installer Boost
26 juin 2011 à 20:17:07

Citation : Freedom

@rom1504: C'est pareil. La différence est sur l'accessibilité par défaut. Dans son cas ca lui évite d'écrire un "public :" (et potentiellement 2, celui de l'héritage est superflux dans son cas).


Oui enfin, si ça le fatigue tellement d'écrire public et private, c'est tout aussi possible d'écrire une fois public et pas private en mettant class, bref c'est pareil autant utiliser class ( je me demandais si il y avait une modification parce que c'est du c++11 mais apparemment non )
26 juin 2011 à 20:31:17

@rom1504: C'est juste un choix, comme l'indentation, le nom des identifiant et plein d'autre choses. Tant que ton code est cohérant tu fais ce que tu veux, je vois pas en quoi c'est dérangeant. (Et dans son cas il peut économiser plus qu'avec class puiqu'il aurait aussi pu enlever le public de l'héritage, avec class il doit le mettre, mais je suis d'accord c'est un "cout" dérisoire).
FaQ : Fr | En 1 2 | C++11 | Template || Blog : Deloget | C++|Boost--Dev | C++Next | GotW || Installer Boost
26 juin 2011 à 20:37:08

Oui c'est vrai mais en général je pense qu'il vaut mieux garder struct pour faire une "vrai struct" genre comme en C ( sans méthode et avec les attributs en public ).
Enfin c'est vrai que ça change pas grand chose.