如何在Boost Spirit X3中实现二元运算符的递归解析？

核心问题分析 #

你遇到的嵌套二元运算符解析失败，本质上不是需要手动通过语义动作传值，而是运算符优先级与结合性的定义缺失，或是表达式规则的递归结构设计错误。Spirit X3本身支持通过分层规则处理运算符优先级，无需手动干预值传递——语义动作更多用于AST节点构造，而非解决递归解析问题。

解决方案步骤 #

1. 按优先级分层定义表达式规则 #

HLSL的二元运算符有明确优先级（比如乘法高于加法）和结合性（比如加法左结合），需参考《Crafting Interpreters》附录I的语法结构，把表达式规则拆分为多个层级：

• 最底层：primary_expr（字面量、括号表达式、标识符等）
• 上一层：unary_expr（处理一元运算符，如-、!）
• 按优先级从高到低定义multiplicative_expr、additive_expr等，每层仅处理对应优先级的二元运算符

示例代码结构：

namespace x3 = boost::spirit::x3;

// AST节点定义（示例）
struct Expr {};
struct BinaryExpr : Expr {
    std::unique_ptr<Expr> lhs;
    std::string op;
    std::unique_ptr<Expr> rhs;
};
struct UnaryExpr : Expr {
    std::string op;
    std::unique_ptr<Expr> expr;
};
struct LiteralExpr : Expr {
    int value;
};

// 规则声明
x3::rule<class primary_expr_class, std::unique_ptr<Expr>> const primary_expr = "primary_expr";
x3::rule<class unary_expr_class, std::unique_ptr<Expr>> const unary_expr = "unary_expr";
x3::rule<class additive_expr_class, std::unique_ptr<Expr>> const additive_expr = "additive_expr";
x3::rule<class multiplicative_expr_class, std::unique_ptr<Expr>> const multiplicative_expr = "multiplicative_expr";

// 规则定义
auto const primary_expr_def =
    x3::int_ ([](auto& ctx) { _val(ctx) = std::make_unique<LiteralExpr>(_attr(ctx)); })
    | '(' >> additive_expr >> ')'
    ;

auto const unary_expr_def =
    x3::lit("-") >> unary_expr ([](auto& ctx) { _val(ctx) = std::make_unique<UnaryExpr>("-", _attr(ctx)); })
    | primary_expr
    ;

auto const multiplicative_expr_def =
    unary_expr
    >> *(
        (x3::lit("*") >> unary_expr) ([](auto& ctx) {
            auto rhs = std::move(_attr(ctx).second);
            auto& lhs = _val(ctx);
            _val(ctx) = std::make_unique<BinaryExpr>(std::move(lhs), "*", std::move(rhs));
        })
        | (x3::lit("/") >> unary_expr) ([](auto& ctx) {
            auto rhs = std::move(_attr(ctx).second);
            auto& lhs = _val(ctx);
            _val(ctx) = std::make_unique<BinaryExpr>(std::move(lhs), "/", std::move(rhs));
        })
    )
    ;

auto const additive_expr_def =
    multiplicative_expr
    >> *(
        (x3::lit("+") >> multiplicative_expr) ([](auto& ctx) {
            auto rhs = std::move(_attr(ctx).second);
            auto& lhs = _val(ctx);
            _val(ctx) = std::make_unique<BinaryExpr>(std::move(lhs), "+", std::move(rhs));
        })
        | (x3::lit("-") >> multiplicative_expr) ([](auto& ctx) {
            auto rhs = std::move(_attr(ctx).second);
            auto& lhs = _val(ctx);
            _val(ctx) = std::make_unique<BinaryExpr>(std::move(lhs), "-", std::move(rhs));
        })
    )
    ;

BOOST_SPIRIT_DEFINE(primary_expr, unary_expr, multiplicative_expr, additive_expr);

2. 避免左递归陷阱 #

Spirit X3的PEG语法天然不支持左递归，但通过*(...)重复结构可模拟左结合的二元运算符——比如additive_expr定义为multiplicative_expr >> *(op >> multiplicative_expr)，能正确解析a + b - c这类嵌套表达式，自动按左结合构造AST。

3. 语义动作的正确用法 #

语义动作仅需负责把解析到的运算符和操作数组装成AST节点，无需手动传递值——X3的_val和_attr会自动处理上下文的值传递。你之前怀疑的“手动传值”是多余的，问题根源在规则结构而非语义动作。

验证方法 #

用嵌套表达式测试，比如1 + 2 * 3 - 4，解析后应生成正确AST：((1 + (2*3)) -4)。若仍失败，检查：

• 规则的优先级分层是否正确
• 语义动作中_val和_attr的引用是否正确
• 是否遗漏括号表达式支持（括号是强制改变优先级、实现嵌套解析的关键）

内容的提问来源于stack exchange，提问作者Daniel Dokipen Elliott