Dans un précédent article, j’utilisais des combinateurs de parseurs afin de réaliser l’analyse syntaxique de l’encodage Bencode. Je voudrais revenir sur cet outil qui, à mon humble avis, mérite de figurer dans la trousse à outil de l’ingénieur logiciel.

Nous commencerons par détailler quelques cas d’utilisation où les combinateurs de parseurs tirent leur épingle du jeu. Ensuite, nous découvrirons plus en détail ce en quoi ils consistent, et ce qui les distingue des parseurs plus traditionnels. Enfin, nous mettrons en évidence ce qui fait la force, et parfois la faiblesse, de cet outil.

Cas d’utilisation

Le parsing, ou analyse syntaxique, consiste à transformer des données brutes, souvent textuelles, en des structures plus compréhensibles. Il s’agit d’une étape qui précède l’analyse sémantique, laquelle a pour but de mettre en évidence le sens de ces données.

Un cas d’utilisation très répandu des parseurs est l’analyse de codes informatiques: un développeur rédige un programme sous la forme d’un texte ponctué de symboles particuliers. Pour qui sait le lire, ce texte est structuré en blocs. Les blocs peuvent faire référence les uns aux autres par l’intermédiaire de structures spéciales. Enfin, certaines parties des blocs ont pour fonction de décrire la dynamique d’un programme: le développeur y exprime la manière dont celui-ci doit se comporter selon les circonstances rencontrées, de nouveau grâce à des structures textuelles convenues d’avance. Un parseur a alors pour tâche de transformer un bloc de code, fait de lettres et d’autres symboles, en une structure manipulable par un autre programme.

Les Domain Specific Language (DSL) sont souvent liés aux parseurs: un concepteur imagine la manière de décrire des entités qui ont du sens pour un expert du domaine choisi. Les relations entre ces entités sont décrites au moyen de structures spécifiant une dépendance, une appartenance, une équivalence, ou toute autre relation qui a du sens dans le domaine. Un parseur doit être capable de comprendre une description basée sur un DSL, et en extraire les éléments qui constituent cette description.

Les parseurs sont parfois utilisés afin d’étendre les capacités d’un logiciel: lorsque celui-ci doit pouvoir s’adapter à une grande variété de règles métier, il est délicat d’exiger de ses utilisateurs qu’ils maîtrisent un langage de programmation traditionnel, tel que C ou Python. De plus, la plupart des langages de programmation compilés se prêtent mal à la définition dynamique du comportement du programme. Il peut alors être préférable de laisser les utilisateurs spécifier le comportement souhaité en utilisant un mini-language spécialisé, et de laisser un parseur interpréter dynamiquement cette spécification à la demande.

Dans le domaine de la sécurité, des parseurs peuvent être utilisés pour analyser des fichiers ou des flux de données, y détecter des patrons malveillants (par exemple, l’exploitation de code injecté), et mettre ses patrons en évidence pour qu’un système automatique les traite plus efficacement.

Comme l’illustrent ces quelques cas d’utilisation, les parseurs ne se limitent pas à quelques langages bien connus et pour lesquels il existe depuis longtemps des solutions d’analyse, mais ils sont au contraire un vecteur d’innovation et de dynamisme pour les développeurs d’application.

Combinateurs de parseurs

ll existe une myriade d’outils pour générer des parseurs. La plupart du temps, leurs utilisateurs doivent décrire, grâce à une grammaire précise, les structures que le parseur devra reconnaître. Cette description est alors transformée en une bouillie de code (par exemple, en C) que les utilisateurs pourront exploiter en venant y ajouter l’implémentation de fonctions qui seront appelées lorsque telle ou telle structure sera identifiée. Il est donc nécessaire de mettre en œuvre un mécanisme qui permet la génération du code propre au parseur et son « injection » au sein du projet logiciel auquel on souhaite l’intégrer.

Les combinateurs de parseurs proposent une approche différente de cells de ces outils classiques.

