Parser du texte facilement en C# avec la librairie Sprache

L'analyse syntaxique (parsing) est une tâche très courante, mais qui peut être laborieuse et où il est facile de faire des erreurs. Il existe de nombreuses approches :

• analyse manuelle basée sur Split, IndexOf, Substring, etc. ;
• expressions régulières ;
• parser codé à la main qui scanne les tokens dans une chaîne ;
• parser généré avec ANTLR ou un outil similaire ;
• et certainement beaucoup d'autres qui m'échappent…

Aucune de ces options n'est très séduisante. Pour les cas simples, découper la chaîne ou utiliser une regex peut suffire, mais ça devient vite ingérable pour des grammaires plus complexes. Construire un vrai parser à la main pour une grammaire non triviale est loin d'être facile. ANTLR nécessite Java, un peu de connaissance, et se base sur de la génération de code, ce qui complique le process de build.

Heureusement, Sprache offre une alternative très intéressante. Il fournit de nombreux parsers et combinateurs prédéfinis qu'on peut utiliser pour définir une grammaire. Examinons pas à pas un cas concret : analyser le challenge dans le header WWW-Authenticate d'une réponse HTTP (j'ai dû faire un parser à la main pour ça récemment, et j'aurais aimé connaître Sprache à ce moment-là).

Le header WWW-Authenticate est envoyé par un serveur HTTP dans une réponse 401 : « Non autorisé », pour indiquer au client comment s'authentifier :

# Challenge Basic
WWW-Authenticate: Basic realm="FooCorp"
 
# Challenge OAuth 2.0 après l'envoi d'un token expiré
WWW-Authenticate: Bearer realm="FooCorp", error=invalid_token, error_description="The access token has expired"

Ce que l'on veut parser est le challenge, c'est-à-dire la valeur du header. Nous avons donc un mécanisme d'authentification ou « schème » (Basic, Bearer), suivi d'un ou plusieurs paramètres (paires nom-valeur). Ça semble assez simple, on pourrait sans doute juste découper selon les ',', puis selon les '=' pour obtenir les valeurs… mais les guillemets compliquent les choses, car une chaîne entre guillemets peut contenir les caractères ',' ou '='. De plus, les guillemets sont optionnels si la valeur du paramètre est un simple token, donc on ne peut pas compter sur le fait que les guillemets seront présents (ou pas). Clairement, si on veut parser ça de façon fiable, il va falloir regarder les spécifications de plus près…

Le header WWW-Authenticate est décrit en détail dans la RFC-2617. La grammaire ressemble à ceci, sous une forme que la spécification appelle « forme Backus-Naur augmentée » (voir RFC 2616 §2.1) :

# from RFC-2617 (HTTP Basic and Digest authentication)
 
challenge      = auth-scheme 1*SP 1#auth-param
auth-scheme    = token
auth-param     = token "=" ( token | quoted-string )
 
# from RFC2616 (HTTP/1.1)
 
token          = 1*<any CHAR except CTLs or separators>
separators     = "(" | ")" | "<" | ">" | "@"
               | "," | ";" | ":" | "\" | <">
               | "/" | "[" | "]" | "?" | "="
               | "{" | "}" | SP | HT
quoted-string  = ( <"> *(qdtext | quoted-pair ) <"> )
qdtext         = <any TEXT except <">>
quoted-pair    = "\" CHAR

Nous avons donc quelques règles de grammaire, voyons comment on peut les encoder en C# à l'aide de Sprache, et les utiliser pour analyser le challenge.

Commençons par les parties les plus simples de la grammaire : les tokens (« jetons »). Un token est défini comme un ou plusieurs caractères qui ne sont ni des caractères de contrôle, ni des séparateurs.

Nous allons définir nos règles dans une classe Grammar. Commençons par définir certaines classes de caractères :

static class Grammar
{
    private static readonly Parser<char> SeparatorChar =
        Parse.Chars("()<>@,;:\\\"/[]?={} \t");
 
    private static readonly Parser<char> ControlChar =
        Parse.Char(Char.IsControl, "Control character");
 
}

Chaque règle est déclarée comme un Parser<T> ; puisque ces règles valident des caractères seuls, elles sont de type Parser<char>.

