Partage

[Atelier tous langages] Calculatrice(s)

objectif : apprenez à parser un langage simple !

<< 1 2 3 4 ... 7 >>

20 avril 2009 à 19:33:28

Excusez-moi, je n'apporte pas de code à l'atelier...
Je voudrais seulement proposer un sixième langage à parser: TeX (les opérandes les plus simples, bien sûr)

Maxibolt

20 avril 2009 à 21:11:53

Mouais, le but c'est pas de rajouter des opérateurs, puisqu'une fois qu'on en a implémenté un les autres ne sont pas trop durs à adapter... Le truc qu'on cherche à voir c'est surtout la façon d'implémenter le premier.

Anonyme

21 avril 2009 à 0:28:33

Je suis de retour en Ti-Basic ...

Cette fois j'ai fondu la notation polonaise avec la notation polonaise inversée, en plus d'une petite modification me permettant de ne pas répéter une certaine portion du code. Attention le code est rempli d'une certaine subtilité (cf la variable M :lol:

), pour ceux qui sont intéressés, je peux m'arranger pour donner des explications sur ce topic : http://www.siteduzero.com/forum-83-192 [...] r-les-ti.html

:ClrHome
:Disp "TYPE ?","0: NOT POL INV","1: NOT POL"," "
:Input M
:If M!=0 and M !=1
:Then
        :Disp "ERROR"
        :Stop
:End
:Input Str0
:length(Str0)->L
:1->B
:0->C
:0->D
:If M
        :0->N
:{0}->L1
:For(I,(L-1)M+1,(1-L)M+L,-2M+1)
        :inString(" 0123456789+-*/",sub(Str0,I,1))-2->A
        :If A+1 and A<10
        :Then
                :If M
                :Then
                        :A*10^N+C->C
                        :N+1->N
                :Else
                        A+10C->C
                :End
                :1->D
        :Else
                :If D
                :Then
                        :C->L1(B)
                        :B+1->B
                        :0->C
                        :0->D
                        :If M
                                :0->N
                :End
                :If A>9
                :Then
                        :B-1->B
                        :If not(A-10)
                                :L1(M+B-1)+L1(B-M)->L1(B-1)
                        :If not(A-11)
                                :L1(M+B-1)-L1(B-M)->L1(B-1)
                        :If not(A-12)
                                :L1(M+B-1)*L1(B-M)->L1(B-1)
                        :If not(A-13)
                                :L1(M+B-1)/L1(B-M)->L1(B-1)
                :End
        :End
:End
:Disp L1(1)

Non vous ne rêvez pas, il y a les deux notations à la fois. :-°

bluestorm

21 avril 2009 à 12:31:54

Sauf que tu ne fais aucun effort pour supporter la deuxième de manière efficace, tu te contentes d'appliquer la première après avoir retourné la chaîne en reversant les opérandes.

Cette méthode :
- est moins efficace qu'une méthode "normale" (qui est aussi simple à coder en général) parce qu'elle demande à ce que toute l'entrée soit en mémoire pour pouvoir parser (vu que tu commences par la fin)
- ne s'étend pas à des grammaires plus compliquées, que l'on rencontre forcément dès que l'on essaie de parser un "vrai" langage de programmation

May_Hop

21 avril 2009 à 12:44:03

Plop,

Voici ma participation en C pour le langage n°6:

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

int isOperator (char c) {
    int test = 0;

    if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^')
        test = 1;

    return test;
}

int calcul (int nb1, int nb2, char op) {
    int res = -1;

    switch (op) {
    case '+' :
        res = nb1 + nb2;
        break;
    case '-' :
        res = nb1 - nb2;
        break;
    case '/' :
        res = nb1 / nb2;
        break;
    case '*' :
        res = nb1 * nb2;
        break;
    case '^' :
        res = pow(nb1, nb2);
        break;
    }
    return res;
}

/* Renvoie 1 si op1 est prioritaire sur op2 */
int isMoreImportant (char op1, char op2) {
    int test = 0;

    if (op2 == '+' || op2 == '-')
        test = 1;
    else if ( (op2 == '*' || op2 == '/') && (op1 == '^') )
        test = 1;

    return test;
}

char* parseToRPN (char* in, int size, int* err) {
    char* bout = in;
    char* tmpout = in;
    *err = 0;

    /* pileTemporaire qui contiendra les opérandes.
    Il ne peut pas y avori plus d'opérande que de caracteres dans l'entrée*/
    char* fifo = malloc(size-1);

    if (fifo != NULL) {
        /* pointeur sur le début de la pile */
        char* b = fifo;
        while (*in != '\0' && *err == 0) { /* Tant qu'il y a des tokens */
            if (isdigit(*in)) {
                *tmpout = *in;
                tmpout++;
            } else if (*in == '(') {
                *fifo = *in;
                fifo++;
            } else if (isOperator(*in)) {
                if (fifo == b || *(fifo - 1) == '(' || isMoreImportant(*in, *fifo)) {
                    *fifo = *in;
                    fifo++;
                } else {
                    *tmpout = *(fifo - 1);
                    *(fifo - 1) = *in;
                    tmpout++;
                }
            } else if (*in == ')') {
                while (0 == *err) {
                    if (*(fifo - 1) == '(') {
                        fifo--;
                        break;
                    } else if (fifo - 1 == b) {
                        *err = -1;
                    } else {
                        *tmpout = *(fifo - 1);
                        tmpout++;
                        fifo--;
                    }
                }
            } else
                *err = -1;
            in++; /* on prend le token suivant */
        }
        /* on dépile les opérateurs restant */
        while (1) {
            if (b == fifo)
                break;
            *tmpout = *(fifo - 1);
            tmpout++;
            fifo--;
        }
        *tmpout = '\0';
        free(fifo); /* la pile n'était que temporaire */
    } else {
        *err = -1;
    }

    return bout;
}

int calculRPN (char* in, int size) {
    int* fifo = malloc(size-1);
    int res = -1;

    if (fifo != NULL) {
        while (*in) {
            if (isdigit(*in)) {
                *fifo = *in - '0';
                fifo++;
            } else {
                fifo -= 2;
                *fifo = calcul(*fifo, *(fifo+1), *in);
                fifo++;
            }
            in++;
        }
        res = *(fifo-1);
        free(fifo-1);
    }
    return res;
}

int main(void) {
    char in[] = "5-3";
    int err;
    char* out = NULL;
    int size = strlen(in)+1;

    out = parseToRPN(in, size, &err);

    if (err == 0 && out) {
        printf("Chaine parsee : %s\n", out);
        printf("Resultat : %d\n", calculRPN(out, size));
    } else {
        puts("Erreur\n");
    }

    free(in);

    return 0;
}

En fait, je transcris dans un premier temps l'expression en notation polonaise inverse, au moins je n'ai plus à me préoccuper des parenthèses et après je calcul.
Cet méthode comporte deux inconvénients : nombre d'opérations élevées, allocation de mémoire.
Par contre, si on veut améliorer le parseur c'est assez simple.
Si vous avez des critiques, conseils, questions ...

Il y a quelque mois, j'avais aussi réaliser un parseur pour ce même langage en procédant d'une manière totalement différente. J'avais codé une (bien moche) fonction récursive. Ca avait l'avantage de pouvoir gérer nombre négatif, virgule ... Mais pour améliorer c'est vraiment dur.
Je le mets aussi vu que les deux autres parseurs en C n'utilisent pas cette méthode.

/* Evaluation d'une chaine mathematique à partir d'un fichier calcul.txt */

/* On considère une expression mathématique comme une somme de produits
    Et à chaque fois que l'on rencontre une parenthèse on appelle récursivement la fonction */

