Шаблон интерпретатора

В компьютерном программировании шаблон интерпретатора является шаблоном проектирования , который определяет, как оценивать предложения на языке. Основная идея состоит в том, чтобы иметь класс для каждого символа (терминал или нетерминал ) на специализированном компьютерном языке. Синтаксическое дерево предложения на языке является экземпляром составного шаблона и используется для оценки (интерпретации) предложения для клиента. См. Также Составной шаблон.

• 1 Обзор
• 2 Использование
• 3 Структура
  • 3.1 Класс UML и диаграмма объектов
  • 3.2 Диаграмма классов UML
• 4 Пример
  • 4.1 BNF
  • 4.2 C #
  • 4.3 Java
  • 4.4 PHP (Пример 1)
  • 4.5 PHP (Пример 2)
• 5 См. Также
• 6 Ссылки
• 7 Внешние ссылки

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

Какие проблемы может решить шаблон проектирования интерпретатора?

• A грамматика для простого языка должна быть определена
• так, чтобы предложения на языке можно было интерпретировать.

Когда проблема возникает очень часто его можно представить в виде предложения на простом языке (Domain Specific Languages ​​ ), чтобы интерпретатор мог решить проблему, интерпретируя предложение.

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

Какое решение описывает шаблон проектирования Interpreter?

• Определите грамматику для простого языка, определив иерархию классов Expressionи реализовав операцию Interpreter ().
• Представьте предложение на языке в виде абстрактного синтаксического дерева (AST), состоящего из Expressionэкземпляров.
• Интерпретируйте предложение, вызвав интерпретировать ()в AST.

Объекты выражения рекурсивно составляются в составную / древовидную структуру, которая называется абстрактным синтаксическим деревом (см. Составной шаблон ).. Шаблон интерпретатора не описывает, как построить абстрактное синтаксическое дерево. Это может быть сделано либо вручную клиентом, либо автоматически парсером .

См. Также схему классов и объектов UML ниже.

• специализированные языки запросов к базам данных, такие как SQL.
• специализированные компьютерные языки, которые часто используются для описания протоколов связи.
• Большинство компьютерных языков общего назначения фактически включают несколько специализированные языки.

Класс UML и диаграмма объектов

Пример класса UML и диаграммы объектов для шаблона проектирования Interpreter.

В приведенном выше UML диаграмма классов, класс Clientотносится к общему интерфейсу AbstractExpressionдля интерпретации выражения интерпретировать (контекст).. Класс TerminalExpressionне имеет дочерних элементов и интерпретирует выражение напрямую.. Класс NonTerminalExpressionподдерживает контейнер дочерних выражений (выражений) и пересылает запросы интерпретации этим выражениям..

На диаграмме взаимодействия объектов показаны взаимодействия во время выполнения : Объект Clientотправляет запрос интерпретации абстрактному синтаксическому дереву. Запрос направляется (выполняется) ко всем объектам вниз по древовидной структуре.. Объекты NonTerminalExpression(ntExpr1, ntExpr2) пересылают запрос своим дочерним выражениям.. Объекты TerminalExpression(tExpr1, tExpr2,…) выполняют интерпретацию напрямую.

Схема классов UML

BNF

Следующий пример формы Бэкуса – Наура иллюстрирует шаблон интерпретатора. Грамматика

выражение :: = plus | минус | переменная | число плюс :: = выражение выражение '+' минус :: = выражение выражение '-' переменная :: = 'a' | 'b' | 'c' |... | цифра «z» = «0» | '1' |... | Число '9' :: = цифра | цифровое число

определяет язык, который содержит выражения обратной польской нотации, например:

ab + abc + - ab + ca - -

C #

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

