C++使用模板实现带返回值访问者模式问题求解

我目前正在用C实现一门编程语言，完成语法解析阶段后已经得到可操作的抽象语法树（Abstract Syntax Tree，AST），后续需要基于这棵树完成类型检查、字节码生成等工作，ASTPrinter、类型检查器等多个分析类都需要遍历操作这棵语法树。
此前访问者类的visit()方法返回值均为void，但近期发现部分访问者需要返回特定类型的值。尝试用模板实现该特性时，遇到了静态多态与运行时多态的冲突问题，核心限制是C不支持虚模板方法。

预期实现逻辑 #

以下是目标代码结构（已知无法编译，仅用于说明需求）：

Expression.h #

class Expression {
    public:
        template<typename R> R accept(ExprVisitor<R>& visitor);
};

ExprVisitor.h #

template<typename R>
class ExprVisitor {
    public:
        virtual R visitAssignmentExpression(class Assignment* expression) = 0;
        virtual R visitBinaryExpression(class Binary* expression) = 0;
        // 其余visit方法省略
};

表达式节点示例（Assignment.h） #

class Assignment: public Expression {
    public:
         template<typename R> R accept(ExprVisitor<R>& visitor);
};

访问者示例（ASTPrinter.h） #

class ASTPrinter: public ExprVisitor<std::string> {
    public:
        std::string visitAssignmentExpression(Assignment* expression) override;
        std::string visitBinaryExpression(Binary* expression) override;
        // 其余visit方法省略
};

其中ASTPrinter需要返回std::string类型的结果。问题根源是Expression中的accept()是模板方法，无法声明为virtual，无法实现运行时多态分发。
编译时每个AST节点都会触发如下链接错误：