double calcul(FILE* fichier) {
    char carLu = 0, nombreLu[100] = {0}, signe = '+', dernierSigne = '*', dernierCarLu = 0;
    double somme = 0, produit = 1, nombre = 1;
    int i, testSiNombre;

    if (fichier == NULL)
        printf("Erreur : Fichier inexistant\n");

    while (carLu != '\n') {
        if (carLu == ')')
            return somme;
            
        dernierCarLu = carLu;
        carLu = fgetc(fichier);

        do {
            if (carLu == '*') {
                dernierSigne = '*';
                dernierCarLu = carLu;
                carLu = fgetc(fichier);
            } else if (carLu == '/') {
                dernierSigne = '/';
                dernierCarLu = carLu;
                carLu = fgetc(fichier);
            }
            if (carLu == '-' &&  (dernierCarLu < '0' || dernierCarLu > '9')) {
                produit = -1;
                carLu = '*';
            }
            else if (carLu == '+' &&  (dernierCarLu< '0' || dernierCarLu > '9')) {
                produit = 1;
                carLu = '*';
            }
            testSiNombre = 0;
            for (i = 0; (carLu >= '0' && carLu <= '9') || carLu == '.'; i++) {
                testSiNombre = 1;
                nombreLu[i] = carLu;
                dernierCarLu = carLu;
                carLu = fgetc(fichier);
            }

            nombreLu[i] = '\0';
            nombre = 1;

            if (testSiNombre == 1)
                nombre = strtod(nombreLu, NULL);

            if (dernierSigne == '*')
                produit *= nombre;
            else if (dernierSigne == '/')
                produit /= nombre;

            if (carLu == '(') {
                if (dernierSigne == '*')
                    produit *=  calcul(fichier);
                else if (dernierSigne == '/')
                    produit /= calcul(fichier);
                carLu = fgetc(fichier);
            }
            dernierSigne = '*';

        } while (carLu == '*' || carLu == '/');

        if (signe == '+')
            somme+=produit;
        else if (signe == '-')
            somme-=produit;
        signe = carLu;
        produit = 1;
    } 
    return somme;
}

Merci pour cet atelier dans tout les cas

bluestorm

21 avril 2009 à 13:02:12

Je trouve ton utilisation systématique de "variables de retour" un peu lourde. Ça n'apporte pas grand chose, et ça complique même un peu le code (il faut faire attention à la valeur d'initialisation, etc.).

int isOperator (char c) {
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}

int calcul (int nb1, int nb2, char op) {
    switch (op) {
    case '+' : return nb1 + nb2;
    case '-' : return nb1 - nb2;
    case '/' : return nb1 / nb2;
    case '*' : return nb1 * nb2;
    case '^' : return pow(nb1, nb2);
    default: exit(EXIT_FAILURE);
    }
}

int isMoreImportant (char op1, char op2) {
    return (op2 == '+' || op2 == '-')
        || ((op2 == '*' || op2 == '/') && op1 == '^');
}

J'ai le sentiment qu'il y a des choses non gérées par ton premier code (pas lu le deuxième encore), mais je ne l'ai pas encore assez étudié pour être sûr. Pour commencer, tu ne gères pas les nombres à plus d'un chiffre, n'est-ce pas ?

May_Hop

21 avril 2009 à 13:07:04

Oui le 1er code ne gère pas les nombre, les virgules et nombres négatifs (par contre le 2ème le fait).

Sinon pour les variables, c'est juste une habitude. :euh:

Je vais faire plus attention à leur utilité mais ça évite d'avoir plusieurs return comme dans calcul.

Anonyme

21 avril 2009 à 23:50:04

Citation : bluestorm

Sauf que tu ne fais aucun effort pour supporter la deuxième de manière efficace, tu te contentes d'appliquer la première après avoir retourné la chaîne en reversant les opérandes.

Cette méthode :
- est moins efficace qu'une méthode "normale" (qui est aussi simple à coder en général) parce qu'elle demande à ce que toute l'entrée soit en mémoire pour pouvoir parser (vu que tu commences par la fin)
- ne s'étend pas à des grammaires plus compliquées, que l'on rencontre forcément dès que l'on essaie de parser un "vrai" langage de programmation

J'aimerais bien t'y voir à essayer d'économiser de la place sur ta calculatrice, j'ai pas un disque dur dessus moi. :lol:

Bien sûr, je pourrais utiliser une méthode dans le sens "normal", mais ça ne me motive pas d'utiliser une pile d'opérandes, et surtout je serais obligé d'utiliser une pile LIFO, ce qui est impossible en TI-Basic sans renverser ma pile, ce qui demande des calculs trop nombreux, autant travailler à l'envers. Ensuite je ne fais pas qu'un renversement de chaîne, la méthode pour gérer les nombres au lieu des chiffres est aussi différente (tu te doutes bien que je n'allais pas considérer 21 comme étant un 12 après renversement

).

Ensuite je ne vois pas trop ce que tu veux dire par "elle demande à ce que toute l'entrée soit en mémoire pour pouvoir parser (vu que tu commences par la fin)" ... peu importe la méthode, la mémoire sera autant sollicitée ... l'entrée c'est une chaîne de caractère, peu importe si je la lis à l'endroit ou à l'envers.

Bref ... j'ai aussi fait le LISP ... je lis aussi à l'envers, et j'ai aussi réussi à l'intégrer dans mon code précédent (économie de mémoire FTW).
Il me reste la notation classique et l'opérateur de puissance.

Nanoc

22 avril 2009 à 2:11:55

Sujet très intéressant que j'avais zappé jusqu'à maintenant.

En regardant dans mes tiroirs, j'ai trouvé du code qui pourrait vous intéresser. J'avais à l'époque développé un parseur de notation polonaise inversée qui marchait bien. Des gens m'ayant fait remarquer que la NPI c'est pas intuitif pour eux (bouh...), j'ai développé un traducteur pour mon parser. (Oui c'est tordu)
L'expression suit donc le chemin suivant:

expression usuelle -> NPI -> évaluation de la NPI -> réponse

Pour corser le tout, j'avais ajouté la possibilité de déclarer des variables et d'utiliser des fonctions mathématiques usuelles. Le code résultant est particulièrement moche mais il fonctionne. L'évaluation d'expression se fait de la manière suivante:

1) Tokenisation

L'expression est découpée en morçeaux recevant chacun un attribut pouvant être :

enum TYPE{NOMBRE,
OPERATEUR_1 = 1,   //+ ou -
OPERATEUR_2 = 2 ,  // * ou /
OPERATEUR_3 = 3,   // ^
VARIABLE,          
PARENTHESE_O,      //parenthèse ouvrante
PARENTHESE_F,      //parenthèse fermante
FONCTION, 
DECLARATION,       // Symbole := utilisé pour la déclaration de variables
VIRGULE,           //Virgule utilisée pour séparer les arguments des fonctions
ARGUMENT};         //Argument d'une fonction

L'expression passe donc du type string au type vector<Token> ou chaque Token est une paire (valeur, TYPE).

Voici le code:

bool Interpreteur::tokenize()
{
    m_tokens.clear();
    m_declaration = false;

    for (string::iterator it=m_expression.begin(); it!=m_expression.end();) //On parcourt la chaîne
    {
        if ((*it) == ' ' || (*it) == '\n' || (*it) == '\t') //Si le caractere courant est un espace
        {
            ++it;     //On passe au symbole suivant
        }

        else if ((*it) >= '0' && (*it) <= '9') //Si c'est un nombre
        {
            std::string texte;
            int nbr_virgules=0;
            do                              //On cherche la fin du nombre
            {
                texte += *it;
                ++it;
                if (*it=='.')
                    ++nbr_virgules;
            }
            while (((*it) >= '0' && (*it) <= '9')|| ((*it)=='.' && nbr_virgules <=1));
            //Tant que c'est un chiffre et qu'il y a pas eu plus de 1 virgule

            Token a(texte,NOMBRE);
            m_tokens.push_back(a);          //Et on met le nombre dans la liste

            if (nbr_virgules >1)
            {
                cerr << "ERREUR de parsage: Nombre a 2 virgules" << endl;
                return false;
            }
        }

        else if (((*it) >= 'a'&& (*it) <= 'z') ||((*it) >= 'A'&& (*it) <= 'Z')) //Si c'est une lettre
        {
            std::string texte;
            do                              //On cherche la fin du mot
            {
                texte += *it;
                ++it;
            }
            while (((*it) >= 'a'&& (*it) <= 'z') ||((*it) >= 'A'&& (*it) <= 'Z') || ((*it) >= '0'&& (*it) <= '9') || ((*it) == '_')); //0-9 et _  sont ok mais pas au debut

            if (*(it) == '(') //Si une parenthese ouvrante suit, c'est que c'est une fonction
            {
                Token a(texte,FONCTION);
                m_tokens.push_back(a);          //Et on met le token dans la liste
            }
            else //Sinon c'est une variable
            {
                Token a(texte,VARIABLE);
                m_tokens.push_back(a);          //Et on met le token dans la liste
            }
        }

        else if ((*it) == '+' || (*it) == '-') //Si c'est un operateur de bas niveau de priorite
        {
            std::string texte;
            texte += *it;
            Token a(texte,OPERATEUR_1);
            m_tokens.push_back(a);
            ++it;
        }

        else if ((*it) == '*' || (*it) == '/') //Si c'est un operateur de niveau moyen
        {
            std::string texte;
            texte += *it;
            Token a(texte,OPERATEUR_2);
            m_tokens.push_back(a);
            ++it;
        }

        else if ((*it) == '^')              //Si c'est un operateur de haut niveau
        {
            std::string texte("^");
            Token a(texte,OPERATEUR_3);
            m_tokens.push_back(a);
            ++it;
        }

        else if ((*it) == '(') //Si c'est une parenthese ouvrante
        {
            std::string texte("(");
            Token a(texte,PARENTHESE_O);
            m_tokens.push_back(a);
            ++it;
        }

        else if ((*it) == ')') //Si c'est une parenthese fermante
        {
            std::string texte(")");
            Token a(texte,PARENTHESE_F);
            m_tokens.push_back(a);
            ++it;
        }

        else if ((*it) == ':'  && (*(it+1))=='=') //Si c'est le symbole d'ajout de constante
        {
            std::string texte (":=");
            Token a(texte,DECLARATION);
            m_tokens.push_back(a);
            it+=2;
            if (m_declaration) //Si on a deja eu une declaration
            {
                cerr << "ERREUR de parsage: Double symbole de declaration" << endl;
                return false;
            }
            m_declaration = true;
        }

        else if ((*it) == ',') //Si c'est un separateur d'arguments
        {
            std::string texte(",");
            Token a(texte,VIRGULE);
            m_tokens.push_back(a);
            ++it;
        }
        else
        {
            cerr << "ERREUR de parsage: Symbole non-reconnu" << endl;
            return false;
        }
    }
    return true;
}