Tout d’abord, ils sont basés sur des fonctions et la composition: chaque élément du parseur consiste en une fonction prenant en entrée une chaîne de caractères ou un flux de données. En sortie, la fonction produit une structure telle qu’elle a été détectée, ainsi que le reste de l’entrée qui n’a pas été extrait par la fonction. Des parseurs simples peuvent alors être composés, aussi facilement que peuvent l’être des fonctions. C’est de cette capacité dont dispose le développeur de combiner des parseurs que vient le nom de cette approche. Parmi les combinaisons les plus systématiques, citons:

• La séquence, qui consiste à parser un élément, puis un autre, etc.
• Le choix, qui permet d’indiquer plusieurs alternatives de parsing: l’élément suivant pourrait être parsé par A ou bien par B.
• La répétition: le même parseur est capable d’extraire plusieurs éléments de manière consécutive.
• L’optionnel: Un parseur extraire un élément, ou non.

Étant donné que l’élément de base d’un tel parseur est la fonction, celui-ci est typiquement implémenté grâce à un langage de programmation fonctionnelle, tel que Scala. Comme nous le verrons, d’autres outils propres à la programmation fonctionnelle trouvent leur utilité dans ce cas d’utilisation, ce qui renforce l’intérêt des languages qui la supporte. Cependant, les mêmes principes peuvent s’appliquer grâce à un langage impératif et/ou orienté objet.

Cette approche par fonction favorise la modularité: chaque parseur est une unité autonome, facilement testable et réutilisable. Cela mène à une conception relativement claire, car des parseurs simples peuvent être combinés sans écrire manuellement du code supplémentaire pour gérer la logique de combinaison.

Puisqu’un parseur se résume en une combinaison de fonctions, l’approche est fortement déclarative. Les combinateurs permettent de décrire la grammaire d’un langage ou d’un format de manière très proche de sa définition formelle. Par exemple, une grammaire contextuelle peut être directement traduite en combinateurs de parseurs, ce qui rend le code lisible et maintenable.

Le résultat de l’application d’un parseur à une entrée est typiquement l’une des deux options suivantes:

• Soit le parseur échoue à extraire du début de l’entrée la structure qu’il recherche, auquel cas un autre parseur peut être essayé, par exemple dans le cas d’un choix;
• Soit le parseur réussit à extraire la structure recherchée du début de l’entrée, auquel cas il retourne cette structure ainsi que le reste de l’entrée. Le mécanisme de composition permet de poursuivre le parsing de ce reste, notamment si un combinateur de type séquence est utilisé.

Exemple de combinateur de parseurs

En Scala, chaque parseur est donc décrit par une fonction de type E -> (Option[T], E), où E est le type d’entrée, et T est le type de retour attendu lorsque le parseur réussit l’extraction. Puisque la mécanique d’interrogation d’un parseur et de progression le long d’une entrée est toujours la même, la fonction peut se résumer à la représentation suivante: « si tu détectes tel patron, alors le résultat doit être celui-ci ».

Le hasard faisant bien les choses, une telle règle s’exprime facilement avec la plupart des langages de programmation fonctionnelle, grâce au pattern matching. Si vous ne connaissez pas, imaginez des expressions régulières pouvant être appliquées à des structures complexes. Alors que les expressions régulières ne s’appliquent qu’au texte brut, le pattern matching peut s’appliquer à n’importe quelle structure de données, comme des arbres, des graphes, des tableaux, ou des objets. Et, dans le cas des combinateurs de parseurs, des fonctions représentant d’autres (combinateurs de) parseurs peuvent également s’appliquer. Il est alors possible de récupérer non seulement des sous-chaînes de caractères comme c’est le cas des expressions régulières, mais aussi des structures arbitraires que vous aurez définies sous la forme de case classes, et que votre règle pourra extraire automatiquement grâce aux parseurs embarqués dans votre règle. Quant au résultat, il sera ce que bon vous semble: typiquement une autre instance de case class créée directement à partir des structures extraites par la règle.

Au-delà de la flexibilité qu’apportent les expressions régulières, vous pouvez, en utilisant le pattern matching, imposer des conditions arbitraires sur les structures que vous souhaitez extraire. Ainsi, dans notre exemple de Bencode, il était possible de repérer un flux de données constitué de la taille d’une chaîne binaire, encodée sous la forme d’une chaîne de caractères, suivie du symbole « : » suivi de la chaîne binaire elle-même. Une telle structure est impossible à extraire avec les expressions régulières, car celles-ci ne disposent pas de l’expressivité nécessaire pour récupérer une longueur de chaîne et pour l’appliquer sur la chaîne binaire de la même entrée.

