Parser une expression préfixe

[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 :

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 :

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)

[ceciestunpseudo]

Envoyé par golden boy

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

Code :

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 :

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

[TropMDR]

Envoyé par 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.

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]

Envoyé par TropMDR

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]

Envoyé par TropMDR

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.

Envoyé par gorgonite

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 ?

[gorgonite]

Envoyé par 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 ?

on peut toujours tout faire sans la "feature clé" du langage... mais dans ce cas, il faut se demander si l'on a choisi le bon langage, ou c'est juste le module en cours qui n'est pas adapté "philosophiquement" et le reste du projet qui va bien

[golden boy]

Je compte bien apprendre le monades, mais pour l'instant j'en suis encore loin (je suis au chapitre 6 du RWH). Donc le mieux serait de ré-essayer d'implémenter ce parseur une fois que j'aurais appris les monades ?

[ceciestunpseudo]

Tu n'as pas besoin des monades... mais tu retrouveras dans les monades ce que tu as élaboré.

Revenons sur ton sujet... le type de ton parser n'était pas correct. Tu aimerais qqchose du genre

Code :

1
2
parser:: String -> (Expression, String)

Là, tu crées un parser qui ne traite pas les erreurs. Tu aimerais probablement la possibilité qu'il puisse échouer. Ton type ne l'autorise pas vraiment. Par exemple si qqun te donne "+ + 1 + 2 3". Tu aimerais un échec. Donc ton type serait plus

Code :

1
2
parser:: String -> Maybe (Expression, String)

Ainsi tu vises les résultats suivants

Code :

1
2
3
4
5
parser "1" = Just (Num 1, "")
parser "aa" = Nothing 
parser "+ 1 aa" = Nothing 
parser "+ 1 3 aa" = Just (Plus (Num 1) (Num 3), "aa")

Ça a du bon sens ! Tu sais si tu as obtenu une erreur en cours de route (Nothing te donne un échec) et, si ton parsing termine, tu sais s'il est complet (dans le dernier cas, il reste "aa" à parcourir). Un parsing réussi c'est quelque chose qui renvoie

Code :

Just ( EXPRESSION, "")

Laissons de côté, la gestion de l'ambiguïté (utilisation de la monade [] plutôt que la monade Maybe), le traitement des erreurs (utilisation de la monade Either plutôt que de la Monade Maybe) etc.

Est-ce que ça t'aide ?

[golden boy]

Ah ? Maybe et [] sont des monades ?

Sinon, oui ça m'a aide dans le sens où tu m'as un peu renseigné sur l'intérêt du constructeur Maybe (je ne voyais pas l'intérêt d'utiliser Just x avant, je le vois un peu mieux à présent). Et aussi, sur le fait qu'il faut bien renvoyer le reste de la chaîne à la fonction, pour continuer le parsing.

