Інтерпретатор (шаблон проєктування)
Інтерпретатор (англ. Interpreter) — шаблон проєктування, належить до класу шаблонів поведінки.
Для заданої мови визначає представлення її граматики, а також інтерпретатор речень цієї мови.
У разі, якщо якась задача виникає досить часто, є сенс подати її конкретні проявлення у вигляді речень простою мовою. Потім можна буде створити інтерпретатор, котрий вирішує задачу, аналізуючи речення цієї мови.
Наприклад, пошук рядків за зразком — досить розповсюджена задача. Регулярні вирази — це стандартна мова для задання зразків пошуку.
Шаблон Інтерпретатор слід використовувати, коли є мова для інтерпретації, речення котрої можна подати у вигляді абстрактних синтаксичних дерев. Найкраще шаблон працює коли:
- граматика проста. Для складних граматик ієрархія класів стає занадто громіздкою та некерованою. У таких випадках краще застосовувати генератори синтаксичних аналізаторів, оскільки вони можуть інтерпретувати вирази, не будуючи абстрактних синтаксичних дерев, що заощаджує пам'ять, а можливо і час;
- ефективність не є головним критерієм. Найефективніші інтерпретатори зазвичай не працюють безпосередньо із деревами, а спочатку транслюють їх в іншу форму. Так, регулярний вираз часто перетворюють на скінченний автомат. Але навіть у цьому разі сам транслятор можна реалізувати за допомогою шаблону інтерпретатор.
![](http://upload.wikimedia.org/wikipedia/commons/2/21/Interpreter_design_pattern.png)
- AbstractExpression — абстрактний вираз:
- оголошує абстрактну операцію Interpret, загальну для усіх вузлів у абстрактному синтаксичному дереві;
- TerminalExpression — термінальний вираз:
- реалізує операцію Interpret для термінальних символів граматики;
- необхідний окремий екземпляр для кожного термінального символу у реченні;
- NonterminalExpression — нетермінальний вираз:
- по одному такому класу потребується для кожного граматичного правила;
- зберігає змінні екземпляру типу AbstractExpression для кожного символу;
- реалізує операцію Interpret для нетермінальних символів граматики. Ця операція рекурсивно викликає себе для змінних, зберігаючих символи;
- Context — контекст:
- містить інформацію, глобальну по відношенню до інтерпретатору;
- Client — клієнт:
- будує (або отримує у готовому вигляді) абстрактне синтаксичне дерево, репрезентуюче окреме речення мовою з даною граматикою. Дерево складено з екземплярів класів NonterminalExpression та TerminalExpression;
- викликає операцію Interpret.
- клієнт будує (або отримує у готовому вигляді) речення у вигляді абстрактного синтаксичного дерева, у вузлах котрого знаходяться об'єкти класів NonterminalExpression та TerminalExpression. Далі клієнт ініціалізує контекст та викликає операцію Interpret;
- у кожному вузлі виду NonterminalExpression через операції Interpret визначається операція Interpret для кожного підвиразу. Для класу TerminalExpression операція Interpret визначає базу рекурсії;
- операції Interpret у кожному вузлі використовують контекст для зберігання та доступу до стану інтерпретатора.
- Граматику стає легко розширювати і змінювати, реалізації класів, що описують вузли абстрактного синтаксичного дерева схожі (легко кодуються). Можна легко змінювати спосіб обчислення виразів.
- Супровід граматики з великим числом правил важко.
- Рідко використовується, через свою специфіку
#include <iostream>
#include <string>
#include <list>
#include <map>
using namespace std;
struct Expression
{
virtual int interpret(map<string, Expression*> variables) = 0;
virtual ~Expression() {}
};
class Number : public Expression
{
private:
int number;
public:
Number(int number) { this->number = number; }
int interpret(map<string, Expression*> variables) { return number; }
};
class Operation
{
protected:
Expression* leftOperand;
Expression* rightOperand;
public:
Operation(Expression* left, Expression* right)
{
leftOperand = left;
rightOperand = right;
}
~Operation()
{
delete leftOperand;
delete rightOperand;
}
};
struct Plus : public Expression, public Operation
{
Plus(Expression* left, Expression* right) :Operation(left, right) {}
int interpret(map<string, Expression*> variables)
{
return leftOperand->interpret(variables) + rightOperand->interpret(variables);
}
};
struct Minus : public Expression, public Operation
{
Minus(Expression* left, Expression* right) :Operation(left, right) {}
int interpret(map<string, Expression*> variables)
{
return leftOperand->interpret(variables) - rightOperand->interpret(variables);
}
};
class Variable : public Expression
{
private:
string name;
public:
Variable(string name) { this->name = name; }
int interpret(map<string, Expression*> variables)
{
if (variables.end() == variables.find(name)) return 0;
return variables[name]->interpret(variables);
}
};
class Evaluator : public Expression
{
private:
Expression* syntaxTree;
public:
Evaluator(string expression)
{
list<Expression*> expressionStack;
size_t last = 0;
for (size_t next = 0; last != string::npos; last = (string::npos == next) ? next : (1 + next))
{
next = expression.find(' ', last);
string token(expression.substr(last, (string::npos == next) ?
(expression.length() - last) : (next - last)));
if (token == "+")
{
Expression* right = expressionStack.back();
expressionStack.pop_back();
Expression* left = expressionStack.back();
expressionStack.pop_back();
Expression* subExpression = new Plus(right, left);
expressionStack.push_back(subExpression);
}
else if (token == "-")
{
Expression* right = expressionStack.back();
expressionStack.pop_back();
Expression* left = expressionStack.back();
expressionStack.pop_back();
Expression* subExpression = new Minus(left, right);
expressionStack.push_back(subExpression);
}
else
{
expressionStack.push_back(new Variable(token));
}
}
syntaxTree = expressionStack.back();
expressionStack.pop_back();
}
~Evaluator()
{
delete syntaxTree;
}
int interpret(map<string, Expression*> context)
{
return syntaxTree->interpret(context);
}
};
void main()
{
// польська нотація
Evaluator sentence("w x z - +");// w x z - + => w + x - z
static const int sequences[][3] =
{
{ 5, 10, 42 },// 5 + 10 - 42
{ 1, 3, 2 },// 1 + 3 - 2
{ 7, 9, -5 },// 7 + 9 - -5
};
for (size_t i = 0; i < 3; ++i)
{
map<string, Expression*> variables;
variables["w"] = new Number(sequences[i][0]);
variables["x"] = new Number(sequences[i][1]);
variables["z"] = new Number(sequences[i][2]);
int result = sentence.interpret(variables);
for (map<string, Expression*>::iterator it = variables.begin(); variables.end() != it; ++it)
delete it->second;
cout << "Interpreter result: " << result << endl;
}
}
// глобальні дані доступні усім виразам
class Context
{
private readonly Dictionary<string, object> _variables = new Dictionary<string, object>();
public void SetVariable(string name, object value)
{
_variables[name] = value;
}
public object GetVariable(string name)
{
return _variables[name];
}
}
// базовий клас для виразів
abstract class ExpressionBase
{
public abstract object Interpret(Context context);
}
// об'єктно орієнтоване предсталення мови
class IntegerExpression : ExpressionBase
{
private int _value;
public IntegerExpression(int value)
{
_value = value;
}
public override object Interpret(Context context)
{
return _value;
}
}
class VariableExpression : ExpressionBase
{
private readonly string _name;
public VariableExpression(string name)
{
_name = name;
}
public override object Interpret(Context context)
{
return context.GetVariable(_name);
}
}
class GreaterThanExpression : ExpressionBase
{
private readonly VariableExpression _variableExp;
private readonly IntegerExpression _integerExp;
public GreaterThanExpression(VariableExpression variableExp, IntegerExpression integerExp)
{
_variableExp = variableExp;
_integerExp = integerExp;
}
public override object Interpret(Context context)
{
var variable = (int)_variableExp.Interpret(context);
var number = (int)_integerExp.Interpret(context);
return variable > number;
}
}
class SelectExpression : ExpressionBase
{
private readonly ExpressionBase _dataExp;
public SelectExpression(ExpressionBase dataExp)
{
_dataExp = dataExp;
}
public override object Interpret(Context context)
{
if (_dataExp is IntegerExpression intExp)
{
var value = (int)intExp.Interpret(context);
return new int[] { value };
}
if (_dataExp is VariableExpression varExp)
{
return varExp.Interpret(context) as int[];
}
throw new InvalidOperationException("Invalid value type for Select expression");
}
}
class FilterExpression : ExpressionBase
{
private readonly ExpressionBase _dataExp;
private readonly ExpressionBase _conditionExp;
private readonly string _tempVariableName;
public FilterExpression(ExpressionBase dataExp, ExpressionBase conditionExp, string tempVariableName)
{
_dataExp = dataExp;
_conditionExp = conditionExp;
_tempVariableName = tempVariableName;
}
public override object Interpret(Context context)
{
var data = _dataExp.Interpret(context) as int[];
var result = new List<int>();
foreach (var item in data)
{
context.SetVariable(_tempVariableName, item);
var isSatisfied = (bool)_conditionExp.Interpret(context);
if (isSatisfied)
{
result.Add(item);
}
}
return result.ToArray();
}
}
// не є частиною шаблону, та спрощує побудову дерева виразів
class Parser
{
public ExpressionBase Parse(string expression)
{
var tokens = expression.Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
return ParseNextExpression(tokens);
}
private ExpressionBase ParseNextExpression(IEnumerable<string> tokens)
{
var token = tokens.First();
if (IsNumber(token))
{
return new IntegerExpression(int.Parse(token));
}
if (token.StartsWith("{") && token.EndsWith("}"))
{
var variableName = token.Trim(new char[] { '{', '}' });
return new VariableExpression(variableName);
}
if (token == "greater")
{
var variableExp = ParseNextExpression(tokens.Skip(1)) as VariableExpression;
var integerExp = ParseNextExpression(tokens.Skip(3)) as IntegerExpression;
return new GreaterThanExpression(variableExp, integerExp);
}
if (token == "select")
{
ExpressionBase exp = ParseNextExpression(tokens.Skip(1));
return new SelectExpression(exp);
}
if (token == "filter")
{
ExpressionBase dataExp = ParseNextExpression(tokens.Skip(2));
ExpressionBase conditionExp = ParseNextExpression(tokens.Skip(4));
string tempVariableName = tokens.ElementAt(6).Trim(new char[] { '{', '}' });
return new FilterExpression(dataExp, conditionExp, tempVariableName);
}
if (token == "|")
{
return ParseNextExpression(tokens.Skip(1));
}
if (token == "than")
{
return ParseNextExpression(tokens.Skip(1));
}
throw new InvalidOperationException($"Invalid token {token}");
}
private bool IsNumber(string token)
{
return int.TryParse(token, out int _);
}
}
class Program
{
public static void Main()
{
// нехай необхідно обрахувати значення виразу
var expression = @"
filter
| select {arr}
| greater {x} than 2";
var parameter = "arr";
var parameterValue = new int[] { 1, 2, 3, 4, 5 };
var result = Evaluate(expression, parameter, parameterValue);
result.ToList().ForEach(Console.WriteLine);
}
public static int[] Evaluate(string expression, string parameterName, object parameterValue)
{
// динамічна побудова дерева виразів
var parser = new Parser();
var expressionTree = parser.Parse(expression);
// статична побудова дерева виразів
var staticExpressionTree = new FilterExpression(
new SelectExpression(new VariableExpression("arr")),
new GreaterThanExpression(new VariableExpression("x"), new IntegerExpression(2)),
tempVariableName: "x");
// обрахунок виразу
var context = new Context();
context.SetVariable(parameterName, parameterValue);
return expressionTree.Interpret(context) as int[];
}
}
- Design Patterns: Elements of Reusable Object-Oriented Software [Архівовано 9 листопада 2012 у Wayback Machine.]
- Interpreter [Архівовано 22 січня 2022 у Wayback Machine.]
- Interpreter Design Pattern [Архівовано 22 січня 2022 у Wayback Machine.]
Алан Шаллоуей, Джеймс Р. Тротт. Шаблоны проектирования. Новый подход к объектно-ориентированному анализу и проектированию = Design Patterns Explained: A New Perspective on Object-Oriented Design. — М. : «Вильямс», 2002. — 288 с. — ISBN 0-201-71594-5.