Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 20 sur 20
  1. #1
    Membre confirmé Avatar de golden boy
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2010
    Messages
    120
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2010
    Messages : 120
    Points : 206
    Points
    206

    Par défaut Parser une expression préfixe

    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 !

  2. #2
    Futur Membre du Club
    Inscrit en
    octobre 2007
    Messages
    16
    Détails du profil
    Informations forums :
    Inscription : octobre 2007
    Messages : 16
    Points : 18
    Points
    18

    Par défaut

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

  3. #3
    Membre confirmé Avatar de golden boy
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2010
    Messages
    120
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2010
    Messages : 120
    Points : 206
    Points
    206

    Par défaut

    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)

  4. #4
    Membre du Club
    Inscrit en
    août 2009
    Messages
    38
    Détails du profil
    Informations forums :
    Inscription : août 2009
    Messages : 38
    Points : 48
    Points
    48

    Par défaut

    Citation Envoyé par golden boy Voir le message
    [...]
    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 !
    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

  5. #5
    Membre chevronné
    Inscrit en
    mars 2010
    Messages
    308
    Détails du profil
    Informations forums :
    Inscription : mars 2010
    Messages : 308
    Points : 793
    Points
    793

    Par défaut

    Citation Envoyé par sharpdev Voir le message
    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.

  6. #6
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro Nicolas Vallée
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 208
    Détails du profil
    Informations personnelles :
    Nom : Homme Nicolas Vallée
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 208
    Points : 16 756
    Points
    16 756

    Par défaut

    Citation Envoyé par TropMDR Voir le message
    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
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  7. #7
    Membre du Club
    Inscrit en
    août 2009
    Messages
    38
    Détails du profil
    Informations forums :
    Inscription : août 2009
    Messages : 38
    Points : 48
    Points
    48

    Par défaut

    Citation Envoyé par TropMDR Voir le message
    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.

    Citation Envoyé par gorgonite Voir le message
    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.

  8. #8
    Membre confirmé Avatar de golden boy
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2010
    Messages
    120
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2010
    Messages : 120
    Points : 206
    Points
    206

    Par défaut

    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 ?

  9. #9
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro Nicolas Vallée
    Ingénieur d'études
    Inscrit en
    décembre 2005
    Messages
    10 208
    Détails du profil
    Informations personnelles :
    Nom : Homme Nicolas Vallée
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : décembre 2005
    Messages : 10 208
    Points : 16 756
    Points
    16 756

    Par défaut

    Citation Envoyé par golden boy Voir le message
    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
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  10. #10
    Membre confirmé Avatar de golden boy
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2010
    Messages
    120
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2010
    Messages : 120
    Points : 206
    Points
    206

    Par défaut

    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 ?

  11. #11
    Membre du Club
    Inscrit en
    août 2009
    Messages
    38
    Détails du profil
    Informations forums :
    Inscription : août 2009
    Messages : 38
    Points : 48
    Points
    48

    Par défaut

    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
    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 ?

  12. #12
    Membre confirmé Avatar de golden boy
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2010
    Messages
    120
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2010
    Messages : 120
    Points : 206
    Points
    206

    Par défaut

    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).

  13. #13
    Membre du Club
    Inscrit en
    août 2009
    Messages
    38
    Détails du profil
    Informations forums :
    Inscription : août 2009
    Messages : 38
    Points : 48
    Points
    48

    Par défaut

    Citation Envoyé par golden boy Voir le message
    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.

    Citation Envoyé par golden boy Voir le message
    [...] Et aussi, sur le fait qu'il faut bien renvoyer le reste de la chaîne à la fonction, pour continuer le parsing.
    Exact.

    Citation Envoyé par golden boy Voir le message
    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

  14. #14
    Membre confirmé Avatar de golden boy
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2010
    Messages
    120
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2010
    Messages : 120
    Points : 206
    Points
    206

    Par défaut

    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 ?

  15. #15
    Membre du Club
    Inscrit en
    août 2009
    Messages
    38
    Détails du profil
    Informations forums :
    Inscription : août 2009
    Messages : 38
    Points : 48
    Points
    48

    Par défaut

    Citation Envoyé par golden boy Voir le message
    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 ?
    Ç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)

  16. #16
    Membre confirmé Avatar de golden boy
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2010
    Messages
    120
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2010
    Messages : 120
    Points : 206
    Points
    206

    Par défaut

    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 ;) )

  17. #17
    Membre du Club
    Inscrit en
    août 2009
    Messages
    38
    Détails du profil
    Informations forums :
    Inscription : août 2009
    Messages : 38
    Points : 48
    Points
    48

    Par défaut

    Citation Envoyé par golden boy Voir le message
    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).

    Citation Envoyé par golden boy Voir le message
    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

    Citation Envoyé par golden boy Voir le message
    (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.

  18. #18
    Membre confirmé Avatar de golden boy
    Homme Profil pro
    Étudiant
    Inscrit en
    novembre 2010
    Messages
    120
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : novembre 2010
    Messages : 120
    Points : 206
    Points
    206

    Par défaut

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

  19. #19
    Nouveau Membre du Club
    Profil pro
    Inscrit en
    octobre 2002
    Messages
    37
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : octobre 2002
    Messages : 37
    Points : 28
    Points
    28

    Par défaut

    Citation Envoyé par ceciestunpseudo Voir le message
    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 :-)

  20. #20
    Membre du Club
    Inscrit en
    août 2009
    Messages
    38
    Détails du profil
    Informations forums :
    Inscription : août 2009
    Messages : 38
    Points : 48
    Points
    48

    Par défaut

    Citation Envoyé par viro Voir le message
    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.

    Citation Envoyé par viro Voir le message
    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 ^_^

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •