Элементарная левая рекурсия в правиле парсера духа x3

В настоящее время я придерживаюсь правила, которое я пытаюсь проанализировать, используя 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%",", ">"]

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

У меня есть живой пример того, что я сейчас пытаюсь здесь, который не работает, я также попытался изменить порядок парсера варианта, который не помогает, Я получаю бесконечное отступление, или не поведение, которое я ожидал бы (или пожелал). Может кто-нибудь помочь мне отладить этот парсер? Я думаю, что в парсере есть какая-то левая рекурсия, есть ли шанс избежать этого или нет возможности переписать грамматику? Является ли этот грамм равным даже с повышающим духом x3?

EDIT:

Мне удалось выровнять левую рекурсию в этой грамматике. Теперь следующая грамматика:

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 x3 анализировать эти правила в данных структурах? Я не могу себе представить, что теперь парсеры A или one_arg_lambda возвращаются, парсер one_arg_lambda должен анализироваться в структуру LambdaType, но в зависимости от того, что A анализирует на то, что теперь не требуется true. Итак, вопрос в том, как я могу получить не левый рекурсивный синтаксический анализатор, который анализирует грамматику выше в мои структуры, используя boost-spirit-x3?

ИЗМЕНИТЬ II:

Мне хотелось бы, чтобы => был правильным ассоциативным, поэтому foo => bar => baz => baham
означает foo => (bar => (baz => bahama))

Ответы

Ответ 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%",", ">"]

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

эта вторая грамматика описывает тот же самый язык, но без левой рекурсии и без изменения структуры грамматики. Это было действительно удачей и не работает для каждой грамматики.