Parser un format simple en Haskell avec Parsec

Introduction du cours

Ce tutoriel a pour but de vous présenter les bases de l'utilisation de Parsec, une bibliothèque écrite en Haskell. Parsec facilite l'écriture d'analyseur syntaxique (parser) en fournissant des parsers plus ou moins basiques ainsi que des combinateurs pour les lier. Le parsing étant une tâche courante en programmation (que ce soit pour lire un fichier de configuration, des résultats dans une base de données ou interpréter un langage), la connaissance de Parsec peut très largement vous simplifier la vie.
Contrairement à bison ou à Happy, avec Parsec, la grammaire du langage à parser s'écrit directement en Haskell. Pour suivre ce tutoriel, il est donc seulement nécessaire d'avoir des bases dans ce langage. Si vous ne savez pas ce que sont une monade ou un foncteur, reportez-vous au cours de gnomnain (à ce jour, il est suffisant pour comprendre de quoi il retourne dans ce tutoriel).

PrémicesOutils

Pour suivre le tutoriel, vous n'aurez besoin que d'un éditeur, d'un compilateur Haskell (de préférence avec un mode interactif) et de Parsec.
Parsec est disponible sur HackageDB. Vous pouvez télécharger le paquet directement et suivre les instructions du README ou utiliser cabal-install, voir les paquets de votre distribution. Attention tout de même, ce tutoriel est prévu pour la version 3.*. Pensez à vérifier quelle version vous installez (précisez là si vous utilisez cabal-install).

Objectifs

Afin d'en apprendre un peu plus sur Parsec, nous allons écrire un parser pour un format simple. J'ai choisi d'implémenter un parser pour les "Desktop Entries". Ce sont des fichiers de configuration donnant des informations sur la façon d'ouvrir un programme, comment l'afficher dans un menu … La spécification de ce format fait partie de celles proposées par le groupe Freedesktop.org et est utilisée, entre autres, par GNOME et KDE. Cette spécification a le mérite d'être courte, simple, disponible librement et en ligne (bien qu'en anglais), tout en permettant de jouer avec les bases de Parsec.
Voici à quoi ressemble le type de fichier que nous allons analyser:

[Desktop Entry] Cle=Valeur Name=XMonad Comment=Lightweight tiling window manager Comment[fr]=Un gestionnaire de fenêtre pavant et léger Exec=xmonad Icon=xmonad Type=Application Version=0.9 NoDisplay=true # Un commentaire [Autre Groupe] X-IsAwesome=true X-CeNestPasUnBooleen=True X-DonotKnow= X-JaiBesoinDunExemple=des chaînes contenant un caractère spécial:\t \n etc.

L'exemple parle de lui-même: un fichier .desktop est une suite de clef/valeur (comme Name=XMonad) appartenant à un groupe (X-IsAwesome=True appartient au groupe Autre Groupe) et les lignes commençant par un dièse sont des commentaires. Toutes les clefs se trouvant après la déclaration d'un groupe appartiennent à celui-ci.
Notre parser respectera les règles suivantes:

• Un nom de groupe peut contenir n'importe quel caractère, sauf les crochets ([]) et les caractères spéciaux (\n, \t…), et doit être unique.

• Un nom de clef peut contenir uniquement des caractères alphanumériques non accentués ainsi que le tiret (-) et les crochets.

• Au sein d'un même groupe, deux clefs ne peuvent avoir le même nom.

• La spécification retient 4 types pour les valeurs: string, localestring, boolean et numeric. Nous conserverons ces types à l'exception de localestring, qui sera traité comme string (la différence entre les deux se situant dans l'encodage, ça ne me semble pas intéressant d'en parler).

Nous ajouterons deux ou trois choses au cours du tutoriel, mais il est plus que temps de lancer notre éditeur et d'utiliser Parsec.

Premier contact

Dans la partie précédente, nous avons distingué trois éléments principaux dans notre spécification: les groupes, les commentaires et les paires clefs/valeurs. Le but de cette partie sera de parser chacun d'entre eux.

Parser une ligne

Dans un fichier .desktop, les lignes ont une particularité intéressante: elles contiennent un et un seul élément: une déclaration de groupe, un commentaire ou une paire (éventuellement rien, mais ce ne sera pas un problème). Commençons donc par parser une ligne.

Parser un commentaire

Les commentaires sont les lignes les plus simples à parser. En effet, il suffit de vérifier que la ligne commence par un dièse. Voyons comment implémenter ça avec Parsec. Les deux premières lignes du code permettent d'importer Parsec. Par la suite, on les considérera comme sous-entendues.

import Text.Parsec import Text.Parsec.String (Parser) commentaire :: Parser String commentaire = char '#' >> (many $ noneOf "\n")

Tout d'abord, un commentaire sur le type de la fonction commentaire . Parser String est un alias pour le type ParsecT String () Identity String . ParsecT s u m a est la monade (en fait, le transformeur de monade) utilisé par Parsec. Son premier paramètre (s ) est le type du flux à parser. Un flux est une instance de la classe Stream , définie par Parsec et dont le but est entre autres de gérer la position actuelle dans le flux. Ici, nous allons parser une liste de caractères. Le second (u ) ne nous sera pas utile et donc nous n'en parlerons pas. Le troisième (m ) est une monade. Comme ParsecT est un transformeur de monade, on peut le composer avec d'autres monades pour profiter des caractéristiques de chacune. Mais ici, nous utilisons la monade Identity qui permet d'obtenir en fait une monade classique. Il n'est pas nécessaire de bien comprendre ce qu'est un transformeur de monade pour la suite puisque nous allons l'utiliser comme une simple monade. Toutefois, ceux souhaitant en savoir plus peuvent lire le chapitre de Real World Haskell sur le sujet. Enfin, le dernier (a ) est le type de retour du parser.

Après ce point légèrement délicat, jetons un coup d'œil au corps de la fonction. L'une des choses qu'on peut remarquer en premier est l'utilisation de l'opérateur >> . Comme je l'ai dit, Parsec est une bibliothèque monadique: on va donc pouvoir utiliser toutes les fonctions sur les monades et la notation do . Dans Parsec, >> va appliquer le parser à sa droite si celui à sa gauche a réussi. On retrouve un peu la logique de la monade Maybe qui court-circuite toute la suite d'action si l'une d'entre elles retourne Nothing . Là, si un parser échoue, tout le reste échoue. Sinon, on évalue la fonction suivante.

À gauche de >> se trouve la fonction char . C'est une fonction fournie par Parsec. Elle prend en paramètre un caractère (en Haskell, on note les caractères entre guillemets simples) et va tenter de le parser. Si elle réussit, c'est donc qu'on a affaire à un commentaire.

Il ne nous reste plus qu'à analyser le reste de la ligne. noneOf prend en paramètre une liste de caractère et réussi si le caractère à parser n'est pas dans la liste. Parsec contient également une fonction s'appelant oneOf qui fait l'opposé (elle parse seulement les caractères qui sont dans la liste qui lui est fournie). Comme un commentaire peut contenir n'importe quoi à l'exception d'un retour à la ligne, on utilise noneOf "\n" .

many est un combinateur très courant qui va appliquer le parser qu'on lui passe en argument autant de fois que possible (ça peut être 0, 1 ou n'importe quel nombre de fois, tant que le parser réussi) et retourner une liste des éléments parsés. noneOf retournant le caractère analysé — tout comme char d'ailleurs — commentaire nous retournera une liste de caractère. Cette liste sera le commentaire, privé du dièse initial.