пространство имен DesignPatterns.Interpreter {// "Контекст", класс Context {} // Абстрактный класс "AbstractExpression" AbstractExpression {public abstract void Interpret (Context context); } // Класс "TerminalExpression" TerminalExpression: AbstractExpression {public override void Interpret (Context context) {Console.WriteLine ("Called Terminal.Interpret ()"); }} // Класс "NonterminalExpression" NonterminalExpression: AbstractExpression {public override void Interpret (Context context) {Console.WriteLine ("Called Nonterminal.Interpret ()"); }} класс MainApp {static void Main () {var context = new Context (); // Обычно дерево var list = new List (); // Заполнение списка 'абстрактного синтаксического дерева'. Add (new TerminalExpression ()); list.Add (новое Нетерминальное выражение ()); list.Add (новое выражение терминала ()); list.Add (новое выражение терминала ()); // Интерпретировать foreach (AbstractExpression exp в списке) {exp.Interpret (context); }}}}

Java

Следуя шаблону интерпретатора, нам нужно реализовать интерфейс Expr с лямбда-выражением (это может быть класс) для каждого правила грамматики.

общедоступный класс Interpreter {@FunctionalInterface открытый интерфейс Expr {int Interpreter (Map context); статический номер выражения (целое число) {контекст возврата ->число; } static Expr plus (Expr left, Expr right) {return context ->left.interpret (context) + right.interpret (контекст); } статическое Expr минус (Expr left, Expr right) {return context ->left.interpret (context) - right.interpret (context); } статическая переменная Expr (имя строки) {контекст возврата ->context.getOrDefault (имя, 0); }}

Хотя шаблон интерпретатора не обращается к синтаксическому анализу, синтаксический анализатор предоставляется для полноты.

частный статический Expr parseToken (String token, ArrayDeque stack) {Expr left, right; switch (token) {case "+": // Сначала необходимо удалить из стека правый операнд right = stack.pop (); //... а потом левый left = stack.pop (); return Expr.plus (слева, справа); case "-": right = stack.pop (); left = stack.pop (); вернуть Expr.minus (слева, справа); по умолчанию: return Expr.variable (token); }} общедоступный статический синтаксический анализ Expr (строковое выражение) {ArrayDeque stack = new ArrayDeque (); for (Строковый токен: выражение.split ("")) {stack.push (parseToken (токен, стек)); } return stack.pop (); }

Наконец, вычисление выражения "wxz - +" с w = 5, x = 10 и z = 42.

public static void main (final String args) {Expr expr = parse ("wxz - +"); Карта context = Map.of («w», 5, «x», 10, «z», 42); int result = expr.interpret (контекст); System.out.println (результат); // -27}}

PHP (пример 1)

/ ** * AbstractExpression * / interface Expression {интерпретация публичной функции (массив $ context): int; }

/ ** * TerminalExpression * / class TerminalExpression реализует Expression {/ ** @var string * / private $ name; публичная функция __construct (строка $ name) {$ this->name = $ name; } интерпретация публичной функции (массив $ context): int {return intval ($ context [$ this->name]); }}

/ ** * NonTerminalExpression * / абстрактный класс NonTerminalExpression реализует Expression {/ ** @var Expression $ left * / protected $ left; / ** @var? Выражение $ right * / protected $ right; публичная функция __construct (Выражение $ left,? Выражение $ right) {$ this->left = $ left; $ this->right = $ right; } абстрактная интерпретация публичной функции (массив $ context): int; публичная функция getRight () {return $ this->right; } публичная функция setRight ($ right): void {$ this->right = $ right; }}

/ ** * NonTerminalExpression - PlusExpression * / class PlusExpression extends NonTerminalExpression {интерпретация публичной функции (массив $ context): int {return intval ($ this->left->интерпретация ($ context) + $ this->право->интерпретировать ($ context)); }}

/ ** * NonTerminalExpression - MinusExpression * / class MinusExpression extends NonTerminalExpression {интерпретация публичной функции (массив $ context): int {return intval ($ this->left->интерпретация ($ context) - $ this->право->интерпретировать ($ context)); }}

/ ** * Клиент * / класс InterpreterClient {защищенная функция parseList (массив и $ stack, массив $ list, int $ index) {/ ** @var string $ token * / $ token = $ list [ $ index]; переключатель ($ токен) {case '-': list ($ left, $ right) = $ this->fetchArguments ($ stack, $ list, $ index); вернуть новое MinusExpression ($ left, $ right); case '+': список ($ left, $ right) = $ this->fetchArguments ($ stack, $ list, $ index); return new PlusExpression ($ left, $ right); по умолчанию: вернуть новое выражение TerminalExpression ($ token); }} защищенная функция fetchArguments (массив $ stack, array $ list, int $ index): array {/ ** @var Expression $ left * / $ left = array_pop ($ stack); / ** @var Выражение $ right * / $ right = array_pop ($ stack); если ($ right === null) {++ $ index; $ this->parseListAndPush ($ stack, $ list, $ index); $ right = array_pop ($ стек); } return array ($ left, $ right); } защищенная функция parseListAndPush (массив $ stack, массив $ list, int $ index) {array_push ($ stack, $ this->parseList ($ stack, $ list, $ index)); } синтаксический анализ защищенной функции (строка $ data): Выражение {$ stack =; $ list = explode (', $ данные); for ($ index = 0; $ index parseListAndPush ($ stack, $ list, $ index);} return array_pop ($ stack);} публичная функция main () {$ data = "u + v - w + z "; $ expr = $ this->parse ($ data); $ context = ['u' =>3, 'v' =>7, 'w' =>35, 'z' =>9]; $ res = $ expr->интерпретация ($ context); echo "result: $ res". PHP_EOL;}}

// test.php function loadClass ($ className) {require_once __DIR__. "/$className.php";} spl_autoload_register ('loadClass'); (new InterpreterClient ()) ->main (); // результат: -16

PHP (Пример 2)

на основе приведенного выше примера с другой реализацией Клиента

/ ** * Клиент * / class InterpreterClient {публичная функция parseToken (строка $ token, массив и $ stack): Expression {switch ($ token) {case '-': / ** @var Expression $ left * / $ left = array_pop ($ stack); / ** @var Expression $ right * / $ right = array_pop ($ stack); return new MinusExpression ($ left, $ right); case '+': / ** @var Выражение $ left * / $ left = array_pop ($ stack); / ** @var Выражение $ right * / $ right = array_pop ($ stack); return n новое выражение PlusExpression ($ left, $ right); по умолчанию: вернуть новое выражение TerminalExpression ($ token); }} синтаксический анализ публичной функции (строка $ data): Выражение {$ notinishedData = null; $ stack =; $ list = explode (', $ данные); foreach ($ list as $ token) {$ data = $ this->parseToken ($ token, $ stack); if (($ notinishedData instanceof NonTerminalExpression) ($ data instanceof TerminalExpression)) {$ notinishedData->setRight ($ data); array_push ($ stack, $ unfinishedData); $ undefinishedData = ноль; Продолжать; } if ($ data instanceof NonTerminalExpression) {if ($ data->getRight () === null) {$ notinishedData = $ data; Продолжать; }} array_push ($ stack, $ data); } return array_pop ($ stack); } публичная функция main () {$ data = "u + v - w + z"; $ expr = $ this->parse ($ data); $ context = ['u' =>3, 'v' =>7, 'w' =>35, 'z' =>9]; $ res = $ expr->интерпретировать ($ context); echo "результат: $ res". PHP_EOL; }}

• Форма Бэкуса – Наура
• Комбинаторная логика в вычислениях
• Шаблоны проектирования
• Доменно-ориентированный язык
• Интерпретатор (вычисления)

1. ^ Gamma, Erich ; Хелм, Ричард ; Джонсон, Ральф; Влиссидес, Джон (1994). Шаблоны проектирования: элементы объектно-ориентированного программного обеспечения многократного использования. Эддисон-Уэсли. ISBN 0-201-63361-2.
2. ^Эрих Гамма, Ричард Хелм, Ральф Джонсон, Джон Влиссидес (1994). Шаблоны проектирования: элементы объектно-ориентированного программного обеспечения многократного использования. Эддисон Уэсли. Стр. 243ff. ISBN 0-201-63361-2. CS1 maint: несколько имен: список авторов (ссылка )
3. ^«Шаблон проектирования интерпретатора - проблема, решение, и применимость ". w3sDesign.com. Проверено 12 августа 2017 г.
4. ^" Шаблон проектирования интерпретатора - структура и взаимодействие ". w3sDesign.com. Проверено 12 августа 2017 г.

В Викибуке Шаблоны проектирования компьютерных наук есть страница по теме: Интерпретации на разных языках

• Реализация интерпретатора в Ruby
• Реализация интерпретатора в C ++
• Учебник по созданию исходного кода
• Описание шаблона интерпретатора из Портлендского репозитория шаблонов