Programmation fonctionnelle / Développement web

Introduction aux combinateurs de parseurs monadiques ou comment écrire des compilateurs en Haskell

Julien Dehos

Pour réagir au contenu de ce tutoriel, un espace de dialogue vous est proposé sur le forum. Commentez

- Titre : Programmation fonctionnelle / Développement web

- Auteur : Julien Dehos

- Parution : 12 novembre 2020

- Licence : Copyright ® 2020 Julien Dehos. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Introduction

- II. Exemple de base

- II-A. Présentation

- II-B. Organisation générale

- II-C. Représentation intermédiaire

- II-D. Évaluation directe

- II-E. Génération de code LISP

- II-F. Programme principal

- II-G. Grammaire

- III. Les parseurs récursifs descendants

- III-A. Présentation

- III-B. Un type Result

- III-C. Parseurs bas-niveau

- III-D. Parseurs de Expr

- IV. Notion de foncteur

- IV-A. Rappel sur les foncteurs

- IV-B. Intérêt pour les parseurs

- V. Implémenter des parseurs par des types

- V-A. Un type Parser

- V-B. Exemple : parser le caractère '0'

- V-C. Parseurs de bas niveau

- V-D. Les combinateurs de parseurs monadiques

- V-E. Motivation

- V-F. Classes instanciables pour le type Parser

- V-G. Utilisation pour nos parseurs

- V-H. Implémentation des instances de classes

- VI. Les bibliothèques « à la Parsec »

- VI-A. Le module ReadP

- VI-B. Exemple d'utilisation

- VII. Conclusion

- VIII. Quelques références

- IX. Note de la rédaction de Developpez.com

I - Introduction

Le parsing (ou analyse syntaxique) est une opération, très courante en informatique, qui consiste à « comprendre » un texte selon des règles prédéterminées (c.-à-d. sa grammaire). Du parsing est réalisé dans les compilateurs mais également dans n'importe quel programme qui lit des documents structurés (XML, YAML…), qui reçoit des requêtes (HTTP…) ou encore qui propose une interface textuelle.

Sans entrer dans le domaine de la compilation, il existe de nombreux algorithmes de parsing, notamment l'analyse LALR (utilisée dans Lex/Yacc) ou l'analyse LL (utilisée dans Antlr). Les combinateurs de parseurs monadiques sont une façon particulière d'implémenter des parseurs. Ils ont été proposés dans les années 1990 avec le langage Haskell. Ce dernier permet de les implémenter de façon simple, élégante et facile à utiliser.

Dans ce tutoriel, on va partir d'un exemple de base (une mini-calculatrice), avec un parseur « classique ». On va ensuite modifier ce parseur successivement jusqu'à aboutir à une implémentation basée sur les combinateurs de parseurs monadiques. On ne donnera ici que les sections de code les plus importantes mais le code complet est disponible en ligne. Enfin, on suppose ici que le lecteur connaît les notions et syntaxes de base de Haskell, notamment les types algébriques et les classes de types.

II - Exemple de base

II-A - Présentation

On veut écrire une calculatrice basique permettant d'ajouter ou de multiplier des entiers positifs, en respectant les priorités des opérateurs. Par exemple, on veut pouvoir gérer les expressions suivantes.

12+3
123
2+5*8
2*5+8

C'est un exemple très classique, mais qui a l'avantage d'avoir une grammaire simple. En sortie, on veut évaluer les expressions analysées et générer leur code LISP équivalent.

II-B - Organisation générale

Le parsing est généralement la première étape d'un processus plus complet. En effet, le texte d'entrée est d'abord analysé de façon à en construire une structure de données interne. Celle-ci peut ensuite être analysée, optimisée ou servir à générer du code de sortie (code machine, code source dans un autre langage…).

II-C - Représentation intermédiaire

À partir du texte d'entrée analysé, le parsing génère une représentation intermédiaire (par exemple, un arbre syntaxique abstrait). Celle-ci contient ce qui a été compris concrètement de l'entrée et qui peut être utilisé ensuite dans le reste du programme.

Pour implémenter une représentation intermédiaire, on peut définir des types de données algébriques. Ces types sont très pratiques pour écrire des structures de données arborescentes. Par exemple, pour notre calculatrice en Haskell, on peut définir le type Expr suivant.