(Je vous avais dit que c'était dégeulasse)

2) Remplacement

A ce moment là, les variables sont remplacées par leur valeurs et les moins unaires sont remplacés par 0-x.
Les variables et constantes sont contenues dans des map<nom, valeur>.

bool Interpreteur::replace()
{
    for (vector<Token>::iterator it=m_tokens.begin(); it!=m_tokens.end(); ++it)
    {
        if (it->second == VARIABLE)
        {
            double val;
            if (m_constantes.find(it->first) !=m_constantes.end())
            {
                val = m_constantes[it->first];
            }
            else if (m_variables.find(it->first) !=m_variables.end())
            {
                val = m_variables[it->first];
            }
            else
            {
                cerr << "ERREUR de remplacement: Variable inconnue" << endl;
                return false;
            }

            (*it) = Token(toStr(val),NOMBRE);
        }
        else if (it->first == "-")  //On verifie si on a affaire au moins unaire
        {
            if (it==m_tokens.begin()) //Si on est au debut
            {
                Token a("0",NOMBRE); //On ajoute 0 devant de sorte a avoir 0-a
                it = m_tokens.insert(it,a);
            }
            else if ((it-1)-> first == "(") //ou si on a une parenthese ouvrante avant
            {
                Token a("0",NOMBRE); //On ajoute aussi un 0 devant
                it = m_tokens.insert(it,a);
            }
        }
    }
    return true;
}

3) Traduction en NPI

L'algorithme utilisé est décrit ici.
Tout se passe en jouant avec deux piles.

bool Interpreteur::toNPI()
{
    m_NPI.clear();

    stack<Token> pile;  //Pile temporaire

    for (vector<Token>::iterator it=m_tokens.begin(); it!=m_tokens.end(); ++it)
    {
        if (it->second == NOMBRE) //Si c'est un nombre
        {
            m_NPI.push_back(*it);  //On l'empile dans la sortie
        }
        else if (it->second == FONCTION) //Si c'est une fonction
        {
            pile.push(*it);
        }
        else if (it->second == OPERATEUR_1 || it->second == OPERATEUR_2 || it->second == OPERATEUR_3) //Si c'est un operateur
        {
            while (!pile.empty()) //Tant que la pile est non-vide
            {
                if (pile.top().second != PARENTHESE_O) //Et que c'est un operateur au sommet
                {
                    Token O2 = pile.top();
                    int P_op1 = it->second;
                    int P_op2 = O2.second;
                    if (P_op1<=P_op2)                 //Si la priorite de l'operateur est inferieur a celui de la pile
                    {
                        pile.pop();                   //alors on met O2 dans la sortie
                        m_NPI.push_back(O2);
                    }
                    else                                //Dans le cas contraire, on sort
                    {
                        break;
                    }
                }
                else        //Si c'est une parenthese ouvrante, on sort
                {
                    break;
                }
            }
            pile.push(*it);  //On empile notre operateur
        }
        else if (it->second == VIRGULE)  // Si c'est un separateur d'arguments
        {
            while (pile.top().second != PARENTHESE_O && !pile.empty())  //Jusqu ce que le sommet de la pile soit une parenthese ouvrante
            {
                m_NPI.push_back(pile.top());  //Empiler l'element au sommet dans la sortie
                pile.pop();
            }

            if (pile.empty()) //Si la pile est vide
            {
                cerr << "ERREUR de traduction: Expression mal parenthesee" << endl;
                return false;
            }
        }

        else if (it->second == PARENTHESE_O) //Si c'est une parenthese ouvrante
        {
            pile.push(*it); //On l'empile dans la pile
        }
        else if (it->second == PARENTHESE_F) //Si c'est une parenthese fermante
        {
            Token current;
            do
            {
                if (pile.size()>0)    //On depile jusqu'a ce qu'on trouve une parenthese ouvrante
                {
                    current=pile.top();
                    if (current.second!=PARENTHESE_O)
                        m_NPI.push_back(current);
                    pile.pop();
                }
                else
                {
                    //Si la pile est vide c'est qu'il y a une erreur de parentheses
                    cerr << "ERREUR de traduction: Expression mal parenthesee" << endl;
                    return false;
                }
            }
            while (current.second!=PARENTHESE_O); //On depile tant qu'on a pas une parenthese ouvrante

            if (pile.size()!=0)
            {
                if (pile.top().second == FONCTION) //Si on a une fonction au sommet de la pile
                {
                    m_NPI.push_back(pile.top());  //On la depile dans la sortie
                    pile.pop();
                }
            }
        }
        else
        {
            //Ne devrait jamais arriver
            cerr << "ERREUR de traduction: Token inconnu" << endl;
            return false;
        }
    }

    //On termine en vidant la pile dans la sortie
    while (!pile.empty())
    {
        if (pile.top().second==PARENTHESE_O)
        {
            cerr << "ERREUR de traduction: Expression mal parenthesee" << endl;
            return false;
        }
        else
        {
            m_NPI.push_back(pile.top());
        }
        pile.pop();
    }
    return true;
}

4) Evaluation

Il ne reste plus alors qu'à évaluer l'expression en NPI en utilisant l'algorithme classique.
Les fonctions sont contenues dans une map< nom, Fonction> ou Fonction est une classe qui permet de contenir n'importe quelle fonction recevant n (n<4) doubles et renvoyant un double.

bool Interpreteur::calculate()
{
    stack<double> pile;
    double a,b; //Variables pour les operandes

    for (vector<Token>::iterator it=m_NPI.begin(); it!=m_NPI.end(); ++it)
    {
        if (it->second == NOMBRE)
        {
            pile.push(frmStr(it->first));
        }
        else if (it->second == OPERATEUR_1 || it->second == OPERATEUR_2 || it->second == OPERATEUR_3)
        {
            b = pile.top();
            pile.pop();

            if(pile.empty())
            {
                cerr << "ERREUR d'evaluation: Nombre d'operandes invalide" << endl;
                return false;
            }

            a = pile.top();
            pile.pop();

            switch ((it->first)[0])
            {
            case '+':
                pile.push(a+b);
                break;
            case '-':
                pile.push(a-b);
                break;
            case '*':
                pile.push(a*b);
                break;
            case '/':
                pile.push(a/b);
                break;
            case '^':
                pile.push(pow(a,b));
                break;
            }
        }

        else if (it->second == FONCTION)
        {
            if (m_fonctions.find(it->first) !=m_fonctions.end()) //Si la fonction existe
            {
                Fonction f(m_fonctions[it->first]);

                std::vector<double> arguments(f.getnbArguments());  //On vérifie le nombre d'arguments

                for (unsigned int i=0;i<f.getnbArguments();++i)
                {
                    arguments[f.getnbArguments() - i -1] = pile.top();
                    pile.pop();
                }
                pile.push(f.eval(arguments));

            }
            else
            {
                cerr << "ERREUR d'evaluation: Fonction inconnue" << endl;
                return false;
            }
        }
        else    //Ne devrait jamais arriver
        {
            cerr << "ERREUR d'evaluation: Symbole non-reconnu" << endl;
            return false;
        }
    }
    m_result = pile.top();
    return true;
}