Des robots

Réalisons un exemple de combinateur de parseurs. Évitons la sempiternelle calculatrice, et supposons que vous souhaitiez configurer des robots. Chaque robot a les propriétés suivantes:

• Nom: son identifiant.
• Type: la catégorie du robot, comme éclaireur, combattant ou travailleur
• Énergie: une valeur numérique représentant l’énergie qu’il reste au robot.
• Position: les coordonnées (x,y) du robot sur la carte.
• Capacité: les actions que le robots peut réaliser.

Concrètement, voici un fichier qui représente trois robots grâce au DSL que nous souhaitons créer.

robot "R2-D2" type scout energy 100 position (10, 20) abilities [move, scan]
robot "C3-PO" type worker energy 50 position (5, 5) abilities [translate]
robot "T-800" type fighter energy 200 position (0, 0) abilities [attack, defend]

Commençons par importer la bibliothèque de combinateurs de parseur de Scala.

import scala.util.parsing.combinator.{JavaTokenParsers, RegexParsers}

Ensuite, représentons le concept de robot.

sealed trait Ability
object Move extends Ability
object Scan extends Ability
object Translate extends Ability
object Attack extends Ability
object Defend extends Ability

sealed trait RobotType
object Scout extends RobotType
object Worker extends RobotType
object Fighter extends RobotType

case class Robot(name: String, robotType: RobotType, energy: Int, position: (Int, Int), abilities: List[Ability])

Petite parenthèse sur les types algébriques

Lorsqu’un développeur habitué à la programmation orientée objet observe le code ci-dessus, il ne peut que lever les bras au ciel devant son inutilité apparente: ni les traits ni les objets n’ont d’attributs pouvant leur apporter une certaine richesse. Aucun élément n’a de méthode, et donc aucun comportement. Seule la classe Robot dispose de quelques éléments qui semblent importer. Dès lors, ce code peut-il se ramener à quelques lignes, voire être complètement supprimé? Pouvoir, certainement, mais devoir, cela est discutable. On appelle les capacités et les types de robots, tels que nous les avons décrits, des types algébriques. Bien qu’ils puissent avoir attributs et méthodes, ils en sont généralement dépourvus. Ils formalisent des concepts propres à un métier et se répartissent en deux catégories: les types produits et les types sommes.

Les types produits combinent plusieurs valeurs en un seul ensemble structuré. Chaque instance contient toutes les valeurs spécifiées, et les langages de programmation qui les supportent fournissent des fonctionnalités pratiques comme l’égalité, l’affichage lisible et l’extraction via le pattern matching. Les types produits sont essentiels pour représenter des entités ou objets du monde réel en regroupant leurs attributs. En Scala, les case classes incarnent parfaitement cette idée.

Les types sommes permettent de représenter plusieurs possibilités alternatives pour une donnée. En Scala, cela se fait souvent à l’aide de types scellés ou via un hiérarchie de classes abstraites et d’implémentations concrètes. Ces types permettent de limiter les possibilités à un ensemble défini et de les traiter de manière exhaustive via le pattern matching, renforçant ainsi la sûreté du code.

L’un des grands avantages des types algébriques est qu’ils offrent une sécurité accrue au niveau du typage. En modélisant précisément les données, ils réduisent les erreurs liées à des états invalides. Par exemple, un type somme peut garantir qu’une variable est toujours dans un état valide, en excluant les cas incohérents. Les types algébriques se combinent également bien avec le pattern matching, permettant de gérer toutes les options possibles et de compiler des alertes en cas d’omission.

Les types algébriques sont omniprésents dans la programmation fonctionnelle. En Scala, des structures comme Option, Either et Try sont des exemples typiques de types sommes. Ces types permettent de représenter des états comme « une valeur peut être présente ou non » (Option) ou « un résultat peut être une réussite ou une erreur » (Either, Try). Leur utilisation encourage un style de programmation plus déclaratif et robuste, où les erreurs ou cas limites sont explicitement modélisés.

