算法与数据解耦，当算法需要派生知识时类

Question

抱歉，标题太复杂了，用一句话来解释有点困难。

所以我正在编写一种简单的解释型语言来帮助处理一些我经常做的事情。我设置了词法分析器，输入抽象语法树生成器。

抽象语法树吐出表达式。（我正在使用 unique_ptrs 传递）。从这个基础 class 派生出几种类型的表达式，其中包括：

数字
变量
函数调用/原型
二元运算

等每个派生 class 都包含该表达式所需的信息，即变量包含其标识符的 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 具有有关如何获取标记并将它们以正确的顺序转换为 表达式树的信息。

现在，解释器应该能够遍历这个自上而下的表达式列表，并递归地计算每个子表达式，将定义添加到内存中，计算常量，将定义分配给它们的函数等等。但是，每个评估 必须 return 一个值，以便我可以递归遍历表达式树 。

例如，二元运算表达式必须递归计算左侧和右侧，然后对两侧进行加法运算，然后return。

现在，问题是 AST returns 指向 base class、Expr 的指针——而不是派生类型。调用 getExpression returns 下一个表达式，而不管它的派生类型，这使我可以轻松地递归评估二进制操作等。为了让解释器获取有关这些表达式的信息（例如数值或标识符), 我基本上必须动态转换每个表达式并检查它是否有效，而且我必须重复执行此操作。另一种方法是做一些类似于访问者模式的事情——Expr 调用解释器并将 this 传递给它，这允许解释器为每个派生类型有多个定义。但同样，解释器 必须 return 一个值 !

这就是为什么我不能使用访问者模式的原因——我必须 return 值，这将把 AST 完全耦合到解释器。

我也不能使用策略模式，因为每种策略 return 都是截然不同的东西。例如，解释器策略与 LLVM 策略相差太大。

我完全不知道该做什么。一个非常棘手的解决方案是从字面上将每个表达式类型的枚举作为 expr 基 class 的成员，并且解释器可以检查类型，然后进行适当的类型转换。但这很丑陋。真丑。

我在这里有哪些选择？谢谢！

Answer 1

通常的答案（与大多数解析器生成器一样）是同时具有标记类型值和关联数据（在讨论此类事物时称为属性）。类型值通常是一个简单的整数，表示 "number"、"string" "binary op" 等。在决定使用什么产品时，您只检查令牌类型以及何时与产品规则匹配然后你就会知道什么样的标记会进入该规则。

如果您想自己实现它，请查找解析算法（LALR 和 GLR 是两个示例），或者您可以切换到使用解析器生成器，只需担心语法正确，然后正确实现制作，而不必担心自己实现解析引擎。

Answer 2

为什么不能使用访客模式？任何 return 结果简单地变成本地状态：

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

算法与数据解耦，当算法需要派生知识时类

Decoupling algorithm from data, when the algorithm needs knowledge of derived classes

c++

inheritance

design-patterns

decoupling