Discussion :

[golden boy]

Bonjour,

je suis dans l'idée d'implémenter un petit calculateur d'expression préfixe.

J'ai, pour l'instant, fait un type récursif pour représenter mes expressions, ainsi que la fonction pour l'évaluer et donner le résultat (ces deux ne posent pas de problèmes) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
data Expr  = Num Int
           | Add Expr Expr
	| Mul Expr Expr
	| Div Expr Expr
 
eval (Num x)               = x
eval (Add (Num a) (Num b)) = a+b
eval (Mul (Num a) (Num b)) = a*b
eval (Div (Num a) (Num b)) = a `div`b
eval (Add a b) = (eval a) + (eval b)	
eval (Mul a b) = (eval a) * (eval b)	
eval (Div a b) = (eval a) `div` (eval b)

L'idée est donc de parser un type [Char] (par exemple "+ 9 * 3 1") et de le transformer en type Expr qui pourra être évalué par la fonction 'eval" (pour donner (Add (Num 9) (Mul (Num 3) (Num 1)) ).

J'avais commencé à écrire une telle fonction, mais je suis bloqué, de plus je pense ne pas utiliser la bonne voie :

Code :

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

1
2
3
4
parse :: [Char] -> Expr
parse (x:xs:ys)
	| x == '+' = (Add) (parse xs) (parse ys)
	| x == '*' = (Mul) (parse xs) (parse ys)

Donc voilà, j'aimerais avoir vos conseils, j'aurais aimé faire la parsing moi-même, mais pensez-vous qu'utiliser un module comme Text.Parsec pourrait être mieux ?

Merci d'avance !

[sharpdev]

Analyser une expression arithmétique est loin d'être évident. Il faut en effet tenir compte de la priorité des opérations, de leur associativité, du "moins" à la fois binaire et unaire etc. Les parsers monadiques sont parfaits pour résoudre ces problèmes. On peut bien sûr utiliser Parsec mais il me semble plus intéressant de créer son propre parser. Le chapitre 8 de l'excellent "programming in Haskell" de Graham Hutton est une très bonne introduction ainsi que la video http://channel9.msdn.com/Shows/Going...hapter-8-of-13 qui lui est consacré.

[golden boy]

Merci pour la vidéo, pour tout te dire, bien que je comprenne assez bien l'Anglais écrit, je comprends très mal l'Anglais oral, mais j'essayerai de comprendre quelque chose... (je sais que c'est mal de pas connaître l'Anglais en informatique)

[TropMDR]

Analyser une expression arithmétique est loin d'être évident. Il faut en effet tenir compte de la priorité des opérations, de leur associativité, du "moins" à la fois binaire et unaire etc. Les parsers monadiques sont parfaits pour résoudre ces problèmes.

Euh, non... Il veut parser des expressions préfix ! Donc c'est trivial... Il faut pas dégainer les solutions de combats pour ça.

[gorgonite]

Euh, non... Il veut parser des expressions préfix ! Donc c'est trivial... Il faut pas dégainer les solutions de combats pour ça.

certes, mais ça n'empêche pas les combinateurs de parseurs d'être intéressants aussi sur cet exemple... surtout s'il veut réellement créer une structure pour ces expressions et pas seulement les évaluer

[ceciestunpseudo]

Euh, non... Il veut parser des expressions préfix ! Donc c'est trivial... Il faut pas dégainer les solutions de combats pour ça.

Ce n'est pas « sortir l'artillerie lourde » (c'est ce que tu veux dire je suppose) que de fournir une solution élégante et simple. Car les combinateurs de parseurs donne une telle solution. C'est vrai que ça demande de comprendre le principe des monades. Mais si on ne veut pas se plonger dans les monades, on ne fait pas d'Haskell me semble.

Écrire entièrement « à la main » un parser ad-hoc, même pour une grammaire n'utilisant que des opérateurs préfixés n'est pas une bonne idée. Ce n'est pas si trivial que ça... pour preuve : il n'y arrive pas. L'évidence n'est là que pour ceux qui sont déjà aguerris.

certes, mais ça n'empêche pas les combinateurs de parseurs d'être intéressants aussi sur cet exemple... surtout s'il veut réellement créer une structure pour ces expressions et pas seulement les évaluer

Tout à fait mon cher Dr. démon.

[golden boy]

Salut,

alors en fait, je ne connais pas du tout les monades (et je suis encore loin du chapitre). On peut le faire sans monade je suppose ?

[ceciestunpseudo]

[...]
J'avais commencé à écrire une telle fonction, mais je suis bloqué, de plus je pense ne pas utiliser la bonne voie :

Code :

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

1
2
3
4
parse :: [Char] -> Expr
parse (x:xs:ys)
	| x == '+' = (Add) (parse xs) (parse ys)
	| x == '*' = (Mul) (parse xs) (parse ys)

Donc voilà, j'aimerais avoir vos conseils, j'aurais aimé faire la parsing moi-même, mais pensez-vous qu'utiliser un module comme Text.Parsec pourrait être mieux ?

Merci d'avance !

Tu es bloqué parce que ton typage n'est pas bon.
Un parser prend en entrée une chaîne de caractère (pourquoi n'as-tu pas écrit String? ça ne change rien de toute façon) et fournit en sortie ce que tu veux produire (expression pour toi) ET le reste de la chaîne de caractères qui n'a pas été traité.

Le bon type (naïf) est donc

Code :

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

1
2
 
type Parser a = String -> (a,String)

Si tu as l'oeil tu y reconnais une monade. Mais même si ce n'est pas le cas tu peux voir où ça te mène : tu peux ainsi créer des parsers qui analysent des « morceaux » et les assembler pour faire ton système.

Le livre de Graham Hutton est effectivement pertinent sur le sujet. C'est ce monsieur qui a produit l'idée de l'analyse syntaxe monadique (Monadic Parsing) : eprints.nottingham.ac.uk/archive/00000223/01/pearl.pdf