1. data Expr

2. = ExprVal Int

3. | ExprAdd Expr Expr

4. | ExprMul Expr Expr

5. deriving (Eq, Show)

On notera la nature récursive du type Expr. Par exemple, la valeur ExprAdd, qui modélise l'addition, contient deux sous-expressions, de type Expr également.

Ainsi, on peut représenter l'expression 2*5+8 par la valeur ExprAdd (ExprMul (ExprVal 2) (ExprVal 5)) (ExprVal 8), ce qui correspond à l'arbre suivant.

II-D - Évaluation directe

Une fois la représentation intermédiaire implémentée par des types algébriques, il est très facile de manipuler les données analysées par notre calculatrice. Par exemple, pour évaluer une expression construite lors du parsing, on peut utiliser la fonction eval suivante.

1. eval :: Expr -> Int

2. eval (ExprVal v) = v

3. eval (ExprAdd e1 e2) = eval e1 + eval e2

4. eval (ExprMul e1 e2) = eval e1 * eval e2

Cette fonction fait du pattern matching sur les différentes valeurs possibles du type Expr et retourne le calcul correspondant au pattern. Là encore, la récursivité se fait très naturellement  : par exemple, évaluer une valeur ExprAdd revient à ajouter l'évaluation de ses deux sous-expressions.

II-E - Génération de code LISP

De façon similaire, on peut générer du code LISP à partir de notre représentation intermédiaire.

1. toLisp :: Expr -> String

2. toLisp (ExprVal v) = show v

3. toLisp (ExprAdd e1 e2)

4. = "(+ " ++ toLisp e1 ++ " " ++ toLisp e2 ++ ")"

5. toLisp (ExprMul e1 e2)

6. = "(* " ++ toLisp e1 ++ " " ++ toLisp e2 ++ ")"

II-F - Programme principal

Finalement, notre calculatrice va permettre de saisir une expression au clavier puis la parser et afficher sa représentation intermédiaire, son code LISP et son évaluation.

1. > 12+3

2. ExprAdd (ExprVal 12) (ExprVal 3)

3. (+ 12 3)

4. 15

6. > 2*5+8

7. ExprAdd (ExprMul (ExprVal 2) (ExprVal 5)) (ExprVal 8)

8. (+ (* 2 5) 8)

9. 18

On peut coder cela en Haskell avec la fonction run suivante.

1. run :: (String -> Either String Expr) -> IO ()

2. run parseExpr = do

3. putStr "\n> "

4. hFlush stdout

5. input <- getLine

6. when (input /= "") $ do

7. case parseExpr input of

8. Left err -> putStrLn $ "error: " ++ err

9. Right expr -> do

10. print expr

11. putStrLn $ toLisp expr

12. print $ eval expr

13. run parseExpr

Il nous reste désormais à écrire la fonction de parsing (parseExpr) passée en paramètre. Du point de vue d’un utilisateur, parseExpr est une fonction qui prend un texte et retourne soit un message d'erreur (si le parsing a échoué), soit une représentation intermédiaire (c.-à-d. une valeur de type Expr).

II-G - Grammaire

Avant de détailler le parsing proprement dit, on doit préciser les « règles » que doit respecter le texte d'entrée de notre calculatrice. Pour cela, on peut utiliser la grammaire formelle suivante (en notation BNF).

1. Additive  ::= Multitive '+' Additive

2. | Multitive

4. Multitive ::= Decimal '*' Multitive

5. | Decimal

7. Decimal   ::= Nat

Intuitivement, cela signifie que pour produire un Additive à partir du flux d'entrée, il y a deux possibilités  : soit parser un Multitive puis un caractère '*' puis un Additive (récursivement donc), soit, si la première possibilité a échoué, parser un Multitive. Le principe est le même pour les règles Multitive et Decimal.

Enfin, Nat représente les entiers naturels habituels, mais on peut également détailler cette règle.

1. Nat       ::= Digits

3. Digits    ::= Digit Digits

4. | Digit

6. Digit     ::= '0' | '1' | ... | '9'

III - Les parseurs récursifs descendants

III-A - Présentation

