Интерпретатор (Interpreter)

Шаблон Интерпретатор задаёт способ вычисления выражений, записанных на некотором специальном языке. Основная идея шаблона – определение класса для каждого символа языка. Вследствие этого выражение на языке представляется в виде композитной объектной структуры.

Сделаем небольшое отступление и рассмотрим формальные понятия язык и грамматика. Словарём будем называть выделенное конечное множество элементов. Элементы словаря будем называть символами, а последовательности символов – предложениями. Множество предложений назовём языком. Грамматикой называется любой конечный механизм задания языка. Формальная грамматика – разновидность грамматики, в которой язык задаётся при помощи порождающих правил. Каждое такое правило имеет вид «левая часть» → «правая часть», где «левая часть» – это непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал, а «правая часть» – любая последовательность терминалов и нетерминалов. В свою очередь, понятие терминал означает объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). Нетерминал – это объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.

Для компактного задания формальной грамматики часто используется форма Бакуса-Наура (БНФ). Вот, например, задание в БНФ грамматики, соответствующей обратной польской нотации для арифметических выражений:

expression ::= plus | minus | variable

plus ::= expression expression '+'

minus ::= expression expression '-'

variable ::= 'a' | 'b' | 'c' | ... | 'z'

Вернёмся к рассмотрению шаблона Интерпретатор. Структура шаблона представлена на рис. 23. Для каждого символа (терминала и нетерминала) создаётся отдельный класс, наследуемый от общего предка. Нетерминальные классы по определению агрегируют другие объекты-символы. Каждый из классов имеет метод, ответственный за вычисление выражения, соответствующего объекту класса.

Рис. 23. Структура шаблона Интерпретатор.

Рассмотрим пример реализации шаблона Интерпретатор. Опишем этот пример для грамматики, которая была представлена выше в виде БНФ. Следуя шаблону, определим классы для правил грамматики.

public interface Expression

{

int Interpret(IDictionary<string, int> variables);

}

public class Number : Expression

{

private readonly int number;

public Number(int number)

{

this.number = number;

}

public int Interpret(IDictionary<string, int> variables)

{

return number;

}

}

public class Plus : Expression

{

private readonly Expression leftOperand;

private readonly Expression rightOperand;

public Plus(Expression left, Expression right)

{

leftOperand = left;

rightOperand = right;

}

public int Interpret(IDictionary<string, int> variables)

{

return leftOperand.Interpret(variables) +

rightOperand.Interpret(variables);

}

}

public class Minus : Expression

{

private readonly Expression leftOperand;

private readonly Expression rightOperand;

public Minus(Expression left, Expression right)

{

leftOperand = left;

rightOperand = right;

}

public int Interpret(IDictionary<string, int> variables)

{

return leftOperand.Interpret(variables) –

rightOperand.Interpret(variables);

}

}

public class Variable : Expression

{

private readonly string name;

public Variable(string name)

{

this.name = name;

}

public int Interpret(IDictionary<string, int> variables)

{

return variables.ContainsKey(name) ? variables[name] : 0;

}

}

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

public class Evaluator

{

private readonly Expression syntaxTree;

public Evaluator(string expression)

{

var expressionStack = new Stack<Expression>();

foreach (var token in expression.Split(' '))

{

switch (token)

{

case "+":

var plus = new Plus(expressionStack.Pop(),

expressionStack.Pop());

expressionStack.Push(plus);

break;

case "-":

var minus = new Minus(expressionStack.Pop(),

expressionStack.Pop());

expressionStack.Push(minus);

break;

default:

expressionStack.Push(new Variable(token));

break;

}

}

syntaxTree = expressionStack.Pop();

}

public int Evaluate(IDictionary<string, int> context)

{

return syntaxTree.Interpret(context);

}

}

Представим код, вычисляющий выражение "w x z - +", при w=5, x=10, z=4.

public class InterpreterExample

{

private static void Main()

{

var sentence = new Evaluator("w x z - +");

var vars = new Dictionary<string, int> { { "w", 5 },

{ "x", 10 }, { "z", 4 } };

Console.WriteLine(sentence.Evaluate(vars));

}

}