Парсер рекурсивного спуска для исчисления конструкций

Question

Я реализовал проверку типов и редукцию исчисления конструкций в Haskell с помощью простого монадического парсера, используя Мегапарсек . Теперь я хочу улучшить его, чтобы он мог распознать этот синтаксический ярлык:

∀(x:A)->B (with x not free in B)  =  A -> B

Грамматика для этого синтаксиса следующая:

<expr>
    = "(" <expr> ")"
    | <expr> <expr>
    | "λ" "(" <name> ":" <expr> ")" "→" <expr>
    | "∀" "(" <name> ":" <expr> ")" "→" <expr>
    | <expr> "→" <expr>
    | <name>
    | "*"

<name> = [_A-Za-z][_0-9A-Za-z]*

Мой текущий синтаксический анализатор использует этот вариант без рекурсии слева (без ярлыка):

<expr>
    = "(" <appl> ")"
    | "λ" "(" <name> ":" <appl> ")" "→" <appl>
    | "∀" "(" <name> ":" <appl> ")" "→" <appl>
    | <name>
    | "*"

<appl> = <expr>+

<name> = [_A-Za-z][_0-9A-Za-z]*

Ранее упомянутый ярлык является леворекурсивным. Я понятия не имею, как преобразовать его в правильно-рекурсивную грамматику, чтобы он мог обрабатываться обычным парсером рекурсивного спуска.

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

Answer 1

Ответ был очевиден после небольшого перерыва. Используйте точно такой же трюк, который мы сделали на <appl>, и расширите его следующим образом:

<expr>
    = "(" <appl> ")"
    | "λ" "(" <name> ":" <appl> ")" "→" <appl>
    | "∀" "(" <name> ":" <appl> ")" "→" <appl>
    | <name>
    | "*"

<appl> = <expr>+ ("→" <appl>)?

<name> = [_A-Za-z][_0-9A-Za-z]*

Я оставлю вопрос открытым, если он кому-нибудь поможет.