Dans la section précédente, on a vu le processus complet réalisé par notre calculatrice (et, plus généralement, par un programme qui lit un texte structuré et fait quelque chose avec les données trouvées). Il nous reste cependant à implémenter le parseur, c'est-à-dire la fonction qui lit du texte et retourne sa représentation intermédiaire (de type Expr) selon la grammaire donnée.

Avec la grammaire de notre calculatrice, le parsing revient à essayer de produire la règle Additive, ce qui nécessite de produire l'une de ses deux sous-règles, en privilégiant celle la plus à gauche. C'est typiquement ce que fait un parseur récursif descendant avec retour arrière.

Pour implémenter ce genre de parseur, il est plus facile de partir des règles de bas-niveau (ici Digit, Digits, Nat, etc.), car on peut les tester immédiatement, sans avoir besoin des règles de plus haut niveau. C'est ce qu'on va voir dans la suite de cette section.

III-B - Un type Result

Du point de vue d’un utilisateur, notre parseur retourne un Either String Expr, c'est-à-dire soit une valeur Left avec un message d'erreur (quand le parsing a échoué), soit une valeur Right avec l'expression arithmétique trouvée.

Pour ce qui concerne l’implémentation, on va écrire des parseurs spécifiques à chaque règle de notre grammaire. Ainsi, le parseur spécifique à une règle pourra être appelé « dans une règle de plus haut-niveau ». Pour cela, on a besoin que ces parseurs retournent un peu plus d'information, par exemple grâce au type Result vsuivant.

1. type Result v = Either String (v, String)

Ainsi un parsing réussi fournit maintenant un tuple (v, String) où le premier élément est la valeur parsée et le second élément est le reste (non-consommé) du texte à parser. On notera que Result v est un type paramétré, qui peut donc représenter les résultats des différents parseurs. Par exemple, un parseur d'entiers retournera un Result Int alors qu'un parseur pour la règle Multitive retournera un Result Expr.

III-C - Parseurs bas-niveau

À partir du type Result v précédent, on peut maintenant écrire le code des différents parseurs, en partant du bas-niveau. La règle la plus basse de notre grammaire est Digit ::= '0' | '1' | ... | '9'. Pour la parser, on peut donc écrire une fonction pDigit qui prend le texte d'entrée et retourne un Result Char.

1. pDigit :: String -> Result Char

2. pDigit "" = Left "no input"

3. pDigit (c:cs) =

4. if isDigit c

5. then Right (c, cs)

6. else Left "not a digit"

Si le texte d'entrée est vide, on retourne le message d'erreur "no input". Si on a lu un caractère et que celui-ci est un chiffre, on retourne le caractère et le texte restant (dans un tuple). Enfin, si le caractère lu n'est pas un chiffre, on retourne le message d'erreur "not a digit".

Comme prévu, on peut tout de suite tester ce parseur, par exemple dans l'interpréteur interactif de Haskell et sur le texte d'entrée "12".

1. *Mycalc.Parser.Recursive> pDigit "12"

2. Right ('1',"2")

Ici, le parsing a bien réussi  : la valeur parsée est le caractère '1' et le texte restant "2".

À partir de ce parseur de chiffres, on peut maintenant écrire un parseur de « nombres », en suivant la règle de grammaire Digits ::= Digit Digits | Digit. Cette règle correspond soit à parser un chiffre puis encore un nombre (récursivement), soit à parser juste un chiffre. Ceci revient donc à consommer tous les chiffres possibles dans le flux d'entrée.

1. pDigits :: String -> Result String

2. pDigits s0 =

3. case pDigit s0 of

4. Left err -> Left err

5. Right (v1, s1) -> case pDigits s1 of

6. Right (v2, s2) -> Right (v1:v2, s2)

7. Left _ -> Right ([v1], s1)

La fonction pDigits est une implémentation directe de la règle de grammaire Digits. Dans le premier case, on essaie d'abord de parser un chiffre, grâce au parseur pDigit précédent. En cas d'erreur, cela signifie que l'entrée n'a aucun chiffre et on propage donc l'erreur. En cas de succès, on a donc parsé un chiffre et on essaie alors de parser d'autres chiffres, avec l'appel récursif du deuxième case. Si l'appel récursif a réussi, on retourne le nombre trouvé, précédé du chiffre qu'on avait déjà trouvé dans le premier case. Si l'appel récursif a échoué, cela signifie juste que le reste de l'entrée ne commence pas par un chiffre et qu'il faut donc retourner uniquement le chiffre trouvé dans le premier case.

