Dans un article précédent, je vous détaillais ma réponse à une question de StackOverflow pour laquelle j’avais écrit un parser d’expression booléenne. A la fin de l’article j’indiquais qu’il était préférable de générer les parsers avec des outils tels qu’ANTLR ou GoldParser. Dans cet article nous allons voir comment utiliser ce dernier.

GOLD is a free parsing system that you can use to develop your own programming languages, scripting languages and interpreters. It strives to be a development tool that can be used with numerous programming languages and on multiple platforms.

La façon dont Gold fonctionne est la suivante :

1. Ecriture de la grammaire
2. Génération des tables d’analyse à l’aide du Builder
3. A l’exécution ces tables sont lues par le moteur choisi et on peut commencer à analyser des fichiers. Il existe différents moteurs pour prendre en charge différents langages / plateformes.

Création de la grammaire

Afin de créer et tester la grammaire j’ai utilisé GOLD Parser Builder.

La grammaire commence par un préambule la décrivant :

"Name"      = 'Boolean Language'     
"Author"    = 'Meziantou'     
"Version"   = '1.0'     
"About"     = 'Boolean Language'     
"Character Mapping" = 'Unicode'     
"Case Sensitive"    = False     
"Start Symbol" = <expression>

On défnit ensuite le format des commentaires (si la grammaire en contient) :

Comment Start = '/*'     
Comment End   = '*/'     
Comment Line  = '--'

Puis on définit les symbôles terminaux. Les symbôles terminaux sont des symbôles tels que des nombres entiers, des nombres réels, des chaines de caractères, des dates, etc.

{Id Ch Standard} = {Alphanumeric} + [_] + [.]     
{Id Ch Extended} = {Printable} + {Letter Extended} - ['['] - [']']    
! Examples: Test; [A B]    
Identifier = {Id Ch Standard}+ | '['{Id Ch Extended}+']'     
Boolean = 'true' | 'false'

Pour finir, on définit les règles au format Backus-Naur Form (BNF) :

<expression> ::= <andExpression>     
   | <orExpression>     
   | <xorExpression>     
   | <subExpression>    
<andExpression> ::= <expression> '&&' <subExpression>     
   | <expression> 'and' <subExpression>    
<orExpression>  ::= <expression> '||' <subExpression>     
   | <expression> 'or' <subExpression>    
<xorExpression> ::= <expression> '^' <subExpression>     
   | <expression> 'xor' <subExpression>    
<subExpression> ::= <parentheseExpression>     
   | <notExpression>     
   | <value>    
<parentheseExpression> ::= '(' <expression> ')'    
<notExpression> ::= '!' <subExpression>    
<value> ::= Boolean     
   | Identifier

La grammaire étant terminée, on peut maintenant générer les tables. L’interface est claire : cliquez sur “next” jusqu’à ce qu’on vous propose de sauvegarder le fichier généré.

Il est ensuite possible de tester la grammaire directement dans l’outil (menu Test)  :

Un peu de code

Avant toute chose il faut télécharger le moteur pour .NET : http://goldparser.org/engine/5/net/index.htm.

Le code dans les grandes lignes se décompose en trois étapes :

1. Instancier le moteur d’analyse
2. Charger les tables d’analyse générées à partir de la grammaire
3. Lire le fichier à analyser
4. Créer un objet pour chaque règle de la grammaire (étape Reduction). Par exemple pour la règle <orExpression> on crée un objet OrExpression contenant l’expression de gauche et l’expression de droite. A la fin de l’analyse (étape Accept) on peut récupérer le dernier objet ainsi créé. Celui-ci représente un arbre correspondant à l’expression analysée. Par exemple pour le texte “[Expert] && ([ReadWrite] || [ReadOnly])” l’arbre créé sera :

// Instancie le parser et charge le fichier egt    
Parser parser = new Parser();     
using (BinaryReader grammar = GetGrammar())     
{     
   parser.LoadTables(grammar);     
}    
using (TextReader textReader = new StringReader("true || false"))     
{     
   parser.Open(textReader);     
   parser.TrimReductions = true;    
   while (true)     
   {    
   // Boucle permettant de traiter le texte à analyser     
   // Les 4 messages intéressants sont:     
   //   Reduction : Une règle de la grammaire vient d'être trouvée => on peut créer un objet représentant son contenu     
   //   Accept : fin de l'analyse => On peut récupérer le résultat     
   //   LexicalError et SyntaxError : Le texte à analyser n'est pas valide     
   ParseMessage response = parser.Parse();     
   switch (response)     
   {    
   case ParseMessage.TokenRead:     
   Trace.WriteLine("Token: " + parser.CurrentToken.Parent.Name);     
   break;    
   case ParseMessage.Reduction:     
   parser.CurrentReduction = CreateNewObject(parser.CurrentReduction as Reduction);     
   break;    
   case ParseMessage.Accept: // Fin de l'analyse     
   Expression result = parser.CurrentReduction as Expression;     
   if (result != null)     
   {     
   Console.WriteLine(result.DisplayName);     
   }     
   return;     
   case ParseMessage.LexicalError:     
   Console.WriteLine("Lexical Error. Line {0}, Column {1}. Token {2} was not expected.",     
   parser.CurrentPosition.Line,     
   parser.CurrentPosition.Column,     
   parser.CurrentToken.Data);     
   return;     
   case ParseMessage.SyntaxError:     
   StringBuilder expecting = new StringBuilder();     
   foreach (Symbol tokenSymbol in parser.ExpectedSymbols)     
   {     
   expecting.Append(' ');     
   expecting.Append(tokenSymbol);     
   }     
   Console.WriteLine("Syntax Error. Line {0}, Column {1}. Expecting: {2}.",     
   parser.CurrentPosition.Line,     
   parser.CurrentPosition.Column,     
   expecting);     
   return;     
   case ParseMessage.InternalError:     
   case ParseMessage.NotLoadedError:     
   case ParseMessage.GroupError:     
   return;     
   }     
   }     
}    
    
    
static object CreateNewObject(Reduction r)     
{     
   string ruleName = r.Parent.Head.Name;     
   Trace.WriteLine("Reduce: " + ruleName);    
   if (ruleName == "orExpression")     
   {     
   var left = r.GetData(0) as Expression;     
   var right = r.GetData(2) as Expression;     
   return new OrExpression(left, right);     
   }     
   else if (ruleName == "andExpression")     
   {     
   var left = r.GetData(0) as Expression;     
   var right = r.GetData(2) as Expression;     
   return new AndExpression(left, right);     
   }    
   /// ...    
   else if (ruleName == "value")     
   {     
   var value = r.GetData(0) as string;     
   if (value != null)     
   {     
   value = value.Trim();     
   bool boolean;     
   if (bool.TryParse(value, out boolean))     
   {     
   return new BooleanValueExpression(boolean);     
   }    
   return new RoleNameExpression(value);     
   }     
   }    
   return null;     
}

Le code complet est disponible sur GitHub : https://github.com/meziantou/GoldParser-Engine