Les parseurs proprement dits

Créons à présent les parseurs pour les différents constituants d’un robot:

object RobotConfigParser extends RegexParsers with JavaTokenParsers {
  // Nom entre guillemets
  def name: Parser[String] = "\"" ~> "[^\"]+".r <~ "\""

  // Entier positif ou nul.
  def nonNegativeNumber: Parser[Int] = """\d+""".r ^^ { _.toInt }

  // Type du robot (scout, worker, etc.)
  def robotType: Parser[RobotType] = """\w+""".r ^^ {
    case "scout" => Scout
    case "worker" => Worker
    case "fighter" => Fighter
  }

  // Énergie
  def energy: Parser[Int] = nonNegativeNumber

  def position: Parser[(Int, Int)] = "(" ~> wholeNumber ~ "," ~ wholeNumber <~ ")" ^^ {
    case x ~ _ ~ y => (x.toInt, y.toInt)
  }

  def abilities: Parser[List[Ability]] = "[" ~> repsep("""\w+""".r, ",") <~ "]" ^^ { case l => l.map {
    case "move" => Move
    case "scan" => Scan
    case "translate" => Translate
    case "attack" => Attack
    case "defend" => Defend
  }}

  // Un robot complet
  def robot: Parser[Robot] =
    ("robot" ~> name) ~ ("type" ~> robotType) ~ ("energy" ~> energy) ~
      ("position" ~> position) ~ ("abilities" ~> abilities) ^^ {
      case n ~ t ~ e ~ pos ~ abil => Robot(n, t, e, pos, abil)
    }

  // Parseur principal, pour plusieurs robots
  def robots: Parser[List[Robot]] = rep(robot)

  // Fonction utilitaire pour exécuter le parseur
  def parseRobots(input: String): Either[String, List[Robot]] = parseAll(robots, input) match {
    case Success(result, _) => Right(result)
    case NoSuccess(msg, _) => Left(s"Erreur de parsing : $msg")
  }
}

Le plus dur est fait. Prenons le temps d’éplucher ces quelques lignes de code.

La ligne 1 permet d’utiliser un certain nombre de parseurs définis dans les traits RegexParsers et JavaTokenParsers. Le premier permet la conversion automatique d’expressions régulières en parseur, dont nous pouvons voir un exemple d’utilisation en ligne 3. Le second trait définit des parseurs pour la syntaxe du langage Java, mais, en dépit du nom de ce trait, ils sont en réalité utilisables dans de nombreuses situations: chaînes de caractères, nombres (le wholenumber de la ligne 18), séparation par un caractère quelconque (ligne 22), etc.

En plus de ces parseurs prédéfinis, nous réutilisons également des parseurs que nous avons nous-même définis: par exemple, nonNegativeNumber est utilisé en ligne 16; le parseur global du robot, en ligne 31, utilise tous les parseurs que nous avons définis au préalable; finalement, un parseur d’une liste de robot (défini en ligne 38) n’est qu’une répétition du parseur de robot.

Remarquez que nos parseurs gèrent assez élégamment les parties d’entrées qui sont utiles pour marquer des structures à extraire tout en excluant ces marqueurs du traitement appliqué à la structure. Par exemple, dans les lignes 32 et 33, chaque caractéristique du robot commence par un marqueur ("robot", par exemple) suivi du parseur qui nous intéresse véritablement (name, dans le même exemple). L’opérateur ~ indique une séquence de parseurs, tandis que l’opérateur ~> signifie que le terme à sa gauche n’est qu’un marqueur ne devant pas être traité.

Exploitation

Concluons notre exemple en appliquant notre parseur à un jeu de données:

object main {
  def main(args: Array[String]): Unit = {
    val input =
      """
         robot "R2-D2" type scout energy 100 position (10, 20) abilities [move, scan]
         robot "C3-PO" type worker energy 50 position (5, 5) abilities [translate]
         robot "T-800" type fighter energy 200 position (0, 0) abilities [attack, defend]
       """

    // Parsing de l'entrée
    RobotConfigParser.parseRobots(input) match {
      case Right(robots) =>
        println("Robots extraits :")
        robots.foreach(println)
      case Left(error) =>
        println(s"Erreur : $error")
    }
  }
}