On peut tester notre parseur pDigits, par exemple sur l'entrée "12".

1. *Mycalc.Parser.Recursive> pDigits "12"

2. Right ("12","")

On notera que pDigits retourne une chaîne de caractères correspondant à un nombre, mais pas un type de nombres comme Int. Pour cela, on peut écrire le parseur pNat suivant, qui appelle tout simplement pDigits et construit un Int à partir de son résultat en cas de succès, grâce à la fonction read de Haskell.

1. pNat :: String -> Result Int

2. pNat s0 =

3. case pDigits s0 of

4. Right (v, s1) -> Right (read v, s1)

5. Left err -> Left err

III-D - Parseurs de Expr

De la même façon que pNat retourne un Result Int, on peut très facilement écrire un parseur pDecimal qui retourne un Result Expr (il suffit d'appeler pNat et de construire une valeur ExprVal à partir de son Int).

Toujours selon la même méthode, on peut implémenter la règle Multitive ::= Decimal '*' Multitive | Decimal. On a juste un case de plus, car il faut également détecter le caractère '*'.

1. pMultitive :: String -> Result Expr

2. pMultitive s0 = alt1 where

4. -- 1er cas : Decimal '*' Multitive

5. alt1 = case pDecimal s0 of

6. Right (vleft, s1) -> case s1 of

7. ('*':s2) -> case pMultitive s2 of

8. Right (vright, s3) ->

9. Right (ExprMul vleft vright, s3)

10. _ -> alt2

11. _ -> alt2

12. _ -> alt2

14. -- 2e cas : Decimal

15. alt2 = pDecimal s0

Pour la règle Additive, on écrit un parseur pAdditive, de façon très similaire.

Finalement, on écrit la fonction de parsing principale, qui consiste juste à appeler pAdditive et à retourner uniquement les informations voulues (message d'erreur ou Expr).

IV - Notion de foncteur

IV-A - Rappel sur les foncteurs

En Haskell, un Functor est un type « à l'intérieur duquel on peut appliquer une fonction », grâce à la fonction fmap ou à l'opérateur <$>. Par exemple, les listes sont des Functor.

1. Prelude> (*2) <$> [2, 21]

2. [4,42]

De même, les types Either sont des Functor, où la fonction s'applique sur les valeurs Right.

1. Prelude> x1 = Right 21 :: Either String Int

3. Prelude> x2 = Left "foo" :: Either String Int

5. Prelude> (*2) <$> x1

6. Right 42

8. Prelude> (*2) <$> x2

9. Left "foo"

IV-B - Intérêt pour les parseurs

Pour rappel, le type Result v, utilisé pour écrire nos parseurs précédents, est défini de la façon suivante.

1. type Result v = Either String (v, String)

C'est un Either, donc un Functor. On peut donc « fmapper » une fonction sur la valeur de succès d'un parseur. Par exemple, on avait écrit pDecimal de la façon suivante.

1. pDecimal :: String -> Result Expr

2. pDecimal s0 = case pNat s0 of

3. Right (v, s1) -> Right (ExprVal v, s1)

4. Left err -> Left err

En fait, pDecimal est exactement pNat, mais où l'on a juste appliqué la fonction ExprVal sur le premier élément du tuple des valeurs Right.

Comme Result v est un foncteur, on peut réécrire pDecimal plus simplement, en « fmappant » une fonction sur le résultat de pNat.

1. pDecimal :: String -> Result Expr

2. pDecimal s0 = (\(x,y) -> (ExprVal x, y)) <$> pNat s0

Pour résumer, on a donc défini un type Result v représentant le résultat d'un parsing. On peut ensuite définir des fonctions de parsing qui retournent des valeurs de ce type. Et comme Result v est un foncteur, on peut définir de nouveaux parseurs simplement en « fmappant » des fonctions sur les résultats de parseurs existants.

En fait, on peut même aller plus loin et définir un type non pas pour le résultat d'un parsing, mais pour la fonction de parsing elle-même. Et si ce nouveau type (qu'on appellera Parser) est un foncteur, on pourra de même définir de nouveaux parseurs directement en « fmappant » sur des parseurs existants. C'est cette idée qui est développée dans les sections suivantes.

V - Implémenter des parseurs par des types

V-A - Un type Parser

Comme annoncé précédemment, on peut définir, en plus du typeResult v, un type Parser v qui représente une fonction de parsing.

1. type Result v = Either String (v, String)

3. newtype Parser v = Parser { runParser :: String -> Result v }

Ainsi, le type Parser v représente des valeurs Parser comportant un champ runParser. Ce champ est une fonction qui prend un String et retourne un Result v.

V-B - Exemple : parser le caractère '0'

Pour illustrer l'usage de notre type Parser v, on va considérer un problème simple  : parser le caractère '0'. Si l’on utilise la méthode précédente, avec les parseurs récursifs descendants, on peut écrire la fonction pZero suivante, qui prend un String et retourne un Result Char.

1. pZero :: String -> Result Char

2. pZero ('0':xs) = Right ('0', xs)

3. pZero str      = Left ("no parse", str)

Mais on peut également définir un Parser Char permettant de parser le caractère '0'. Pour cela, il suffit de construire une valeur Parser dont le champ runParser est la fonction pZero précédente.

1. zeroP :: Parser Char

2. zeroP = Parser { runParser = pZero }

Pour utiliser ce parser zeroP, il suffit de récupérer son champ runParser, c'est-à-dire la fonction de parsing, et ensuite d'appliquer cette fonction de parsing sur le flux d'entrée.

1. > runParser zeroP "0foobar"

2. Right ('0', "foobar")

4. > runParser zeroP "foobar"

5. Left ("no parse", "foobar")

On notera qu'on peut également définir zeroP sans expliciter le nom du champ.

1. zeroP :: Parser Char

2. zeroP = Parser pZero

En fait, on peut même écrire directement la fonction de parsing dans la définition du parseur, par exemple avec une lambda.

1. zeroP :: Parser Char

2. zeroP = Parser (\str ->

3. case str of

4. ('0':xs) = Right ('0', xs)

5. _        = Left ("no parse", str))

V-C - Parseurs de bas niveau

Revenons maintenant à notre calculatrice et réécrivons-la en utilisant le type Parser v. Tout d'abord, on peut écrire un parseur itemP, qui extrait simplement un caractère du flux d'entrée.

1. itemP :: Parser Char

2. itemP = Parser $ \s0 ->

3. case s0 of

4. (x:xs) -> Right (x, xs)

5. [] -> Left "no input"

On peut ensuite écrire nos autres parseurs à partir de itemP, par exemple digitP pour parser un chiffre.

1. digitP :: Parser Char

2. digitP = Parser $ \s0 ->

3. case runParser itemP s0 of

4. Right (c, cs) ->

5. if isDigit c

6. then Right (c, cs)

7. else Left "not a digit"

8. Left err -> Left err

Et là, c'est le drame  : l'implémentation est nettement plus compliquée qu'avec les parseurs récursifs descendants. En effet, on avait écrit pDigit de la façon suivante.

1. pDigit :: String -> Result Char

2. pDigit (c:cs) =

3. if isDigit c

4. then Right (c, cs)

5. else Left "not a digit"

6. pDigit _ = Left "no input"

Le problème vient du fait que notre fonction de parsing est désormais « à l'intérieur d'un type », ce qui signifie qu'on doit extraire la fonction de parsing de itemP puis l'appliquer pour récupérer son résultat, et intégrer tout cela dans une fonction et dans une valeur de type Parser v.

Fort heureusement, on a déjà un début de solution à ce problème  : les foncteurs. En effet, si le type Parser v est un foncteur, alors on peut définir des parseurs en « fmappant » une fonction sur un parseur précédent.

V-D - Les combinateurs de parseurs monadiques

V-E - Motivation

Dans la section précédente, on a défini un type Parser v pour représenter des parseurs. On a vu que ce type ne simplifiait pas à lui seul l'implémentation de nos parseurs mais qu'il pouvait servir de support à des « outils » de plus haut niveau comme les foncteurs.

En Haskell, les classes de types permettent d'implémenter des fonctionnalités communes à tout un ensemble de types, un peu comme les interfaces en POO. Par exemple, tous les types de classe Show implémentent une fonction show; n'importe quelle valeur d'un de ces types peut donc être passée en argument à la fonction print (qui est définie par print x = putStrLn (show x)).

Par conséquent, si on instancie la classe Functor pour notre type Parser v, alors on pourra utiliser fmap pour définir nos parseurs plus simplement. De plus, il existe d'autres classes de types qui peuvent être intéressantes pour manipuler des parseurs  : Applicative, Monad, Alternative.

V-F - Classes instanciables pour le type Parser

On a déjà parlé de la classe Functor, qui permet d'appliquer une fonction « à l'intérieur du type ». Pour cela, elle définit la fonction fmap ou, de façon équivalente, l'opérateur <$>.

1. (<$>) :: Functor f => (a -> b) -> f a -> f b

Ainsi, si l’on instancie cette classe pour notre type Parser v, on peut, par exemple, définir un parseur de Int à partir d'un parseur de chiffre, de la façon suivante (digitToInt retourne l'entier correspondant à un chiffre).

