Fixing Ambiguity for CallExpression, MemberAccessExpression etc

[jtenner]

I have the following grammar and I'm genuinely confused how to fix it so that there are no ambiguities and we avoid left recursion.

NewExpression:
    "new" expression=NewExpression ("<" typeParameters+=TypeExpression ("," typeParameters+=TypeExpression)* ">")? "(" (parameters+=Expression ("," parameters+=Expression)*)? ")"
    | CallExpression;

CallExpression:
    callRoot=MemberAccessExpression (
        ("<" typeParameters+=TypeExpression ("," typeParameters+=TypeExpression)* ">")? "(" (parameters+=Expression ("," parameters+=Expression)*)? ")"
    )*
    | MemberAccessExpression;

MemberAccessExpression:
    memberRoot=ArrayAccessExpression (
       "." member=ID
    )*
    | ArrayAccessExpression;
 
 ArrayAccessExpression:
    arrayRoot=PrimaryExpression ( "[" indexExpression=Expression "]")*;

1. I am trying to follow JavaScript's order of operations, making something typescript-like
2. The full grammar in question can be located here.

I think I need some general help too, because I've read the docs front and back, and I think I am missing something 👍 .

All in-all this software has been genuinely amazing and it really does the job, I just think I need one last little push over the edge and it can be incredibly useful for my needs.

[msujew]

Hey @jtenner, thanks we're always glad to hear positive feedback :)

So basically, you're almost there, you can fix your ambiguities by using assigned actions. For example your rule MemberAccessExpression can be refactored into:

MemberAccessExpression:
    ArrayAccessExpression (
       {infer MemberAccessExpression.previous=current} "." member=ID
    )*
;

This can be read as follows: Parse an ArrayAccessExpression, but if a .ID can be parsed afterwards, assign the previously parsed ArrayAccessExpression to the previous property and continue. I would recommend you to read into tree-rewriting actions and the langium-lox language, which also implements an expression system.

[jtenner]

@msujew Can I ask for more detailed help with refactoring my language grammar because my ExpressionStatement is producing multiple statements per expression. It's a little weird.

[msujew]

my ExpressionStatement is producing multiple statements per expression. It's a little weird.

Uhm, that certainly sounds weird. Can you explain a bit more what you mean by that? Also do you have a reproducible example at hand?

[jtenner]

Thanks! I will produce the grammar and file soon. My guess is I did something fundamentally wrong and it will be very easy to identify the problem

[jtenner]

@msujew once again thank you for your time!

Full Grammar here: https://github.com/jtenner/whacko-lang/blob/experimental-grammar/src/language-server/whacko.langium

Test file here: https://github.com/jtenner/whacko-lang/blob/experimental-grammar/myFile.wo

parsing the file yields four ExpressionStatements despite there only being one conceptually. I wonder what assumption I'm making about writing Langium grammar that I'm messing up?

[msujew]

Have you fixed it in the meantime? When inspecting your AST, it only shows me one Expression node for your statements.

Also, note that your grammar still contains ambiguities, for example between TupleExpression and FunctionExpression.

[jtenner]

For anyone reading about this problem, Langium has an excellent means of dealing with MemberAccess and right associative left recursive stuff like this:

PathExpression:
    PrimaryExpression (
        {infer CallExpression.callRoot=current} ("<" typeParameters+=TypeExpression ("," typeParameters+=TypeExpression)* ">")? "(" (parameters+=Expression ("," parameters+=Expression)*)? ")"
        | {infer MemberAccessExpression.memberRoot=current} "." member=ID
        | {infer ArrayAccessExpression.arrayRoot=current} "[" indexExpression=Expression "]"
    )+
    | PrimaryExpression;

[msujew]

Please note that writing rules in the style of (A B+) | (A) works, but is heavily discouraged due to massively increased parsing time. The parser needs to decide at every alternative whether B+ is a possible suffix, which requires to look deeply into the token stack.

The recommended way is to simply transform it into A B*:

PathExpression:
    PrimaryExpression (
        {infer CallExpression.callRoot=current} ("<" typeParameters+=TypeExpression ("," typeParameters+=TypeExpression)* ">")? "(" (parameters+=Expression ("," parameters+=Expression)*)? ")"
        | {infer MemberAccessExpression.memberRoot=current} "." member=ID
        | {infer ArrayAccessExpression.arrayRoot=current} "[" indexExpression=Expression "]"
    )*;

[jtenner]

Oh okay. I'm so used to writing pegjs grammar.

🙏 Thanks!