Chargez le code précédent avec GHCi et essayons de parser un texte.

*Main>parse commentaire "" "#Salut" Right "Salut"

Comme on s'y attendait, la fonction parse retourne le commentaire, le dièse en moins. La fonction parse prend trois arguments : un parser, une chaîne de caractère utilisée comme label pour les erreurs (le nom du fichier en général) et le texte à analyser. Elle retourne une valeur du type Either ParseError a où a est le type de retour du parser passé en argument.

Essayons maintenant avec autre chose qu'un commentaire.

*Main>parse commentaire "" "Salut" Left (line 1, column 1): unexpected "S" expecting "#"

Parsec renvoie une erreur, mais précise aussi ce qui a causé cette erreur. Ici, le premier caractère doit être un dièse, pas un S. On verra avant la fin du tutoriel qu'on peut personnaliser le message d'erreur grâce au combinateur <?> .

Parser une déclaration de groupe

Si vous avez bien compris comment parser un commentaire, vous devriez déjà être capable de parser une déclaration de groupe. Voici une première implémentation n'utilisant que ce qu'on a vu pour les commentaires :

groupe :: Parser String groupe = do char '[' nom <- many $ noneOf ("[]\127"++['\0'..'\31']) char ']' return nom

La liste fournie à noneOf est la seule chose nouvelle. Dans la première partie, nous avons fixé que les noms de groupe pouvaient contenir tous les caractères ASCII à l'exception des crochets et des caractères de contrôle. En Haskell, on peut écrire les caractères soit en les tapant directement comme 'A' soit en donnant leur représentation numérique ('\65' par exemple). Les caractères de contrôles sont tous ceux ayant un code inférieur à 32 ou égal à 127. Nous autorisons l'utilisation de '\32' car c'est l'espace. La notation [a..b] permet de lister tout les éléments entre a et b (avec a=2 et b=5, la liste sera [2,3,4,5] ).