On a ainsi notre résultat.

5) Declaration

Si à l'étape 1 on a détecté un symbole := qui sert à la déclaration de variables, on passe alors à un traitement supplémentaire qui évalue l'expression à droite de l'opérateur et qui sauvegarde le résultat dans la liste des variables.

std::string Interpreteur::declare()
{
    if (m_tokens.size() > 2)
    {
        //de la forme "var := expression"
        if (m_tokens[0].second == VARIABLE && m_tokens[1].second == DECLARATION)
        {
            std::string var = m_tokens[0].first;  //On sauvegarde la variable
            if (m_constantes.find(var) != m_constantes.end())  //Si cette var existe deja en constante
            {
                cerr << "ERREUR de declaration: Nom de variable deja pris par une constante" << endl;
                m_result =0;
                m_tokens.clear();
                return "";
            }
            m_tokens.erase(m_tokens.begin(),m_tokens.begin()+2);
            return var;
        }
    }
    cerr << "ERREUR de declaration: Arguments non-valide" << endl;
    m_tokens.clear();
    m_result=0;
    return "";
}

Comme vous pouvez le voir, le code est extremement long en C++, principalement à cause des difficultés de parsage des chaînes de caractères.

Le code complet du programme tient en 5 fichiers:

#include <iostream>
#include "Interpreteur.h"

using namespace std;

int main()
{
    Interpreteur a;

    cout << "'quit' ou 'exit' pour quitter" << endl;

    string expr;

    cout.precision(15);

    do
    {
        cout << "> " << flush;
        getline(cin,expr);

        if (expr == "quit" || expr=="exit")
            break;

        cout << a.evaluate(expr) << endl;
    }
    while (true);

    return 0;
}

#ifndef INTERPRETEUR_H
#define INTERPRETEUR_H

#include <string>
#include <vector>
#include <map>

class Fonction;

enum TYPE{NOMBRE,OPERATEUR_1 = 1,OPERATEUR_2 = 2 ,OPERATEUR_3 = 3,VARIABLE,PARENTHESE_O,PARENTHESE_F,FONCTION,DECLARATION,VIRGULE,ARGUMENT};
//Operateur_1 = +-  Operateur_2 = /*  Operateur_3 = ^
typedef std::pair<std::string,TYPE> Token;

class Fonction;

class Interpreteur
{
//---------------------------------------------------------------------------------

public:

    Interpreteur();
    ~Interpreteur();

    double evaluate(const std::string& expr);  //Evalue l'expression passée en argument

    void addConstante(const std::string& nom, double val);  //Ajoute une constante dans la liste

    void addVariable(const std::string& nom, double val);    //Ajoute une variable dans la liste

    void addFonction(const Fonction& f);  //Ajoute une fonction dans la liste

private:

    Interpreteur(const Interpreteur&);
    void operator=(const Interpreteur&);

    bool tokenize();    //Découpe l'expression en tokens et classe les tokens selon leur TYPE

    bool toNPI();    //Traduit les tokens en notation polonaise inversée

    bool calculate();   //Calcule le résulat de NPI et le met dans m_result

    bool replace();   //Remplace les variables par leur valeur et les moins unaire

    std::string declare();  //Renvoit le nom de la nouvelle variable déclarée si valide

    //--------------------------------------------------------------------------

    std::string m_expression;       //L'expression sous forme de string
    std::vector<Token> m_tokens;    //L'expression découpée en tokens
    std::vector<Token> m_NPI;       //L'expression tokenisée traduite en NPI
    double m_result;                //Le résultat de l'évaluation

    std::map< std::string, double> m_variables;              //Les variables
    std::map< std::string, double> m_constantes;             //Les constantes
    std::map< std::string, Fonction> m_fonctions;            //Les fonctions

    bool m_declaration;             //True si l'expression est une déclaration

};

#endif

#include "Interpreteur.h"
#include "Fonction.h"

#include <iostream>
#include <cmath>
#include <stack>

using namespace std;

Interpreteur::Interpreteur()
    :m_expression(),
    m_tokens(),
    m_NPI(),
    m_result(0),
    m_variables(),
    m_constantes(),
    m_fonctions(),
    m_declaration()
{
    //On ajoute les constantes a l'interpreteur
    m_constantes["pi"] = M_PI;
    m_constantes["e"] = M_E;
    m_constantes["RAND_MAX"] = RAND_MAX;

    //On ajoute quelques variables
    m_variables["leet"] = 1337;
    m_variables["devil"] = 666;
    m_variables["Version"] = 1.3;

    //On ajoute quelques fonctions
    m_fonctions["sin"] = Fonction(sin,"sin");
    m_fonctions["cos"] = Fonction(cos,"cos");
    m_fonctions["tan"] = Fonction(tan,"tan");
    m_fonctions["asin"] = Fonction(asin,"asin");
    m_fonctions["acos"] = Fonction(acos,"acos");
    m_fonctions["atan"] = Fonction(atan,"atan");
    m_fonctions["sinh"] = Fonction(sinh,"sinh");
    m_fonctions["cosh"] = Fonction(cosh,"cosh");
    m_fonctions["tanh"] = Fonction(tanh,"tanh");
    m_fonctions["abs"] = Fonction(abs,"abs");
    m_fonctions["exp"] =Fonction(exp,"exp");
    m_fonctions["ln"] = Fonction(log,"ln");
    m_fonctions["log"] = Fonction(log10,"log");
    m_fonctions["sqrt"] = Fonction(sqrt,"sqrt");
    m_fonctions["floor"] = Fonction(floor,"floor");
    m_fonctions["ceil"] = Fonction(ceil,"ceil");
    m_fonctions["rand"] = Fonction(myRand,"rand");
    m_fonctions["max"] = Fonction(myMax,"max");
    m_fonctions["min"] = Fonction(myMin,"min");

    srand(time(NULL));
}

Interpreteur::~Interpreteur()
{}

void Interpreteur::addConstante(const std::string& nom, double val)
{
    m_constantes[nom]=val;
}

void Interpreteur::addVariable(const std::string& nom, double val)
{
    m_variables[nom]=val;
}

void Interpreteur::addFonction(const Fonction& f)
{
    m_fonctions[f.getNom()] = f;
}

double Interpreteur::evaluate(const string& expression)
{
    m_expression =  expression;

    if (expression == "")
        return 0;

    std::string var;      //Nom en cas de nouvel variable

    if (tokenize())
    {
        if (m_declaration)
            var = declare();

        if (replace()) //Si le remplacement passe
        {
            if (toNPI())    //Si la traduction passe
            {
                if (calculate())  //Si le calcule passe
                {
                    if (m_declaration)
                        addVariable(var,m_result);
                    return m_result;
                }
            }
        }
    }

    return 0;
}