• La classe Parse de Sprache expose des primitives d'analyse et des combinateurs.
• Parse.Chars valide n'importe quel caractère de la chaîne spécifiée, on l'utilise pour spécifier la liste des caractères de séparation.
• La surcharge de Parse.Char que l'on utilise ici prend un prédicat qui sera appelé pour valider un caractère et une description de cette classe de caractères. Ici on utilise la méthode System.Char.IsControl comme prédicat pour identifier les caractères de contrôle.

Définissons maintenant une classe de caractères TokenChar, qui correspond aux caractères qui peuvent être inclus dans un token. Selon la RFC, il s'agit de n'importe quel caractère qui n'appartient pas aux deux classes précédemment définies :

private static readonly Parser<char> TokenChar =
    Parse.AnyChar
        .Except(SeparatorChar)
        .Except(ControlChar);

• Parse.AnyChar, comme son nom l'indique, valide n'importe quel caractère.
• Except permet de spécifier des exceptions, c'est-à-dire des règles qui ne doivent pas valider le caractère.

Enfin, un token est une séquence d'un ou de plusieurs de ces caractères :

private static readonly Parser<string> Token =
    TokenChar.AtLeastOnce().Text();

• Un token est une chaîne, donc la règle qui lui est appliquée est de type Parser<string>.
• AtLeastOnce() signifie une ou plusieurs répétitions, et puisque TokenChar est un Parser<char>, AtLeastOnce() renvoie un Parser<IEnumerable<char>>.
• Text() combine la séquence de caractères en une chaîne, et renvoie donc un Parser<string> .

Nous voilà donc capables de parser un token. Mais ce n'est qu'un premier pas, il nous reste encore pas mal de travail…

La RFC définit une chaîne entre guillemets (quoted string) comme une séquence de :

• un guillemet qui ouvre la chaîne ;

• n'importe quel nombre de l'un de ces éléments :

  • un « qdtext », c'est-à-dire n'importe quel caractère sauf un guillemet,
  • un « quoted pair », c'est-à-dire n'importe quel caractère précédé d'un backslash (c'est utilisé pour échapper les guillemets à l'intérieur d'une chaîne) ;
• un guillemet qui ferme la chaîne.

Écrivons donc les règles pour qdtext et quoted pair :

private static readonly Parser<char> DoubleQuote = Parse.Char('"');
private static readonly Parser<char> Backslash = Parse.Char('\\');
 
private static readonly Parser<char> QdText =
    Parse.AnyChar.Except(DoubleQuote);
 
private static readonly Parser<char> QuotedPair =
    from _ in Backslash
    from c in Parse.AnyChar
    select c;

La règle QdText se passe d'explication, mais QuotedPair est plus intéressante… Comme vous pouvez le voir, ça ressemble à une requête Linq : c'est comme ça que l'on spécifie une séquence avec Sprache. Cette requête-là signifie : prendre un backslash (qu'on nomme _ parce qu'on va l'ignorer) suivi de n'importe quel caractère nommé c, et renvoyer juste c (les « quoted pairs » ne sont pas vraiment des séquences d'échappement comme en C, Java ou C#, donc "\n" n'est pas interprété comme « nouvelle ligne », mais simplement comme "n").

On peut donc maintenant écrire la règle pour une chaîne entre guillemets :

private static readonly Parser<string> QuotedString =
    from open in DoubleQuote
    from text in QuotedPair.Or(QdText).Many().Text()
    from close in DoubleQuote
    select text;

• La méthode Or indique un choix entre deux parsers. QuotedPair.Or(QdText) essaie de valider une « quoted pair » et si cela échoue, il essaie de valider un « qdtext » à la place.
• Many() indique un nombre quelconque de répétitions.
• Text() combine les caractères en une chaîne.
• On sélectionne juste text, car on n'a plus besoin des guillemets (ils ne servaient qu'à délimiter la chaîne).

Nous avons maintenant toutes les briques de base, on va donc pouvoir passer à des règles de plus haut niveau.

Un challenge est constitué d'un schème d'authentification suivi d'un ou plusieurs paramètres. Le schème est trivial (c'est juste un token), donc commençons par parser les paramètres.

Bien que la RFC n'ait pas de règle nommée pour ça, définissons-nous une règle pour les valeurs des paramètres. La valeur peut être soit un token, soit une chaîne entre guillemets :

private static readonly Parser<string> ParameterValue =
    Token.Or(QuotedString);

Puisqu'un paramètre est un élément composite (nom et valeur), déclarons une classe pour le représenter :

class Parameter
{
    public Parameter(string name, string value)
    {
        Name = name;
        Value = value;
    }
     