1. digitP :: Parser Char

2. digitP = ...

4. intP :: Parser Int

5. intP = digitToInt <$> digitP

La classe Applicative représente les foncteurs applicatifs. L'opérateur <*> est assez similaire à <$>, mais avec une fonction qui est elle-même « à l'intérieur du type ». Concrètement, cela permet de « fmapper » des fonctions à plusieurs paramètres. Applicative définit également la fonction pure qui « met à l'intérieur du type ».

1. (<*>) :: Applicative f => f (a -> b) -> f a -> f b

3. pure :: Applicative f => a -> f a

Dans notre contexte de parseurs, si l’on reprend le parseur intP précédent, on peut définir un nouveau parseur qui parse deux chiffres, les convertit en Int et retourne leur somme, de la façon suivante.

1. addP :: Parser Int

2. addP = (+) <$> intP <*> intP

La classe Alternative correspond aux « foncteurs avec une structure de monoïde ». Plus concrètement, il s'agit de l'opérateur d'alternative <|> et de l'élément neutre empty.

1. (<|>) :: Alternative f => f a -> f a -> f a

3. empty :: Alternative f => f a

Dans le contexte des parseurs, il s'agit d'une classe intéressante, car elle permet d'essayer un parseur et, en cas d'échec, d'en essayer un autre. Par exemple, si zeroP parse le caractère '0' et unP le caractère '1', alors on peut définir le parseur zeroOuUnP qui parse '0' ou sinon '1', de la façon suivante.