bool Interpreteur::tokenize()
{
    m_tokens.clear();
    m_declaration = false;

    for (string::iterator it=m_expression.begin(); it!=m_expression.end();) //On parcourt la chaîne
    {
        if ((*it) == ' ' || (*it) == '\n' || (*it) == '\t') //Si le caractere courant est un espace
        {
            ++it;     //On passe au symbole suivant
        }

        else if ((*it) >= '0' && (*it) <= '9') //Si c'est un nombre
        {
            std::string texte;
            int nbr_virgules=0;
            do                              //On cherche la fin du nombre
            {
                texte += *it;
                ++it;
                if (*it=='.')
                    ++nbr_virgules;
            }
            while (((*it) >= '0' && (*it) <= '9')|| ((*it)=='.' && nbr_virgules <=1));
            //Tant que c'est un chiffre et qu'il y a pas eu plus de 1 virgule

            Token a(texte,NOMBRE);
            m_tokens.push_back(a);          //Et on met le nombre dans la liste

            if (nbr_virgules >1)
            {
                cerr << "ERREUR de parsage: Nombre a 2 virgules" << endl;
                return false;
            }
        }

        else if (((*it) >= 'a'&& (*it) <= 'z') ||((*it) >= 'A'&& (*it) <= 'Z')) //Si c'est une lettre
        {
            std::string texte;
            do                              //On cherche la fin du mot
            {
                texte += *it;
                ++it;
            }
            while (((*it) >= 'a'&& (*it) <= 'z') ||((*it) >= 'A'&& (*it) <= 'Z') || ((*it) >= '0'&& (*it) <= '9') || ((*it) == '_')); //0-9 et _  sont ok mais pas au debut

            if (*(it) == '(') //Si une parenthese ouvrante suit, c'est que c'est une fonction
            {
                Token a(texte,FONCTION);
                m_tokens.push_back(a);          //Et on met le token dans la liste
            }
            else //Sinon c'est une variable
            {
                Token a(texte,VARIABLE);
                m_tokens.push_back(a);          //Et on met le token dans la liste
            }
        }

        else if ((*it) == '+' || (*it) == '-') //Si c'est un operateur de bas niveau de priorite
        {
            std::string texte;
            texte += *it;
            Token a(texte,OPERATEUR_1);
            m_tokens.push_back(a);
            ++it;
        }

        else if ((*it) == '*' || (*it) == '/') //Si c'est un operateur de niveau moyen
        {
            std::string texte;
            texte += *it;
            Token a(texte,OPERATEUR_2);
            m_tokens.push_back(a);
            ++it;
        }

        else if ((*it) == '^')              //Si c'est un operateur de haut niveau
        {
            std::string texte("^");
            Token a(texte,OPERATEUR_3);
            m_tokens.push_back(a);
            ++it;
        }

        else if ((*it) == '(') //Si c'est une parenthese ouvrante
        {
            std::string texte("(");
            Token a(texte,PARENTHESE_O);
            m_tokens.push_back(a);
            ++it;
        }

        else if ((*it) == ')') //Si c'est une parenthese fermante
        {
            std::string texte(")");
            Token a(texte,PARENTHESE_F);
            m_tokens.push_back(a);
            ++it;
        }

        else if ((*it) == ':'  && (*(it+1))=='=') //Si c'est le symbole d'ajout de constante
        {
            std::string texte (":=");
            Token a(texte,DECLARATION);
            m_tokens.push_back(a);
            it+=2;
            if (m_declaration) //Si on a deja eu une declaration
            {
                cerr << "ERREUR de parsage: Double symbole de declaration" << endl;
                return false;
            }
            m_declaration = true;
        }

        else if ((*it) == ',') //Si c'est un separateur d'arguments
        {
            std::string texte(",");
            Token a(texte,VIRGULE);
            m_tokens.push_back(a);
            ++it;
        }
        else
        {
            cerr << "ERREUR de parsage: Symbole non-reconnu" << endl;
            return false;
        }
    }
    return true;
}

bool Interpreteur::replace()
{
    for (vector<Token>::iterator it=m_tokens.begin(); it!=m_tokens.end(); ++it)
    {
        if (it->second == VARIABLE)
        {
            double val;
            if (m_constantes.find(it->first) !=m_constantes.end())
            {
                val = m_constantes[it->first];
            }
            else if (m_variables.find(it->first) !=m_variables.end())
            {
                val = m_variables[it->first];
            }
            else
            {
                cerr << "ERREUR de remplacement: Variable inconnue" << endl;
                return false;
            }

            (*it) = Token(toStr(val),NOMBRE);
        }
        else if (it->first == "-")  //On verifie si on a affaire au moins unaire
        {
            if (it==m_tokens.begin()) //Si on est au debut
            {
                Token a("0",NOMBRE); //On ajoute 0 devant de sorte a avoir 0-a
                it = m_tokens.insert(it,a);
            }
            else if ((it-1)-> first == "(") //ou si on a une parenthese ouvrante avant
            {
                Token a("0",NOMBRE); //On ajoute aussi un 0 devant
                it = m_tokens.insert(it,a);
            }
        }
    }
    return true;
}

bool Interpreteur::toNPI()
{
    m_NPI.clear();

    stack<Token> pile;  //Pile temporaire

    for (vector<Token>::iterator it=m_tokens.begin(); it!=m_tokens.end(); ++it)
    {
        if (it->second == NOMBRE) //Si c'est un nombre
        {
            m_NPI.push_back(*it);  //On l'empile dans la sortie
        }
        else if (it->second == FONCTION) //Si c'est une fonction
        {
            pile.push(*it);
        }
        else if (it->second == OPERATEUR_1 || it->second == OPERATEUR_2 || it->second == OPERATEUR_3) //Si c'est un operateur
        {
            while (!pile.empty()) //Tant que la pile est non-vide
            {
                if (pile.top().second != PARENTHESE_O) //Et que c'est un operateur au sommet
                {
                    Token O2 = pile.top();
                    int P_op1 = it->second;
                    int P_op2 = O2.second;
                    if (P_op1<=P_op2)                 //Si la priorite de l'operateur est inferieur a celui de la pile
                    {
                        pile.pop();                   //alors on met O2 dans la sortie
                        m_NPI.push_back(O2);
                    }
                    else                                //Dans le cas contraire, on sort
                    {
                        break;
                    }
                }
                else        //Si c'est une parenthese ouvrante, on sort
                {
                    break;
                }
            }
            pile.push(*it);  //On empile notre operateur
        }
        else if (it->second == VIRGULE)  // Si c'est un separateur d'arguments
        {
            while (pile.top().second != PARENTHESE_O && !pile.empty())  //Jusqu ce que le sommet de la pile soit une parenthese ouvrante
            {
                m_NPI.push_back(pile.top());  //Empiler l'element au sommet dans la sortie
                pile.pop();
            }

            if (pile.empty()) //Si la pile est vide
            {
                cerr << "ERREUR de traduction: Expression mal parenthesee" << endl;
                return false;
            }
        }

        else if (it->second == PARENTHESE_O) //Si c'est une parenthese ouvrante
        {
            pile.push(*it); //On l'empile dans la pile
        }
        else if (it->second == PARENTHESE_F) //Si c'est une parenthese fermante
        {
            Token current;
            do
            {
                if (pile.size()>0)    //On depile jusqu'a ce qu'on trouve une parenthese ouvrante
                {
                    current=pile.top();
                    if (current.second!=PARENTHESE_O)
                        m_NPI.push_back(current);
                    pile.pop();
                }
                else
                {
                    //Si la pile est vide c'est qu'il y a une erreur de parentheses
                    cerr << "ERREUR de traduction: Expression mal parenthesee" << endl;
                    return false;
                }
            }
            while (current.second!=PARENTHESE_O); //On depile tant qu'on a pas une parenthese ouvrante

            if (pile.size()!=0)
            {
                if (pile.top().second == FONCTION) //Si on a une fonction au sommet de la pile
                {
                    m_NPI.push_back(pile.top());  //On la depile dans la sortie
                    pile.pop();
                }
            }
        }
        else
        {
            //Ne devrait jamais arriver
            cerr << "ERREUR de traduction: Token inconnu" << endl;
            return false;
        }
    }

    //On termine en vidant la pile dans la sortie
    while (!pile.empty())
    {
        if (pile.top().second==PARENTHESE_O)
        {
            cerr << "ERREUR de traduction: Expression mal parenthesee" << endl;
            return false;
        }
        else
        {
            m_NPI.push_back(pile.top());
        }
        pile.pop();
    }
    return true;
}

