xtext grouping grammar warning

Question

I'm trying to create an xtext grammar for a language that has multiple lines that can be grouped together based on their structure. I'm having trouble getting rid of warnings out of the grammar when it's generated. As an example I've put together the following grammar that has the same problem:

Groups: groups += Group*;

Group: content = (As | Bs);

As: 'a'+;

Bs: 'b'+;

For example for the input "aaaa" it ambiguous if its one group of 4 a's or two groups of 2 a's (or the other alternatives).

I just want it to be 1 groups of 4 a's. but there is no place to put a '=>' predicate?

Does anyone know how to refactor this grammar so that the ambiguity is removed?

Answer 1

yes your grammar is ambiguous. Your paser can match 'aaaa' in different ways. To solve it you can add a syntactic predicate as follow :

Groups: groups += Group*;

Group: content = (As | Bs);

As: =>'a'+;

Bs: =>'b'+;

Answer 2

Adding syntactic predicates does not solve the ambiguities in your grammar. The problem is that the token stream which is provided by the lexer does not contain any information whether one group is complete or not. In your conrete case there is the rule As: 'a'+;. It describes a list of at least one or more letters a. Each upcomming a is consumed but so called Whitespaces (e.g. simple whitespace, tab or linebreak) between these a's will be ignored. The parser will continue to put the next upcomming a to this rule until an other letter (the b) will follow in the token stream.

The problem with your grammar is that more then one list of a's can be parsed in your grammar. Example:

a
aa
aaa

is a valid input for your grammar, but the parser does not know that the first As rule ends after the a in the first line. This is because the linebreak is a whitespace that is ignored! For the parser this input of three As bloks looks equal to one As block aaaaaa.

Introducing a syntactic predicate does not solve this problem! For my opinion there are only two resolutions for your problem.

1. Provide some 'syntactic sugar' e.g. by closing an As rule with a semicolon or any other sign. The rule would look like this: As: 'a'+ ';';

2. Take care that you prevent whitespaces between a word of a's and ensure that at least one whitespace occure after a word:

   Group: content = (As | Bs) WS+;
   As hidden(): 'a'+;
   Bs hidden(): 'b'+;
   

   Then, your grammar will compile and behave like intended.