1. zeroP :: Parser Char

2. zeroP = ...

4. unP :: Parser Char

5. unP = ...

7. zeroOuUnP :: Parser Char

8. zeroOuUnP = zeroP <|> unP

Enfin la classe Monad permet de représenter une « suite d'actions ». Elle comporte l'opérateur >>=, qui permet de chaîner des actions et la fonction return, qui est l'équivalent de pure, mais dans le contexte des monades. Généralement, on définit également une fonction fail qui permet d'interrompre une chaîne d'actions, avec un message d'erreur.

1. (>>=) :: Monad m => m a -> (a -> m b) -> m b

3. return :: Monad m => a -> m a

5. fail :: Monad m => String -> m a

Par exemple, on peut écrire le parseur addP précédent dans un style monadique, de la façon suivante.

1. addP :: Parser Int

2. addP = intP

3. >>= \i1 -> intP

4. >>= \i2 -> return (i1 + i2)

Avec les monades, on peut également utiliser la notation do, qui est généralement plus lisible.

1. addP :: Parser Int

2. addP = do

3. i1 <- intP

4. i2 <- intP

5. return (i1 + i2)

V-G - Utilisation pour nos parseurs

Les classes de types précédentes permettent de simplifier l'écriture de nos parseurs. Ainsi le parseur pDigit était initialement  :

1. pDigit :: String -> Result Char

2. pDigit (c:cs) =

3. if isDigit c

4. then Right (c, cs)

5. else Left "not a digit"

6. pDigit _ = Left "no input"

