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

Я хотел бы проанализировать два типа выражения с логическим значением:
- первое было бы выражением инициализации с логическим значением, например: 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 "


java antlr4 left-recursion
person talohsa    schedule 29.05.2019    source источник
comment
Сообщение об ошибке кажется немного вводящим в заблуждение (утверждается, что существует взаимная левая рекурсия, когда левая рекурсия на самом деле прямая), но похоже, что поддержка левой рекурсии ANTLR4 не работает с предикатом. Можете ли вы объяснить, для чего нужен предикат и когда vConstraintType меняет свое значение? Также опубликуйте минимально воспроизводимый пример.   -  person sepp2k    schedule 29.05.2019
comment
@ sepp2k, я отредактировал свой пост с лучшим объяснением того, что я хотел бы попробовать сделать, и с минимальным воспроизводимым примером, как вы просили.   -  person talohsa    schedule 30.05.2019
comment
Пробовали ли вы переместить семантические предикаты с самого начала во что-то другое? Кроме того, я думаю, что его можно переписать вообще без семантических предикатов.   -  person Ivan Kochurkin    schedule 30.05.2019

Ответы (1)


arrow_upward
0
arrow_downward

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

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

initDefinition  : t=INIT ':' boolLiteral ;

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

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

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

person sepp2k    schedule 30.05.2019
comment
Это правда, что я мог бы сделать просто как ваш пример без предикатов. Но я ограничил тип ограничения init в моем примере, а также упростил правило boolExpression. На самом деле, я пытаюсь разобрать 4 типа ограничений с разными типами логических выражений. Вот почему я пытался использовать семантические предикаты только в одном правиле boolExpression, которые описывают несколько вариантов логического выражения, чем писать несколько версий boolExpression для каждого ограничения в разных правилах. - person talohsa; 30.05.2019
comment
Но вы правы, писать код с действиями и предикатами хлопотно... Я посмотрю, читабелен мой код или нет. В любом случае, вы мне очень помогли, и теперь это работает. Большое спасибо. - person talohsa; 30.05.2019