Блог

Недавно я работал над небольшой демонстрационной грамматикой выражений в Xtext:

Грамматика

 grammar org.example.expressions.Expressions with org.eclipse.xtext.common.Terminals

generate expressions "http://www.example.org/expressions/Expressions"

ExpressionsModel:
    elements =AbstractElement*;

AbstractElement:
    Variable | EvalExpression;

Variable:
    'var' name=ID '=' expression=Expression;

EvalExpression:
    'eval' expression=Expression;

/*-----------------------------------EXPRESSIONS-----------------------------------*/
//Note that expressions on the same precedence get grouped into a single rule, but not necessarily into the same AST node.
//Examples of this pattern are compound rules such as the AddOrSubExpression, or the ComparisonOrInExpression

Expression:
    ConditionalExpression;

ConditionalExpression returns Expression:
    OrExpression ({ConditionalExpression.condition=current} '?' trueExp=OrExpression ':' falseExp=OrExpression)*;

OrExpression returns Expression:
    AndExpression ({BinaryExpression.left=current} operator='||' right=AndExpression)*;

AndExpression returns Expression:
    BinOrExpression ({BinaryExpression.left=current} operator='amp;amp;' right=BinOrExpression)*;

BinOrExpression returns Expression:
    BinXorExpression ({BinaryExpression.left=current} operator='|' right=BinXorExpression)*;

BinXorExpression returns Expression:
    BinAndExpression ({BinaryExpression.left=current} operator='^' right=BinAndExpression)*;

BinAndExpression returns Expression:
    EqualityExpression ({BinaryExpression.left=current} operator='amp;' right=EqualityExpression)*;

EqualityExpression returns Expression:
    ComparisonOrInExpression ({BinaryExpression.left=current} operator=('==' | '!=') right=ComparisonOrInExpression)*;

ComparisonOrInExpression returns Expression:
    BitShiftExpression (({BinaryExpression.left=current} operator=('<' | '>' | '<=' | '>=') right=BitShiftExpression) // ComparisonExpression
    | ({InExpression.left=current} 'in' (right=BitShiftExpression | ('[' openRangeList =OpenRangeValue (','
    openRangeList =OpenRangeValue)* ']'))) // InExpression
    )*;

OpenRangeValue:
    lowBound=Expression ('..' highBound=Expression)?;

BitShiftExpression returns Expression:
    AddOrSubExpression ({BinaryExpression.left=current} operator=('<<' | '>>') right=AddOrSubExpression)*;

AddOrSubExpression returns Expression:
    MulOrDivExpression ({BinaryExpression.left=current} operator=(' ' | '-') right=MulOrDivExpression)*;

MulOrDivExpression returns Expression:
    PowExpression ({BinaryExpression.left=current} operator=('*' | '/' | '%') right=PowExpression)*;

PowExpression returns Expression:
    BitSliceExpression ({BinaryExpression.left=current} operator='**' right=BitSliceExpression)*;

BitSliceExpression returns Expression:
    FieldOperationExpression ({BitSliceExpression.operand=current} '[' highBound=Expression ':' lowBound=Expression ']')*;

FieldOperationExpression returns Expression:
    UnaryExpression (({CollectionAccess.operand=current} '[' index=Expression ']') // CollectionAccessExpression
    | ({FunctionCallExpression.targetObject=current} '.' name=ID '(' (params =Expression (','
    params =Expression)*)? ')') // FieldAccessFunction
    | ({FieldAccessExpression.targetObject=current} '.' fieldIdentifier=ID))*; // FieldAccessExpression

UnaryExpression returns Expression:
    PrimaryExpression
    | {UnaryExpression} operator=UnaryOperator operand=PrimaryExpression;

PrimaryExpression returns Expression:
    '(' Expression ')'
    | FunctionCallExpression
    | CompileHasExpression
    | StaticRefrencePathExpression
    | {Expression} NullRefrenceExperession
    | StringConstantExpression
    | BoolConstantExpression
    | IntConstantExpression;

FunctionCallExpression:
    name=ID '(' (params =Expression (',' params =Expression)*)? ')';

CompileHasExpression:
    'compile' 'has' staticRefPath=StaticRefrencePathExpression;

StaticRefrencePathExpression:
    (globalScope?='::')? (identifiers =ID ('::' identifiers =ID)*);

NullRefrenceExperession:
    'null';

IntConstantExpression:
    value=INT;

StringConstantExpression:
    value=STRING;

BoolConstantExpression:
    value=BoolValue;

/*-----------------------------------ENUM_TERMINALS-----------------------------------*/
enum UnaryOperator:
    ARITH_NEGATE='-' | BOOL_NEGATE='!' | BIN_NEGATE='~' | BIN_AND='amp;' | BIN_OR='|' | BIN_XOR='^';

enum BoolValue:
    TRUE='true' | FALSE='false';
 

Все здесь, казалось, работало хорошо, но когда я добавил выражение BitSliceExpression и попытался обработать грамматику, я получил следующую ошибку:

Ошибка:

 error(211): ../org.example.expressions/src-gen/org/example/expressions/parser/antlr/internal/InternalExpressions.g:1626:3: [fatal] rule ruleFieldOperationExpression has non-LL(*) decision due to recursive rule invocations reachable from alts 1,4.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.
 

После небольшого тестирования я пришел к выводу, что эта проблема вызвана неоднозначностью между выражением BitSliceExpression и выражением collectionaccess

 //BitSliceExpression example:
[5:3]
//CollectionAccessExpression example:
[5]
 

У меня очень мало знаний о Xtext, Antlr3, и алгоритмов синтаксического анализа в целом
но я могу только предположить, что, поскольку выражение является рекурсивное правило, синтаксический анализатор не слишком смотрю мимо него и проверить, точка с запятой литерал, который является отличительной чертой между
BitSliceExpression и CollectionAccessExpression во время выполнения, и, таким образом, неоднозначность рождается.

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

(Пожалуйста, сообщите мне, требуется ли дополнительная информация о моем проекте)