Антлр оставил рекурсивный

Question

Я пытаюсь преобразовать правила postfix, infix и prefix из scala в форме EBNF в ANTLR, но вижу ошибку, касающуюся левой рекурсии в правиле infixExpression.

Рассматриваемые правила:

public symbolOrID
:   ID
|   Symbol
;

public postfixExpression
:   infixExpression symbolOrID? -> ^(R__PostfixExpression infixExpression symbolOrID?)
;

public infixExpression
:   prefixExpression
|   infixExpression (symbolOrID infixExpression)? -> ^(R__InfixExpression infixExpression symbolOrID? infixExpression?)
;

public prefixExpression
:   prefixCharacter? simpleExpression -> ^(R__PrefixExpression prefixCharacter? simpleExpression)
;

public prefixCharacter
:   '-' | '+' | '~' | '!' | '#'
;

public simpleExpression
:   constant
;

Если я изменил правило infixExpression на:

public infixExpression
:   prefixExpression (symbolOrID infixExpression)? -> ^(R__InfixExpression prefixExpression symbolOrID? infixExpression?)
;

Тогда вместо этого он жалуется:

warning(200): Hydra.g3:108:26: Decision can match input such as "{ID, Symbol} {'!'..'#', '+', '-', '~'} String" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
warning(200): Hydra.g3:108:26: Decision can match input such as "{ID, Symbol} {'!'..'#', '+', '-', '~'} Number" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
warning(200): Hydra.g3:108:26: Decision can match input such as "{ID, Symbol} {'!'..'#', '+', '-', '~'} Boolean" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
warning(200): Hydra.g3:108:26: Decision can match input such as "{ID, Symbol} {'!'..'#', '+', '-', '~'} Regex" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
warning(200): Hydra.g3:108:26: Decision can match input such as "{ID, Symbol} {'!'..'#', '+', '-', '~'} Null" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input

Наконец, есть ли способ условно создатьузлы в AST, так что если только левая часть правила является истинной, то это не добавляет этот уровень в?Например:

conditional_or_expression:
    conditional_and_expression  ('||' conditional_or_expression)?
;

Допустим, я создаю грамматику, которая следует иерархии, например:

conditional_and_expression
  conditional_or_expression
    null_coalescing_expression

, если анализируемое выражение равно a || b, в настоящее время AST, которыйсоздан для этого выражения будет

conditional_and_expression
  conditional_or_expression

Как я могу получить его, чтобы он просто получил conditional_or_expression часть?

В JavaCC вы можете просто установить arity узла, например: #ConditionalOrExpression(>1)

РЕДАКТИРОВАТЬ: вчера вечером было немного поздно, инфиксное выражение теперь корректно изменено!

Окончательное редактирование: То, как я заставил его работать вВ конце были следующие правила:

public symbolOrID
:   ID
|   Symbol
;

public postfixExpression
:   infixExpression (symbolOrID^)?
;

public infixExpression
:   (prefixExpression symbolOrID)=> prefixExpression symbolOrID^ infixExpression
|   prefixExpression
;

public prefixExpression
:   prefixCharacter^ simpleExpression
|   simpleExpression
;

public prefixCharacter
:   '-' | '+' | '~' | '!' | '#'
;

public simpleExpression
:   constant
;

Answer 1

Darkzaelus писал:

Я пытаюсь преобразовать правила postfix, infix и prefix от scala в форме EBNF в ANTLR, но вижуошибка, связанная с левой рекурсией

Как я уже сказал в моем комментарии: в ваших правилах не осталось левой рекурсии.

Darkzaelus написал:

Как я могу получить его, чтобы он просто получал часть conditional_or_expression?

Я предполагаю, что вы используете интерпретатор или отладчик ANTLRWorks, вВ этом случае дерево:

conditional_and_expression
            \
  conditional_or_expression

отображается только так (отображается дерево разбора, а не AST).Если вы правильно преобразуете orExpression в AST, выражение a || b станет:

  ||
 /  \
a    b

(то есть || как корень, а a и b как потомокузлы)

Например, возьмите следующую грамматику:

grammar T;

options {
  output=AST;
}

parse
  :  expr EOF -> expr
  ;

expr
  :  or_expr
  ;

or_expr
  :  and_expr ('||'^ and_expr)*
  ;

and_expr
  :  add_expr ('&&'^ add_expr)*
  ;

add_expr
  :  atom (('+' | '-')^ atom)*
  ;

atom
  :  NUMBER
  |  '(' expr ')' -> expr
  ;

NUMBER : '0'..'9'+;

Если вы сейчас анализируете 12+34 с помощью синтаксического анализатора, сгенерированного из приведенной выше грамматики, ANTLRWorks (или Eclipse ANTLRIDE) покажет следующее дерево разбора:

, но это , а не AST, который создает анализатор.На самом деле AST выглядит так:

(то есть or_expr, and_expr "слоев" там , а не )

Darkzaelus писал:

К сожалению, это довольно важный, но ранний этап для языка, поэтому я вынужденхранить полную информацию о грамматике в тайне.

Нет проблем, но вы должны понимать, что люди не могут ответить на ваши вопросы должным образом, если вы скрываете важную информацию.Вам не нужно публиковать всю грамматику, но если вам нужна помощь с левой рекурсией, вы должны опубликовать (частичную) грамматику, которая фактически вызывает ошибки, о которых вы упомянули.Если я не могу воспроизвести его, его не существует!:)

Answer 2

Это производство:

infixExpr ::= PrefixExpr
            | InfixExpr id [nl] InfixExpr

Может быть переписано как

infixExpr ::= PrefixExpr
            | PrefixExpr id [nl] InfixExpr

На самом деле, держу пари, что это просто ошибка в грамматике. Давайте покажем пример, что это нормально. Давайте уменьшим (частично) кое-что с первой грамматикой, а затем попробуем вторую.

InfixExpr id [nl] InfixExpr                      
// Apply the second reduction to the first InfixExpr
InfixExpr id [nl] InfixExpr id [nl] InfixExpr
// Apply the first reduction to the (new) first InfixExpr
PrefixExpr id [nl] InfixExpr id [nl] InfixExpr
// Apply the first reduction to the new first InfixExpr
PrefixExpr id [nl] PrefixExpr id [nl] InfixExpr
// Apply the first reduction to the new first InfixExpr
PrefixExpr id [nl] PrefixExpr id [nl] PrefixExpr

Давайте уменьшим это со второй грамматикой:

PrefixExpr id [nl] InfixExpr                      
// Apply the second reduction to the first InfixExpr
PrefixExpr id [nl] PrefixExpr id [nl] InfixExpr
// Apply the first reduction to the new first InfixExpr
PrefixExpr id [nl] PrefixExpr id [nl] PrefixExpr

Как видите, в обоих случаях вы заканчиваете эквивалентными AST.