L’idée de cet article m’est venue d’une question sur Stackoverflow.

La question porte sur la possibilité d’écrire

[Authorize(Roles = "Expert && (ReadWrite || ReadOnly)")]

Cette syntaxe n’est pas supportée par l’attribut Authorize. Il est tout de même possible d’arriver à ses fins en utilisant l’attribut 2 fois :

[Authorize(Roles = "Expert")] 
[Authorize(Roles = "ReadWrite, ReadOnly")]

Mais ce n’est pas fun (et trop simple). Dans cet article je vais donc vous montrer comment supporter la première syntaxe (et plus) en écrivant un petit parser, ou analyseur syntaxique en français, pour ce langage.

Le but est de “comprendre” le contenu de la chaine de caractère. Il faut donc en extraire les différentes informations : opérateurs et nom des rôles tout en gérant les priorités (parenthèses). L’idée est d’obtenir un arbre syntaxique représentant l’expression :

Avant d’en arriver là, commençons par les bases. Un langage, sans rentrer dans la théorie, c’est :

1. Un alphabet : ensemble de caractères valides
2. Des mots : ensemble cohérent de lettres de l’alphabet
3. Une grammaire : ensemble cohérent de mots. Pour ceux que ça intéresse, il existe différents types de grammaire. Noam Chomsky, un grand linguiste, les a classées en 4 catégories : http://fr.wikipedia.org/wiki/Hiérarchie_de_Chomsky

Pour parser notre langage, il faut donc commencer par définir ces 3 élements.

L’alphabet est composé :

• de lettres ‘[a-zA-Z]’,
• des caractères ‘&’, ‘|’, ‘ (‘ et ‘)’,
• d’espaces.

Il y a 3 types de mots :

• Les opérateurs : ‘&&’ et ‘||’ ,
• Les parenthèses ‘ (‘ et ‘)’,
• Les rôles : ensemble de lettres ‘[a-zA-Z]+’.

La grammaire, de type non contextuelle, est la suivante :

1. S : := Expression
2. Expression : := SubExpression
3.                      | SubExpression ‘&&’ Expression
4.                      | SubExpression ‘||’ Expression
5. SubExpression : := ‘ (‘ Expression ‘)’
6.                              | RoleName
7. RoleName : := [a-zA-Z]

Prenons l’exemple de l’expression ci-dessus pour comprendre comment elle dérive de la grammaire :

Expression
SubExpression && Expression
RoleName      && SubExpression
‘Expert’      && (Expression)
‘Expert’      && (SubExpression || Expression)
…
‘Expert’      && (‘ReadWrite’   || ‘ReadOnly’)

Un peu de code

La première étape est d’extraire les tokens (les différents mots de la chaine). On parcourt la chaine caractère par caractère et on stocke les tokens dans une liste :

List<string> tokens = new List<string>();
StringBuilder sb = new StringBuilder();
 
for (int i = 0; i < text.Length; i++)
{
   char c = text[i];
   switch (c)
   {
   case ' ':
   if (sb.Length == 0)
   continue;
   sb.Append(c);
   break;
   case '(':
   case ')':
   if (sb.Length > 0)
   {
   tokens.Add(sb.ToString());
   sb.Clear();
   }
   tokens.Add(c.ToString(CultureInfo.InvariantCulture));
   break;
   case '&':
   case '|':
   if (sb.Length != 0)
   {
   char prev = sb[sb.Length - 1];
   if (c == prev) // && or ||
   {
   sb.Remove(sb.Length - 1, 1); // remove last char
   tokens.Add(sb.ToString().Trim());
   sb.Clear();
   tokens.Add(c == '&' ? "&&" : "||");
   break;
   }
   }
   sb.Append(c);
   break;
   default:
   sb.Append(c);
   break;
   }
}
 
if (sb.Length > 0)
{
   tokens.Add(sb.ToString());
}

A la fin on se retrouve avec une liste de tokens valides, mais on ne sait pas si ceux-ci ont un sens. Il faut maintenant parcourir ces tokens et vérifier qu’il respecte la grammaire . Pour cela il suffit de transcrire la grammaire en C# :

• Une règle => 1 méthode
• Un ‘|’ => if / else if

static Node Parse(string[] tokens)
{
   int index = 0;
   return ParseExp(tokens, ref index); // Règle 1
}
 
static Node ParseExp(string[] tokens, ref int index)
{
   Node leftExp = ParseSubExp(tokens, ref index); 
   if (index >= tokens.Length) // dernier token : Règle 2
   return leftExp; 
   string token = tokens[index];
   if (token == "&&") // Règle 3
   {
   index++;
   Node rightExp = ParseExp(tokens, ref index);
   return new AndNode(leftExp, rightExp);
   }
   else if (token == "||") // Règle 4
   {
   index++;
   Node rightExp = ParseExp(tokens, ref index);
   return new OrNode(leftExp, rightExp); 
   }
   else
   {
   throw new Exception("Expected '&&' or '||' or EOF");
   }
}
 
static Node ParseSubExp(string[] tokens, ref int index)
{
   string token = tokens[index];
   if (token == "(") // Règle 5
   {
   index++;
   Node node = ParseExp(tokens, ref index);
   if (tokens[index] != ")")
   throw new Exception("Expected ')'");
   index++; // Skip ')'
   return node;
   }
   else
   {
   index++;
   return new RoleNode(token); // Règle 6
   }
}

Le code suit logiquement la grammaire. On commence par le point d’entrée de la grammaire, qui appelle la règle Expression qui appelle la règle SubExpression puis, selon le token, choisi la bonne règle…

Au final on récupère un arbre représentant l’expression origale. On peut donc l’évaluer ce qui était le but.

Le code complet est disponible sur Github : https://gist.github.com/meziantou/10603804.

En 130 lignes de code ‘utiles’ on peut écrire un parser capable de comprendre une expression booléenne (OR, AND, XOR, NOT et priorité). Pour ceux qui en veulent plus :

• Il s’agit d’un parser LL. Ce type de parser est plutôt limité. Pour des besoins plus complexes il en existe d’autres : LALR, LR, GLR.
• Ce parser pourrait être amélioré, par exemple en “streamant” les tokens au lieu de les extraire tous au début. Cela permet de traiter les grandes expressions sans déteriorer les performances.
• Ecrire un parser est fun une ou deux fois pour de petites grammaires. Ensuite vous pouvez regarder des outils tels que ANTLR ou Gold Parser dont le but est de les générer pour vous.

La théorie des langages (THL pour les intimes) est un sujet pationnant. N’hésitez pas à y jeté un oeil à l’occasion ;)