Are syntactic predicates supported?

[mrtnstn]

Firstly, my compliments for this amazing project. Langium will be really useful for me to migrate my eclipse/xtext-based DSLs to VSCode extensions.

In some of my xtext grammars, I needed to use syntactic predicates => and -> to help the parser to choose between initially ambiguous alternatives. I see the Langium grammar language allows me to write these also, but they do not seem to have an effect on the parser behaviour. Are they not supported yet?

As an example, I have a javascript-like language in which expressions can reference variables and functions using qualified names, and they can also be post-fixed with member calls. Below a simplified excerpt from my grammar. Note the colon in the qualified name to disambiguate it from subsequent member calls.

PostfixExpression: FeatureReference ({infer MemberCall} '.' member=ID)*
Reference: ref=[Definition:QualifiedName] (functioncall?='(' Arguments? ')')?
QualifiedName: ID =>(('.' ID)* ':' ID)?;

Now, if I offer an expression like x.length, where x is a variable in scope, then I'd like the parser to first try to parse a complete qualified name, accepting that it can only parse one ID, because there is no ':', and then continuing to parse a MemberCall. However, it gets stuck in the second part of the QualifiedName rule and sees the entire expression as a qualified name, that it obviously cannot resolve.

Any hints on resolving this ambiguity in any other way than with syntactic predicates is also welcome, of course.

Cheers,
Maarten

[msujew]

Hi @mrtnstn,

thanks for the compliment :)

You're right in your assumption that Langium doesn't respect syntactic predicates. They are only in there for the purpose of Xtext "backwards compatibility". The issue here is based on our underlying parser library Chevrotain and is twofold:

1. Chevrotain always tries to pick the first fitting alternative to match (and not the longest), resulting in very little need to actually support syntactic predicates compared to something like Xtext/ANTLR3
2. As Chevrotain is an LL(k) parser library (see the PR to change this), it cannot support syntactic predicates such as ID =>(('.' ID)* ':' ID)?; at all, a more powerful approach (ANTLR3/4 style LL(*)) is needed.

Although we can fix most issues with syntactic predicates due to 1. by simply reordering alternatives, I don't think that this special case can the represented in Langium due to 2. In theory, Chevrotain is capable of resolving this by using backtracking, but Langium doesn't expose that much of the Chevrotain API to actually do this. We probably have to wait until the mentioned PR is merged, then it should work out-of-the-box (even without the syntactic predicate). Unfortunately the maintainer of Chevrotain is quite busy at the moment, so it might take some time until this is done.

[snarkipus]

Tags: @msujew

we can fix most issues with syntactic predicates due to 1. by simply reordering alternatives

So, as I'm continuing to work through this, I came across the following (Chapter 9 - SmallJava in Xtext) which uses the syntactic predicate feature:

...
SJBlock:
	{SJBlock} '{' statements+=SJStatement* '}';

 SJStatement:
	SJVariableDeclaration |
	SJReturn |
	SJExpression ';' |
	SJIfStatement;
...
SJIfStatement:
	'if' '(' expression=SJExpression ')' thenBlock=SJIfBlock
	(=>'else' elseBlock=SJIfBlock)?;

SJIfBlock returns SJBlock:
	statements+=SJStatement
	| SJBlock;
...

The rough langium equivalent I've come up with is:

...
SJBlock:
    {infer SJBlock} '{' statements+=SJStatement* '}'
;

SJStatement:
      SJVariableDeclaration
    | SJReturn
    | SJExpression ';'
    | SJIfStatement
;
...
SJIfStatement:
    'if' '(' expression=SJExpression ')' thenBlock=SJIfBlock
    (=>'else' elseBlock=SJBlock)?
;

SJIfBlock infers SJBlock:
    statements+=SJStatement | SJBlock
;
...

While it compiles (reflecting the backward compatibility), it obviously doesn't parse correctly. Note, it will compile without error even in the absence of the non-functional but tolerated => operator. Should it be asserting a warning like Xtext's warning(200): Decision can match input such as "'else'" using multiple alternatives: 1, 2 ... As a result, alternative(s) 2 were disabled for that input? I didn't look into the Chevrotain parser implementation to see if you attempt to detect it.

Regardless, I've tried a few different ways of refactoring the grammar to address the dangling else dilemma to no avail. It would seem like this would be a common stumbling block so I thought I'd ask the professionals.

Example Source:

class C {
    C c;
    C m() {
        if (true)
            if (false)
                this.c = null;
            else
                this.c = null;
        return this.c;
    }
}

Error: Expecting keyword '{' but found this.small-java(parsing-error)

[msujew]

@snarkipus As mentioned above, only Antlr3 actually needs the syntactic predicate feature. Both Chevrotain and Antlr4 do not require it. In your case the issue is that your (=>'else' elseBlock=SJBlock)? definition requires that an else is always followed by an { (you should use elseBlock=SJIfBlock instead).

Although the dangling else problem is always a grammar ambiguity, basically all parsers (except for Antlr3) choose to ignore the problem and simply go for the inner-most option that is able to be parsed. I.e. it will always assign the next else statement it can find to the directly preceding if branch.

[snarkipus]

@msujew Thanks!

I appreciate you answering these questions though I realize they're purely academic.

[mrtnstn]

Thank you for the explanation @msujew . Good to know a solution is coming in the hopefully not too distant future. Keep up the good work.