bool Interpreteur::calculate()
{
    stack<double> pile;
    double a,b; //Variables pour les operandes

    for (vector<Token>::iterator it=m_NPI.begin(); it!=m_NPI.end(); ++it)
    {
        if (it->second == NOMBRE)
        {
            pile.push(frmStr(it->first));
        }
        else if (it->second == OPERATEUR_1 || it->second == OPERATEUR_2 || it->second == OPERATEUR_3)
        {
            b = pile.top();
            pile.pop();

            if(pile.empty())
            {
                cerr << "ERREUR d'evaluation: Nombre d'operandes invalide" << endl;
                return false;
            }

            a = pile.top();
            pile.pop();

            switch ((it->first)[0])
            {
            case '+':
                pile.push(a+b);
                break;
            case '-':
                pile.push(a-b);
                break;
            case '*':
                pile.push(a*b);
                break;
            case '/':
                pile.push(a/b);
                break;
            case '^':
                pile.push(pow(a,b));
                break;
            }
        }

        else if (it->second == FONCTION)
        {
            if (m_fonctions.find(it->first) !=m_fonctions.end()) //Si la fonction existe
            {
                Fonction f(m_fonctions[it->first]);

                std::vector<double> arguments(f.getnbArguments());

                for (unsigned int i=0;i<f.getnbArguments();++i)
                {
                    arguments[f.getnbArguments() - i -1] = pile.top();
                    pile.pop();
                }
                pile.push(f.eval(arguments));

            }
            else
            {
                cerr << "ERREUR d'evaluation: Fonction inconnue" << endl;
                return false;
            }
        }
        else    //Ne devrait jamais arriver
        {
            cerr << "ERREUR d'evaluation: Symbole non-reconnu" << endl;
            return false;
        }
    }
    m_result = pile.top();
    return true;
}

std::string Interpreteur::declare()
{
    if (m_tokens.size() > 2)
    {
        //de la forme "var := expression"
        if (m_tokens[0].second == VARIABLE && m_tokens[1].second == DECLARATION)
        {
            std::string var = m_tokens[0].first;  //On sauvegarde la variable
            if (m_constantes.find(var) != m_constantes.end())  //Si cette var existe deja en constante
            {
                cerr << "ERREUR de declaration: Nom de variable deja pris par une constante" << endl;
                m_result =0;
                m_tokens.clear();
                return "";
            }
            m_tokens.erase(m_tokens.begin(),m_tokens.begin()+2);
            return var;
        }
    }
    cerr << "ERREUR de declaration: Arguments non-valide" << endl;
    m_tokens.clear();
    m_result=0;
    return "";
}

#ifndef FONCTION_H
#define FONCTION_H

#include <string>
#include <vector>

#include "Interpreteur.h"

class Fonction
{

typedef double(*F0)();
typedef double(*F1)(double);
typedef double(*F2)(double,double);
typedef double(*F3)(double,double,double);

public:
    Fonction();  //Jamais appelé mais nécessaire pour compiler
    Fonction(F0 ptr,const std::string& nom);
    Fonction(F1 ptr,const std::string& nom);
    Fonction(F2 ptr,const std::string& nom);
    Fonction(F3 ptr,const std::string& nom);

    bool operator<(const Fonction&) const;   //Pour pouvoir trier
    double eval(const std::vector<double>& arguments) const;   //Evalue la fonction selon les arguments passés
    unsigned int getnbArguments() const;
    const std::string& getNom() const;

private:

    bool m_isPointeur;              //True si la fonction utilise un pointeur sur fonction
    unsigned int m_nbArguments;     //Le nombre d'arguments de la fonction
    std::string m_nom;              //Le nom de la fonction

    //LEs pointeurs sur fonctions

    double(*m_F0)(void) ;
    double(*m_F1)(double) ;
    double(*m_F2)(double,double) ;
    double(*m_F3)(double,double,double);
};

//Quelques fonctions mathématiques triviales

double myRand(); // Renvoit un double entre 0 et 1
double myMax(double a,double b);
double myMin(double a,double b);

//FONCTION UTILE POUR LES STRINGS
std::string toStr(double a);
double frmStr(const std::string& s);

#endif

#include "Fonction.h"

#include <iostream>
#include <algorithm>
using namespace std;

Fonction::Fonction()
        :m_isPointeur(false),
        m_nbArguments(0),
        m_nom("none"),
        m_F0(0),
        m_F1(0),
        m_F2(0),
        m_F3(0)
{}

Fonction::Fonction(F0 ptr,const std::string& nom)
        :m_isPointeur(true),
        m_nbArguments(0),
        m_nom(nom),
        m_F0(ptr),
        m_F1(0),
        m_F2(0),
        m_F3(0)
{}

Fonction::Fonction(F1 ptr,const std::string& nom)
        :m_isPointeur(true),
        m_nbArguments(1),
        m_nom(nom),
        m_F0(0),
        m_F1(ptr),
        m_F2(0),
        m_F3(0)
{}

Fonction::Fonction(F2 ptr,const std::string& nom)
        :m_isPointeur(true),
        m_nbArguments(2),
        m_nom(nom),
        m_F0(0),
        m_F1(0),
        m_F2(ptr),
        m_F3(0)
{}

Fonction::Fonction(F3 ptr,const std::string& nom)
        :m_isPointeur(true),
        m_nbArguments(3),
        m_nom(nom),
        m_F0(0),
        m_F1(0),
        m_F2(0),
        m_F3(ptr)
{}

double Fonction::eval(const std::vector<double>& arguments) const
{
    if (arguments.size() != m_nbArguments)
    {
        cerr << "ERREUR: La fonction " << m_nom << " n'a pas recu le bon nombre d'arguments" << endl;
        return 0;
    }

    if (m_isPointeur)    //Si c'est une fonction "C++"
    {
        switch (m_nbArguments)
        {
        case 0:
            return m_F0();
        case 1:
            return m_F1(arguments[0]);
        case 2:
            return m_F2(arguments[0],arguments[1]);
        case 3:
            return m_F3(arguments[0],arguments[1],arguments[2]);
        default:
            return 0;    //Ne devrait jamais arriver
        }
    }
    return 0;
}

unsigned int Fonction::getnbArguments() const
{
    return m_nbArguments;
}

bool Fonction::operator<(const Fonction& autre) const
{
    return m_nom < autre.m_nom;
}

const std::string& Fonction::getNom() const
{
    return m_nom;
}

//FONCTIONS MATHEMATIQUES-------------------------------------------------------------------


double myRand()
{
    return static_cast<double>(std::rand()) / static_cast<double>(RAND_MAX);
}

double myMax(double a,double b)
{
    return (a>b)? a : b;
}

double myMin(double a,double b)
{
    return (a<b)? a : b;
}

//FONCTION UTILE POUR LES STRINGS ---------------------------------------------------------

#include <sstream>

std::string toStr(double a)
{
    std::ostringstream oss;
    oss << a;
    return oss.str();
}

double frmStr(const std::string& s)
{
    std::istringstream iss( s);
    double nombre;
    iss >> nombre;
    return nombre;
}

Si j'ai le temps un de ces jours, je coderai une version plus propre (exceptions, const-correct, sans warnings,...) et sans trop de fioritures inutiles (variables, fonctions,...) tel que demandé.

Voici quand même ce que ça donne (pour ceux qui ont pas le courage de compiler :-°

'quit' ou 'exit' pour quitter
> pi
3.14159
> r:=4 
4
> aire := pi*r^2   
50.26544
> rand()
0.647600840147399
> 1+cos(0.5) 
1.87758256189037
> (4+3)/2*5^4
2187.5
> sin(4+3)
0.656986598718789
> aire + 1 / 2
50.76544
> quit

J'ai posté même si c'est ce code contient trop de fonctionnalités pour la partie "traduction".

Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.

rks`

22 avril 2009 à 11:44:31

Hum, petite remarque n'ayant pas grand chose à voir avec le sujet : le code à l'intérieur des blocs « secret » c'est bien sympa pour pas faire des posts de 15km, mais pour la lisibilité c'est quand même pas le top, pourquoi ne pas utiliser un pastebin externe au site dans ce cas ?
(En vrac : http://paste.pocoo.org , http://pastebin.be ).

Sinon, pour en revenir au sujet, tu gères déjà la déclaration de variables Nanoc? Cool !

PS: J'ai terriblement honte de mes codes par rapport à ceux de Sprank

bluestorm

23 avril 2009 à 20:12:54

Les langages 4 et 5, en OCaml (syntaxe révisée) en utilisant la lib Camlp4 (compilation : ocamlfind ocamlc -pp camlp4rf -package camlp4.lib -linkpkg -o test parse.ml) :

open Camlp4.PreCast;
module CalcGram = MakeGram(Lexer);
  
value expr = CalcGram.Entry.mk "expr";

EXTEND CalcGram
  GLOBAL: expr;  
  expr:
  [ "+" [ e1 = SELF; op = ["+" -> (+) | "-" -> (-) ]; e2 = SELF -> op e1 e2 ]
  | "*" [ e1 = SELF; op = ["*" -> ( * ) | "/" -> (/) ]; e2 = SELF -> op e1 e2 ]
  | "^" RIGHTA [ e1 = SELF; "^"; e2 = SELF -> truncate (float e1 ** float e2) ]
  | "simple" [ `INT i _ -> i
             | "("; e = SELF; ")" -> e ] ];
