Quand les regexes ne suffisent plus, il faut sortir sa grammaire

Les regexes sont pratiques. Malheureusement, si vous n'y prenez pas garde, elles se juxtaposeront, s'empileront, s'agglomèreront et s'interpénètreront pour former un affreux amoncellement. Très vite, vous n'oserez plus toucher le moindre appendice de cette chose tentaculaire de peur qu'il se rende compte de votre présence.

Nous avions déjà évoqué la toxicité des regexes. Dans ce billet, nous allons évoquer une autre façon d'exprimer les mots d'une langue formelle : en spécifiant une grammaire.

Développer des phrases

Machine à réécrire

Une grammaire formelle donne une recette pour produire un mot d'une langue formelle.

La définition d'une grammaire formelle peut rebuter au début. Pourquoi se compliquer la vie alors qu'une regex peut (parfois) faire le boulot ?

Rappelons qu'une langue formelle est un ensemble de mots dont les lettres sont dans un alphabet fixé. Les lettres sont à entendre dans un sens très large : une lettre peut désigner un chiffre, un caractère spécial comme Ớ, un emoji comme 🦄. Ou même un mot entier. Et, dans ce cas, un mot d'une langue formelle pourra correspondre à une phrase d'une langue naturelle.

Pour éviter les confusions, le terme de symbole sera employé à la place de lettre. De même, le terme de vocabulaire sera préféré à celui d'alphabet.

L'idée d'une grammaire formelle est d'utiliser un deuxième vocabulaire, qualifié de non terminal, disjoint du premier vocabulaire, qualifié de terminal. Les symboles non terminaux seront remplacés au fur et à mesure par des symboles terminaux. Les mots qui résulteront de tous ces remplacements auront bien toutes leurs lettres dans l'alphabet de la langue formelle.

Les différentes façons de remplacer les variables sont fixées par la grammaire : ce sont des règles de réécriture. Ces règles précisent comment tel mot est remplacé par tel autre.

Plus précisément, une grammaire formelle est la donnée :

Cette recette n'est pas unique : des grammaires différentes peuvent engendrer la même langue formelle. Et trouver la grammaire la plus petite est un problème compliqué.

Le binaire

Donnons une grammaire pour la langue binaire de vocabulaire terminal {a, b} avec une seule variable M et trois règles :

Par exemple, pour produire le mot abab, l'enchaînement des règles est le suivant :

Dans ce cas, la grammaire formelle ne semble pas plus efficace que l'expression régulière classique [ab]*.

Fermer les portes ouvertes

Considérons la langue des mots bien parenthésés dont le vocabulaire terminal est l'ensemble des deux parenthèses ( et ), avec les deux règles suivantes :

Quelques mots bien parenthésés : (), ()(), (())(()()).

Une telle langue est appelée langue de Dyck. Les langues de Dyck jouent un rôle important en informatique, notamment pour savoir si votre code est valide. On peut remplacer les parenthèses par d'autres symboles habituellement utilisés en programmation, comme les accolades, des crochets ou encore une indentation.

Les expressions régulières classiques ne sont pas capables de décrire tous les mots bien parenthésés : il faut en effet disposer d'une mémoire arbitrairement grande pour compter les parenthèses encore ouvertes. Certaines regexes, comme celles de Perl, peuvent décrire les mots bien parenthésés via l'opérateur de sous-motif récursif.

Mais bon, ça ressemble à un hack sournois que nous ne saurions décemment cautionner.

Voici une grammaire formelle qui décrit honnêtement les mots bien parenthésés. Il suffit de prendre une seule variable M et les trois règles suivantes :

Par exemple, pour produire (())(()()) :

Sujet, verbe, complément

Les grammaires formelles ont bien sûr été utilisées pour modéliser les grammaires des langues naturelles.

Décrivons quelques phrases en français-emoji en laissant tomber la ponctuation et les espaces ; on a tous été collégien un jour.

Cette grammaire engendre la phrase « le 🐱 observe la 🐭 », qui est correcte et ennuyeuse. La phrase « la 🐭 mange la 🐶 » est elle aussi correcte, mais sa syntaxe est défaillante et le sens étonnant.

Décrire la grammaire française dans son ensemble paraît inacessible. Dresser un tableau exhaustif des règles requiert un travail monumental. D'autant plus que la langue française évolue avec le temps, le lieu, les cultures, le contexte, les usages, etc. Mais notez que les langues naturelles peuvent souvent être partiellement traitées par des grammaires formelles.

Une grammaire pour les lier toutes

La flemme

