Parsing Recursive Expressions

[brsanthu]

Working on parsing for recursive expression DSL where expression could be of type Value/Function/Math Expr/Logical Expr in recursive format. Below grammar works for most of usecases but for expr (0 + 1) * 50 fails with error Expecting end of file but found *. [(0 + 1) * 50].

I thought Multiplication is handled as parr of LogicalExpr hierarchy at line 10. Not sure where I'm doing wrong. I can make sense of other part of grammar except for these recursive expressions. Thank you for taking a look and suggesting any changes.

grammar GenericExpr

entry FormulaExpr:
    expression=Expr;

Expr infers Expr:
    PrimaryExpr;

PrimaryExpr infers Expr:
    paren?='(' Expr paren?=')' | LogicalExpr;

LogicalExpr infers Expr:
    ComparisonExpr ({infer LogicalExpr.left=current} operator=('&&' | '||') right=ComparisonExpr)*;

ComparisonExpr infers Expr:
    AdditionExpr ({infer ComparisonExpr.left=current} operator=('=' | '!=' | '<' | '<=' | '>' | '>=') right=AdditionExpr)*;

AdditionExpr infers Expr:
    MultiplicationExpr ({infer AdditionExpr.left=current} operator=('+' | '-' | '&') right=MultiplicationExpr)*;

MultiplicationExpr infers Expr:
    ExponentiationExpr ({infer MultiplicationExpr.left=current} operator=('*' | '/') right=ExponentiationExpr)*;

ExponentiationExpr infers Expr:
    UnaryExpr ({infer ExponentiationExpr.left=current} operator=('^') right=UnaryExpr)*;

UnaryExpr infers Expr:
    ValueExpr | {infer UnaryExpr} operator=('!' | '-') expression=UnaryExpr;

ValueExpr:
    Literal |
    FunctionCall |
    FieldRef
;

FunctionCall:
    name=ID '(' (arguments+=Expr (',' arguments+=Expr)*)? ')';

FieldRef:
    field=QualifiedName
;

QualifiedName:
    parts+=(GLOBAL_ID | ID) ('.' parts+=ID)*;

Literal:
    StringVal |
    NumberVal |
    BooleanVal |
    NullVal;

NullVal infers NullVal:
    value='null'
;

StringVal:
    value=(SINGLE_STRING | DOUBLE_STRING);

NumberVal:
    value=NUMBER;

BooleanVal:
    value?='true' | 'false';


hidden terminal WS: /\s+/;
terminal GLOBAL_ID: /\$[_a-zA-Z][\w_]*/;
terminal ID: /[_a-zA-Z][\w_]*/;
terminal SINGLE_STRING returns string:"'" ('\\' . |  !('\\' | "'"))*"'"  ;
terminal DOUBLE_STRING returns string:'"' ('\\' . |  !('\\' | '"'))*'"'  ;
terminal NUMBER: /[0-9]+(\.[0-9]+)?/;
hidden terminal ML_COMMENT: /\/\*[\s\S]*?\*\//;

[cdietrich]

your primary expression looks wired. you ususally put this next to the literals

Expr infers Expr:
    LogicalExpr;

PrimaryExpr infers Expr:
    (paren?='(' Expr paren?=')');

ValueExpr:
    PrimaryExpr |
    Literal |
    FunctionCall |
    FieldRef
;

[brsanthu]

Thank you for the reply. I made those changes, and it compiled fine but parsing is going on infinite loop and exit with below error

