Інтерпретатор (шаблон проєктування) — Вікіпедія
Інтерпретатор (англ. Interpreter) — шаблон проєктування, належить до класу шаблонів поведінки.
Для заданої мови визначає представлення її граматики, а також інтерпретатор речень цієї мови.
У разі, якщо якась задача виникає досить часто, є сенс подати її конкретні проявлення у вигляді речень простою мовою. Потім можна буде створити інтерпретатор, котрий вирішує задачу, аналізуючи речення цієї мови.
Наприклад, пошук рядків за зразком — досить розповсюджена задача. Регулярні вирази — це стандартна мова для задання зразків пошуку.
Шаблон Інтерпретатор слід використовувати, коли є мова для інтерпретації, речення котрої можна подати у вигляді абстрактних синтаксичних дерев. Найкраще шаблон працює коли:
- граматика проста. Для складних граматик ієрархія класів стає занадто громіздкою та некерованою. У таких випадках краще застосовувати генератори синтаксичних аналізаторів, оскільки вони можуть інтерпретувати вирази, не будуючи абстрактних синтаксичних дерев, що заощаджує пам'ять, а можливо і час;
- ефективність не є головним критерієм. Найефективніші інтерпретатори зазвичай не працюють безпосередньо із деревами, а спочатку транслюють їх в іншу форму. Так, регулярний вираз часто перетворюють на скінченний автомат. Але навіть у цьому разі сам транслятор можна реалізувати за допомогою шаблону інтерпретатор.
- 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.