Écrire toutes les règles d'une grammaire formelle peut être laborieux. On reprendrait bien certains des opérateurs des regexes, comme par exemple l'alternative | ou la répétition *. De même, si notre grammaire possède une règle qui remplace une variable Lettre par n'importe laquelle des 26 lettres de l'alphabet fondamental français, alors on aimerait condenser les 26 règles Lettre → a, ..., Lettre → z par une seule : Lettre → a .. z.

Les règles perdent leur caractère explicite mais gagnent en concision. D'un côté l'effort est reporté sur le lecteur qui doit interpréter correctement les deux points « .. ». De l'autre côté la factorisation du nombre de règles rend la grammaire plus simple à saisir. C'est un compromis. Un peu comme les abréviations ou l'adv. « respectivement », qui permettent resp. d'économiser des caractères et des répétitions au détriment de la fluidité.

Méta-langue ailleurs

En pratique, de nombreuses grammaires formelles (mais pas toutes) sont décrites en employant les mêmes conventions pour regrouper les règles : la forme de Backus-Naur étendue. Ou une variante.

Cette forme de Backus-Naur est elle-même une langue formelle. C'est donc une langue qui sert à décrire des langues : une méta-langue. D'ailleurs, elle pourrait peut-être se décrire elle-même... La forme de Backus-Naur reprend plusieurs opérateurs des regexes, proposant ainsi de se servir de la concision des regexes pour faciliter l'écriture d'une grammaire formelle.

Par exemple, la langue unaire {a}* peut être décrite par l'unique règle : X → ε | a X. Autrement dit : un mot de {a}* est soit le mot vide, soit la lettre a suivie d'un mot de {a}*.

Analyser du JSON

Essayons de convaincre le lecteur faussement sceptique de l'intérêt d'utiliser des grammaires formelles.

JSON, la langue franche

Le JSON (JavaScript Object Notation) est l'un des formats qui s'est imposé pour l'échange de données structurées. La plupart des interfaces programmatiques (API) aujourd'hui dialoguent en JSON, notamment grâce à JavaScript.

Le JSON utilise un système de clé-valeur, comme les tableaux associatifs, les objets en Javascript, les dictionnaires en Python ou les map en C++. Une valeur peut elle-même être un tableau associatif. Le JSON est donc plus pratique que le format CSV pour les données imbriquées.

Aaaaah, le CSV, il faudra en parler un jour.

Le JSON n'est pas très compact. Supposons donc développer une application web qui récupère des données au format JSON et qui essaie de faire quelque chose avec. Disons qu'elle se contente de vérifier que les données sont au bon format et renvoie une erreur 400 ou un autre message d'insulte en cas de mauvais format.

La donnée attendue possède deux clés :

Par exemple : {"foo": 42, "bar": "baz"}.

Avec des regexes et du courage

Le JSON n'est pas une langue régulière ; les expressions régulières classiques ne peuvent pas valider en général un texte écrit en JSON et les regexes, extensions des expressions régulières classiques, sont donc a priori mal adaptées à ce format. Mais comme nous sommes idiots naïfs courageux, on va quand même le faire.

Après quelques tests, nous tombons nez-à-nez sur la regex suivante :

{\s*"foo" *: *\d+ *,\s*"bar" *: *"[^"]*"\s*}

qui valide cette donnée, où \s désigne un espacement comme une espace ou une nouvelle ligne et \d un chiffre.

Le JSON standard n'accepte que des guillemets droits doubles ". Or, dans les objets Python par exemple, les guillemets droits simples ' sont parfois utilisés à la place. Pour plus de souplesse, nous pouvons accepter les deux. De plus, les clés ne sont pas toujours renseignées dans le même ordre. Et ça ne dérange pas Python d'avoir une virgule qui traîne. Ainsi, la donnée suivante paraît acceptable :

{\n 'bar': 'baz',\n'foo':'42' ,}

Ce qui complique la regex :