    public string Name { get; }
    public string Value { get; }
}

Le T de Parser<T> n'est pas limité aux caractères ou aux chaînes, ça peut être n'importe quel type. La règle pour parser les paramètres sera donc de type Parser<Parameter> :

private static readonly Parser<char> EqualSign = Parse.Char('=');
 
private static readonly Parser<Parameter> Parameter =
    from name in Token
    from _ in EqualSign
    from value in ParameterValue
    select new Parameter(name, value);

Ici on prend un token (le nom du paramètre), suivi du signe '=', suivi d'une valeur de paramètre, et on combine le nom et la valeur en une instance de Parameter.

Analysons maintenant une séquence d'un ou plusieurs caractères. Les paramètres sont séparés par des virgules, avec des caractères d'espacement optionnels avant et après la virgule (chercher « #rule » dans la RFC 2616 §2.1). La grammaire pour les listes autorise plusieurs virgules successives sans éléments entre elles, par exemple item1 ,, item2,item3, ,item4, donc la règle pour le séparateur de liste peut être écrite comme ceci :

private static readonly Parser<char> Comma = Parse.Char(',');
 
private static readonly Parser<char> ListDelimiter =
    from leading in Parse.WhiteSpace.Many()
    from c in Comma
    from trailing in Parse.WhiteSpace.Or(Comma).Many()
    select c;

On valide juste la première virgule, le reste peut être n'importe quel nombre de virgules et de caractères d'espacement. On renvoie la virgule parce qu'il faut bien renvoyer quelque chose, mais on ne l'utilisera pas (dans un langage fonctionnel, on aurait pu renvoyer le type unit à la place).

On peut maintenant analyser une séquence de paramètres comme ceci :

private static readonly Parser<Parameter[]> Parameters =
    from first in Parameter.Once()
    from others in (
        from _ in ListDelimiter
        from p in Parameter
        select p).Many()
    select first.Concat(others).ToArray();

Mais c'est un peu alambiqué… heureusement Sprache fournit une approche plus facile avec la méthode DelimitedBy :

private static readonly Parser<Parameter[]> Parameters =
    from p in Parameter.DelimitedBy(ListDelimiter)
    select p.ToArray();

On y est presque. On a maintenant tout ce qu'il nous faut pour parser le challenge complet. Déclarons d'abord une classe pour le représenter :

class Challenge
{
    public Challenge(string scheme, Parameter[] parameters)
    {
        Scheme = scheme;
        Parameters = parameters;
    }
    public string Scheme { get; }
    public Parameter[] Parameters { get; }
}

Et on peut enfin écrire la règle globale :

public static readonly Parser<Challenge> Challenge =
    from scheme in Token
    from _ in Parse.WhiteSpace.AtLeastOnce()
    from parameters in Parameters
    select new Challenge(scheme, parameters);

Remarquez que j'ai déclaré cette règle comme publique, contrairement aux autres : c'est la seule que l'on a besoin d'exposer.

Notre parseur est terminé, il n'y a plus qu'à l'utiliser, ce qui est assez simple :

void ParseAndPrintChallenge(string input)
{
    var challenge = Grammar.Challenge.Parse(input);
    Console.WriteLine($"Scheme: {challenge.Scheme}");
    Console.WriteLine($"Parameters:");
    foreach (var p in challenge.Parameters)
    {
        Console.WriteLine($"- {p.Name} = {p.Value}");
    }
}

Avec le challenge OAuth 2.0 de l'exemple précédent, ce code produit la sortie suivante :

Scheme: Bearer
Parameters:
- realm = FooCorp
- error = invalid_token
- error_description = The access token has expired

S'il y a une erreur de syntaxe dans le texte en entrée, la méthode Parse lancera une ParseException avec un message décrivant où et pourquoi l'analyse a échoué. Par exemple, si j'enlève l'espace entre « Bearer » et « realm », j'obtiens l'erreur suivante :

Vous trouverez le code complet de cet article ici.

Comme vous le voyez, il est très facile avec Sprache de parser un texte complexe. Le code n'est pas particulièrement concis, mais il est complètement déclaratif ; il n'y a pas de boucles, pas de conditions, pas de variables temporaires, pas d'état… Cela rend le code très facile à comprendre, et il peut facilement être comparé à la définition originale de la grammaire pour s'assurer de sa conformité. Sprache fournit aussi de bons retours en cas d'erreur, ce qui est assez difficile à implémenter dans un parseur écrit à la main.

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