Mais d'autre choses me turlupinent... Quand je prends mon caractère, je dois évaluer si c'est un opérateur ou un chiffre. Si c'est un chiffre, je dois alors vérifier qu'il n'y a pas encore de chiffre(s) derrière (gestion des nombres à plusieurs chiffres).
(si je pars de l'hypothèse que je déstructure avec le pattern (x : xs) la chaîne à parser et que je lis x).

[ceciestunpseudo]

Envoyé par golden boy

Ah ? Maybe et [] sont des monades ?

Oui. Une monade c'est un processus de calcul. Tu verras ça plus tard, mais l'idée est que le type te renseigne sur ce qu'on calcule.

Envoyé par golden boy

[...] Et aussi, sur le fait qu'il faut bien renvoyer le reste de la chaîne à la fonction, pour continuer le parsing.

Exact.

Envoyé par golden boy

Mais d'autre choses me turlupinent... Quand je prends mon caractère, je dois évaluer si c'est un opérateur ou un chiffre. Si c'est un chiffre, je dois alors vérifier qu'il n'y a pas encore de chiffre(s) derrière (gestion des nombres à plusieurs chiffres).
(si je pars de l'hypothèse que je déstructure avec le pattern (x : xs) la chaîne à parser et que je lis x).

Ah ah !!! Tu arrives à l'intérêt de considérer ton parser comme une monade. Pourquoi ? Parce que pour te simplifier la tâche tu aimerais disposer de parsers élémentaires.

Par exemple, il est utile de penser à un parser qui lit juste un chiffre. Un autre qui lit juste un opérateur serait utile. Mais à y bien penser un qui lirait n'importe quoi et renverrait le caractère serait intéressant.

Tu viens de découvrir que ton type de parser mérite d'être généralisé (paramétré)

Code :

type Parser a = String -> Maybe (a,String)

Ainsi tu définis un parser pour chaque chose qui t'intéresse. Pour toi ça veut dire un pour les chiffres, un pour les opérateurs et un pour la parenthèse ouvrante, un pour la parenthèse fermante. Tu pourras les combiner pour obtenir un parser pour les nombres, puis un autre pour chaque type d'expression... finalement tu auras ce que tu voulais en les combinant avec des choix par exemples. Bon ceci demandera des combinateurs... pour l'instant commences par les premiers (chiffres, symbole +, symbole *, parenthèse ouvrante et fermante) en produisant le code pour chaque.

Moi je te donne deux parsers important pour la suite

Code :

1
2
3
4
5
6
7
8
-- Le parser qui renvoie une erreur
erreur :: Parser a
erreur = \ _ -> Nothing

-- Le parser qui renvoie exactement ce qu'on lui donne
pure :: a -> Parser a
pure x = \ _ -> x

On pourra améliorer les tiens après

[golden boy]

Par exemple, il est utile de penser à un parser qui lit juste un chiffre. Un autre qui lit juste un opérateur serait utile. Mais à y bien penser un qui lirait n'importe quoi et renverrait le caractère serait intéressant.

Je dois avouer que je ne comprends pas bien l'intérêt de ce dernier parser...


Donc si je suis bien, l'idée c'est de faire un truc de ce genre :

Code :

1
2
3
4
5
6
7
8
digit = ['0'..'9']
ops   = ['+','-','*','/']

parse (x:xs)
      | x `elem` digit = -- on envoie x au parser de nombre
      | x `elem` ops   = -- on envoie x au parser d'opérateur
      | x == ' '       = parse xs -- on ignore l'espace
      | _              = -- ...

...pour pouvoir envoyer à chaque parser concerné en fonction du caractère reçu ?

[ceciestunpseudo]

Envoyé par golden boy

Je dois avouer que je ne comprends pas bien l'intérêt de ce dernier parser...


Donc si je suis bien, l'idée c'est de faire un truc de ce genre :

Code :

...pour pouvoir envoyer à chaque parser concerné en fonction du caractère reçu ?

Ça c'est le parser "final" pour l'instant tu en es à créer des unités de parsers : celui qui lit un nombre celui qui lit un opérateur etc. Après tu pourras reconstruire le "gros morceau".

Par exemple

Code :

1
2
3
4
5
6
7
8
9
operateur :: Parser Char
operateur (c:cs) | c `elem` ops = pure c cs 
operateur s =  erreur s

-- nécessite un import de Data.Char
chiffre :: Parser Int
chiffre (c:cs) | isDigit c = pure (ord c - ord '0') cs 
chiffre s =  erreur s

Mais cependant tu peux effectivement t'attaquer tout de suite au gros morceau. Dans le cas d'expressions préfixés, le travail n'est pas très difficile.

Au passage, j'avais écrit une ânerie

Code :

1
2
3
-- Le parser qui renvoie exactement ce qu'on lui donne
pure :: a -> Parser a
pure x = \ cs -> Just (x,cs)

[golden boy]

Ok, je vais essayer d'écrire les petits parsers (il renvoient tous le même type ou alors tous un couple je suppose ?).

Sinon, je comprends pas trop la fonction pure, enfin son intérêt si ce n'est juste mettre sous la forme d'un couple ?

(tiens, je vois que tu aimes la syntaxe OCaml pour les listes ;) )

[ceciestunpseudo]

Envoyé par golden boy

Ok, je vais essayer d'écrire les petits parsers (il renvoient tous le même type ou alors tous un couple je suppose ?).

Un parser est une fonction. Ils doivent tous prendre en entrées une chaîne de caractères et retourner un élément de type Maybe (a, String). Le choix de a dépendra de ce que tu veux obtenir : un chiffre ? alors tu auras un Int ; un caractère ? alors tu auras un Char ; un nombre ? alors tu auras un Int aussi, ou directement une Expr pour toi (Num Int).

Envoyé par golden boy

Sinon, je comprends pas trop la fonction pure, enfin son intérêt si ce n'est juste mettre sous la forme d'un couple ?

Pour l'instant, c'est normal. Ça servira plus tard lorsqu'on combinera le tout.
Au final, je te fais faire le travail décrit par Graham Hutton

Envoyé par golden boy

(tiens, je vois que tu aimes la syntaxe OCaml pour les listes )

À force de faire du Scheme/Racket, du OCaml, du Haskell, du C++, du C et du Java régulièrement, tu finis par tout mélanger. Et c'est pourquoi je remercie de ne plus vivre au temps des punched cards.

[golden boy]

ok merci pour les précisions, je vais essayer d'implémenter tout ça dans la journée.

[viro]

Envoyé par ceciestunpseudo

Oui. Une monade c'est un processus de calcul.

Si j'étais (plus que je ne suis) débutant, je ne suis pas sûr que cette façon de voir m'éclairerait.

En même temps, dire qu'une monade est un type paramétré appartenant à la classe Monad, donc avec deux fonctions définies pour ce type: bind et return, qui de plus sont supposées obéir à quelques lois.... Ca n'aide pas non plus :-)

[ceciestunpseudo]

Envoyé par viro

Si j'étais (plus que je ne suis) débutant, je ne suis pas sûr que cette façon de voir m'éclairerait.

Personnellement ça m'a aidé. Mais c'est vrai que cela dépend de la personne. Il me semble que considérer qu'une monade est un calcul (un processus de calcul) est l'essence même de son utilisation. Moggi a utilisé les monades pour décrire les calculs informatiques dans son article de 1989. Wadler les a utiliser alors pour exprimer le processus (dans le sens unité de calcul) que Moggi décrivait. C'est la naissance de la monade en Haskell. Je ne pense pas être éloigné de l'intuition primitive derrière tout ça donc.

Mais encore une fois, j'admet que c'est selon les personnes.

Envoyé par viro

En même temps, dire qu'une monade est un type paramétré appartenant à la classe Monad, donc avec deux fonctions définies pour ce type: bind et return, qui de plus sont supposées obéir à quelques lois.... Ca n'aide pas non plus :-)

Ou dire que c'est un endofoncteur avec deux transformations naturelles d'injection et d'applanissement non plus d'ailleurs ^_^