Почему моя грамматика работает для операторов типа *, -, /, но не +?

Question

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

Вот связанная часть моей грамматики:

SUBTRACT: '-';
PLUS: '+';
DIVIDE: '/';
MULTIPLY: '*';

expr: 
      (
        IDENTIFIER 
        | INTEGER 
        | STRING 
        | TRUE 
        | FALSE
      )
      (
        PLUS expr 
        | SUBTRACT expr 
        | MULTIPLY expr 
        | DIVIDE expr 
        | LESS_THAN expr 
        | LESS_THAN_OR_EQUAL expr 
        | EQUALS expr
      )*
      ;

INTEGER: ('0'..'9')*;
IDENTIFIER: ('a'..'z' | 'A'..'Z' | '_') ('a'..'z' | 'A'..'Z' | '0'..'9' | '_')*;

Затем, когда я пытаюсь сделать что-то вроде

x*1

Это отлично работает. Однако, когда я пытаюсь сделать что-то вроде

x+1

Я получаю сообщение об ошибке:

MismatchedTokenException: несоответствующий ввод '+' ожидающий '\u001C'

Я занимался этим некоторое время, но не понимаю, почему это работает с *, - и /, но не +. У меня точно такой же код для всех них.

Редактировать: если я переупорядочу его и поставлю SUBTRACT выше PLUS, символ + теперь будет работать, но символ - не будет. Почему Antlr беспокоиться о порядке вещей такого рода?

Answer 1

Избегание левой рекурсии (в грамматике выражения) обычно выполняется следующим образом:

grammar Expr;

parse
  :  expr EOF
  ;

expr
  :  equalityExpr
  ;

equalityExpr
  :  relationalExpr (('==' | '!=') relationalExpr)*
  ;

relationalExpr
  :  additionExpr (('>=' | '<=' | '>' | '<') additionExpr)*
  ;

additionExpr
  :  multiplyExpr (('+'| '-') multiplyExpr)*
  ;

multiplyExpr
  :  atom (('*' | '/') atom)*
  ;

atom
  :  IDENTIFIER
  |  INTEGER
  |  STRING
  |  TRUE
  |  FALSE
  |  '(' expr ')'
  ;

// ... lexer rules ...

Например, вход A+B+C будет проанализирован следующим образом:

Также посмотрите этот связанный ответ: ANTLR: Есть простой пример?

Answer 2

Я исправил это, сделав новое правило для части в конце, которое я сделал из удаления левой рекурсии:

expr: 
      (
        IDENTIFIER 
        | INTEGER 
        | STRING 
        | TRUE 
        | FALSE
      ) lr*
      ;

lr:         PLUS expr 
        | SUBTRACT expr 
        | MULTIPLY expr 
        | DIVIDE expr 
        | LESS_THAN expr 
        | LESS_THAN_OR_EQUAL expr 
        | EQUALS expr;