Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Інтерпретатор (англ. Interpreter) — шаблон проєктування, належить до класу шаблонів поведінки.
Призначення
Для заданої мови визначає представлення її граматики, а також інтерпретатор речень цієї мови.
Мотивація
У разі, якщо якась задача виникає досить часто, є сенс подати її конкретні проявлення у вигляді речень простою мовою. Потім можна буде створити інтерпретатор, котрий вирішує задачу, аналізуючи речення цієї мови.
Наприклад, пошук рядків за зразком — досить розповсюджена задача. Регулярні вирази — це стандартна мова для задання зразків пошуку.
Застосування
Шаблон Інтерпретатор слід використовувати, коли є мова для інтерпретації, речення котрої можна подати у вигляді абстрактних синтаксичних дерев. Найкраще шаблон працює коли:
- граматика проста. Для складних граматик ієрархія класів стає занадто громіздкою та некерованою. У таких випадках краще застосовувати генератори синтаксичних аналізаторів, оскільки вони можуть інтерпретувати вирази, не будуючи абстрактних синтаксичних дерев, що заощаджує пам'ять, а можливо і час;
- ефективність не є головним критерієм. Найефективніші інтерпретатори зазвичай не працюють безпосередньо із деревами, а спочатку транслюють їх в іншу форму. Так, регулярний вираз часто перетворюють на скінченний автомат. Але навіть у цьому разі сам транслятор можна реалізувати за допомогою шаблону інтерпретатор.
Структура
- AbstractExpression — абстрактний вираз:
- оголошує абстрактну операцію Interpret, загальну для усіх вузлів у абстрактному синтаксичному дереві;
- TerminalExpression — термінальний вираз:
- реалізує операцію Interpret для термінальних символів граматики;
- необхідний окремий екземпляр для кожного термінального символу у реченні;
- NonterminalExpression — нетермінальний вираз:
- по одному такому класу потребується для кожного граматичного правила;
- зберігає змінні екземпляру типу AbstractExpression для кожного символу;
- реалізує операцію Interpret для нетермінальних символів граматики. Ця операція рекурсивно викликає себе для змінних, зберігаючих символи;
- Context — контекст:
- містить інформацію, глобальну по відношенню до інтерпретатору;
- Client — клієнт:
- будує (або отримує у готовому вигляді) абстрактне синтаксичне дерево, репрезентуюче окреме речення мовою з даною граматикою. Дерево складено з екземплярів класів NonterminalExpression та TerminalExpression;
- викликає операцію Interpret.
Відносини
- клієнт будує (або отримує у готовому вигляді) речення у вигляді абстрактного синтаксичного дерева, у вузлах котрого знаходяться об'єкти класів NonterminalExpression та TerminalExpression. Далі клієнт ініціалізує контекст та викликає операцію Interpret;
- у кожному вузлі виду NonterminalExpression через операції Interpret визначається операція Interpret для кожного підвиразу. Для класу TerminalExpression операція Interpret визначає базу рекурсії;
- операції Interpret у кожному вузлі використовують контекст для зберігання та доступу до стану інтерпретатора.
Переваги
- Граматику стає легко розширювати і змінювати, реалізації класів, що описують вузли абстрактного синтаксичного дерева схожі (легко кодуються). Можна легко змінювати спосіб обчислення виразів.
Недоліки
- Супровід граматики з великим числом правил важко.
- Рідко використовується, через свою специфіку
Реалізація
C++
#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; } } C#
// глобальні дані доступні усім виразам 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 с. — .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Interpretator angl Interpreter shablon proyektuvannya nalezhit do klasu shabloniv povedinki PriznachennyaDlya zadanoyi movi viznachaye predstavlennya yiyi gramatiki a takozh interpretator rechen ciyeyi movi MotivaciyaU razi yaksho yakas zadacha vinikaye dosit chasto ye sens podati yiyi konkretni proyavlennya u viglyadi rechen prostoyu movoyu Potim mozhna bude stvoriti interpretator kotrij virishuye zadachu analizuyuchi rechennya ciyeyi movi Napriklad poshuk ryadkiv za zrazkom dosit rozpovsyudzhena zadacha Regulyarni virazi ce standartna mova dlya zadannya zrazkiv poshuku ZastosuvannyaShablon Interpretator slid vikoristovuvati koli ye mova dlya interpretaciyi rechennya kotroyi mozhna podati u viglyadi abstraktnih sintaksichnih derev Najkrashe shablon pracyuye koli gramatika prosta Dlya skladnih gramatik iyerarhiya klasiv staye zanadto gromizdkoyu ta nekerovanoyu U takih vipadkah krashe zastosovuvati generatori sintaksichnih analizatoriv oskilki voni mozhut interpretuvati virazi ne buduyuchi abstraktnih sintaksichnih derev sho zaoshadzhuye pam yat a mozhlivo i chas efektivnist ne ye golovnim kriteriyem Najefektivnishi interpretatori zazvichaj ne pracyuyut bezposeredno iz derevami a spochatku translyuyut yih v inshu formu Tak regulyarnij viraz chasto peretvoryuyut na skinchennij avtomat Ale navit u comu razi sam translyator mozhna realizuvati za dopomogoyu shablonu interpretator StrukturaUML diagrama sho opisuye strukturu shablonu proyektuvannya Intepretator AbstractExpression abstraktnij viraz ogoloshuye abstraktnu operaciyu Interpret zagalnu dlya usih vuzliv u abstraktnomu sintaksichnomu derevi TerminalExpression terminalnij viraz realizuye operaciyu Interpret dlya terminalnih simvoliv gramatiki neobhidnij okremij ekzemplyar dlya kozhnogo terminalnogo simvolu u rechenni NonterminalExpression neterminalnij viraz po odnomu takomu klasu potrebuyetsya dlya kozhnogo gramatichnogo pravila zberigaye zminni ekzemplyaru tipu AbstractExpression dlya kozhnogo simvolu realizuye operaciyu Interpret dlya neterminalnih simvoliv gramatiki Cya operaciya rekursivno viklikaye sebe dlya zminnih zberigayuchih simvoli Context kontekst mistit informaciyu globalnu po vidnoshennyu do interpretatoru Client kliyent buduye abo otrimuye u gotovomu viglyadi abstraktne sintaksichne derevo reprezentuyuche okreme rechennya movoyu z danoyu gramatikoyu Derevo skladeno z ekzemplyariv klasiv NonterminalExpression ta TerminalExpression viklikaye operaciyu Interpret Vidnosinikliyent buduye abo otrimuye u gotovomu viglyadi rechennya u viglyadi abstraktnogo sintaksichnogo dereva u vuzlah kotrogo znahodyatsya ob yekti klasiv NonterminalExpression ta TerminalExpression Dali kliyent inicializuye kontekst ta viklikaye operaciyu Interpret u kozhnomu vuzli vidu NonterminalExpression cherez operaciyi Interpret viznachayetsya operaciya Interpret dlya kozhnogo pidvirazu Dlya klasu TerminalExpression operaciya Interpret viznachaye bazu rekursiyi operaciyi Interpret u kozhnomu vuzli vikoristovuyut kontekst dlya zberigannya ta dostupu do stanu interpretatora PerevagiGramatiku staye legko rozshiryuvati i zminyuvati realizaciyi klasiv sho opisuyut vuzli abstraktnogo sintaksichnogo dereva shozhi legko koduyutsya Mozhna legko zminyuvati sposib obchislennya viraziv NedolikiSuprovid gramatiki z velikim chislom pravil vazhko Ridko vikoristovuyetsya cherez svoyu specifikuRealizaciyaC Priklad realizaciyi movoyu S include lt iostream gt include lt string gt include lt list gt include lt map gt using namespace std struct Expression virtual int interpret map lt string Expression gt variables 0 virtual Expression class Number public Expression private int number public Number int number this gt number number int interpret map lt string Expression gt 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 lt string Expression gt variables return leftOperand gt interpret variables rightOperand gt interpret variables struct Minus public Expression public Operation Minus Expression left Expression right Operation left right int interpret map lt string Expression gt variables return leftOperand gt interpret variables rightOperand gt interpret variables class Variable public Expression private string name public Variable string name this gt name name int interpret map lt string Expression gt variables if variables end variables find name return 0 return variables name gt interpret variables class Evaluator public Expression private Expression syntaxTree public Evaluator string expression list lt Expression gt 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 lt string Expression gt context return syntaxTree gt interpret context void main polska notaciya Evaluator sentence w x z w x z gt 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 lt 3 i map lt string Expression gt 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 lt string Expression gt iterator it variables begin variables end it it delete it gt second cout lt lt Interpreter result lt lt result lt lt endl C Priklad realizaciyi movoyu S globalni dani dostupni usim virazam class Context private readonly Dictionary lt string object gt variables new Dictionary lt string object gt public void SetVariable string name object value variables name value public object GetVariable string name return variables name bazovij klas dlya viraziv abstract class ExpressionBase public abstract object Interpret Context context ob yektno oriyentovane predstalennya movi 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 gt 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 lt int gt foreach var item in data context SetVariable tempVariableName item var isSatisfied bool conditionExp Interpret context if isSatisfied result Add item return result ToArray ne ye chastinoyu shablonu ta sproshuye pobudovu dereva viraziv class Parser public ExpressionBase Parse string expression var tokens expression Split char null StringSplitOptions RemoveEmptyEntries return ParseNextExpression tokens private ExpressionBase ParseNextExpression IEnumerable lt string gt tokens var token tokens First if IsNumber token return new IntegerExpression int Parse token if token StartsWith amp amp 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 nehaj neobhidno obrahuvati znachennya virazu 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 dinamichna pobudova dereva viraziv var parser new Parser var expressionTree parser Parse expression statichna pobudova dereva viraziv var staticExpressionTree new FilterExpression new SelectExpression new VariableExpression arr new GreaterThanExpression new VariableExpression x new IntegerExpression 2 tempVariableName x obrahunok virazu var context new Context context SetVariable parameterName parameterValue return expressionTree Interpret context as int DzherelaDesign Patterns Elements of Reusable Object Oriented Software 9 listopada 2012 u Wayback Machine Interpreter 22 sichnya 2022 u Wayback Machine Interpreter Design Pattern 22 sichnya 2022 u Wayback Machine LiteraturaAlan Shallouej Dzhejms R Trott Shablony proektirovaniya Novyj podhod k obektno orientirovannomu analizu i proektirovaniyu Design Patterns Explained A New Perspective on Object Oriented Design M Vilyams 2002 288 s ISBN 0 201 71594 5