Отключение алгоритма от данных, когда алгоритм требует знания производных классов

Question

Извините за сложное название, но это немного сложно объяснить только одним предложением.

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

Абстрактное синтаксическое дерево выплевывает выражения. (Который я передаю с помощью unique_ptrs). Есть несколько типов выражений, которые получены из этого базового класса, в том числе:

• Цифры
• Переменные
• Вызовы функций / прототипы
• Двоичные операции

и т.д.. Каждый производный класс содержит информацию, необходимую ему для этого выражения, то есть переменные содержат std :: string их идентификатора, двоичные операции содержат unique_ptrs слева и справа, а также символ оператора.

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

This is what an AST would look like for 'x=y*6^(z-4)+5'

   +--Assignment (=)--+
   |                  |
Var (x)   +--------BinOp (+)----+
          |                     |
          5     +------------BinOp (*)---+
                |                        |
   +---------BinOp (^)-------+         Var (y)
   |                         |
 Num (6)           +------BinOp (-)-----+
                   |                    |
                 Var (z)              Num (4)

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

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

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

Теперь проблема в том, что AST возвращает указатели на базовый класс , Expr , а не на производные типы. Вызов getExpression возвращает следующее выражение независимо от его производного типа, что позволяет мне легко рекурсивно оценивать двоичные операции и т. Д. Чтобы интерпретатор мог получить информацию об этих выражениях (например, числовое значение или идентификатор), я бы в основном динамически приводить каждое выражение и проверять, работает ли оно, и мне придется делать это повторно. Другим способом было бы сделать что-то вроде шаблона Visitor - Expr вызывает интерпретатор и передает ему this , что позволяет интерпретатору иметь несколько определений для каждого производного типа. Но опять же, интерпретатор должен вернуть значение !

Вот почему я не могу использовать шаблон посетителя - мне нужно возвращать значения, которые бы полностью связывали AST с интерпретатором.

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

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

Какие у меня есть варианты? Спасибо!

Answer 1

Почему вы не можете использовать шаблон посетителя? Любые возвращаемые результаты просто становятся локальными:

class EvalVisitor
{
    void visit(X x)
    {
         visit(x.y);
         int res1 = res();
         visit(x.z);
         int res2 = res();
         res(res1 + res2);
    }
  ....
};

Выше можно абстрагироваться так, чтобы логика находилась в правильном Функции:

class Visitor 
{
public:
    virtual void visit(X) = 0;
    virtual void visit(Y) = 0;
    virtual void visit(Z) = 0;
};

class EvalVisitor : public Visitor
{
public:
    int eval(X); 
    int eval(Y);
    int eval(Z);

    int result;

    virtual void visit(X x) { result = eval(x); } 
    virtual void visit(Y y) { result = eval(y); } 
    virtual void visit(Z z) { result = eval(z); } 
};

int evalExpr(Expr& x)
{
    EvalVisitor v;
    x.accept(v);
    return x.result;
}

Тогда вы можете сделать:

Expr& expr = ...;
int result = evalExpr(expr);

Answer 2

Обычный ответ (как и в большинстве генераторов синтаксического анализатора) состоит в том, чтобы иметь как значение типа токена, так и связанные с ним данные (называемые атрибутами при обсуждении таких вещей). Значение типа, как правило, представляет собой простое целое число и говорит: «число», «строка», «двоичная операция» и т. Д. При определении типа использования вы проверяете только типы токенов, а когда получаете соответствие правилу производства, вы знаете, какого рода токенов вводятся в это правило.

Если вы хотите реализовать это самостоятельно, посмотрите алгоритмы синтаксического анализа (LALR и GLR - пара примеров), или вы можете переключиться на использование генератора синтаксического анализатора, и вам нужно только беспокоиться о том, чтобы ваша грамматика была правильной, а затем о правильной реализации произведений. и не нужно заботиться о том, чтобы самостоятельно реализовать механизм синтаксического анализа.