11

我目前坚持使用 boost spirit x3 解析的规则。这是我要解析的 EBNF（使用精神中的 % 运算符作为列表）：

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的是什么，解析器应该解析成一个结构，但取决于解析成的内容，现在这不是必需的。所以现在的问题是，我怎样才能得到一个非左递归解析器，它使用 boost-spirit-x3 将上面的语法解析成我的结构？one_arg_lambdaone_arg_lambdaLambdaTypeA

编辑二：

我想=>成为正确的联想所以foo => bar => baz => baham
意味着foo => (bar => (baz => bahama))

4

1 回答 1

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%",", ">"]

这第二种文法描述了完全相同的语言，但没有左递归，也没有改变文法的结构。这实际上是运气，显然不适用于每种语法。

于 2017-01-09T12:42:37.710 回答