Cette implémentation marche correctement, mais on peut faire beaucoup plus concis en regardant dans les combinateurs proposés par Parsec. between est un combinateur prenant trois parsers en paramètre. Il va parser le premier puis le troisième et après, le second et retourner le résultat du troisième. Dans notre cas, la valeur de retour sera donc le nom du groupe, sans les crochets. C'est exactement ce que fait notre fonction groupe . En utilisant between , elle devient ceci :

groupe :: Parser String groupe = between (char '[') (char ']') (many $ noneOf ("[]\127"++['\0'..'\31']))

C'est déjà plus esthétique, non? Il faut tout de même faire attention lorsqu'on utilise between à ce que le troisième parser n'inclue pas le délimiteur de fin, sinon between échouera forcément.
Si nous avions écrit groupe de cette façon (anyChar parse n'importe quel caractère), groupe = between (char '[') (char ']') $ many anyChar , lors de l'exécution de notre parser, nous aurions eu droit à une erreur du type "unexpected end of input", indiquant que le parser a consommé tout le fichier sans pour autant réussir.

Parser une paire

Après tout cela, parser une paire se révèle être extrêmement simple. Je vous recommande d'ailleurs d'essayer d'implémenter vous même le parser avant de voir la solution que voici :

paire :: Parser String paire = do c <- clef char '=' v <- valeur return $ c ++ " vaut " ++ v clef :: Parser String clef = many (alphaNum <|> oneOf "[]_-@") valeur :: Parser String valeur = many $ noneOf "\n"

La grande nouveauté est le combinateur <|> . Il applique tout d'abord le parser à sa gauche. S'il réussit, il retourne le résultat. S'il échoue sans modifier l'état du flux (le flux est ici la chaîne de caractère à lire, par exemple, le contenu d'un fichier .desktop), il applique le second. Un parser consomme le flux à partir du moment où il parse quelque chose, et ce même s'il rencontre une erreur après. Prenons le parser suivant :

test = anyChar >> char '#'

Comme anyChar réussi pour tout caractère, on est quasiment sûr que ce parser va consommer une partie du flux. Si on l'utilise avec <|> , le parser à droite ne sera jamais essayé. Nous verrons ce problème plus en détail par la suite. Pour l'instant, aucun problème puisqu'alphaNum ne consomme rien lorsqu'il échoue. Une autre chose à laquelle nous devons prendre garde lorsqu'on utilise <|> , c'est que les deux parsers doivent être du même type, et donc retourner des données du même type.
Par ailleurs, alphaNum est la seule autre nouveauté de ce code. Il réussit dans le cas où le caractère à parser est un chiffre ou une lettre.

La fonction paire retourne la clef et la valeur sous la forme d'une chaîne de caractère.

Parser un fichier

Pouvoir parser une ligne, c'est cool mais c'est assez limité surtout quand la plupart des fichiers utilisant le format que nous devons parser sont généralement composés de plusieurs dizaines de lignes. Toutefois, nous n'avons pas perdu notre temps: nous avons un parser pour chaque élément de base de notre spécification. Il suffit maintenant d'assembler le tout et ce à l'aide, évidemment, des combinateurs de Parsec.

Il faut tout d'abord définir une fonction capable de parsern'importe quelle ligne qu'on puisse trouver dans un fichier .desktop, c'est-à-dire soit une déclaration de groupe, soit un commentaire, soit une paire. Si vous avez pensé utiliser le combinateur <|> , bravo, vous avez bien suivi. Mais dans quel ordre? On sait que si un parser consomme une partie de l'entrée, les autres options sont ignorées. Il faut donc d'abord préciser des parsers qui ne consommeront rien dans le cas où ils échouent. On sait que commentaire ne posera aucun problème puisqu'il ne peut échouer que si char '#' échoue, et lorsque char échoue, cela veut dire qu'il n'a rien parsé, et s'il réussi, on se trouve nécessairement face à un commentaire. Le problème se pose pour groupe et paire . En effet, dans le cas d'une ligne commençant par un crochet ouvrant ([), groupe va parser tout les caractères suivants n'étant pas des caractères de contrôle. Le problème est qu'on pourrait avoir en fait affaire à une clef, ce qu'on ne saura qu'au moment où nous trouverons le crochet fermant ou le retour à la ligne. Ça semble mal engagé.

On peut envisager deux solutions : la première serait de récupérer l'état actuel...