Le résultat à l’écran:

Robots extraits :
Robot(R2-D2,Scout$@66480dd7,100,(10,20),List(Move$@5ec0a365, Scan$@4fe3c938))
Robot(C3-PO,Worker$@20398b7c,50,(5,5),List(Translate$@6fc6f14e))
Robot(T-800,Fighter$@56235b8e,200,(0,0),List(Attack$@3632be31, Defend$@5abca1e0))

Au-delà des chaînes de caractères

Bien que les parseurs soient généralement destinés à l’analyse de contenus textuels, leur champ d’action s’étend à n’importe quel flux de données. Au début de cet article, j’ai évoqué leur usage afin d’analyser des fichiers ou des flux de données (a priori binaires) à des fins de sécurité. Je mentionnais aussi un précédent article dans lequel un parseur pour le format Bencode, (partiellement) binaire, était développé.

De manière générale, les parseurs peuvent être utilisés pour le décodage de formats quelconques. Ils peuvent donc constituer la partie « décodeur » d’un codec. Il y a cependant, le plus souvent, une différence entre les données analysées par les parseurs et celles décodées au sein d’un flux: les premières possèdent un contexte qui complexifie grandement l’analyse. Dans le cas d’un programme, il s’agira par exemple du fait qu’on soit en train de décrire les arguments d’une fonction ou de rédiger un commentaire. L’entrée, lue du début à sa fin, peut être temporairement ambiguë: ce n’est qu’en poursuivant la lecture qu’un parseur peut déterminer de manière univoque le contexte d’analyse et en déduire les structures à extraire. Au contraire, l’analyse des formats de fichier et de flux est souvent simple et directe: l’ambiguïté n’est jamais de mise et le contexte, lorsqu’il existe, est toujours évident.

Les combinateurs de parseurs, parce qu’ils permettent l’expression de parseurs par combinaison, facilitent la gestion du contexte en la rendant implicite: on déclare la possibilité d’une structure optionnelle, et c’est à l’analyseur de déterminer si elle est effectivement présente. On indique une séquence de structures, à charge du parseur d’en déterminer le nombre d’éléments.

Grâce à leur capacité à prendre en compte un contexte plus riche que les expressions régulières, les combinateurs de parseurs constituent une alternative intéressante à ces dernières. Cela a cependant un prix: ce type de parseur nécessite une certaine quantité de mémoire afin d’être capable d’explorer l’ensemble des structures potentiellement extractibles, et de « revenir sur ses pas » lorsqu’une extraction a priori prometteuse se termine en un cul-de-sac en cours d’analyse. De même, ce parcours des possibilités demande du temps. Les combinateurs de parseurs sont donc réputés pour être moins performants que d’autres approches plus directes. En particulier, dans le cas du décodage d’un fichier ou d’un flux de données, le format de celui-ci aura normalement été conçu pour en faciliter l’analyse, si bien qu’une approche plus simple serait préférable.

Conclusion

À mon avis, Scala tire profit de son support de la programmation fonctionnelle (et, en particulier, de son système de pattern matching), pour nous offrir un joyau trop souvent mésestimé. Si les combinateurs de parseurs ne constituent pas une solution miracle à tous nos problèmes, leur concours s’avère bien utile dans de nombreuses circonstances, pour autant qu’on connaisse leur existence.

Par exemple, la mise en œuvre d’un DSL est quelque chose qui tend à effrayer un gestionnaire de projet, qui y voit un risque important d’échec, et, dans le meilleur des cas, de nombreuses semaines passées à rédiger des grammaires dans d’obscures langages. Vous savez à présent que la vérité est toute autre: il est possible de concevoir et d’outiller ces DSL sans quitter votre langage de programmation.

Chaque règle est une fonction. Chaque fonction permet d’extraire une instance d’un type Scala à partir d’une entrée. Les règles se combinent en des règles plus complexes. C’est tout.