END;

value () = Printf.printf "%d\n"
  (CalcGram.parse expr (CalcGram.Loc.mk "<stdin>") (Stream.of_channel stdin));

robocop

23 avril 2009 à 22:22:40

Haha ton truc blustorm ça ressemble presque a du ocamlyacc/lex.
Sinon, j'ai essayé de faire le lisp, mais j'ai une erreure je sais pas trop pourquoi :

open Genlex;;

let cal f l =
  List.fold_left f (List.hd l) (List.tl l)
;;
let f = function "+" -> (+) | "-" -> (-) | "*" -> ( * ) | _ -> (/);;
let lexer i = make_lexer ["+";"-";"*";"/"; "("; ")"] (Stream.of_string i)
;;

let rec exec = parser
    [<'Kwd "("; 'Kwd (("*" | "/" | "+" | "-") as op); l = rules; 'Kwd ")">] -> cal (f op) l
and el = parser
    [<e = exec; ss>] -> e::(el ss)
  | [<>] -> []
and nums = parser 
    [<'Int n; ss >] -> n :: (nums ss) 
  | [<>] -> []
and rules = parser
    [<e = el>] -> e
  | [<n = nums>] -> n
;;
exec (lexer "(+ 5 3)");;

Il me sort toujours :

# exec (lexer "(+ 5 3)");;
Exception: Stream.Error "".

Une idée ?

Nanoc

23 avril 2009 à 22:26:58

Bon puisque les paquets externes sont à la mode, voici une version C++ utilisant boost::spirit. La grammaire que j'ai spécifiée pour ce parser correspond au langage usuel sans les puissances.

#include <iostream>
#include <stack>
#include <functional>

#include <boost/spirit.hpp>
using namespace boost::spirit;

std::stack<int> pile;  //Pile des resultats intermediaires

struct ajouteInt  //Foncteur ajoutant un entier a la pile en l'extrayant d'une chaine
{
    void operator()(char const* str, char const*) const
    {
        pile.push(std::strtol(str, 0, 10));
    }
};

//Un foncteur evaluant les deux derniers elements de la pile et empilant le resultat de l'evaluation
//operateur est lui-meme un foncteur venant de la STL (du header functional)
template <class operateur>
struct Evalue
{
    Evalue(operateur const& the_op) : m_op(the_op) {}

    void operator()(char const*, char const*) const
    {
        const int rhs = pile.top();
        pile.pop();
        const int lhs = pile.top();
        pile.pop();
        pile.push(m_op(lhs, rhs));
    }
private:
    operateur m_op;
};

//Un foncteur pour utiliser le moins unaire
struct MoinsUnaire
{
    void operator()(char const*, char const*) const
    {
        const int lhs = pile.top();
        pile.pop();
        pile.push(-lhs);
    }
};

int main()
{
//Definition de la grammaire ---------------------------------------------

    rule<phrase_scanner_t> expression, terme, facteur, nombre;

    // 1) Un nombre est un signe moins (ou pas) suivi d'un certain nombre de digits (1 au minimum)
    //    Si on en rencontre un, on appelle ajouteInt()
    nombre =
         lexeme_d[ (!ch_p('-') >> +digit_p)[ajouteInt()] ];

    // 2) Un facteur est un nombre OU unes expression entre parentheses OU un moins unaire devant un facteur
    //    Si c'est un moins unaire alors on appelle MoinsUnaire
    facteur =
            nombre
        |   '(' >> expression >> ')'
        |   ('-' >> facteur)[MoinsUnaire()];

    // 3) Un terme est un facteur suivi d'un nombre quelquonque de ( '*' suivi d'un facteur OU '/' suivi d'un facteur)
    //    Si il y a un des operateurs, on appelle le foncteur correspondant
    terme =
        facteur >>
            *( ('*' >> facteur)[Evalue<std::multiplies<long> >(std::multiplies<long>())]
             | ('/' >> facteur)[Evalue<std::divides<long> >(std::divides<long>())]);

    // 4) Une expression est un terme suivi d'un nombre quelqueonque de ( '+' suivi d'un terme OU '-' suivi d'un terme)
    //    Si il y a un des operateurs, on appelle le foncteur correspondant
    expression  =
        terme >>
            *( ('+' >> terme)[Evalue<std::plus<long> >(std::plus<long>())]
             | ('-' >> terme)[Evalue<std::minus<long> >(std::minus<long>())]);

//Fin de la definition -----------------------------------------------------

    std::cout << "'quit' ou 'exit' pour quitter" << std::endl;
    std::string chaine;

    do
    {
        std::cout << "> " << std::flush;
        std::getline(std::cin,chaine);

        if (chaine == "quit" || chaine=="exit")
            break;

        //On parse la chaine et si il n'y a pas d'erreur on affiche le resultat
        if (parse(chaine.c_str(), expression,space_p).full)
            std::cout << pile.top() << std::endl;
        else
            std::cout << "Erreur" << std::endl;

        while(!pile.empty())
            pile.pop();
    }
    while (true);

    return 0;
}

La partie intéressante se situe entre les lignes 50 et 80 du script. C'est là que la grammaire EBNF du langage se définit.

Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.

bluestorm

24 avril 2009 à 0:30:58

robocop : le problème vient de ta fonction "rules"

and el = parser
    [<e = exec; ss>] -> e::(el ss)
  | [< >] -> []
and nums = (* ... *)
and rules = parser
    [<e = el>] -> e
  | [<n = nums>] -> n

Ta fonction rules est un choix "soit el, soit nums", mais à cause de la règle [< >], el accepte tout donc sera toujours choisi, et nums n'est jamais essayé, d'où l'erreur.

Pour corriger il faut virer les flots vides de el et nums. Au passage, "el" rappelait "el" et "nums" rappelait "nums", ce qui clairement ne va pas marcher (ça revient à n'accepter que des listes de nombres, ou que des listes d'expressions, mais pas un mélange des deux). Il faut rappeler "rules", donc on a :

let rec exec = parser
    [<'Kwd "("; 'Kwd (("*" | "/" | "+" | "-") as op); l = rules; 'Kwd ")">] -> cal (f op) l
and el = parser
    [<e = exec; ss >] -> e :: el ss
and nums = parser 
    [<'Int n; ss >] -> n :: nums ss
and rules = parser
    [< e = el >] -> e
  | [< n = nums >] -> n
  | [< >] -> []

Maintenant, on voit que "el" et "nums" sont simplifiables :

let rec exec = parser
    [<'Kwd "("; 'Kwd (("*" | "/" | "+" | "-") as op); l = rules; 'Kwd ")">] -> cal (f op) l
and rules stream = match stream with parser
    [< e = exec >] -> e :: rules stream
  | [< 'Int n >] -> n :: rules stream
  | [< >] -> []
;;

robocop

24 avril 2009 à 9:51:14

A oui, exact, merci de ton aide bluestorm.
Voici mon code final ainsi revisité :

open Genlex
let eval s = 
  let cal f l =
    List.fold_left f (List.hd l) (List.tl l)
  in
  let f = function "+" -> (+) | "-" -> (-) | "*" -> ( * ) | _ -> (/) in
  let lexer i = make_lexer ["+";"-";"*";"/"; "("; ")"] (Stream.of_string i) in
  let rec exec = parser
      [<'Kwd "("; 'Kwd (("*" | "/" | "+" | "-") as op); l = rules; 'Kwd ")">] -> cal (f op) l
  and rules = parser
      [<e = exec; ss>] -> e::(rules ss)
    | [<'Int n; ss >] -> n ::(rules ss) 
    | [<>] -> []
  in exec (lexer s)
let () =  
  print_int (eval "(-(+ 5 2 3) ( * 4 2))")

robocop

25 avril 2009 à 16:23:08

En me basant sur le code de Cacophrene, j'ai fais un analyseur de booléens.
Ex : true&&false => false
Ex 2 : ((true||false)&&(true=true))=false => false

Code :
lexer.mll

{ open Parser }

rule token = parse
  | "&&"        { AND }
  | "||"        { OR  }
  | '='         { EQ  }
  | '('         { LPA }
  | ')'         { RPA }
  | "true"      { BOOL true }
  | "false"     { BOOL false }
  | _           { token lexbuf }
  | eof         { EOF }

paser.mly

%token LPA RPA EOF AND OR EQ
%token <bool> BOOL

%start eval
%type <bool option> eval

%%

eval:
  | /* Empty */         { None }
  | expr EOF            { Some $1 }
  | error               { failwith "Syntax error" }

expr:
  | BOOL                { $1 }
  | LPA expr RPA        { $2 }
  | expr AND expr       { $1 && $3 }
  | expr OR expr        { $1 || $3 }
  | expr EQ expr        { $1 = $3 }

bluestorm

25 avril 2009 à 16:54:47

Il manque les règles de priorité : && a la priorité sur ||, et il manque "not".

pen Camlp4.PreCast
module CalcGram = MakeGram(Lexer)
let expr = CalcGram.Entry.mk "expr"

let () = EXTEND CalcGram
  expr:
  [ "||" [ e1 = SELF; "||"; e2 = SELF -> e1 || e2 ]
  | "&&" [ e1 = SELF; "&&"; e2 = SELF -> e1 && e2 ]
  | "not" [ "not"; e = SELF -> not e ]
  | "simple" [ "true" -> true | "false" -> false
             | "("; e = SELF; ")" -> e ] ];
END

let () = Printf.printf "%B\n"
  (CalcGram.parse expr (CalcGram.Loc.mk "<stdin>") (Stream.of_channel stdin))

Cacophrene

25 avril 2009 à 17:52:39

Salut !

Citation : robocop

En me basant sur le code de Cacophrene, j'ai fais un analyseur de booléens.

Oui, c'est important, il faut le rappeler : mon code à base de lex/yacc ne se soucie pas des priorités des opérateurs, ce qui donne assez vite une mauvaise réponse. Utilise %left, %right et %nonassoc pour les règles d'associativité, et l'ordre relatif de ces éléments pour les priorités. Exemple :

%token ADD MUL POW

%left ADD   /* Associatif à gauche  */
%left MUL   /* Prioritaire sur ADD. */
%right POW  /* Associatif à droite. */

%%
/* suite du code ici */

Extrait du tutoriel d'ocamlyacc, en anglais :

Citation : ocamlyacc tutorial

Ocamlyacc allows you to specify these choices with the operator precedence declarations %left and %right. Each such declaration contains a list of tokens, which are operators whose precedence and associativity is being declared. The %left declaration makes all those operators left-associative and the %right declaration makes them right-associative. A third alternative is %nonassoc, which declares that it is a syntax error to find the same operator twice ``in a row''.

The relative precedence of different operators is controlled by the order in which they are declared. The first %left or %right declaration in the file declares the operators whose precedence is lowest, the next such declaration declares the operators whose precedence is a little higher, and so on.

Cordialement,
Cacophrène

robocop

25 avril 2009 à 18:18:13

Merci pour vos réponses.
Du coup, j'ai fais une autre version un peu plus fun :
lexer.mll

{ open Parser }

rule token = parse
  | '!'         { NOT }
  | "&&"        { AND }
  | "||"        { OR  }
  | '='         { EQ  }
  | '<'         { SI }
  | '>'         { SS }
  | "<="        { IE }
  | ">="        { SE }
  | '('         { LPA }
  | ')'         { RPA }
  | "true"      { BOOL true }
  | "false"     { BOOL false }
  | ['0'-'9']+  { NUM (int_of_string (Lexing.lexeme lexbuf))}
  | '+'         { ADD }
  | '-'         { REM }
  | '*'         { MUL }
  | "if"        { IF }
  | "then"      { THEN }
  | "else"      { ELSE}
  | _           { token lexbuf }
  | eof         { EOF }

parser.mly

%token LPA RPA EOF NOT AND OR EQ SI SS IE SE ADD REM MUL IF THEN ELSE
%token <bool> BOOL
%token <int> NUM

%start eval
%type <int option> eval

%left ADD  
%left REM
%left MUL

%left NOT
%left OR
%left AND

%%

eval:
  | /* Empty */         { None }
  | expr EOF            { Some $1 }
  | error               { failwith "Syntax error" }

expr:
  | IF cond THEN expr ELSE expr  {if $2 then $4 else $6}
  | IF LPA cond RPA THEN expr ELSE expr  {if $3 then $6 else $8}
  | num       { $1 }
  | LPA expr RPA       { $2 }
cond:
  | BOOL                { $1 }
  | LPA cond RPA        { $2 }
  | NOT cond            { not $2 }
  | cond OR cond        { $1 || $3 }
  | cond AND cond       { $1 && $3 }
  | cond EQ cond        { $1 = $3 }
  | num EQ num          { $1 = $3 }
  | num SI num          { $1 < $3 }
  | num SS num          { $1 > $3 }
  | num IE num          { $1 <= $3 }
  | num SE num          { $1 >= $3 }
num:
  | NUM                   { $1 }
  | expr ADD expr         { $1 + $3}
  | expr REM expr         { $1 - $3}
  | expr MUL expr         { $1 * $3}

Exemple de ce que l'on peut faire :

5 + if (!(5=3 && true)) then 3 else 2
8

Mais ça devient un peu bordelique ce truc en une passe.
Prochaine étape : arbre et typage :).

rks`

25 avril 2009 à 20:11:08

On sort du cadre du sujet là...
Moi j'ai jamais vu de calculatrices avec notions de typage, de tests conditionnels ni quoi que ce soit de ce genre.

ordiclic

25 avril 2009 à 20:53:37

Moi si, ma Casio...

Maxibolt

25 avril 2009 à 21:18:21

T'as vu du typage sur ta casio toi ? T'as bien de la chance alors.

ordiclic

25 avril 2009 à 22:48:07

Non, pas typage, mais calcul avec des conditions.
J'aurais dû préciser.

Anonyme

26 avril 2009 à 16:32:36

Les conditions oui.
Le typage ... euh, y'a les nombres, les listes, les matrices et les chaînes de caractères, m'enfin bon, quand on veut un certain type, on est limité à certains noms de variables. (pas vraiment du typage ...)

Sinon, on peut vraiment faire des tests conditionnels sur certaines, si je tape "If A/2=ipart(A/2):Then:A/2->A:Else:3A+1->A:End" sur l'écran principal, ça va marcher, à condition que la variable A existe (je rappelle que sur les plus petites TI/Casio les variables sont toujours globales).

Enfin bref, je ne pense pas qu'on nous demande de refaire ce genre de calculatrice, sinon on va dériver sur "comment codez-vous l'écran graphique ?". :lol:

Maxibolt

26 avril 2009 à 17:38:42

"on peut vraiment faire des tests conditionnels sur certaines" -> sans blague. Tu peux en faire sur des matrices ou des listes aussi, mais ça n'est pas ce qu'on cherche à faire.

gnomnain

26 avril 2009 à 17:51:21

Bah il y a du typage sur ta calculatrice (en tout cas sur ma Ti-84) : t'as des matrices, des listes, des nombres, et tu peux pas mélanger ça n'importe comment.

Maxibolt

26 avril 2009 à 19:00:53

C'est pas vraiment du typage ça, en tout cas sur casio, et sur TI ça doit ressembler, les variables ne peuvent prendre que des nombres, et le fait qu'on ne puisse pas les additionner avec des matrices relève plus de la syntaxe.
En pratique, le résultat est le même, mais pour moi c'est pas le même conception.

Anonyme

26 avril 2009 à 20:55:37

Citation : Maxibolt

"on peut vraiment faire des tests conditionnels sur certaines" -> sans blague. Tu peux en faire sur des matrices ou des listes aussi, mais ça n'est pas ce qu'on cherche à faire.

Non mais certaines personnes croyaient le contraire ...

Au fait, on peut multiplier une matrice par un nombre hein. :-°

Maxibolt

26 avril 2009 à 21:32:47

Oui, en fait on peut même additionner matrice et nombre. Raison de plus pour qu'il n'y ait pas de typage alors :-°

robocop

27 avril 2009 à 16:59:50

...
Ou alors qu'il y a une surcharge de l'opérateur"+" pour qu'il fonctionne avec un nombre ou une matrice...

Bref, pouvons nous revenir au sujet de départ qui était (lui) interessant ?
Merci.

<< 1 2 3 4 ... 7 >>