Оценка выражения по шаблону посетителя - PullRequest
Новая
       8

Оценка выражения по шаблону посетителя

1 голос
/ 18 апреля 2020

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

  1. Текущий дизайн хорошо работает с арифметическими c операторами, но когда дело доходит до логических операторов, например, 5 > 6 будет выводить в false это не работает. Поскольку Visitor является универсальным c интерфейсом, поэтому, если я скажу Visitor<Boolean>, возвращаемое значение станет boolean, но участвующие значения integer, следовательно, я не могу иметь целое число в качестве параметра.
  2. Дизайн требует класс для каждого оператора, можно ли его минимизировать?
  3. Пожалуйста, поделитесь своими соображениями по дизайну. Выглядит ли это хорошо или требуется какая-либо модификация.

Ниже приведены участвующие классы.

Вот интерфейс посетителя 

public interface Visitor<T> {

    T visit(Expression expression);

    T visit(BinaryExpression binaryExpression);

    T visit(ConstantExpression expression);
}

реализация посетителя 

public class ExpressionVisitor<T> implements Visitor<T> {

    @Override
    public T visit(Expression expression) {
        return expression.accept(this);
    }

    @Override
    public T visit(BinaryExpression arithmeticExpression) {
        Operator op = arithmeticExpression.getOperator();
        T left = visit(arithmeticExpression.getLeft());
        T right = visit(arithmeticExpression.getRight());
        return op.apply(left, right);
    }

    @Override
    public T visit(ConstantExpression expression) {
        return (T) expression.getValue();
    }
}

Класс, представляющий выражение 

public abstract class Expression {

    public abstract  <T>  T accept(Visitor<T> visitor);
}

Класс для двоичного выражения 

public class BinaryExpression extends Expression {

    private Operator operator;
    private Expression left;
    private Expression right;

  //constructor and getters

    @Override public <T> T accept(Visitor<T> visitor) {
        return visitor.visit(this);
    }
}

Класс, представляющий значение константы 

public class ConstantExpression extends Expression {


    private Object value;

//constructor and getter

    @Override public <T> T accept(Visitor<T> visitor) {
        return visitor.visit(this);
    }
}

Класс оператора 

public abstract class Operator {

    public <T> T apply(T left, T right) {
        try {
            Method method = this.getClass().getMethod("do" + left.getClass().getSimpleName() + this.getClass().getSimpleName(), left.getClass(), right.getClass());
            method.setAccessible(true);
            return (T) method.invoke(this, left, right);
        } catch (NoSuchMethodException | InvocationTargetException | IllegalAccessException e) {
           throw new RuntimeException("Failed");
        }
    }
}

И оператор сложения 

public class Addition extends Operator {


    public Integer doIntegerAddition(Integer left, Integer right) {
        return left + right;
    }

    public Double doDoubleAddition(Double left, Double right) {
        return left + right;
    }

    public String doStringAddition(String left, String right) {
        return left + right;
    }
}

Ответы [ 2 ]

0 голосов
/ 19 апреля 2020

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

К тому времени, когда вы получите это "что-то, что вы можете оценить", детали языка выражения Вы проанализировали, включая древовидную структуру, типы операторов и т. д. c., все должны быть учтены. Не вставляйте sh эти проблемы в код, который нужно просто оценить.

Итак, ваш процесс синтаксического анализа должен создать объект, который реализует интерфейс примерно так: 

interface IExpression {
    double evaluateNumeric(Environment env);
    boolean evaluateLogical(Environment env);
    String evaluateString(Environment env);
    boolean isConstant();
}

Здесь объект Environment содержит значения переменных, определений функций или чего-либо еще - все, что выражения могут использовать в качестве входных данных.

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

У вас также могут быть методы, которые сообщают вам о выражении, например isConstant. В зависимости от языка, может быть важно предоставить тип объекта, который выражение генерирует естественным образом.

Чтобы исключить проблемы реализации операций из анализатора, вы можете предоставить ему заводской интерфейс, подобный этому: 

IExpressionFactory {

    IExpression add(IExpression left, IExpression right);
    IExpression multiply(IExpression left, IExpression right);
    ///... etc. etc.
}

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

Различные виды подвыражений могут быть реализованы любым удобным для вас способом. В Java я обычно использую классы для каждой категории с такими лямбда-аргументами, как: 

class ExpressionFactory : IExpressionFactory {
    ...
    IExpression add(final IExpression left, final IExpression right) {
        return arithmeticBinary(left, right, (a,b)->a+b);
    }
    ...
}

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

ВАЖНО: обратите внимание, что поскольку скомпилированный IExpression не предоставляет дерево выражений, которое было проанализировано для его создания, вам не нужно сохранять эту структуру, и вы можете выполнять оптимизации, такие как постоянное свертывание: 

IExpression arithmeticBinary(IExpression left, IExpression right, DoubleBiFunc operator) {
    if (left.isConstant() && right.isConstant()) {
        // The operands are constant, so we can evaluate this during compilation
        double value = operator.apply(
            left.evaluateNumeric(EMPTY_ENV),
            right.evaluateNumeric(EMPTY_ENV));
        return new NumericConstant(value);
    } else {
        return new ArithmeticBinaryExpression(left, right, operator);
    }
}

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

0 голосов
/ 18 апреля 2020

Что касается вашего первого вопроса, я думаю, вам не нужно привязывать значения left и right к T в ExpressionVisitor<T>.

Вы можете установить thenm как Object. 

public class ExpressionVisitor<T> implements Visitor<T> {

    @Override
    public T visit(Expression expression) {
        return expression.accept(this);
    }

    @Override
    public T visit(BinaryExpression arithmeticExpression) {
        Operator op = arithmeticExpression.getOperator();
        Object left = visit(arithmeticExpression.getLeft());
        Object right = visit(arithmeticExpression.getRight());
        return op.apply(left, right);
    }

    @Override
    public T visit(ConstantExpression expression) {
        return (T) expression.getValue();
    }
}

Тогда вы можете иметь Operator GreaterThan: 

public class GreaterThan extends Operator{

    public Boolean doIntegerGreaterThan(Integer left, Integer right) {
        return left > right;
    }

    public Boolean doDoubleGreaterThan(Double left, Double right) {
        return left > right;
    }

    public Boolean doStringGreaterThan(String left, String right) {
        return left.length() > right.length();
    }
}
...