Левое рекурсивное правило Antlr4 содержит леворекурсивную альтернативу, за которой может следовать пустая строка

Поэтому я определил грамматику для анализа синтаксиса языка C:

grammar mygrammar;

program
: (declaration)*
  (statement)*
  EOF
;

declaration
: INT ID '=' expression ';'
;

assignment
: ID '=' expression ';'
;

expression
: expression (op=('*'|'/') expression)*
| expression (op=('+'|'-') expression)*
| relation
| INT
| ID
| '(' expression ')'
;

relation
: expression (op=('<'|'>') expression)*
;

statement
: expression ';'
| ifstatement
| loopstatement
| printstatement
| assignment
;

ifstatement
: IF '(' expression ')' (statement)* FI ';'
;

loopstatement
: LOOP '(' expression ')' (statement)* POOL ';'
;

printstatement
: PRINT '(' expression ')' ';'
;

IF : 'if';
FI : 'fi';
LOOP : 'loop';
POOL : 'pool';
INT : 'int';
PRINT : 'print';
ID : [a-zA-Z][a-zA-Z0-9]*;
INTEGER : [0-9]+;
WS : [ \r\n\t] -> skip;

И я могу разобрать простой тест следующим образом:

int i = (2+3)*3/2*(3+36);
int j = i;
int k = 2*1+i*3;
if (k > 2)
  k = k + 1;
  i = i / 3;
  j = j / 3;
fi;
loop (i < 10)
  i = i + 1 * (i+k);
  j = (j + 1) * (j-k);
  k = i + j;
  print(k);
pool;

Однако, когда я хочу сгенерировать ANTLR Recogonizers в intelliJ, я получил эту ошибку:

sCalc.g4:19:0: выражение леворекурсивного правила содержит леворекурсивную альтернативу, за которой может следовать пустая строка

Интересно, это вызвано тем, что мой ID может быть пустой строкой?


antlr4 left-recursion
person RandomEli    schedule 26.09.2016    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Есть пара проблем с вашей грамматикой:

  • у вас есть INT в качестве альтернативы внутри expression, хотя вы, вероятно, хотите вместо этого INTEGER
  • нет необходимости делать expression (op=('+'|'-') expression)*: сойдет: expression op=('+'|'-') expression
  • ANTLR4 не поддерживает косвенные левые рекурсивные правила: вы должны включить relation внутри expression

Что-то вроде этого должно сделать это:

grammar mygrammar;

program
: (declaration)*
  (statement)*
  EOF
;

declaration
: INT ID '=' expression ';'
;

assignment
: ID '=' expression ';'
;

expression
: expression op=('*'|'/') expression
| expression op=('+'|'-') expression
| expression op=('<'|'>') expression
| INTEGER
| ID
| '(' expression ')'
;

statement
: expression ';'
| ifstatement
| loopstatement
| printstatement
| assignment
;

ifstatement
: IF '(' expression ')' (statement)* FI ';'
;

loopstatement
: LOOP '(' expression ')' (statement)* POOL ';'
;

printstatement
: PRINT '(' expression ')' ';'
;

IF : 'if';
FI : 'fi';
LOOP : 'loop';
POOL : 'pool';
INT : 'int';
PRINT : 'print';
ID : [a-zA-Z][a-zA-Z0-9]*;
INTEGER : [0-9]+;
WS : [ \r\n\t] -> skip;

Также нельзя сказать, что это (statement)* можно просто записать как statement*.

person Bart Kiers    schedule 27.09.2016
comment
Спасибо, это работает. Но я также хочу знать, как antlr4 может просто сопоставить от 0 до многих операторов, не перехватывая их группу, используя '()' - person RandomEli; 27.09.2016
comment
Эрр, я не понимаю. (a)* просто совпадает с a*. Если вам нужно повторить более 1 вещи, вам нужно заключить их в скобки: (a b)* (не то же самое, что a b*) - person Bart Kiers; 27.09.2016

arrow_upward
1
arrow_downward

Речь идет о ваших правилах expression и relation. Правило выражения может соответствовать relation в одном alt, что, в свою очередь, рекурсивно возвращается к expression. Правилу relation, кроме того, потенциально может ничего не соответствовать из-за (op=('<'|'>') expression)*

Лучший подход, вероятно, состоит в том, чтобы relation вызвать expression и удалить relation alt из expression. Затем используйте relation везде, где вы использовали expression сейчас. Это типичный сценарий в выражениях, начиная с операций с низким приоритетом в качестве правил верхнего уровня и переходя к правилам с более высоким приоритетом, в конечном итоге заканчивая простым правилом выражения (или подобным).

person Mike Lischke    schedule 27.09.2016