Discussion :

[millie]

Bonjour,

Pour le deuxième défi, l'équipe de developpez.com vous propose un challenge un peu plus délicat que le précédent.

Challenge :

Le but est de réaliser un interpréteur d'expression mathématiques. Il y aura en entrée du programme (ou de la fonction) soit une chaine de caractères, soit un fichier. En sortie, il y aura le résultat de l'évaluation de l'expression arithmétique.

Si une erreur de syntaxe est détectée, un message d'erreur pourra s'afficher. La grammaire (que nous n'allons pas décrire) sera celle des expressions arithmétiques parenthésées avec les 4 opérateurs +, -, * et /, et pouvant comprendre les fonctions : sin et cos.
Les nombres pourront être des entiers (0, 1, -1), ou des flottants (0.01, -9.78) que vous pourrez limiter à deux décimales après la virgule (et séparé par un .)

Par exemple, votre programme pourra évaluer des expressions comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
1+1
1+ 1
-3.0 + 4 -6.00
1.00 + 1
(1+ (2) * 3 + cos(3 + 2)/sin(1))
1-1
1-(-1)

Donner une erreur dans un cas comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
1+(
1+*3
tan(3)

Et éventuellement émettre un message de division par 0 dans le cas d'une expression comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
1/0
1/sin(1-1)

Modification : Le programme peut fonctionner ou donner une erreur de syntaxe dans ces cas comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
cos 3
1--1

Les règles

Il n'y a pas de règle particulière (évidemment, il faut que la solution proposée fonctionne). Vous pouvez proposer des solutions aussi bien dans des langages fonctionnels (caml, haskell, scheme, lisp...) qu'impératif. Le public pourra ainsi juger du code suivant divers critères :

• la maintenabilité
• la simplicité
• le fait qu'il soit optimisé

Attention, nous interdisons toutefois l'utilisation d'un évaluateur d'expressions mathématiques "tout prêt", le but étant quand même de montrer à quoi ressemble un "micro-interprète". Ainsi, nous refuserons des propositions du style suivant :

Code perl :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
open (my $in, '<', 'exp.txt') or die "Erreur I/O : $!";
 
while (<$in>)
{
	my $var = eval "$_";
	$@ ? print "$@\n" : print "$var\n";
}

Par ailleurs, nous apprécierions quelques remarques sur le fonctionnement de votre programme, comme le nombre de passes nécessaires pour traiter un fichier, éventuellement les complexités spatiales et temporelles, etc.



Le public pourra également juger les différences entre une solution fonctionnelle et une solution impérative. Il lui sera ainsi plus facile de voir, pour un même problème, les différences entre divers paradigmes.


A vos claviers
de votre participation.

[Jean-Marc.Bourguet]

Rien que pour m'amuser:

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <math.h>
 
typedef enum fn_id { bad_id, sin_id, cos_id } fn_id;
 
double eval_factor(char const* exp, char const** end);
double eval_term(char const* exp, char const** end);
double eval_exp(char const* exp, char const** end);
 
int error_occured = 0;
 
void error(char const* msg, char const* remainder)
{
  if (!error_occured) {
    printf("%s at: %s\n", msg, remainder);
    error_occured = 1;
  }
 
}
 
char const* skipws(char const* exp)
{
  while (isspace((int)(unsigned char)*exp)) {
    exp++;
  }
  return exp;
 
}
 
fn_id getfn(char const** x)
{
    if ((*x)[0] == 's' && (*x)[1] == 'i' && (*x)[2] == 'n' && !isalpha((*x)[3])) {
        (*x) += 3;
        return sin_id;
    } else if ((*x)[0] == 'c' && (*x)[1] == 'o' && (*x)[2] == 's' && !isalpha((*x)[3])) {
        (*x) += 3;
        return cos_id;
    } else {
        error("Bad function name", *x);
        while (isalpha(**x)) {
            ++(*x);
        }
        return bad_id;
    }
}
 
double eval_factor(char const* exp, char const** end)
{
  double result;
  exp = skipws(exp);
  if (*exp == '(') {
    result = eval_exp(exp+1, end);
    if (**end != ')') {
      error("missing closing parenthesis", *end);
    } else {
      ++*end;
    }
  } else if (*exp == '+') {
    result = eval_factor(exp+1, end);
  } else if (*exp == '-') {
    result = -eval_factor(exp+1, end);
  } else if (isalpha(*exp)) {
    switch(getfn(&exp)) {
    case sin_id:
        result = sin(eval_factor(exp, end));
        break;
    case cos_id:
        result = cos(eval_factor(exp, end));
        break;
    case bad_id:
        break;
    }
  } else {
    char* endptr;
    result = strtod(exp, &endptr);
    *end =  endptr;
    if (*end == exp) {
      error("invalid number", *end);
    }
  }
  return result;
 
}
 
double eval_term(char const* exp, char const** end)
{
  double result = eval_factor(exp, end);
  *end = skipws(*end);
  while (**end == '*' || **end == '/') {
    char const* op = *end;
    double factor = eval_factor(*end+1, end);
    if (*op == '*') {
      result *= factor;
    } else if (factor != 0.0) {
      result /= factor;
    } else {
      error("divide by 0.0", op);
    }
    *end = skipws(*end);
  }
  return result;
 
}
 
double eval_exp(char const* exp, char const** end)
{
  double result = eval_term(exp, end);
  *end = skipws(*end);
  while (**end == '+' || **end == '-') {
    char const* op = *end;
    double term = eval_term(*end+1, end);
    if (*op == '+') {
      result += term;
    } else {
      result -= term;
    }
    *end = skipws(*end);
  }
  return result;
 
}
 
double eval(char const* exp)
{
  char const* end;
  double result = eval_exp(exp, &end);
  if (*end != '\0') {
    error("trailing data after the expression", end);
  }
  return result;
 
}
 
int main(int argc, char *argv[])
{
  while (*++argv != NULL) {
    double result;
    error_occured = 0;
    printf("evaluating %s\n -> ", *argv);
    result = eval(*argv);
    if (!error_occured) {
      printf("%.10g\n", result);
    }
  }
  return 0;
 
}

Note que j'accepte:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
1--1
cos 3

avec la signification evidente.

[millie]

Rapide

Je pensais que les solutions en C ou en C++ auraient tendance à utiliser des outils comme lex/yacc.

[Jean-Marc.Bourguet]

Rapide

http://www.developpez.net/forums/sho...09&postcount=4

J'ai juste eu a ajouter sin/cos.

Je pensais que les solutions en C ou en C++ auraient tendance à utiliser des outils comme lex/yacc.

Overkill.

[LLB]

Code lexer.fsl :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
{
 open Lexing
 open Parser
}

let num   = ['0'-'9' '.']+
let space = [' ' '\t' '\n' '\r']+

rule main = parse
 | space   { main lexbuf }
 | num     { VAL (lexeme lexbuf |> Float.of_string) }
 | "("     { LPAR }
 | ")"     { RPAR }
 | "cos"   { FCT cos }
 | "sin"   { FCT sin }
 | "+"     { OP1 (+) }
 | "-"     { OP1 (-) }
 | "*"     { OP2 ( *) }
 | "/"     { OP2 (/) }
 | "%"     { OP2 (%) }
 | eof     { EOF }
 | _       { failwith (lexeme lexbuf) }

Code parser.fsy :

Sélectionner tout - Visualiser dans une fenêtre à part

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
%{
open Lexing

type fct_1 = float -> float
type fct_2 = float -> float -> float
%}

%token EOF LPAR RPAR
%token <float> VAL
%token <fct_2> OP1 OP2
%token <fct_1> FCT

%left OP1
%left OP2
%left FCT

%start main
%type <float> main exp
%%

main: exp EOF    { $1 }

exp:
 | VAL           { $1 }
 | LPAR exp RPAR { $2 }
 | OP1 exp       { $1 0. $2 }
 | exp OP1 exp   { $2 $1 $3 }
 | exp OP2 exp   { $2 $1 $3 }
 | FCT exp       { $1 $2 }

Code eval.fs :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
try
  Parser.main Lexer.main (Lexing.from_string Sys.argv.[1]) |> printf "%.2f\n"
with
  _ -> printf "Error"

Overkill.

Ça dépend ce que tu cherches à optimiser : simplicité de code, maintenabilité, extensibilité...
Dans mon code, il suffit d'ajouter une ligne pour gérer une nouvelle fonction ou un nouvel opérateur, par exemple : "| "abs" { FCT abs }".

Et pareil, les expressions suivantes sont acceptées :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
1--1
cos -1
cos(-1)
cos sin 1
+ cos 1

[gorgonite]

j'avais une version ocaml avec lex et yacc, puis interprétation (donc 3 passes)... mais LLB vient d'en donner la solution optimisée "calcul en 2 passes"

Code lexer.mll :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
{
  open Parser
}

let dot = ['.']
let chiffre = ['0'-'9']
let lettre = ['a'-'z''A'-'Z']
let alphanum = lettre | chiffre
let operateurs_add = ['+' '-']
let operateurs_mul = ['*' '/']

rule nextToken = parse
        eof { EOF }
        |'(' { LPAR }
        |')' { RPAR } 
        |operateurs_mul as o { OP_mul(String.make 1 o) }
        |operateurs_add as o { OP_add(String.make 1 o) }
        |chiffre* as nb { INT(int_of_string nb)}
        |chiffre+ dot chiffre+ as nb { FLOAT(float_of_string nb)}
        |lettre alphanum* as f { FUNC(f) }
        |_ { nextToken lexbuf }

{
}

Code parser.mly :

Sélectionner tout - Visualiser dans une fenêtre à part

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
%{
  open Ast;;
%}

%token EOF
%token <int> INT
%token <float> FLOAT
%token LPAR
%token RPAR
%token <string> FUNC
%token <string> OP_add
%token <string> OP_mul

%left OP_add
%left OP_mul

%start main
%type <Ast.struct_expr> main

%%
main: expr EOF { $1 }
;

expr:
  |INT { Intconst($1)}
  |FLOAT { Floatconst($1)}
  |FUNC LPAR params RPAR { Func($1,$3) }
  |LPAR expr RPAR { $2 }
  |expr OP_add expr { Op($2,$1,$3) }
  |expr OP_mul expr { Op($2,$1,$3) }
;

params:
  |expr params { $1::$2 }
  |/* rien */ { [] }
;

%%

Code main.ml :

Sélectionner tout - Visualiser dans une fenêtre à part

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
open Ast;;

let rec print_ast t =
        match t with
                 Intconst(i) -> Printf.printf " %d " i
                |Floatconst(f) -> Printf.printf " %.2f " f
                |Op(o,e1,e2) -> Printf.printf " ( "; print_ast e1 ; Printf.printf " %s " o ; print_ast e2 ; Printf.printf " ) "
                |Func(f,args) ->
                        Printf.printf " %s ( " f ; print_args args ; Printf.printf " ) "
(*                |_ -> Printf.printf "\n\n erreur \n" *)
and
print_args args =
        let rec aux l =
                match l with
                         [] -> ()
                        |a::q -> Printf.printf "," ; print_ast a ; aux q
        in
        match args with
                 [] -> ()
                |a::q -> print_ast a ; aux q
;;

let rec interpret ast =
        match ast with
                 Intconst(i)  -> float_of_int i
                |Floatconst(f) -> f
                |Op(o,e1,e2) -> (
                        let n1 = interpret e1 in
                        let n2 = interpret e2 in
                        match o with
                                 "+" -> n1 +. n2
                                |"-" -> n1 -. n2
                                |"*" -> n1 *. n2
                                |"/" -> n1 /. n2
                                |_ -> failwith "erreur op" 
                        )
                |Func(f,[e]) -> (
                        let n = interpret e in
                        match f with
                                 "cos" -> cos n
                                |"sin" -> sin n
                                |_ -> failwith "erreur func" 
                        )
                |Func(f,args) -> 
                        Printf.printf "\n\n erreur func %s\tavec %d args \n\n" f (List.length args) ;
                        failwith "erreur interpret" 
                |_ -> failwith "erreur interpret" 
;;


let main () = 
  let input_name = Sys.argv.(1) in
  let fichier = open_in input_name in
  let buffer = Lexing.from_channel fichier in
  let ast = Parser.main Lexer.nextToken buffer in
(*  print_ast ast ; Printf.printf "\n\n" ; *)
  Printf.printf "%.2f\n\n" (interpret ast)
;;

main ();;

Code ast.mli :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
type struct_expr =
         Intconst of int
        |Floatconst of float
        |Op of string * struct_expr * struct_expr
        |Func of string * struct_expr list 
;;

là, on peut vraiment parler d'overkill... car il s'agit d'un interprète pour une machine virtuelle "quelconque"

je reviendrais

[souviron34]

questions :

• On suppose des maths, donc pas de pbes d'unités entre les opérandes, c'est bien ça ?
• Pourquoi pour les flottants 2 chiffres après la virgule ?
• Pas d'opérations vectorielles, c'est bien ça ?

[gorgonite]

questions :

• On suppose des maths, donc pas de pbes d'unités entre les opérandes, c'est bien ça ?
• Pourquoi pour les flottants 2 chiffres après la virgule ?
• Pas d'opérations vectorielles, c'est bien ça ?

2 chiffres après la virgule... pour les erreurs d'arrondis (on ne sait jamais... certains voudront peut-être implanter un calcul de cos récursif avec une précision via un seuil )

pas de vecteurs... exact

pas de problèmes d'unités puisque c'est des maths (mais en maths 1+cos n'existe pas... attention )

[Jean-Marc.Bourguet]

Overkill

Ça dépend ce que tu cherches à optimiser : simplicité de code, maintenabilité, extensibilité...

J'ai assure le support d'un parseur ecrit avec bison et d'un autre ecrit par descente recursive. Je t'assure que la maintenabilite etait meilleure dans le second cas. L'extensibilite n'en parlons pas des qu'il y a des choses qui ne sont pas LALR. Et quand a la simplicite du code... elle correspondait a la maintenabilite.

Dans le meme esprit, le projet GCC a reecrit ses parseurs bisons pour le C et pour le C++ de bison a l'utilisation de parseurs ecrits a la main. Et B. Stroustrup a declare qu'une de ses plus grosses erreurs avait ete de se laisser convaincre d'utiliser yacc lors d'une reecriture de CFront.

Les generateurs sont utiles tout compte fait sur une classe de langage de complexite moyenne. Les frontieres exactes vont dependre de la familiarite avec les outils et les techniques, de la volatilite de la grammaire et de la capacite a contraindre celle-ci a ce qui passe bien sur le generateur utilise.

Dans mon code, il suffit d'ajouter une ligne pour gérer une nouvelle fonction ou un nouvel opérateur, par exemple : "| "abs" { FCT abs }".

Mauvais exemple. En pratique on va rarement encombrer le lexer avec des etats pour reconnaitre des identificateurs un par un mais reconnaitre la syntaxe des identificateurs et puis utiliser un tableau associatif. Ca marche dans un cas comme dans l'autre: il suffit d'ecrire la fonction a appeler et de l'enregistrer dans le tableau.

[millie]

questions :
Pourquoi pour les flottants 2 chiffres après la virgule ?

Ca peut être plus, c'était pour éviter d'avoir à traiter des cas de flottant très long : du style 0.0000000000000000000000000000000000000001 qui risquait de poser problème. Donc on s'est limité à 2, mais vous pouvez vous limiter à un nombre fixe autres.

D'ailleurs au passage, il y a le même problème pour les entiers normaux,du style : 100000000000000000000000000000000 qui risque de poser problème

[millie]

Vu que presque tout le monde a accepté les expressions du type : 1--1 ou cos 1. J'ai laissé le choix à la personne d'évaluer ces expressions ou de les considérer comme des erreurs syntaxiques.

[InOCamlWeTrust]

j'avais une version ocaml avec lex et yacc, puis interprétation (donc 3 passes)...

Pourquoi trois passes ?

[gorgonite]

Pourquoi trois passes ?

lex -> 1 passe
yacc -> 1 passe
interprète -> 1 passe


au passage, avec le packrat, on fait l'équivalent de lex+yacc en une passe seulement... modulo une compensation d'un cout temporel en cout mémoire

[InOCamlWeTrust]

Ca fait deux passes... à chaque fois que yacc a besoin d'un léxème, yacc appelle la fonction qui lui donne le prochain léxème : c'est pas comme si on construisait la liste de tous les léxèmes, puis que yacc parsait le tout pour construire l'arbre de syntaxe... et pas besoin de packrat pour faire lex + yacc en une seule passe : c'est déjà comme ça.

[gorgonite]

Ca fait deux passes... à chaque fois que yacc a besoin d'un léxème, yacc appelle la fonction qui lui donne le prochain léxème : c'est pas comme si on construisait la liste de tous les léxèmes, puis que yacc parsait le tout pour construire l'arbre de syntaxe... et pas besoin de packrat pour faire lex + yacc en une seule passe : c'est déjà comme ça.

ce n'est pas parce qu'on peut faire les deux passes presque simultanément, qu'il ne s'agit pas de deux passes... donc je maintiens ce que j'ai dit


par ailleurs, le packrat apporte réellement un gain de vitesse sur le parsage, mais au prix d'un coût "transféré" sur la complexité spatiale

[gasche]

Une version différente, qui utilise (détourne) les facilités de créations de grammaires de Camlp4 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
open Camlp4.PreCast

let sem_op = function
| "*" -> ( *.)
| "/" -> (/.)
| "+" -> (+.)
| "-" -> (-.)
| op -> failwith (Printf.sprintf "unknown op '%s'" op)

let sem_func = function
| "sin" -> sin
| "cos" -> cos
| func -> failwith (Printf.sprintf "unknown func '%s'" func)

let neg x = function
| None -> x
| _ -> 0. -. x

open Syntax 

let () = Gram.Entry.clear str_item
let math_expr = Gram.Entry.mk "math_expr"

EXTEND Gram
    str_item: [[ e = math_expr -> <:str_item< $`flo:e$ >> ]];
    math_expr: 
    [ "mul" LEFTA [ e1 = SELF; op = ["*" | "/"]; e2 = SELF -> (sem_op op) e1 e2 ]
    | "add" LEFTA [ e1 = SELF; op = ["+" | "-"]; e2 = SELF -> (sem_op op) e1 e2 ]
    | "apply" RIGHTA [ func = LIDENT; arg = SELF -> (sem_func func) arg ]
    | "simple"
      [ signe = OPT "-"; x = FLOAT -> neg (float_of_string x) signe
      | signe = OPT "-"; n = INT -> neg (float_of_string n) signe
      | "("; e = SELF; ")" -> e ]
    ];
END

Compilation :
$ ocamlc -c -I +camlp4 -pp camlp4of maths.ml

Exemple :
$ camlp4o ./maths.cmo -str '1 + 2 * cos sin 0'
3.

[Jedai]

Avec Parsec en Haskell, Parsec.Expr est particulièrement utile dans ce cas, faisant tout le travail de gestion des priorités pour nous, les seuls points un peu plus délicat sont la gestion des espaces et du (-) préfixe.
En deux modules (soyons propre ) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
module Calculator (expr) where

import Control.Monad
import Text.ParserCombinators.Parsec hiding (token)
import Text.ParserCombinators.Parsec.Expr

expr    :: Parser Double
expr    = buildExpressionParser table (token factor)
        <?> "expression"

table   = [[Prefix $ try (token (char '-')) >> return negate]
          ,[pre "sin" sin, pre "cos" cos, pre "abs" abs]
          ,[op "*" (*) AssocLeft, op "/" (/) AssocLeft]
          ,[op "+" (+) AssocLeft, op "-" (-) AssocLeft]
          ]          
        where
          op s f assoc = Infix (string s >> return f) assoc
          pre s f = Prefix (string s >> return f)

factor  = between (char '(') (char ')') (token expr) <|> number
        <?> "simple expression"

number  :: Parser Double
number  = (do
            ds <- many1 digit
            decs <- option "" $ do
                      char '.'
                      dds <- countFromTo 1 5 digit
                      return $ '.' : dds
            return (read $ ds ++ decs)
          ) <?> "number"

token :: Parser a -> Parser a
token = between ws ws
    where ws = many $ char ' '

countFromTo :: Int -> Int -> Parser a -> Parser [a]
countFromTo f t p
    | t == 0    = return []
    | f <= 0    = option [] $ liftM2 (:) p (countFromTo f (t-1) p)
    | otherwise = liftM2 (:) p (countFromTo (f-1) (t-1) p)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
module Main where

import Calculator
import Text.ParserCombinators.Parsec

main = do line <- getLine
          if line == "quit"
            then return ()
            else do
              parseTest calculation line
              main
    where
      calculation = do { x <- expr; eof; return x }

--
Jedaï

[LLB]

Et voici la version avec FParsec, l'adaptation de Parsec pour F#. La logique est la même, on utilise des monades, là aussi. Une différence quand même : Parsec.Expr n'est pas implémenté dans FParsec.

Code F# :

Sélectionner tout - Visualiser dans une fenêtre à part

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
#light
#nowarn "40" // références circulaires
open FParsec.Primitives
open FParsec.CharParser
 
let float = parse {let! s = regex "[0-9]+(\.[0-9]+)?"
                   return Float.of_string s}
 
let mulop = (char "*" >>$ ( * ))  <|> (char '/' >>$ (/))
 
let addop = (char "+" >>$ ( + ))  <|> (char '-' >>$ (-))
 
let unop = (char '+' >>$ (~+))    <|> (char '-' >>$ (~-))    <|>
           (string "sin" >>$ sin) <|> (string "cos" >>$ cos)
 
let rec expr = chainl1 term addop
 
and term = chainl1 factor mulop
 
and prefix = parse {let! f = unop
                    let e = factor
                    return! e |>> f}
 
and factor =
    let p st = (float <|> prefix <|> between (char '(') (char ')') expr) st
    between spaces spaces p
 
System.Console.ReadLine() |> run (expr .>> eof) |> print_any

Et par rapport à la version fslex/fsyacc, on gagne des messages d'erreurs plus explicites.

Edit : Merci Alex.

[alex_pi]

Code F# :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
let unop = (char '+' >>$ (~+))    <|> (char '-' >>$ (~-))    <|>
           (string "sin" >>$ sin) <|> (string "cos" >>$ sin)

Petite erreur de copier coller pour le cos

[Fractal LLG]

Bonjour

Ça y est, mon interpréteur est fin prêt !
Il a été fait à la base en Caml Light mais je le donne ici en syntaxe OCaml.
Je ne me sers de plus d'aucun module externe genre ocamllex et ocamlyacc, c'est le programme qui fait tout.
Comme la plupart des autres programmes, j'accepte les expressions du type 1--1, ou encore ---1-+cossin--sin-cossin-(sin1-sin-1)
Je ne me suis pas fixé de limites pour les flottants, donc il peut y avoir des petites erreurs d'arrondi.
Ensuite (mais j'ai pas fait exprès ) il ferme tout seul les parenthèses à la fin si vous les oubliez.
Voilà, j'ai essayé de commenter pas mal le code, mais si vous avez des questions , des remarques, ou si vous trouvez une erreur, n'hésitez pas

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
(* 

      Interpréteur d'expressions mathématiques (OCaml)

   Mode d'emploi : compiler ce fichier tout d'un bloc dans l'interpréteur OCaml, ensuite lancer ` eval "1+1";; ` pour évaluer une unique chaîne de caractères ou encore ` eval_it();; ` pour en évaluer plusieurs d'affilée.

   Portable sous Caml light sans problème, il faut juste remplacer les "String.length" par "string_length" et les "'" par "`"
*)


    (* Définitions des types *)


type lexeme = (* Comprend les "vrais" lexèmes (nombres et symboles), les listes de lexèmes ainsi qu'un symbole particulier Nil qui sert lors de la reconnaissance des parenthèses *)
  | Nil
  | Num of float
  | Symb of char (* peut être '+', '-', '*', '/', '(', ')', 'c' ou 's' *)
  | List of lexeme list;;
  
type expr =  (* Type d'une expression mathématique sous forme d'un arbre *)
  | Nb of float
  | Add of expr * expr
  | Sub of expr * expr
  | Mul of expr * expr
  | Div of expr * expr
  | Neg of expr
  | Sin of expr
  | Cos of expr;;
  
  
    (* Analyseur lexical : il y rentre une chaîne de caractères, il en ressort une liste de Lexeme ne contenant pas de Nil ni de List : attention, la liste de lexèmes est dans le sens inverse par rapport à la chaîne de caractères *)


let valeur c = float_of_int( (int_of_char c) - 48 );;

let lex str = 
  let rec lexi str i lexlist = (* trie la chaîne str à partir du caractère i et place les lexèmes obtenus à la suite de lexlist *)
    if i >= String.length str then lexlist
    else let c = str.[i] in match c with
      |'+' |'-' |'*' |'/' |'(' |')' -> lexi str (i+1) ((Symb c)::lexlist)
      |('0'..'9') -> let rec nombre str i nb is_flott eps = (* nombre renvoie le nombre dans la chaîne de caractères str commencant au caractère i, ainsi que l'indice du caractère suivant ce nombre *)
                       if i = String.length str then (nb,i) 
                       else begin
                         let c = str.[i] in match c with 
                           |('0'..'9') -> if is_flott then nombre str (i+1) (nb +. (valeur c)*.eps) true (eps /. 10.)
                                          else nombre str (i+1) (10. *. nb +. (valeur c)) false eps
                           |'.' -> if is_flott then failwith "Erreur de syntaxe" else nombre str (i+1) nb true 0.1
                           |_ -> (nb,i)
                       end
                       in let (nb,j) = (nombre str i 0. false 57.) in lexi str j ((Num (nb))::lexlist)
      |'s' -> if (String.length str) > (i + 2) && str.[i+1] = 'i' && str.[i+2] = 'n' then lexi str (i+3) ((Symb 's')::lexlist) else failwith "Erreur de syntaxe"
      |'c' -> if (String.length str) > (i + 2) && str.[i+1] = 'o' && str.[i+2] = 's' then lexi str (i+3) ((Symb 'c')::lexlist) else failwith "Erreur de syntaxe"
      |' ' -> lexi str (i+1) lexlist
      |_ -> failwith "Erreur de syntaxe"
  in lexi str 0 [];;
  
  
    (* Prédécoupage selon les parenthèses : on remplace tout couple de parenthèses par la liste des lexèmes situés entre, il y rentre une liste de Lexeme ne contenant pas de Nil ni de List, et en ressort une liste de Lexeme ne contenant pas de (Symb '(') ni de (Symb')') même dans les sous listes *)


(* Fonction auxiliaire : étant donnés une liste de Lexeme et un Lexeme, rajoute ce dernier à la fin de la liste et le plus profondément, ie si la fin de la liste est aussi une liste, on le rajoute à la fin de celle-ci et ainsi de suite, mais en considérant que les listes se terminant par Nil sont pleines *)

let rec add lexlist lex = match lexlist with
  | [] -> [lex]
  | Nil::_ -> failwith "Erreur de syntaxe"
  | (Num _)::_ | (Symb _)::_ -> lex::lexlist
  | (List [])::t -> (List [lex])::t
  | (List (Nil::l))::t -> lex::(List (Nil::l))::t
  | (List l)::t -> (List (add l lex))::t;;
  
(* Prédécoupage, attention, la liste de lexèmes entrante est dans le sens inverse, à cause de l'analyse lexicale *)

let decoup liste = 
  let rec decoupage fait reste = match reste with
    | [] -> fait
    | h::t when (h = Symb ')') -> decoupage (add fait (List [])) t (* On ouvre une parenthèse *)
    | h::t when (h = Symb '(') -> decoupage (add fait Nil) t       (* On la ferme *)
    | h::t ->                     decoupage (add fait h) t;        (* On la remplit *)
  in (decoupage [] liste);;

let rec purge liste = match liste with (* On supprime tous les Nil de la liste de lexèmes (y compris ceux dans les sous-listes) *)
  | [] -> []
  | h::t -> match h with
              |Nil -> purge t
              |Num _ | Symb _ -> h::(purge t)
              |List l -> (List (purge l))::(purge t)
  ;;


    (* Résolution des opérateurs unaires : après les opérations précédentes, s'il n'y a pas d'erreur de syntaxe, la liste et toute ses sous-listes sont de la forme {s}c{{s}^+ c}  où s représente un symbole binaire ou unaire (+ - * / sin cos), c désigne soit un Nil soit une List et {.} signifie que . peut-être répété zéro, une ou plusieurs fois (et le ^+ indique qu'il en faut au moins un).
    En effet quelque chose comme +---(--1-sin cos-3) doit être compilé correctement. unaires se charge simplement de tout parenthéser (avec des sous-listes) comme il faut de façon à n'obtenir que sc ou c{sc} pour les sous-listes et la liste complète*)


let rec unaires lexlist = match lexlist with
  | [] -> []
  | Nil::t -> t
  | [Num _] -> lexlist
  | [List l] -> [List (unaires l)]
  | [Symb _] -> failwith "Erreur de syntaxe"
  | (List l)::b::t -> (List (unaires l))::b::(unaires t)
  | (Num n)::b::t -> (Num n)::b::(unaires t)
  | (Symb c)::h::t -> let rec unary_solve lexlist = match lexlist with (* parenthèse comme il faut tous les s à partir de celui du début de lexlist avec le prochain c *)
                        | [] | (Num _)::_ | (List _)::_ | Nil::_ -> failwith "Impossible"
                        | [Symb _] -> failwith "Erreur de syntaxe"
                        | (Symb c)::(Num n)::t -> ([Symb c; Num n], t)
                        | (Symb c)::(List l)::t -> ([Symb c; List (unaires l)], t)
                        | (Symb c)::t -> let r = unary_solve t in ([Symb c; List (fst r)], (snd r))
                      in let r = unary_solve lexlist in match (snd r) with
                                                          | [] -> [List (fst r)]
                                                          | Nil::_ | (Num _)::_ | (List _)::_ -> failwith "Erreur de syntaxe"
                                                          | h::t -> (List (fst r))::h::(unaires t)
  ;;


    (* Convertisseur en expression : la liste de lexèmes en entrée est normalisée : toute sous-liste est de la forme sc ou c{sc} et on le convertit en expression.
   prior et priority servent à recueillir la priorité respectivement d'un opérateur ou d'une liste de lexèmes : 1 pour +-, 2 pour */ et 3 pour les expressions parenthésées *)


let prior c = if (c = '+') || (c = '-') then 1 else 2;; (* si (prior c) = 2, c'est que c = '*' ou '/' vu qu'on ne l'utilisera que sur des opérateurs binaires *)
let rec priority liste = match liste with
  |[] | [_] -> 3
  |[a;b] -> failwith "Erreur de syntaxe"
  |t::(Symb o)::q -> if (priority q) = 3 then (prior o) else (max (prior o) (priority q))
  |_ -> failwith "Erreur de syntaxe";;

let rec syntax liste = match liste with
  | [] | [Symb _] -> failwith "Erreur de syntaxe"
  | [Num n] -> Nb n
  | [List l] -> syntax l
  | [Symb '-'; n] -> Neg (syntax [n])
  | [Symb '+'; n] -> syntax [n]
  | [Symb 'c'; n] -> Cos (syntax [n])
  | [Symb 's'; n] -> Sin (syntax [n])
  | avant::(Symb c)::apres -> if (prior c) < priority apres then (match c with
                                | '+' -> Add ((syntax [avant]),(syntax apres))
                                | '-' -> Sub ((syntax [avant]),(syntax apres))
                                | '*' -> Mul ((syntax [avant]),(syntax apres))
                                | '/' -> Div ((syntax [avant]),(syntax apres))
                                | _ -> failwith "Erreur de syntaxe")
                              else syntax ((List [avant; Symb c; List.hd apres])::(List.tl apres));
  | _ -> failwith "Erreur de syntaxe";;


    (* Évaluateur : il y rentre une expression et il en ressort sa valeur calculée (en float) *)


let rec calc expr = match expr with
  | Nb n -> n
  | Add(a,b) -> (calc a) +. (calc b)
  | Sub(a,b) -> (calc a) -. (calc b)
  | Mul(a,b) -> (calc a) *. (calc b)
  | Div(a,b) -> let cb = calc b in (if cb = 0. then (failwith "Division par zéro !") else (calc a) /. (calc b))
  | Neg a -> -.(calc a)
  | Sin a -> sin (calc a)
  | Cos a -> cos (calc a)
;;


    (* Fonctions finales d'évaluation d'une chaîne de caractères *)


let eval str = 
  print_float (calc (syntax (unaires (purge (decoup (lex str))))));
  print_newline();;

let eval_it () = 
  while true do
    eval (read_line ());
  done;;

(rajouter éventuellement une ligne vide à la fin pour s'assurer que la définition de eval_it() a bien été prise en compte)

Fractal