Как исправить ошибку в левой рекурсии, используемой с семантическими предикатами? - PullRequest
Новая
       44

Как исправить ошибку в левой рекурсии, используемой с семантическими предикатами?

0 голосов
/ 29 мая 2019

Я хотел бы проанализировать два типа выражения с логическим:
- первым будет выражение init с логическим выражением типа: init : false
- и последнее будет производным выражением с логическим выражением типа: derive : !express or (express and (amount >= 100))

Моя идея состоит в том, чтобы поместить семантические предикаты в набор правил, цель в том, что когда я разбираю логическое выражение, начинающееся со слова 'init', то нужно перейти только к одному предложенному альтернативному правилу: boolliteral , последняя альтернатива в boolExpression, И если это выражение начинается со слова «производная», то оно может иметь доступ ко всем альтернативам boolExpression .

Я знаю, что мог бы создать два типа boolExpression без семантических предикатов, таких как boolExpressionInit и boolExpressionDerive ... Но я хотел бы попробовать свою идею, если бы он мог работать только с одним boolExpression с семантическими предикатами.

Вот моя грамматика 

grammar TestExpression;

@header
{
package testexpressionparser;
}

@parser::members {
                    int vConstraintType;
                 }

/* SYNTAX RULES */
textInput       : initDefinition 
                | derDefinition ;

initDefinition  : t=INIT {vConstraintType = $t.type;} ':' boolExpression ;

derDefinition   : t=DERIVE {vConstraintType = $t.type;} ':' boolExpression ;

boolExpression  : {vConstraintType != INIT || vConstraintType == DERIVE}? boolExpression (boolOp|relOp) boolExpression 
                | {vConstraintType != INIT || vConstraintType == DERIVE}? NOT boolExpression
                | {vConstraintType != INIT || vConstraintType == DERIVE}? '(' boolExpression ')' 
                | {vConstraintType != INIT || vConstraintType == DERIVE}? attributeName
                | {vConstraintType != INIT || vConstraintType == DERIVE}? numliteral
                | {vConstraintType == INIT || vConstraintType == DERIVE}? boolliteral
                ;

boolOp          : OR | AND ;
relOp           : EQ | NEQ | GT | LT | GEQT | LEQT ;
attributeName   : WORD;
numliteral      : intliteral | decliteral;
intliteral      : INT ;
decliteral      : DEC ;
boolliteral     : BOOLEAN;


/* LEXICAL RULES */
INIT            : 'init';
DERIVE          : 'derive';
BOOLEAN         : 'true' | 'false' ;
BRACKETSTART    : '(' ;
BRACKETSTOP     : ')' ;
BRACESTART      : '{' ;
BRACESTOP       : '}' ;
EQ              : '=' ;
NEQ             : '!=' ;
NOT             : '!' ;
GT              : '>' ;
LT              : '<' ;
GEQT            : '>=' ;
LEQT            : '<=' ;
OR              : 'or' ;
AND             : 'and' ;
DEC             : [0-9]* '.' [0-9]* ;
INT             : ZERO | POSITIF;
ZERO            : '0';
POSITIF         : [1-9] [0-9]* ;
WORD            : [a-zA-Z] [_0-9a-zA-Z]* ;
WS              : (SPACE | NEWLINE)+ -> skip ;
SPACE           : [ \t] ;                       /* Space or tab */
NEWLINE         : '\r'? '\n' ;                  /* Carriage return and new line */

Я за исключением того, что грамматика будет работать успешно, но я получаю следующее: "ошибка (119): TestExpression.g4 ::: Следующие наборы правил взаимно леворекурсивны [boolExpression]
1 ошибка BUILD FAIL "

1 Ответ

0 голосов
/ 30 мая 2019

Очевидно, что поддержка ANTLR4 для (прямой) левой рекурсии не работает, когда предикат появляется перед вызовом леворекурсивного правила. Таким образом, вы можете исправить ошибку, переместив предикат после первого boolExpression в леворекурсивных альтернативах.

Тем не менее, кажется, что предикаты на самом деле не нужны в первую очередь - по крайней мере, не в том примере, который вы нам показали (или в том, что перед вашим редактированием, насколько я могу судить). Поскольку boolExpression с типом ограничения INIT, по-видимому, может соответствовать только boolLiteral, вы можете просто изменить initDefinition следующим образом: 

initDefinition  : t=INIT ':' boolLiteral ;

Тогда boolExpression всегда будет иметь тип ограничения DERIVE, и предикаты больше не нужны.

Как правило, если вы хотите разрешить разные альтернативы в нетерминальном x в зависимости от того, был ли он вызван y или z, вам просто нужно иметь несколько версий x, а затем вызвать одну из y и другой от z. Обычно это намного меньше хлопот, чем засорение кода действиями и предикатами.

Точно так же может иметь смысл иметь правило, которое соответствует больше, чем должно, а затем обнаруживать недопустимые выражения на более позднем этапе, вместо того, чтобы пытаться отклонить их на уровне синтаксиса. В частности, новички часто пытаются написать грамматики, которые допускают только хорошо типизированные выражения (отклоняя что-то вроде 1+true с синтаксической ошибкой) и которые никогда не сработают.

...