RangeError: Maximum call stack size exceeded
    at GenericExprAstReflection.isSubtype (file:///Users/name/projects/gitworkspace/langium-genericexpr/node_modules/langium/src/syntax-tree.ts:162:14)

[cdietrich]

hmmm i tried this grammar in playground

grammar xxxx
entry FormulaExpr:
    expression=Expr;

Expr infers Expr:
    LogicalExpr;

PrimaryExpr infers Expr:
    (paren?='(' Expr paren?=')');

LogicalExpr infers Expr:
    ComparisonExpr ({infer LogicalExpr.left=current} operator=('&&' | '||') right=ComparisonExpr)*;

ComparisonExpr infers Expr:
    AdditionExpr ({infer ComparisonExpr.left=current} operator=('=' | '!=' | '<' | '<=' | '>' | '>=') right=AdditionExpr)*;

AdditionExpr infers Expr:
    MultiplicationExpr ({infer AdditionExpr.left=current} operator=('+' | '-' | '&') right=MultiplicationExpr)*;

MultiplicationExpr infers Expr:
    ExponentiationExpr ({infer MultiplicationExpr.left=current} operator=('*' | '/') right=ExponentiationExpr)*;

ExponentiationExpr infers Expr:
    UnaryExpr ({infer ExponentiationExpr.left=current} operator=('^') right=UnaryExpr)*;

UnaryExpr infers Expr:
    ValueExpr | {infer UnaryExpr} operator=('!' | '-') expression=UnaryExpr;

ValueExpr:
    PrimaryExpr |
    Literal |
    FunctionCall |
    FieldRef
;

FunctionCall:
    name=ID '(' (arguments+=Expr (',' arguments+=Expr)*)? ')';

FieldRef:
    field=QualifiedName
;

QualifiedName:
    parts+=(GLOBAL_ID | ID) ('.' parts+=ID)*;

Literal:
    StringVal |
    NumberVal |
    BooleanVal |
    NullVal;

NullVal infers NullVal:
    value='null'
;

StringVal:
    value=(SINGLE_STRING | DOUBLE_STRING);

NumberVal:
    value=NUMBER;

BooleanVal:
    value?='true' | 'false';


hidden terminal WS: /\s+/;
terminal GLOBAL_ID: /\$[_a-zA-Z][\w_]*/;
terminal ID: /[_a-zA-Z][\w_]*/;
terminal SINGLE_STRING returns string:"'" ('\\' . |  !('\\' | "'"))*"'"  ;
terminal DOUBLE_STRING returns string:'"' ('\\' . |  !('\\' | '"'))*'"'  ;
terminal NUMBER: /[0-9]+(\.[0-9]+)?/;
hidden terminal ML_COMMENT: /\/\*[\s\S]*?\*\//;

[brsanthu]

@cdietrich Parsing was fine but the issue was serializing and other functions where we used ast.ts utilities like isFormulaExpr. When one is called, it was going on infite loop. I think issue was PrimaryExpr which was same as Expr due to optional parenthesis nature (or other ones may. be). I tweaked the grammar to be below and now all our usecases (so far at least) are passing and we can use those utilities without any issues.

grammar xxx

entry FormulaExpr:
    expression=Expr;

Expr infers Expr:
    LogicalExpr;

LogicalExpr infers Expr:
    ComparisonExpr ({infer LogicalExpr.left=current} operator=('&&' | '||') right=ComparisonExpr)*;

ComparisonExpr infers Expr:
    AdditionExpr ({infer ComparisonExpr.left=current} operator=('=' | '!=' | '<' | '<=' | '>' | '>=') right=AdditionExpr)*;

AdditionExpr infers Expr:
    MultiplicationExpr ({infer AdditionExpr.left=current} operator=('+' | '-' | '&') right=MultiplicationExpr)*;

MultiplicationExpr infers Expr:
    ExponentiationExpr ({infer MultiplicationExpr.left=current} operator=('*' | '/') right=ExponentiationExpr)*;

ExponentiationExpr infers Expr:
    UnaryExpr ({infer ExponentiationExpr.left=current} operator=('^') right=UnaryExpr)*;

ParenExpr infers ParenExpr:
    paren='(' expr=Expr ')';

ValueExpr infers Expr:
    Literal |
    FunctionCall |
    FieldRef |
    ParenExpr
;

UnaryExpr infers Expr:
    ValueExpr | {infer UnaryExpr} operator=('!' | '-') expression=UnaryExpr;

FunctionCall:
    name=ID '(' (arguments+=Expr (',' arguments+=Expr)*)? ')';

FieldRef:
    field=QualifiedName
;

QualifiedName:
    parts+=(GLOBAL_ID | ID) ('.' parts+=ID)*;

Literal:
    StringVal |
    NumberVal |
    BooleanVal |
    NullVal;

NullVal infers NullVal:
    value='null'
;

StringVal:
    value=(SINGLE_STRING | DOUBLE_STRING);

NumberVal:
    value=NUMBER;

BooleanVal:
    value?='true' | 'false';

hidden terminal WS: /\s+/;
terminal GLOBAL_ID: /\$[_a-zA-Z][\w_]*/;
terminal ID: /[_a-zA-Z][\w_]*/;
terminal SINGLE_STRING returns string:"'" ('\\' . |  !('\\' | "'"))*"'"  ;
terminal DOUBLE_STRING returns string:'"' ('\\' . |  !('\\' | '"'))*'"'  ;
terminal NUMBER: /[0-9]+(\.[0-9]+)?/;
hidden terminal ML_COMMENT: /\/\*[\s\S]*?\*\//;

[cdietrich]

ah yes i missed that you even made these optional