Статьи

Пример шаблона интерпретатора

Ноябрь 26, 2018

Эта статья является частью нашего курса Академии под названием « Шаблоны проектирования Java» .

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

Содержание

1. Введение
2. Что такое шаблон дизайна переводчика
3. Реализация шаблона проектирования интерпретатора
4. Когда использовать шаблон проектирования переводчика
5. Шаблон дизайна переводчика в JDK
6. Загрузите исходный код

1. Введение

Модель Интерпретатора — это сверхмощная модель. Все дело в том, чтобы собрать свой собственный язык программирования или обработать существующий, создав интерпретатор для этого языка. Чтобы использовать этот шаблон, вы должны знать немало о формальных грамматиках для составления языка. Как вы можете себе представить, это один из тех шаблонов, которые разработчики на самом деле не используют каждый день, потому что создание собственного языка — это не то, что делают многие люди.

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

expression ::= <command> | <repetition> | <sequence>

Таким образом, каждое выражение на вашем новом языке может состоять из команд, повторений команд и выражений последовательностей. Каждый элемент может быть представлен как объект с методом интерпретации, чтобы перевести ваш новый язык во что-то, что вы можете запустить в Java.

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

2. Что такое шаблон дизайна переводчика

Для данного языка определите представление для его грамматики вместе с интерпретатором, который использует представление для интерпретации предложений на языке.

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

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

В таких случаях вместо того, чтобы рассматривать каждую отдельную комбинацию правил как отдельный случай, для приложения может быть полезно иметь возможность интерпретировать общую комбинацию правил. Шаблон Interpreter может использоваться для разработки этой возможности в приложении, чтобы другие приложения и пользователи могли определять операции, используя простой язык, определенный набором правил грамматики.

Иерархия классов может быть разработана для представления набора правил грамматики, при этом каждый класс в иерархии представляет отдельное правило грамматики. Модуль интерпретатора может быть разработан для интерпретации предложений, построенных с использованием иерархии классов, разработанной выше, и выполняет необходимые операции.

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

Рисунок 1 - Диаграмма классов

Рисунок 1 — Диаграмма классов

AbstractExpression

  • Объявляет абстрактную операцию Interpret которая является общей для всех узлов в абстрактном синтаксическом дереве.

TerminalExpression

  • Реализует операцию Interpret связанную с терминальными символами в грамматике.
  • Экземпляр требуется для каждого терминального символа в предложении.

NonterminalExpression

  • Один такой класс необходим для каждого правила R ::= R1 R2 ... Rn в грамматике.
  • Поддерживает переменные экземпляра типа AbstractExpression для каждого из символов от R1 до Rn .
  • Реализует операцию Interpret для нетерминальных символов в грамматике. Interpret обычно вызывает себя рекурсивно для переменных, представляющих R1 Rn .

контекст

  • Содержит информацию, которая является глобальной для переводчика.

клиент

  • Создает (или задается) абстрактное синтаксическое дерево, представляющее конкретное предложение на языке, который определяет грамматика. Абстрактное синтаксическое дерево собрано из экземпляров классов NonterminalExpression и TerminalExpression .
  • Вызывает операцию Interpret .

3. Реализация шаблона проектирования интерпретатора

1
2
3
4
5
package com.javacodegeeks.patterns.interpreterpattern;
 
public interface Expression {
    public int interpret();
}

Приведенный выше интерфейс используется всеми различными конкретными выражениями и переопределяет метод интерпретации для определения их конкретной операции над выражением.

Ниже приведены классы выражений для конкретных операций.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
package com.javacodegeeks.patterns.interpreterpattern;
 
public class Add implements Expression{
     
    private final Expression leftExpression;
    private final Expression rightExpression;
 
    public Add(Expression leftExpression,Expression rightExpression ){
        this.leftExpression = leftExpression;
        this.rightExpression = rightExpression;
    }
    @Override
    public int interpret() {
        return leftExpression.interpret() + rightExpression.interpret();
    }
 
}
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
package com.javacodegeeks.patterns.interpreterpattern;
 
public class Product implements Expression{
 