^{\s*([\'"]?)(foo)?(?(2)|bar)\1 *: *([\'"]?)(?(2)\d+|[^\3]*)\3\s*,\s* \1(?(2)bar|foo)\1 *: *([\'"]?)(?(2)[^\4]*|\d+)\4 *,?\s*}$

Si nous ajoutons des champs supplémentaires, nous perdrons le contrôle de la regex, déjà passablement sauvage. Moi-même, qui relis le billet en ce moment, me demande si elle est vraiment correcte.

Il faudrait peut-être se contenter de capturer des couples de clés-valeurs et laisser à un autre programme le soin de vérifier que les clés sont valides, uniques et que les valeurs sont du bon type. On pourrait considérer cette stratégie comme une preuve d'intelligence. Ou bien comme un renoncement, un compromis honteux, une défaite misérable.

Avec une grammaire formelle

Comparons maintenant avec une grammaire formelle décrite via (une variante de) la forme de Backus-Naur étendue.

La valeur associée à la clé bar est une chaîne de caractères entre guillemets droits (doubles ou simples). Elle est représentée par la regex [^"]* ou [^']*, c'est-à-dire une chaîne de caractères différents de " ou bien une chaîne de caractères différents de '. Utilisons donc un vocabulaire terminal très large, disons tous les caractères Unicode et notons-le V. La regex [^"]* correspondra à V - " et la regex [^']* correspondra à V - '.

Comme vocabulaire non terminal : {JDoc, Opening, Closing, Separator, Spaces, Foo, Bar, KeyFoo, KeyBar, ValueFoo, ValueBar, Colon, Digits, Digit}.

Voici donc les règles de la grammaire, la virgule représentant la concaténation de symboles :

Le lecteur jugera s'il préfère cette présentation à la regex

^{\s*([\'"]?)(foo)?(?(2)|bar)\1 *: *([\'"]?)(?(2)\d+|[^\3]*)\3\s*,\s* \1(?(2)bar|foo)\1 *: *([\'"]?)(?(2)[^\4]*|\d+)\4 *,?\s*}$

En tout cas, à moins d'être de mauvaise foi, il conviendra qu'il est plus simple d'ajouter des clés-valeurs avec la grammaire qu'avec la regex.

Un peu de combinatoire

En Python, le module standard re permet d'utiliser une regex pour effectuer des tâches. Il existe des modules pour employer une grammaire formelle, mais rien d'officiel.

C'est l'occasion de changer de langue de programmation.

Ça tombe bien : la librairie megaparsec de la langue de programmation Haskell s'avère pratique dans notre cas. Nous allons écrire un programme qui ne va pas se contenter de vérifier qu'une chaîne de caractère est conforme à une grammaire, mais construire un objet avec cette chaîne de caractère. Un tel programme est appelé parser, parseur ou analyseur syntaxique.

Voici le code, basé sur la grammaire formelle décrite plus haut, avec un cérémoniel allégé, c'est-à-dire sans importations, ni typage.

La structure de données de la charge utile : 

data Payload = Payload
    { foo :: Int
    , bar :: String
    } deriving Show

Une charge utile est entre accolades. Les deux champs sont séparés par une virgule et le dernier champ termine éventuellement par une virgule. On autorise les espacements un peu partout. Deux arrangements possibles, suivant la position de la clé foo.

payload = 
    between opening closing (fooBar <|> barFoo)
  where
    opening = char '{' >> space
    closing = space >> 
        optional (char ',') >>
        space >>
        char '}' >>
        return ()

D'abord la clé foo, puis la clé bar.

fooBar = Payload <$> fieldFoo <*> (sep >> fieldBar)

D'abord la clé bar, puis la clé foo.

barFoo = fieldBar >>= \barValue ->
    sep >>
    fieldFoo >>= \fooValue -> 
    return (Payload fooValue barValue)

La valeur à la clé foo est un entier.

fieldFoo = field "foo" (possiblyQuoted digits)
  where
    digits = fmap read (many digitChar) :: Parser Int

La valeur à la clé bar est une chaîne de caractères.

fieldBar = 
    field "bar" (quotedStringWith '\'' <|> quotedStringWith '"')
  where
    quotedStringWith c = quotedWith c (many (anySingleBut c))

Une fonction qui crée un analyseur clé/valeur.

field key parserValue = 
    possiblyQuoted (string key) >>
    space >>
    char ':' >>
    space >>
    parserValue

Un parseur éventuellement entouré de ' ou ".

possiblyQuoted p = quoted p <|> p

Un parseur entouré de ' ou ".

quoted p = quotedWith '\'' p <|> quotedWith '"' p

Une fonction qui évite la répétition de code.

quotedWith c = between (char c) (char c)

Le séparateur entre les clés : une virgule avec des espacements.

sep = space >> char ',' >> space

Soyons sérieux

La regex est certes plus compacte que le parseur maison. Mais le parseur est beaucoup plus compréhensible, même si vous débutez en Haskell. Le code peut être adapté facilement si le format accepté change. Et il ne fait pas que vérifier si la donnée est au bon format.

Évidemment, si votre tâche est réellement de développer une API, utilisez plutôt des outils déjà existant pour analyser le JSON. Sous Haskell, le module aeson fait très bien le boulot, par exemple.

Soyons fous

Hélas, la vie est une chienne. Le data scientist se retrouve parfois face à des fichiers écrits selon un format maison baroque, portant une structure clé-valeur inventive, enkysté dans le système informatique pour des raisons historiques. Raisons qui, si elles semblaient valables à l'époque, sont devenues clairement scandaleuses. If it ain't broke, don't fix it se rappelle l'homme de l'art : traduire ces fichiers vers un format plus adapté ou standard est peut-être trop coûteux, ou trop dangereux pour la sécurité de tous.

Par exemple, celui-là (fortement adapté d'un cas réel) : 

NUMERO: 42
NUMERO DU PARENT: 
ZONE : DTC 

DATE : 21/12/84      
DATEHEURE_TZER0=45:51;903212
LG_VALEUR=8 
CHAMPS=DEGRES AMPERE AMPERE BARS KIWIS % 
VALEURS =0032E+02, 000024.5, 000032.7, 
    00.75313, 0032E-01, 
        00000067

Avec des clés dont la position change suivant le fichier. Bien sûr.

Dans ce cas, les regexes ne sont pas adaptées. Vous devrez écrire votre parseur à la main. Ou vous servir d'un générateur automatique de parseur qui, étant donnée une grammaire formelle, engendre directement un parseur.

La présentation est importante, comme dans Top Chef

Les opérateurs des regexes peuvent servir à écrire une grammaire formelle et, réciproquement, une regex peut être présentée sous la forme d'une grammaire formelle. Ou de plusieurs, d'ailleurs. En revanche, la regex ainsi traduite perd sa forme compacte, donc son intérêt.

Grammaire régulière

Plus généralement, à toute expression régulière classique correspond au moins une grammaire dont chaque règle de réécriture est soit de la forme X → a, soit de la forme X → aY, avec a une lettre de l'alphabet et X et Y deux variables. Autrement dit, le membre de gauche est une variable et le membre de droite est soit une lettre, soit une lettre suivie d'une variable.

Une telle grammaire est dite régulière, ou rationnelle.

Par exemple, à l'expression régulière classique a(a[ab])*b, désignant les mots comme ab, aabb, aabaaabb, correspond la grammaire régulière suivante :

Pour engendrer le mot aabaaabb, l'enchaînement suivant convient :

Grammaire associée à une regex

Pour une regex générale, il n'y a pas de résultat similaire à celui sur les expressions régulières classiques.

Considérons la regex a(b*)[ab]{,2}\1 qui engendre les mots abab, abaab ou abbabb. Voici une grammaire qui effectue le même travail que cette brave regex :

Ça va bien se passer, même si on perd en concision sans gagner en clarté. Pour engendrer le mot abbabb, l'enchaînement suivant convient :

Cette grammaire n'est pas régulière : la règle (R2) contient deux lettres dans son membre de droite. C'est justement la règle qui correspond à la référence arrière \1, garantissant d'avoir le même nombre d'occurrences de la lettre b à la fin du mot que dans le groupe (b*).

Les automates, une autre vision du bonheur

Les regexes et les grammaires formelles, prises ensembles, forment une bel avant-goût du Paradis, c'est acté. Mais saviez-vous qu'il est aussi possible de décrire les mots des langues formelles à l'aide d'automates ? L'idée est simple : les états des automates correspondent aux variables et les règles de réécriture donnent les transitions entre ces états. Vu la longueur de ce billet, je vous épargne les détails.

Moralité

Chaque présentation a ses avantages et ses inconvénients, correspondant à différents points de vue sur le même objet.

Si la tâche paraît suffisamment simple pour tenir dans une petite regex, allez-y.

Si, finalement, la regex n'était pas si petite et qu'elle commence à agiter ses mignons tentacules, voire donner des signes de conscience, utilisez un automate.

Si vous n'arrivez pas à définir l'automate, écrivez votre grammaire dans un fichier et donnez-le à manger à un générateur automatique de parseur qui crééra l'automate à votre place, avec peut-être ce sale petit sourire méprisant qu'ont souvent ces programmes.

Si le générateur automatique de parseur n'est pas non plus capable d'engendrer un parseur, penchez-vous de nouveau sur votre automate, plus sérieusement. Ne boudez pas cette magnifique occasion de démontrer que l'être humain est encore plus fort que la machine, même si vous risquez d'y perdre quelques années d'espérance de vie.

De toute façon, la bonne tâche à résoudre n'est peut-être pas celle-là.


Antoine