undefined reference to `std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > Expression::accept<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >(ExprVisitor<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >&)'

main.cpp #

#include "Literal.h"
#include "Binary.h"
#include "ASTPrinter.h"

int main(int argc, char** argv) {
    Binary expr = Binary(Literal("10"), "+", Literal("10"));
    ASTPrinter ast = ASTPrinter();
    ast.constructTree(expr);
}

Expression.h #

#ifndef CODEPULSAR_EXPRESSION_H
#define CODEPULSAR_EXPRESSION_H
#include "ExprVisitor.h"

class Expression {
    public:
        template<typename R> R accept(ExprVisitor<R>& visitor);
};
#endif

ExprVisitor.h #

#ifndef CODEPULSAR_EXPRVISITOR_H
#define CODEPULSAR_EXPRVISITOR_H

template<typename R> class ExprVisitor {
    public:
        virtual R visitBinaryExpression(class Binary expression) = 0;
        virtual R visitLiteralExpression(class Literal expression) = 0;
};
#endif

ASTPrinter实现 #

ASTPrinter.h #

#ifndef CODEPULSAR_ASTPRINTER_H
#define CODEPULSAR_ASTPRINTER_H
#include <string>
#include <iostream>
#include "ExprVisitor.h"
#include "Expression.h"
#include "Binary.h"
#include "Literal.h"

class ASTPrinter: public ExprVisitor<std::string> {
    public:
        void constructTree(Expression ast);
        std::string visitBinaryExpression(Binary expression) override;
        std::string visitLiteralExpression(Literal expression) override;
};
#endif

ASTPrinter.cpp #

#include "ASTPrinter.h"

void ASTPrinter::constructTree(Expression ast) {
    std::cout << ast.accept(*this) << std::endl;
}

std::string ASTPrinter::visitBinaryExpression(Binary expression) {
    return "Binary(" + expression.left.accept(*this) + expression.operatorType + expression.right.accept(*this);
}

std::string ASTPrinter::visitLiteralExpression(Literal expression) {
    return "Literal(" + expression.value + ")";
}

Binary实现 #

Binary.h #

#ifndef CODEPULSAR_BINARY_H
#define CODEPULSAR_BINARY_H
#include <string>
#include "Expression.h"

class Binary: public Expression {
public:
    Binary(Expression left, std::string operatorType, Expression right);
    template<typename R> R accept(ExprVisitor<R>& visitor);
    Expression left;
    std::string operatorType;
    Expression right;
};
#endif

Binary.cpp #

#include "Binary.h"

Binary::Binary(Expression left, std::string operatorType, Expression right) {
    this->left = left;
    this->operatorType = operatorType;
    this->right = right;
}

template<typename R>
R Binary::accept(ExprVisitor<R>& visitor) {
    visitor.visitBinaryExpression(this);
}

Literal实现 #

Literal.h #

#ifndef CODEPULSAR_LITERAL_H
#define CODEPULSAR_LITERAL_H
#include <string>
#include "Expression.h"

class Literal: public Expression {
public:
    Literal(std::string value);
    template<typename R> R accept(ExprVisitor<R>& visitor);
    std::string value;
};
#endif

Literal.cpp #

#include "Literal.h"

Literal::Literal(std::string value) {
    this->value = value;
}

template<typename R>
R Literal::accept(ExprVisitor<R>& visitor) {
    visitor.visitLiteralExpression(this);
}

问题本质由三个原因导致：

• C++语法不支持虚函数模板，基类的模板accept无法完成运行时多态调度
• 模板函数实现放在.cpp文件中，编译期无法为R=std::string生成对应实例，触发链接错误
• 代码中所有AST节点采用值传递、值存储，存在对象切片问题，即使解决多态问题也无法正常运行
  以下三个是工业界实现编译器/解释器AST访问者的成熟方案，可根据需求选择：

方案1：成员变量存返回值（改造成本最低，推荐优先使用） #

完全保留原有void返回值的虚函数访问者结构，将遍历结果存在访问者实例的成员变量中，遍历完成后直接读取成员变量取值即可，无需修改多态逻辑。
修改示例：

class ASTPrinter: public ExprVisitor {
public:
    std::string result; // 存储遍历结果
    void visitBinaryExpression(Binary* expression) override {
        // 遍历左子树，取结果
        expression->left->accept(*this);
        std::string left_res = result;
        // 遍历右子树，取结果
        expression->right->accept(*this);
        std::string right_res = result;
        // 组装当前节点结果
        result = "Binary(" + left_res + expression->operatorType + right_res + ")";
    }
    void visitLiteralExpression(Literal* expression) override {
        result = "Literal(" + expression->value + ")";
    }
};

调用方式：

// 注意需要改成指针传递，避免对象切片
auto left = std::make_unique<Literal>("10");
auto right = std::make_unique<Literal>("10");
auto expr = std::make_unique<Binary>(std::move(left), "+", std::move(right));
ASTPrinter printer;
expr->accept(printer);
std::cout << printer.result << std::endl;

• 优点：零额外抽象，无性能损耗，兼容所有C++版本，是Crafting Interpreters等主流手写解释器采用的实现
• 缺点：递归遍历子节点时需要临时存储子节点结果，代码多两行冗余

方案2：CRTP静态多态（零开销，类型安全） #

采用CRTP（奇异递归模板模式）实现静态多态，不需要虚函数，自然规避虚模板的语法限制。
修改示例：

// 先定义无模板的空基类，用于统一存储AST节点指针
class ExprBase {};

// Expression模板基类
template <typename Derived>
class Expression: public ExprBase {
public:
    template <typename R>
    R accept(ExprVisitor<R>& visitor) {
        // 编译期静态绑定到实际派生类，无虚函数开销
        return visitor.visit(static_cast<Derived*>(this));
    }
};

// 节点继承时将自身作为模板参数传入
class Binary: public Expression<Binary> {
public:
    std::unique_ptr<ExprBase> left;
    std::string op;
    std::unique_ptr<ExprBase> right;
    // 构造函数省略
};

class Literal: public Expression<Literal> {
public:
    std::string value;
    // 构造函数省略
};

注意所有模板实现必须放在头文件中，不能放在cpp里。

• 优点：完全类型安全，返回值直接通过函数返回，无运行时虚函数开销
• 缺点：需要统一用ExprBase指针存储节点，节点实现需要传入自身作为模板参数

方案3：类型擦除无环访问者（扩展性最好） #

如果后续需要频繁新增访问者、新增返回类型，不想修改基类代码，可以采用类型擦除实现无环访问者，核心是将Visitor基类设为空类，每个节点类型定义单独的访问接口，运行时通过dynamic_cast判断访问者是否支持当前节点。该方案实现稍复杂，适合大型项目长期迭代使用。

内容的提问来源于stack exchange，提问作者FireTheLost