En style monadique, on peut écrire le parseur digitP équivalent  :

1. digitP :: Parser Char

2. digitP = do

3. c <- itemP

4. if isDigit c

5. then return c

6. else fail "not a digit"

Pour pDigits, on avait  :

1. pDigits :: String -> Result String

2. pDigits s0 = case pDigit s0 of

3. Right (v1, s1) -> case pDigits s1 of

4. Right (v2, s2) -> Right (v1:v2, s2)

5. Left _ -> Right ([v1], s1)

6. Left err -> Left err

que l'on peut réécrire en style monadique  :

1. digitsP :: Parser String

2. digitsP = do

3. c <- digitP

4. cs <- (digitsP <|> return "")

5. return (c:cs)

ou encore, en style « foncteur applicatif »  :

1. digitsP :: Parser String

2. digitsP = (:) <$> digitP <*> (digitsP <|> return "")

et même, en utilisant la fonction some du module Control.Applicative  :

1. digitsP :: Parser String

2. digitsP = some digitP

Ce qui est clairement plus simple que la première implémentation pDigits.
De même, pour pMultitive, on avait  :

1. pMultitive :: String -> Result Expr

2. pMultitive s0 = alt1 where

4. alt1 = case pDecimal s0 of

5. Right (vleft, s1) -> case s1 of

6. ('*':s2) -> case pMultitive s2 of

7. Right (vright, s3) ->

8. Right (ExprMul vleft vright, s3)

9. _ -> alt2

10. _ -> alt2

11. _ -> alt2

13. alt2 = pDecimal s0

Avec le type Parser v et en style monadique, on obtient  :

1. multitiveP :: Parser Expr

2. multitiveP

3. =   (do e1 <- decimalP

4. _ <- charP '*'

5. e2 <- multitiveP

6. return $ ExprMul e1 e2)

7. <|> decimalP

Ou encore, en style « applicatif »  :

1. multitiveP :: Parser Expr

2. multitiveP

3. =   (ExprMul <$> decimalP <*> (charP '*' *> multitiveP))

4. <|> decimalP

V-H - Implémentation des instances de classes

Dans les sections précédentes, on a vu qu'on pouvait définir un type Parser v, que ce type pouvait être de classe Functor, Applicative, Alternative ou Monad, et que ceci permettait de simplifier grandement l'écriture de nos parseurs.

Cependant, on a passé sous silence l'instanciation de ces classes pour le type Parser v, c'est-à-dire comment écrire concrètement les fonctions et opérateurs correspondants (<$>, <*>, pure, etc.). Ceci est donné ci-dessous à titre informatif, mais ne sera pas détaillé, car c'est assez technique et à ne faire qu’une fois pour toutes avec le type Parser v tel qu'on l'a défini.

1. instance Functor Parser where

3. fmap fct (Parser p) =

4. Parser $ \s0 -> do

5. (x, s1) <- p s0

6. return (fct x, s1)

1. instance Applicative Parser where

3. pure x = Parser $ \s -> Right (x, s)

5. (Parser p1) <*> (Parser p2) =

6. Parser $ \s0 -> do

7. (fct, s1) <- p1 s0

8. (x, s2) <- p2 s1

9. return (fct x, s2)

1. instance Alternative (Either String) where

3. empty = Left "empty"

5. Left _ <|> e2 = e2

6. e1 <|> _ = e1

8. instance Alternative Parser where

10. empty = Parser $ const empty

12. (Parser p1) <|> (Parser p2)

13. = Parser $ \input -> p1 input <|> p2 input

1. instance Monad Parser where

3. (Parser p) >>= fct =

4. Parser $ \s0 -> do

5. (x1, s1) <- p s0

6. (x2, s2) <- runParser (fct x1) s1

7. return (x2, s2)

9. fail msg = Parser $ \_ -> Left msg

VI - Les bibliothèques « à la Parsec »

Il existe de nombreuses bibliothèques Haskell implémentant les combinateurs de parseurs monadiques  : parsec, attoparsec, megaparsec… Concrètement, ces bibliothèques implémentent un type Parser avec les instances de classes correspondantes, des parseurs de base et enfin quelques fonctions pour lancer le parsing global, gérer les erreurs, etc.

