Разбор лямбды в стиле haskell в antlr - PullRequest
Новая
       5

Разбор лямбды в стиле haskell в antlr

0 голосов
/ 05 декабря 2018

Я пытаюсь разобрать язык, похожий на haskell, используя antlr4, и я застрял с лямбдами.В haskell лямбды можно смешивать с операторами.Таким образом, с учетом операторов >>=, + и синтаксиса лямбда '\\' args* '->' expr, следующее выражение будет valid : 

a >>= \a -> b >>= \b -> Just(a + b)

, и оно должно быть проанализировано в следующем AST: 

  >>=
 /   \
a     ->
     /  \
    a   >>=
       /   \
      b    ->
          /  \
         b   Just
              |
              +
             / \
            a   b

Таким образом, я могу придумать два способа структурирования грамматики для этого типа синтаксиса.

Первый - поместить лямбда-выражение в верхнее правило выражения, среди которых есть if s идругие синтаксические конструкции: 

grammar Test;

root
    : expr0 EOF
    ;

expr0
    : '\\' ID '->' expr0
    | expr1
    ;

expr1
    : expr2 ('>>=' expr2)*
    ;

expr2
    : expr3 ('+' expr3)*
    ;

expr3
    : '(' expr0 ')'
    | ID ('(' expr0 ')')?
    ;

Эта грамматика не может проанализировать вышеприведенное выражение.Вокруг лямбды необходимо добавить парены: a >>= (\a -> b >>= (\b -> Just(a + b))).Хотя я понимаю, почему требуются парены, такое поведение довольно неудобно.

Второй подход заключается в том, чтобы поместить лямбду в последнее правило выражения, среди литералов и вложенных выражений: 

grammar Test;

root
    : expr0 EOF
    ;

expr0
    : expr1 ('>>=' expr1)*
    ;

expr1
    : expr2 ('+' expr2)*
    ;

expr2
    : '(' expr0 ')'
    | ID ('(' expr0 ')')?
    | '\\' ID '->' expr0
    ;

Эта грамматика принимает мое выражение, однако она содержит неоднозначность, потому что a >>= \a -> b >>= \b -> Just(a + b) может быть проанализирован как a >>= \a -> (b >>= \b) -> Just(a + b) или как a >>= \a -> (b >>= \b -> Just(a + b)).

Так что мой вопрос, как правильно реализовать этот вид грамматики?

...