Интерпретатор - паттерн поведения объектов, реализующий динамические алгоритмы с помощью декларативного описания.

• LiteralExpression проверяет, соответствует ли входная строка литералу, который хранится в объекте подкласса.
• AlternationExpression проверяет, соответствует ли строка одной из альтернатив.
• RepetitionExpression проверяет, если в строке повторяющиеся вхождения выражения, совпадающего с тем, что хранится в объекте.

И так далее.

Очевидно, что все это выполняется рекурсивно, теоретически без ограничения глубины вложенности разных выражений друг в друга.

• Грамматика достаточно проста.
  Для сложных грамматик иерархия классов становится слишком громоздкой и неуправляемой. В таких случаях лучше применять генераторы синтаксических анализаторов, поскольку они могут интерпретировать выражения, не строя абстрактных синтаксических деревьев, что экономит память, а возможно, и время.
• Эффективность не является главным критерием.
  Наиболее эффективные интерпретаторы обычно не работают непосредственно с деревьями, а сначала транслируют их в другую форму. Так, регулярное выражение часто преобразуют в конечный автомат. Но даже в этом случае сам транслятор можно реализовать с помощью данного паттерна интерпретатор.

Решение

Участники паттерна Интерпретатор (Interpreter)

1. AbstractExpression (RegularExpression) - абстрактное выражение.
   Объявляет абстрактную операцию Interpret, общую для всех узлов в абстрактном синтаксическом дереве.
2. TerminalExpression (LiteralExpression) – терминальное (конечное, неделимое, элементарное) выражение.
   Реализует операцию Interpret для терминальных символов грамматики. Для каждого терминального символа – необходим отдельный экземпляр в предложении.
3. NonterminalExpression (AlternationExpression,RepetitionExpression, SequenceExpressions) - нетерминальное выражение.
   По одному такому классу требуется для каждого грамматического правила:
   R :: = Rl R2... Rn.
   Хранит переменные экземпляра типа AbstractExpression для каждого символа от Rl до Rn. Реализует операцию Interpret для нетерминальных символов грамматики. Эта операция рекурсивно вызывает себя же для переменных, представляющих Rl R2... Rn.
4. Context – контекст.
   Содержит информацию, глобальную по отношению к интерпретатору.
5. Client – клиент.
   Строит (или получает в готовом виде) абстрактное синтаксическое дерево, представляющее отдельное предложение на языке с данной грамматикой. Дерево составлено из экземпляров классов Nonterminal-Expression.Вызывает операцию Interpret и Terminal-Expression.

Операции Interpret в каждом узле используют контекст для сохранения и доступа к состоянию интерпретатора.

1. Создание абстрактного синтаксического дерева.
   Паттерн интерпретатор не поясняет, как создавать дерево, то есть разбор выражения не входит в его задачу. Создать дерево разбора может таблично-управляемый или написанный вручную (обычно методом рекурсивного спуска) анализатор, а также сам клиент.
2. Определение операции Interpret.
   Определять операцию Interpret в классах выражений необязательно. Если создавать новые интерпретаторы приходится часто, то лучше воспользоваться паттерном посетитель и поместить операцию Interpret в отдельный объект-посетитель. Например, для грамматики языка программирования будет нужно определить много операций над абстрактными синтаксическими деревьями: проверку типов, оптимизацию, генерацию кода и т.д. Лучше, конечно, использовать посетителя и не определять эти операции в каждом классе грамматики.
3. Разделение терминальных символов с помощью паттерна приспособленец.
   Для грамматик, предложения которых содержат много вхождений одного и того же терминального символа, может оказаться полезным разделение этого символа, т.е. совместное его использование. Хорошим примером служат грамматики компьютерных программ, поскольку в них каждая переменная встречается в коде многократно. В примере из раздела Мотивация терминальный символ dog (для моделирования которого используется класс LiteralExpression) может попадаться много раз.
   В терминальных узлах обычно не хранится информация о положении в абстрактном синтаксическом дереве. Необходимый для интерпретации контекст предоставляют им родительские узлы. Налицо различие между разделяемым (внутренним) и передаваемым (внешним) состояниями, так что вполне применим паттерн приспособленец.
   Например, каждый экземпляр класса LiteralExpression для dog получает контекст, состоящий из уже просмотренной части строки. И каждый такой экземпляр делает в своей операции Interpret одно и то же - проверяет, содержит ли остаток входной строки слово dog, - безотносительно к тому, в каком месте дерева этот экземпляр встречается.

1. Грамматику легко изменять и расширять.
   Поскольку для представления грамматических правил в паттерне используются классы, то для изменения - или расширения грамматики можно применять наследование. Существующие выражения можно модифицировать постепенно, а новые определять как вариации старых (компоновка, агрегация старых).
2. Простая реализация грамматики.
   Реализации классов, описывающих узлы абстрактного синтаксического дерева, похожи. Такие классы легко кодировать, а зачастую их может автоматически сгенерировать компилятор или генератор синтаксических анализаторов.

1. Сложные грамматики трудно сопровождать.
   В паттерне интерпретатор определяется по меньшей мере один класс для каждого правила грамматики (для правил, определенных с помощью формы Бэкуса-Наура – BNF, может понадобиться и более одного класса). Поэтому сопровождение грамматики с большим числом правил иногда оказывается трудной задачей. Для ее решения могут быть применены другие паттерны. Но если грамматика очень сложна, лучше прибегнуть к другим методам, например, воспользоваться генератором компиляторов или синтаксических анализаторов.
2. Добавление новых способов интерпретации выражений.
   Паттерн интерпретатор позволяет легко изменить способ вычисления выражений. Например, реализовать красивую печать выражения вместо проверки входящих в него типов можно, просто определив новую функциональность операции Interpret в классах выражений.
   Ну а если вам приходится часто создавать новые способы интерпретации выражений, подумайте о применении паттерна посетитель. Это поможет избежать изменения классов, описывающих грамматику.