Cette dernière section explique comment écrire le parseur de notre calculatrice avec ReadP.

VI-A - Le module ReadP

ReadP est un module de la bibliothèque base, qui ne nécessite donc aucune installation particulière. Il suffit d'importer le module Text.ParserCombinators.ReadP puis d'utiliser le type ReadP et les fonctions fournies (voir la documentation de ReadP).

VI-B - Exemple d'utilisation

En utilisant ReadP, on peut implémenter très facilement le parseur de notre calculatrice. Pour les parseurs « bas niveau » de notre grammaire, on utilise satisfy (qui contruit un parseur à partir d'un prédicat sur un Char) et many1 (qui réalise une ou plusieurs occurrences d'un parseur donné).

1. digitP :: ReadP Char

2. digitP = satisfy isDigit

4. digitsP :: ReadP String

5. digitsP = many1 digitP

7. natP :: ReadP Int

8. natP = read <$> digitsP

Enfin, pour les règles de plus haut niveau, on utilise simplement les parseurs précédents et les opérateurs classiques de Functor, Applicative, Alternative et Monad.

1. decimalP :: ReadP Expr

2. decimalP = ExprVal <$> natP

4. multitiveP :: ReadP Expr

5. multitiveP  -- en style applicatif

6. =   (ExprMul <$> decimalP <*> (char '*' *> multitiveP))

7. <|> decimalP

9. additiveP :: ReadP Expr

10. additiveP  -- en style monadique

11. =   do e1 <- multitiveP

12. _ <- char '+'

13. e2 <- additiveP

14. return $ ExprAdd e1 e2

15. <|> multitiveP

Comme on peut le constater, si les concepts et implémentations des combinateurs de parseurs monadiques demandent un peu de réflexion, leur utilisation concrète est plutôt très simple.

VII - Conclusion

Dans ce tutoriel, on a abordé les combinateurs de parseurs monadiques à partir d'un exemple de calculatrice basique en Haskell. Il s'agit du problème classique de parsing, c'est-à-dire comment analyser un texte structuré selon des règles précises (expression arithmétique, document XML, code source en C…). En première approche, un parseur est une fonction qui prend un texte et retourne une valeur d'un type attendu (Char, Int… ou plus généralement un type représentant les données que l'on veut manipuler).

En seconde approche, on a vu qu'on pouvait également représenter un parseur par un type algébrique et en instancier des classes de types comme Functor, Monad, etc. Ainsi, un parseur peut être vu comme une action qui retourne une valeur, dans un contexte de parsing (c'est-à-dire avec un flux de texte que l'on peut consommer). En pratique, on peut définir et combiner des parseurs, de façon simple et élégante, jusqu'à obtenir le parseur complet voulu.

Les combinateurs de parseurs monadiques peuvent s'implémenter dans différents langages de programmation. En Haskell, cette implémentation est assez naturelle et de nombreuses bibliothèques sont effectivement proposées et couramment utilisées. Par exemple, le projet bond est un framework de manipulation de données structurées, largement développé et utilisé par Microsoft, et dont le compilateur est écrit en Haskell (grâce à la bibliothèque Megaparsec).

Certains développeurs Haskell sont même plus prosélytes et vont jusqu'à dire que « Haskell est un langage incroyable pour écrire votre propre compilateur. Si vous écrivez un compilateur dans un autre langage, vous devriez vraiment songer à changer. » Gabriel Gonzales, State of the Haskell ecosystem.

VIII - Quelques références

- Graham Hutton and Erik Meijer, Monadic parser combinators, 1996 : http://www.cs.nott.ac.uk/~pszgmh/bib.html#monparsing

- Graham Hutton, Functional Parsing, 2020 : https://www.youtube.com/watch?v=dDtZLm7HIJs

- Tsodin, JSON Parser 100% From Scratch in Haskell, 2019 : https://www.youtube.com/watch?v=N9RUqGYuGfw

- Haskell basic libraries, Text.ParserCombinators.ReadP : https://hackage.haskell.org/package/base/docs/Text-ParserCombinators-ReadP.html

IX - Note de la rédaction de Developpez.com

Nous tenons à remercier escartefigue pour la relecture orthographique de ce tutoriel.