Остановитесь и продолжите во время вычисления дерева выражений - PullRequest
Новая
       19

Остановитесь и продолжите во время вычисления дерева выражений

1 голос
/ 17 ноября 2009

В офисе мы применили простые доменные языки (DSL) к нескольким проблемным доменам, с которыми мы столкнулись.

По сути, мы анализируем (lex / yacc) пользовательский скрипт в дереве выражений. Каждый узел в дереве выражений имеет метод .evaluate (), который вызывается рекурсивно, пока программа не будет завершена. Красиво и просто, как пирог. Это хорошо, потому что я почти ничего не знаю о методах синтаксического анализа, построении компилятора и о чем-то подобном (хорошо, что мои коллеги знают что-то одно или два).

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

  • останов в любой позиции дерева
  • сохраняются все состояния
  • и восстановить состояние / положение в любое время в будущем.

Сохранение фактического состояния не должно быть слишком сложным, но положение в дереве (или «стек вызовов)» озадачивает меня. Как можно было бы реализовать такую ​​систему? Сохранять позицию в дереве, используя какие-то идентификаторы для каждого узла? Или оценивает само дерево как неправильный подход, и должны ли мы каким-то образом преобразовать его в нечто линейное?

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

(Делаем это в Win32 / Dephi, но, надеюсь, мы сможем сохранить независимость от этого языка)

1 Ответ

1 голос
/ 18 ноября 2009

Положение в дереве можно указать с помощью списка дочерних номеров. Ваши оценки будут выглядеть примерно так (быстро написано; не скомпилировано / протестировано): 

public class Context {
    private Context parent; // set in constructor
    private int child;  // with get/set
}

public ReturnType evaluate(Context context) 
    context.setChild(context.getChild() + 1);
    context = new Context(context); // push a new context for calls
    // do evaluation - when calling kids, pass context            
}

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

Вместо того, чтобы реализовывать это в каждом типе узла, я бы рекомендовал написать декоратор (или суперкласс с использованием метода шаблона), чтобы сделать это для вас, например: 

// decorator
public class ContextTrackerEvaluator<T> implements Evaluator<T> {
    private Evaluator realEvaluator;
    public ContextTrackerEvaluator(Evaluator realEvaluator) {
        this.realEvaluator = realEvaluator;
    }
    public T evaluate(Context context) {
        context.setChild(context.getChild() + 1);
        context = new Context(context); // push a new context for calls
        realEvaluator.evaluate(context);
    }
}

// OR superclass w/ template method
public class EvaluatorBase<T> {
    public final T evaluate(Context context) {
        context.setChild(context.getChild() + 1);
        context = new Context(context); // push a new context for calls
        doEvaluate(context);
    }
    // subclasses override doEvaluate to do their real work
    protected abstract T doEvaluate(Context context);
}

Если вы используете декоратор, убедитесь, что вы украшаете каждый узел ...

Это дает вам доступ к контекстному списку.

Затем вы можете добавить параметр «остановка контекста», который вы можете сравнить (чтобы вы могли передать два контекста и сравнить их, чтобы увидеть, совпадают ли они.

Надеюсь, это поможет! - Скотт

...