Optional elements in Unordered groups are currently not supported

[luan-xiaokun]

Hey guys, I ran into this diagnostic when I use optional operator ? in an unordered group (A & B), i.e. A? & B.

This diagnostic information tells me that such a combination is not allowed, but I am wondering for what reason Langium cannot support the use of optional in unordered group.

One reason that I can think of is that, if some tokens can be both matched by rule A and rule B, then the parser cannot decide whether these tokens should be A or B.

In my case, parse rule A and rule B starts with different keywords, so there is no intersection of these two rules. I suppose as long as the strings that A and B can match do not intersect, there should be no problem, and we can use the optional element inside unordered group. Am I thinking right?

Also, I noticed that the diagnostic says currently not supported, so will this feature be supported in a feature release?

[luan-xiaokun]

Sorry for not reading all the search results before. I found the following explanation in #314 (comment). So lacking underlying tool support is the main reason for this, and this feature may be supported in future.

PR is merged now.
Optional alternatives inside the unordered group are not yet supported, we need to wait for the changes in Chevrotain.

[msujew]

@luan-xiaokun Yep, as mentioned in your other comment, this is due to a limitation of our underlying parser library.

However, I'm wondering why you would need such a construct in the first place. In theory (A? & B) (which parses (A or B or nothing) in any order) is grammatically the same as (A & B)? (which parses (A or B in any order) or nothing, but probably works correctly in Chevrotain).

[luan-xiaokun]

In theory (A? & B) (which parses (A or B or nothing) in any order) is grammatically the same as (A & B)? (which parses (A or B in any order) or nothing

I'm a little bit lost here. Let me explain my case in more details.

Basically I want the B component mandatory and the A component optional, but A can either show up before B or after that, which means (A B), (B A), and (B) are all valid. So I thought that since A? B means that the optional A must comes before B, A? & B is supposed to mean what I want. The parentheses are added to avoid ambiguity, the complete parse rule looks like C (A? & B) D.

Is my understanding of the & operator wrong? Do you have any workaround for this case?

[msujew]

Is my understanding of the & operator wrong? Do you have any workaround for this case?

Looking at our documentation and our implementation, I noticed that they don't match up perfectly, especially since our behavior differs drastically from Xtext. Basically the Langium implementation gives no guarantees that any of the unordered group elements are actually parsed. It only guarantees that none is parsed more then once. It basically performs the following operation (A | B)* but with the additional limit that after - for example - parsing A, it won't try to parse A again.

We might need to make this a bit clearer in the documentation. I don't think that we plan to implement Xtext like behavior, which simply creates all possible permutations of an unordered group.

[luan-xiaokun]

Thanks for your detailed explanation! Although I didn't figure out which part of the code the unordered group operator is implemented in, your explanation is enough for me to understand how it works in Langium