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 :
- Ecriture de la grammaire
- Génération des tables d’analyse à l’aide du Builder
- 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 :
- Instancier le moteur d’analyse
- Charger les tables d’analyse générées à partir de la grammaire
- Lire le fichier à analyser
- 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