    private final Expression leftExpression;
    private final Expression rightExpression;
 
    public Product(Expression leftExpression,Expression rightExpression ){
        this.leftExpression = leftExpression;
        this.rightExpression = rightExpression;
    }
    @Override
    public int interpret() {
        return leftExpression.interpret() * rightExpression.interpret();
    }
}
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
package com.javacodegeeks.patterns.interpreterpattern;
 
public class Substract implements Expression{
     
    private final Expression leftExpression;
    private final Expression rightExpression;
 
    public Substract(Expression leftExpression,Expression rightExpression ){
        this.leftExpression = leftExpression;
        this.rightExpression = rightExpression;
    }
    @Override
    public int interpret() {
        return leftExpression.interpret() - rightExpression.interpret();
    }
 
}
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
package com.javacodegeeks.patterns.interpreterpattern;
 
public class Number implements Expression{
 
    private final int n;
     
    public Number(int n){
        this.n = n;
    }
    @Override
    public int interpret() {
        return n;
    }
 
}

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package com.javacodegeeks.patterns.interpreterpattern;
 
public class ExpressionUtils {
 
    public static boolean isOperator(String s) {
        if (s.equals("+") || s.equals("-") || s.equals("*"))
            return true;
        else
            return false;
    }
     
    public static Expression getOperator(String s, Expression left, Expression right) {
        switch (s) {
        case "+":
            return new Add(left, right);
        case "-":
            return new Substract(left, right);
        case "*":
            return new Product(left, right);
        }
        return null;
    }
 
}

Теперь давайте проверим пример.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package com.javacodegeeks.patterns.interpreterpattern;
 
import java.util.Stack;
 
public class TestInterpreterPattern {
 
    public static void main(String[] args) {
 
        String tokenString = "7 3 - 2 1 + *";
        Stack<Expression> stack = new Stack<>();
        String[] tokenArray = tokenString.split(" ");
        for (String s : tokenArray) {
            if (ExpressionUtils.isOperator(s)) {
                Expression rightExpression = stack.pop();
                Expression leftExpression = stack.pop();
                Expression operator = ExpressionUtils.getOperator(s, leftExpression,rightExpression);
                int result = operator.interpret();
                stack.push(new Number(result));
            } else {
                Expression i = new Number(Integer.parseInt(s));
                stack.push(i);
            }
        }
        System.out.println("( "+tokenString+" ): "+stack.pop().interpret());
 
    }
 
 
}

Код выше предоставит следующий вывод:

( 7 3 - 2 1 + * ): 12

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

Если вы не знаете о postfix, вот краткое введение об этом. В математическом выражении есть три нотации: инфикс, постфикс и префикс.

  • Инфиксная нотация — это стандартная арифметическая и логическая нотационная формула, в которой операторы записываются в инфиксном стиле между операндами, на которые они действуют, например, 3+4 .
  • Постфикс, известный как обратная польская запись (RPN), — это математическая запись, в которой каждый оператор следует за всеми своими операндами, например, 34+ .
  • Префикс (польское обозначение) — это форма обозначения логики, арифметики и алгебры, в которой операторы слева от своих операндов, например, +34 .

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

В вышеприведенном классе мы объявили постфикс выражения в переменной tokenString . Затем мы разделяем tokenString и присваиваем его массиву tokenArray . Выполняя итерацию токенов один за другим, сначала мы проверили, является ли токен оператором или операндом. Если токен является операндом, мы помещаем его в стек, но если это оператор, мы выталкиваем первые два операнда из стека. Метод getOperation из ExpressionUtils возвращает соответствующий класс выражений в соответствии с переданным ему оператором.

Затем мы интерпретируем результат и возвращаем его обратно в стек. После итерации полного tokenList мы получили окончательный результат.

4. Когда использовать шаблон проектирования переводчика

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

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

5. Шаблон дизайна переводчика в JDK

  • java.util.Pattern
  • java.text.Normalizer
  • java.text.Format

6. Загрузите исходный код

Это был урок по шаблону дизайна переводчика. Вы можете скачать исходный код здесь: InterpreterPattern-Project

120
Share: