消除spirit x3解析器规则中的左递归

Question

我目前卡住了一个规则，我试图使用boost spirit x3解析。以下是我试图解析的EBNF(使用来自spirit的%操作符):

type ::= class_type | lambda_type
lambda_type ::= more_arg_lambda | one_arg_lambda
more_arg_lambda ::= "(", type%",", ")", "=>", type
one_arg_lambda ::= type, "=>", type  <- here is the left recursion
class_type ::= identifier%"::", ["<", type%",", ">"]

使用boost spirit x3，我试图解析为以下结构体/变体:

typedef x3::variant<
        nil,
        x3::forward_ast<LambdaType>,
        x3::forward_ast<ClassType>
    > Type;
struct LambdaType {
        std::vector<Type> parameters_;
        Type return_type_;
    };
struct ClassType{
        std::vector<std::string> name_; 
        std::vector<Type> template_args_;
    };

我有一个我目前在这里尝试的实例，这是不工作的，我还试图改变变量解析器的顺序，这没有帮助，我得到无尽的递归，或者不是我期望(或希望)的行为。

谁能帮我调试这个解析器?

我认为我在解析器中有某种类型的左递归，是否有机会避免这种情况或没有机会重写语法?这个语法甚至可以用boost spirit x3解析吗?

编辑:

我设法消除了这个语法中的左递归。现在语法如下:

type ::= class_type | lambda_type
    lambda_type ::= more_arg_lambda | one_arg_lambda
    more_arg_lambda ::= "(", type%",", ")", "=>", type
    one_arg_lambda ::= class_type, "=>" type, A
                       | "(", type%",", ")", "=>", type, "=>", type, A
    class_type ::= identifier%"::", ["<", type%",", ">"]
    A::= "=>", type, A | eps

但现在有下一个问题，我如何使boost spirit x3解析这些规则到给定的结构?我无法想象A或one_arg_lambda解析器现在返回的是什么，one_arg_lambda解析器应该解析成LambdaType结构，但取决于A解析成什么，现在不一定是真的。所以现在的问题是，如何获得一个非左递归解析器，它使用boost-spirit-x3将上面的语法解析为我的结构?

编辑II:

我希望=>是右结合的所以foo => bar => baz => baham
表示foo => (bar => (baz => bahama))

Answer 1

我解决了这个问题，而且这个解决方案非常简单。诀窍是改变语法，这样我就没有左递归了，它可以很好地解析到我的结构体中。

所以我改变了

type ::= class_type | lambda_type
lambda_type ::= more_arg_lambda | one_arg_lambda
more_arg_lambda ::= "(", type%",", ")", "=>", type
one_arg_lambda ::= type, "=>", type  <- here is the left recursion
class_type ::= identifier%"::", ["<", type%",", ">"]

type ::= class_type | lambda_type
lambda_type ::= more_arg_lambda | one_arg_lambda
more_arg_lambda ::= "(", type%",", ")", "=>", type
one_arg_lambda ::= class_type, "=>", type  <- here is the magic trick
class_type ::= identifier%"::", ["<", type%",", ">"]

第二个语法描述了完全相同的语言，但没有左递归，也没有改变语法的结构。这其实是一种运气，显然并不是对所有语法都适用。