ANTLR грамматическая ошибка

Question

Я пытаюсь собрать компилятор C--, используя ANTLR 3.4.

Полный набор грамматики, перечисленной здесь,

program         : (vardeclaration | fundeclaration)*                    ;
vardeclaration  : INT ID (OPENSQ NUM CLOSESQ)? SEMICOL  ;

fundeclaration  : typespecifier ID OPENP params CLOSEP compoundstmt     ;
typespecifier   : INT | VOID                                            ;
params          : VOID | paramlist                                      ;
paramlist       : param (COMMA param)*                                  ;
param           :  INT ID (OPENSQ CLOSESQ)?         ;

compoundstmt    : OPENCUR vardeclaration* statement* CLOSECUR           ;
statementlist   : statement*                                            ;

statement       : expressionstmt | compoundstmt | selectionstmt | iterationstmt | returnstmt;
expressionstmt  : (expression)? SEMICOL;
selectionstmt   : IF OPENP expression CLOSEP statement (options {greedy=true;}: ELSE statement)?;
iterationstmt   : WHILE OPENP expression CLOSEP statement;
returnstmt      : RETURN (expression)? SEMICOL;

expression      : (var EQUAL expression) | sampleexpression;
var             : ID ( OPENSQ expression CLOSESQ )? ;

sampleexpression: addexpr ( ( LOREQ | LESS | GRTR | GOREQ | EQUAL | NTEQL) addexpr)?;
addexpr         : mulexpr ( ( PLUS | MINUS ) mulexpr)*;
mulexpr         : factor  ( ( MULTI | DIV  ) factor )*; 

factor          : ( OPENP expression CLOSEP ) | var | call  | NUM;
call            : ID OPENP arglist? CLOSEP;
arglist         : expression ( COMMA expression)*;

Использовал следующие правила лексера,

ELSE    : 'else'    ;
IF      : 'if'      ;
INT     : 'int'     ;
RETURN  : 'return'  ;
VOID    : 'void'    ;
WHILE   : 'while'   ;

PLUS    : '+' ;
MINUS   : '-' ;
MULTI   : '*' ;
DIV     : '/' ;

LESS    : '<'  ;
LOREQ   : '<=' ;
GRTR    : '>'  ;
GOREQ   : '>=' ;

EQUAL   : '==' ;
NTEQL   : '!=' ;
ASSIGN  : '='  ;

SEMICOL : ';' ;
COMMA   : ',' ;

OPENP   : '(' ;
CLOSEP  : ')' ;
OPENSQ  : '[' ;
CLOSESQ : ']' ;
OPENCUR : '{' ;
CLOSECUR: '}' ;

SCOMMENT: '/*' ;
ECOMMENT: '*/' ;


ID  : ('a'..'z' | 'A'..'Z')+/*(' ')*/ ;
NUM : ('0'..'9')+ ;
WS  : (' ' | '\t' | '\n' | '\r')+ {$channel = HIDDEN;};
COMMENT: '/*' .* '*/' {$channel = HIDDEN;};

Но я пытаюсь сохранить это, выдает ошибку,

error(211): /CMinusMinus/src/CMinusMinus/CMinusMinus.g:33:13: [fatal] rule expression has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.
 |---> expression       : (var EQUAL expression) | sampleexpression;

1 error

Как я могу решить эту проблему?

Answer 1

Как уже упоминалось: ваше правило грамматики expression неоднозначно: обе альтернативы в этом правиле начинаются или могут быть var.

Вам необходимо немного "помочь" вашему анализатору.Если при синтаксическом анализе можно увидеть var, за которым следует EQUAL, ему следует выбрать альтернативу 1, а также альтернативу 2. Это можно сделать с помощью синтаксического предиката (часть (var EQUAL)=> в правиле ниже).

expression
 : (var EQUAL)=> var EQUAL expression
 |               sampleexpression
 ;

Подробнее о предикатах в этом разделе вопросов и ответов: Что такое «семантический предикат» в ANTLR?

Answer 2

Проблема заключается в следующем:

expression      : (var EQUAL expression) | sampleexpression;

, где вы начинаете с var или sampleexpression. Но sampleexpression можно уменьшить до var, выполнив sampleexpression->addExpr->MultExpr->Factor->var

Так что нет способа найти предикат k-длины для компилятора.

Вы можете, как предложено в сообщении об ошибке, установить backtrack=true, чтобы увидеть, решает ли это вашу проблему, но это может привести не к AST-парсетам, которые вы ожидаете, а также может быть медленным при особых условиях ввода. Вы также можете попытаться изменить свою грамматику, чтобы избежать таких рекурсий.