Пример

Рассмотрим систему для манипулирования и вычисления булевых выражений. Терминальными символами (TerminalExpression-ы) в этом языке являются булевы переменные, то есть константы true и false. Нетерминальные символы (NonterminalExpression) представляют выражения, содержащие операторы and, or и not. Приведем определение грамматики (упрощая задачу, мы здесь игнорируем приоритеты выполнения операторов и предполагаем, что их учет возложен на объект, строящий дерево разбора):

Здесь мы подробно опишем только классы BooleanExp, VariableExp и AndExp. Классы OrExp и NotExp аналогичны классу AndExp. Класс Constant представляет булевы константы: Constant.

Известные применения паттерна Интерпретатор (Interpreter)

Паттерн интерпретатор широко используется в компиляторах, реализованных с помощью объектно-ориентированных языков, например в компиляторах Smalltalk. В языке SPECTalk этот паттерн применяется для интерпретации форматов входных файлов. В библиотеке QOCA для разрешения ограничений он применяется для вычисления ограничений.

Но применять паттерн интерпретатор лучше в тех случаях, когда иерархию классов можно представлять себе как описание языка на декларативном.

Родственные паттерны

Посетителя можно использовать для инкапсуляции в одном классе поведения каждого узла абстрактного синтаксического дерева.

package interpreter;
 
public class Constant implements BooleanExp {
	private boolean constant;
 
	public Constant(boolean constant) {
		super();
		this.constant = constant;
	}
 
	public BooleanExp Copy() {
		return new Constant(this.constant);
	}
 
	public boolean Evaluate(Context c) {
		return this.constant;
	}
 
	public BooleanExp Replace(String str, BooleanExp exp) {
		return Copy();
	}
 
}

package interpreter;
 
public interface BooleanExp {
	boolean Evaluate(Context c);
 
	BooleanExp Replace(String str, BooleanExp exp);
 
	BooleanExp Copy();
}

package interpreter;
 
import java.util.HashMap;
import java.util.Map;
 
public class Context {
	Map<String, Boolean> vars = new HashMap<String, Boolean>();
 
	boolean Lookup(String name) {
		if (vars.get(name) == null) return false;
		return vars.get(name).booleanValue();
 
	}
	void Assign(VariableExp exp, boolean val) {
		vars.put(exp.getName(), val);
	}
}

package interpreter;
 
public class VariableExp implements BooleanExp {
	private String name;
 
	public VariableExp(String name) {
		this.name = name;
	}
 
 
	public boolean Evaluate(Context c) {
		return c.Lookup(name);
	}
 
	public BooleanExp Copy() {
		return new VariableExp(name);
	}
 
 
	public BooleanExp Replace(String name, BooleanExp exp) {
		if (this.name.equals(name)) {
			return exp.Copy();
		} else {
			return Copy();
		}
	}
 
	public String getName() {
		return name;
	}
}

package interpreter;
 
public class AndExp implements BooleanExp {
	private BooleanExp operand1, operand2;
 
	public AndExp(BooleanExp operand1, BooleanExp operand2) {
		super();
		this.operand1 = operand1;
		this.operand2 = operand2;
	}
 
	public boolean Evaluate(Context c) {
		return operand1.Evaluate(c) && operand2.Evaluate(c);
	}
 
	public BooleanExp Replace(String str, BooleanExp exp) {
		return new AndExp(operand1.Replace(str, exp), operand2.Replace(str, exp));
	}
 
	public BooleanExp Copy() {
		return new AndExp(operand1.Copy(), operand2.Copy());
	}
}

package interpreter;
 
public class OrExp implements BooleanExp {
	private BooleanExp operand1, operand2;
 
	public OrExp(BooleanExp operand1, BooleanExp operand2) {
		super();
		this.operand1 = operand1;
		this.operand2 = operand2;
	}
 
	public boolean Evaluate(Context c) {
		return operand1.Evaluate(c) || operand2.Evaluate(c);
	}
 
	public BooleanExp Replace(String str, BooleanExp exp) {
		return new OrExp(operand1.Replace(str, exp), operand2.Replace(str, exp));
	}
 
	public BooleanExp Copy() {
		return new OrExp(operand1.Copy(), operand2.Copy());
	}
}

package interpreter;
 
public class NotExp implements BooleanExp {
	private BooleanExp operand;
 
	public NotExp(BooleanExp operand) {
		super();
		this.operand = operand;
	}
 
	public boolean Evaluate(Context c) {
		return !operand.Evaluate(c);
	}
 
	public BooleanExp Replace(String str, BooleanExp exp) {
		return new NotExp(operand.Replace(str, exp));
	}
 
	public BooleanExp Copy() {
		return new NotExp(operand.Copy());
	}
}

package interpreter;
 
public class Expression1 {
 
	/**
	 * @param args
	 */
	public static void main(String[] args) {
 
		// Часть 1:
		BooleanExp expression;
		Context context = new Context();
		VariableExp x = new VariableExp("X");
		VariableExp y = new VariableExp("Y");
		expression = new OrExp(
			new AndExp(new Constant(true), x),
			new AndExp(y, new NotExp(x))
		);
		context.Assign(x, false);
		context.Assign(y, true);
		boolean result = expression.Evaluate(context);
		System.out.println(result);
 
		// Часть 2: замена значения y
		NotExp not_z = new NotExp(z) ;
		BooleanExp replacement = expression.Replace("Y", not_z);
		context.Assign(z, true);
		result = replacement.Evaluate(context);
		System.out.println(result);
	}
 
}