组合异构递归类型以定义子语言

Question

我正在尝试定义一种基本语言来构建表达式，我将根据代码对其进行评估。这样的表达式是在运行时递归定义的。你可能会认为它是布尔表达式，具有True和False等基本表达式，也涉及复杂表达式，如表达式的否定、任意两个表达式的析取和连接。

如前所述，这样的表达式是递归的，将在运行时创建，所以我想模板是没有选择的。为此，在C++2011中实现类型和评估函数最合适的方法是什么？

任何评论都是受欢迎的，因为我对C++模式和功能的了解还不太深入。

示例非工作代码，它说明了我不需要任何表达式的外部表示（作为字符串）：

struct basic {
    bool val;
};
struct complex_neg {
    expression exp;
};
struct complex_and {
    expression exp1, exp2;
};
struct expression : basic, complex_neg, complex_and {
    bool eval() {
        if (dynamic_cast<basic*>(this)) return this->val;
        else if (dynamic_cast<complex_neg*>(this)) return !this->eval();
        else return this->eval() && this->eval();
    }
};

Answer 1

一个好的开始是构建表达式和终端的树/有向图。请参见抽象语法树。

然后计算表达式树。

在C++中，构建AST最方便的方法之一就是使用Boost Spirit，请参阅一个很好的介绍。

Answer 2

您可以尝试的最原始的方法是使用反向抛光符号的调车场算法。

你能做的最专业的事情就是使用助推精神

你能做的最糟糕的事情就是为你自己实现一个特定语法的ll解析器。但是你需要了解一些关于语言解析器的理论。