Design Pattern Interpreter
Représenter et interpréter la grammaire d’un langage
Introduction
Le design pattern Interpreter est un pattern de conception comportemental dont l’objectif est de représenter la grammaire d’un langage sous la forme d’un ensemble de classes, puis d’interpréter des expressions écrites dans ce langage. Chaque règle de la grammaire est représentée par une classe dédiée. Ces classes peuvent être combinées afin de construire des expressions plus complexes. L’interprétation consiste à parcourir cette structure d’objets afin d’évaluer l’expression représentée.
Le design pattern Interpreter est adapté aux langages dont la grammaire est relativement simple. Il peut par exemple être utilisé pour interpréter des expressions arithmétiques, des expressions logiques, des règles métier, des filtres ou encore de petits langages spécifiques à un domaine (Domain-Specific Language, DSL).
Problématique
Nous devons développer une application capable d’évaluer des expressions arithmétiques simples, composées de nombres, d’additions et de soustractions :
Une première solution pourrait consister à analyser directement la chaîne de caractères reçue, à identifier les opérateurs, puis à effectuer les opérations correspondantes. Avec seulement quelques règles, cette approche reste relativement simple. Mais si notre langage évolue et que nous souhaitons ajouter progressivement de nouveaux opérateurs, des parenthèses ou d’autres types d’expressions, le code chargé d’analyser et d’évaluer les expressions risque de devenir de plus en plus complexe.
Une expression peut être un nombre, une addition ou une soustraction de deux expressions. Nous devons disposer d’une solution permettant de représenter explicitement ces différentes règles, et de faire évoluer notre langage, sans centraliser toute la logique d’interprétation dans une seule classe. Le design pattern Interpreter répond à cette problématique en représentant chaque règle de la grammaire par une classe.
Diagramme de classes
L’implémentation du design pattern Interpreter peut être représentée avec le diagramme de classes suivant :
L’interface IExpression représente l’abstraction commune permettant d’interpréter une expression. La classe NumberExpression représente une expression terminale. Les classes AddExpression et SubtractExpression représentent des expressions non terminales composées d’autres expressions. Cette organisation permet de construire un arbre d’objets représentant une expression complète.
Fonctionnement
Le design pattern Interpreter consiste à définir une représentation objet des différentes règles constituant la grammaire d’un langage. Les différentes règles de la grammaire sont représentées par des classes implémentant cette interface. Deux catégories d’expressions peuvent être distinguées :
-
Les expressions terminales, qui représentent les éléments élémentaires du langage. Elles ne contiennent pas d’autres expressions. Dans notre exemple, il s'agit d'un nombre.
-
Les expressions non terminales, qui représentent des règles composées à partir d’autres expressions. Une addition ou une soustraction en sont des exemples.
L’expression 10 + 5 - 2 peut ainsi être représentée sous la forme d’un arbre :
Chaque nœud de cet arbre est représenté par un objet. L’interprétation de l’expression complète est obtenue, en demandant récursivement à chaque objet d’interpréter la partie de l’expression dont il est responsable.
Implémentation en C#
Nous commençons par coder l’interface commune à toutes les expressions :
La méthode Interpret est l’opération qui permet d’interpréter une expression.
Implémenter une expression terminale
Nous représentons les nombres utilisés dans nos expressions :
public class NumberExpression : IExpression
{
private readonly int _value;
public NumberExpression(int value)
{
_value = value;
}
public int Interpret()
{
return _value;
}
}
La classe NumberExpression constitue une expression terminale. Elle représente l’un des éléments les plus simples de notre langage. Son interprétation consiste à retourner la valeur qu’elle contient. Par exemple, nous pouvons représenter le nombre 10 de la manière suivante :
Le résultat de l'interprétation est 10.
Implémenter une expression non terminale
Nous souhaitons maintenant représenter une addition, constituée de deux expressions : une expression située à gauche de l’opérateur et une autre située à droite. Nous implémentons la classe AddExpression :
public class AddExpression : IExpression
{
private readonly IExpression _leftExpression;
private readonly IExpression _rightExpression;
public AddExpression(IExpression leftExpression, IExpression rightExpression)
{
_leftExpression = leftExpression;
_rightExpression = rightExpression;
}
public int Interpret()
=> _leftExpression.Interpret() + _rightExpression.Interpret();
}
Contrairement à la classe NumberExpression, la classe AddExpression constitue une expression non terminale, car elle est composée d’autres expressions. Cette classe ne dépend pas directement de la classe NumberExpression : elle utilise l’interface IExpression. Les expressions peuvent donc elles-mêmes être des nombres, des additions, des soustractions ou n’importe quelle autre expression que nous ajouterons ultérieurement à notre langage.
Nous pouvons maintenant implémenter l’expression 10 + 5 avec le code :
IExpression expression = new AddExpression(
new NumberExpression(10),
new NumberExpression(5));
Console.WriteLine(expression.Interpret());
Le résultat de l'interprétation est 15.
Ajouter une nouvelle règle à la grammaire
Notre langage doit également prendre en charge la soustraction. Nous ajoutons cette nouvelle règle en implémentant une nouvelle classe qui implémente l'interface IExpression :
public class SubtractExpression : IExpression
{
private readonly IExpression _leftExpression;
private readonly IExpression _rightExpression;
public SubtractExpression(IExpression leftExpression, IExpression rightExpression)
{
_leftExpression = leftExpression;
_rightExpression = rightExpression;
}
public int Interpret()
=> _leftExpression.Interpret() - _rightExpression.Interpret();
}
De même que pour l’addition, la soustraction contient deux expressions et délègue leur évaluation à leur méthode Interpret. Nous pouvons maintenant représenter l'expression 10 - 3 avec le code :
IExpression expression = new SubtractExpression(
new NumberExpression(10),
new NumberExpression(3));
Console.WriteLine(expression.Interpret());
Le résultat est 7. L’ajout de cette nouvelle règle n’a nécessité aucune modification des classes NumberExpression et AddExpression.
Composer plusieurs expressions
L’un des intérêts du design pattern Interpreter est la possibilité de composer les expressions. Nous pouvons représenter l'expression 10 + 5 - 2 avec le code :
IExpression expression = new SubtractExpression(
new AddExpression(
new NumberExpression(10),
new NumberExpression(5)),
new NumberExpression(2));
Console.WriteLine(expression.Interpret());
La méthode Interpret de l’objet de type SubtractExpression demande à son expression de gauche, une instance de la classe AddExpression, de s’interpréter. Celle-ci évalue à son tour ses deux instances de la classe NumberExpression. L’addition donne la valeur 15, à laquelle l’expression principale soustrait 2 pour obtenir 13 comme résultat final.
Construire les expressions à partir d’un langage
Dans les exemples précédents, nous avons directement construit notre arbre d’objets :
new SubtractExpression(
new AddExpression(
new NumberExpression(10),
new NumberExpression(5)),
new NumberExpression(2));
Cependant, dans une application réelle, l’expression sera généralement fournie sous une forme textuelle telle que 0 + 5 - 2. Il est alors nécessaire d'analyser cette chaîne de caractères afin de construire les objets correspondants.
Cette responsabilité peut être confiée à un parseur, qui analyse les différents éléments de l’expression, et construit l’arbre syntaxique correspondant. Le design pattern Interpreter intervient ensuite pour interpréter cet arbre.
Utiliser un contexte d’interprétation
Dans notre exemple, chaque expression contient toutes les informations nécessaires à son interprétation. Toutefois, certaines valeurs peuvent n’être connues qu’au moment de l'interprétation. Un contexte d’interprétation peut alors être transmis aux expressions.
Nous souhaitons, par exemple, interpréter l’expression x + 5, dans laquelle la valeur de x est fournie par le contexte :
public class InterpretationContext
{
private readonly Dictionary<string, int> _variables = [];
public void SetVariable(string name, int value)
=> _variables[name] = value;
public int GetVariable(string name)
=> _variables.TryGetValue(name, out int value)
? value
: throw new InvalidOperationException(
$"La variable '{name}' n'est pas définie.");
}
La méthode Interpret prend en paramètre ce contexte :
Toutes les classes implémentant l'interface IExpression doivent désormais prendre en paramètre ce contexte. Les expressions qui n’en ont pas besoin, comme NumberExpression, peuvent ne pas l'utiliser.
Voici une nouvelle expression terminale qui permet de représenter une variable, dont la valeur provient du contexte :
public class VariableExpression : IExpression
{
private readonly string _name;
public VariableExpression(string name)
{
_name = name;
}
public int Interpret(InterpretationContext context)
=> context.GetVariable(_name);
}
Les expressions non terminales transmettent récursivement le même contexte aux expressions qu’elles contiennent :
public int Interpret(InterpretationContext context)
=> _leftExpression.Interpret(context)
+ _rightExpression.Interpret(context);
L’expression x + 5 peut alors être implémentée ainsi :
IExpression expression = new AddExpression(
new VariableExpression("x"),
new NumberExpression(5));
var context = new InterpretationContext();
context.SetVariable("x", 10);
Console.WriteLine(expression.Interpret(context));
Le contexte sépare ainsi la structure de l’expression des données utilisées pour une interprétation particulière. Le même arbre d’expressions peut être réutilisé avec plusieurs contextes contenant des valeurs différentes.
Avantages
Le design pattern Interpreter permet de représenter les différentes règles d’une grammaire. Chaque règle possède sa propre classe et sa propre logique d’interprétation, ce qui évite de concentrer toutes les règles dans une méthode contenant de nombreuses conditions.
Aussi, il facilite l’ajout de nouvelles règles. Dans notre exemple, la soustraction a pu être ajoutée en créant une nouvelle classe implémentant l'interface IExpression, sans modifier les classes représentant les nombres ou les additions.
Design patterns Interpreter et Composite
La structure utilisée par le design pattern Interpreter est proche de celle du design pattern Composite. Les expressions forment un arbre dans lequel les feuilles représentent les expressions terminales, tandis que les nœuds composites représentent les expressions non terminales, constituées d’autres expressions.
La différence réside principalement dans leur intention. Le design pattern Composite permet de manipuler uniformément des objets individuels et des compositions d’objets. Avec le pattern Interpreter, les classes représentent les règles de la grammaire d’un langage, tandis que l’arbre représente une expression construite conformément à cette grammaire. Cet arbre est ensuite parcouru récursivement afin d’interpréter l’expression et d’en obtenir le résultat.