Інтерпретатор (шаблон проєктування)

Інтерпретатор (англ. Interpreter) — шаблон проєктування, належить до класу шаблонів поведінки.

Призначення

Для заданої мови визначає представлення її граматики, а також інтерпретатор речень цієї мови.

Мотивація

У разі, якщо якась задача виникає досить часто, є сенс подати її конкретні проявлення у вигляді речень простою мовою. Потім можна буде створити інтерпретатор, котрий вирішує задачу, аналізуючи речення цієї мови.

Наприклад, пошук рядків за зразком — досить розповсюджена задача. Регулярні вирази — це стандартна мова для задання зразків пошуку.

Застосування

Шаблон Інтерпретатор слід використовувати, коли є мова для інтерпретації, речення котрої можна подати у вигляді абстрактних синтаксичних дерев. Найкраще шаблон працює коли:

• граматика проста. Для складних граматик ієрархія класів стає занадто громіздкою та некерованою. У таких випадках краще застосовувати генератори синтаксичних аналізаторів, оскільки вони можуть інтерпретувати вирази, не будуючи абстрактних синтаксичних дерев, що заощаджує пам'ять, а можливо і час;
• ефективність не є головним критерієм. Найефективніші інтерпретатори зазвичай не працюють безпосередньо із деревами, а спочатку транслюють їх в іншу форму. Так, регулярний вираз часто перетворюють на скінченний автомат. Але навіть у цьому разі сам транслятор можна реалізувати за допомогою шаблону інтерпретатор.

Структура

UML діаграма, що описує структуру шаблону проєктування Інтепретатор

• 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 с. — ISBN 0-201-71594-5.