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

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

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

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

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

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

3

c++decoupling design-patterns inheritance

Решение

Другие решения

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

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);

0

Источник

Accepted Answer

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

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

1