如何替换boost spirit x3中的左递归？

Question

我目前正在尝试使用 boost spirit x3 解析递归表达式，例如 ***a 和 a***。

所以我定义了我的抽象语法树如下：

namespace client {
    namespace ast {

        struct pointer;

        struct type : x3::variant<
                char, x3::forward_ast<pointer>
        > {
            using base_type::base_type;
            using base_type::operator=;
        };

        struct pointer{
            type t;
        };
    }
}

BOOST_FUSION_ADAPT_STRUCT(client::ast::pointer,
                          t
)

这将导致嵌套指针具有最后一个类型的字符。

如果我尝试解析 ***a，我可以简单地定义以下规则：

x3::rule<class t1, ast::type> type_rule = "type_rule";
auto simple_type_rule = x3::rule<class t1, char> {} = x3::lower;
auto pointer_type_rule = x3::rule<class t1, ast::pointer> {} = x3::lit('*') > type_rule;
auto type_rule_def = x3::rule<class t1, ast::type> {} = pointer_type_rule | simple_type_rule;

BOOST_SPIRIT_DEFINE(type_rule);

解析成功:)

现在我想解析像 a***.

这样的表达式

问题 - 我认为 - 是相关规则是递归的，由于计算器溢出，以分段错误结束。

所以为了消除左递归，我想到了使用文法像这样：

auto simple_type_rule = x3::rule<class t1, char> {} = x3::lower;
x3::rule<class t1, x3::unused_type> pointer_suffix = "pointer_suffix";
auto pointer_suffix_def = (x3::lit('*') > pointer_suffix) | x3::eps;
auto type_rule = x3::rule<class t1, ast::type> {} =  simple_type_rule > pointer_suffix;

BOOST_SPIRIT_DEFINE(pointer_suffix);

解析成功，但您可能已经注意到，我使用了 unused_type，因为我不知道，我可能 return。一般来说，我希望它像前面的例子一样嵌套。我是否必须 return 一个虚拟结构的 std::vector，我必须将其转换通过语义操作到我想要的结构？或者我应该尝试使用 x3::with 来解决它吗？我觉得有点奇怪。

推荐的方法是什么？

感谢

CSpille

Answer 1

PEG 在这里不太适合。你基本上可以做到，但效率很低。我会毫不犹豫地将我的 AST 更改为简单地用整数表示间接级别。

如果你真的想要，请继续阅读

相反，在这里您可以非常轻松地使用语义操作，每次我们遇到尾随的“*”时，它都会用指针包装已经解析的类型。

执行此操作的语义操作将简单地将指针包装版本的规则属性分配回自身：

auto wrap_pointer = [](auto& ctx) {
    _val(ctx) = ast::pointer { _val(ctx) };
};

你可以使用：

auto type_rule = identifier >> *(x3::lit('*') [ wrap_pointer ]);

完整演示

我更改了一些名称，我/认为/我可能会交换指针规则与类型规则的术语（*a 是一个表达式，a* 是一种类型）。

但是，代码有效并且应该是不言自明的。我什至加入了调试可视化工具：

static inline std::ostream& operator<<(std::ostream& os, type const& t) {
    struct {
        std::ostream& _os;
        void operator()(ast::type const& t) const { boost::apply_visitor(*this, t); }
        void operator()(ast::identifer identifier) const { _os << identifier; }
        void operator()(ast::pointer const& p) const { _os << "pointer("; operator()(p.t); _os << ')'; }
    } vis{os};
    return vis(t), os;
}

这样就可以看到解析结果了

Live On Coliru

//#define BOOST_SPIRIT_X3_DEBUG
#include <iostream>
#include <iomanip>
#include <boost/fusion/adapted.hpp>
#include <boost/spirit/home/x3.hpp>
#include <boost/spirit/home/x3/support/ast/variant.hpp>

namespace x3 = boost::spirit::x3;

namespace ast {
    using identifer = char;

    struct pointer;

    struct type : x3::variant<identifer, x3::forward_ast<pointer>> {
        using base_type::base_type;
        using base_type::operator=;
    };

    struct pointer {
        type t;
    };

    static inline std::ostream& operator<<(std::ostream& os, type const& t) {
        struct {
            std::ostream& _os;
            void operator()(ast::type const& t) const { boost::apply_visitor(*this, t); }
            void operator()(ast::identifer identifier) const { _os << identifier; }
            void operator()(ast::pointer const& p) const { _os << "pointer("; operator()(p.t); _os << ')'; }
        } vis{os};
        return vis(t), os;
    }
}

BOOST_FUSION_ADAPT_STRUCT(ast::pointer, t)

namespace parser {
    auto const identifier = x3::rule<class t1, ast::identifer> {"identifier"} = x3::lower;

    x3::rule<class t2, ast::type> pointer_expression = "pointer_expression";
    auto pointer_expression_def 
        = (x3::rule<class t1, ast::pointer> {"indirection"} = '*' > pointer_expression) | identifier;

    BOOST_SPIRIT_DEFINE(pointer_expression)

    x3::rule<class t3, ast::type, true> type_rule = "type_rule";
    auto wrap_pointer = [](auto& ctx) {
        _val(ctx) = ast::pointer { _val(ctx) };
    };
    auto type_rule_def = identifier >> *(x3::lit('*') [ wrap_pointer ]);

    BOOST_SPIRIT_DEFINE(type_rule)
}

int main() {
    auto run = [](std::initializer_list<char const*> inputs, auto rule, auto title) {
        for (std::string const input : inputs) {
            std::cout << "====== " << title << ": " << std::quoted(input) << " ======\n";
            auto f = begin(input), l = end(input);
            ast::type t;
            if (parse(f, l, rule, t)) {
                std::cout << "Parsed: " << t << "\n";
            } else {
                std::cout << "Failed\n";
            }

            if (f!=l) {
                std::cout << "Remaining input: " << std::quoted(std::string(f,l)) << "\n";
            }
        }
    };

    run({"", "a", "*a", "**a"}, parser::pointer_expression, "expression");
    run({"", "b", "b*", "b**"}, parser::type_rule, "type");
}

版画

====== expression: "" ======
Failed
====== expression: "a" ======
Parsed: a
====== expression: "*a" ======
Parsed: pointer(a)
====== expression: "**a" ======
Parsed: pointer(pointer(a))
====== type: "" ======
Failed
====== type: "b" ======
Parsed: b
====== type: "b*" ======
Parsed: pointer(b)
====== type: "b**" ======
Parsed: pointer(pointer(b))

如何替换boost spirit x3中的左递归？

How to replace left recursion in boost spirit x3?

c++

boost

abstract-syntax-tree

boost-spirit

boost-spirit-x3

如果你真的想要，请继续阅读

完整演示