Eleminating left recursion in parser rule of spirit x3

Question

I am currently stuck with a rule I am trying to parse using boost spirit x3. Here is the EBNF(using the % operator from spirit for lists) for what I am trying to parse:

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

using boost spirit x3, I am trying to parse into the following struct/variant:

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_;
    };

I have a live example of what I am currently trying here, which is not working, I also tried to change the order of the variant parser, which doesn't help, I get endless recursion, or not the behavior I would expect(or wish).

Can anybody help me debugging this parser?

I think I have some type of left-recursion in the parser, is there a chance to avoid this or is there no chance to rewrite the grammar? Is this grammar even parseable with boost spirit x3?

EDIT:

I managed to eliminate the left recursion in this grammar. Now the grammar is the following:

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

but now there is the next problem, how can I make boost spirit x3 to parse these rules into the given structs? I cannot imagine what the A or the one_arg_lambda parsers are returning now, the one_arg_lambda parser should parse into a LambdaType struct, but depending on what A parses into that's not necessary true now. So the question is now, how can I get a non-left recursive parser, which parses the grammar above into my structs using boost-spirit-x3?

EDIT II:

I would like => to be right associative so foo => bar => baz => baham
means foo => (bar => (baz => bahama))

Can you give an example of the structure ? That would make it easier to understand the grammar correctly. — Arunmu, Oct 14 '16 at 10:57
What do you want `foo => bar => baz` to mean? `( foo => bar ) => baz` or `foo => ( bar => baz )`? — llonesmiz, Oct 15 '16 at 10:15
[This](http://melpon.org/wandbox/permlink/Nnus3lsPnDDFd4AO) is my approach. If nobody else writes an answer (feel free to use this example as a basis if you find it useful) I'll write one when the bounty expires. — llonesmiz, Oct 15 '16 at 10:50
Thank you very much, I will play a little with this approach, I am thankfull for any answer, currently I am parsing in different structs, which is horrible for my ast — Exagon, Oct 15 '16 at 11:03
@jv_ I don't think anybody else will answer this question, so if you would like to earn the bounty, feel free to write an answer, or just provide your approche as an answer, so I can give you the bounty — Exagon, Oct 18 '16 at 09:50
The problem is that I don't want the bounty, otherwise I would have written the answer already. — llonesmiz, Oct 18 '16 at 09:56

score 1 · Accepted Answer · answered Jan 09 '17 at 12:42

I solved this problem and the solution was incredibly easy. The trick is to change the grammar, so I dont have a left recursion, and it parses nice into my structs.

so I changed

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

to

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

this second grammar descripes the exaclty same language, but without left recursion, and without changing the structure of the grammar. This was actualy luck and doesnt work for every grammar obviously.

Eleminating left recursion in parser rule of spirit x3

1 Answers1

Linked