Eclipse Xtext - Syntactic Predicates

This page follows on from the xtext grammar page to discuss syntactic predicates in more detail.

Syntactic predicates allow us to resolve ambiguous grammars.

Non-Recursive Example

The following is an example of an ambiguous grammar. The 'Option' rule has two parts and these parts have an intersecting grammar (in this case ID == ID). This intersection is the cause of the ambiguity as it parses in both option1 and option2.

Here is the complete grammar:

grammar com.euclideanspace.experiment.Mydsl with org.eclipse.xtext.common.Terminals

generate mydsl "https://www.euclideanspace.com/experiment/Mydsl"

Model:
	opt=Option;
	
Option:
	(ID a=Option1 b=ID)
	|
	(ID d=Option2 e=ID)
	;
	
Option1:
	a=('=='|'+=');
	
Option2:
	d=('=='|'-=');

This is not designed to be a grammar with any practical use, it is just a test case so I can experiment with syntactic predicates. I have included assignments (such as 'a=') so that I know which option is taken (I edited the labelProvider file to give me information about this).

As it stands the grammar is ambiguous and it has no syntactic predicates so it gives the following warnings:

warning(200): ../com.euclideanspace.experiment/src-gen/com/euclideanspace/experiment/parser/antlr/internal/InternalMydsl.g:119:1: Decision can match input such as "RULE_ID '==' RULE_ID" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
warning(200): ../com.euclideanspace.experiment.ui/src-gen/com/euclideanspace/experiment/ui/contentassist/antlr/internal/InternalMydsl.g:176:1: Decision can match input such as "RULE_ID '==' RULE_ID" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input

The grammar is ambiguous because input like 'a == b' can match using either Option1 or Option2.

Option:
	=>(ID a=Option1 b=ID)
	|
	(ID d=Option2 e=ID)
	;

I now want to experiment by putting the syntactic predicate in various places in the 'Option' rule and finding out how input is parsed in each case:

Option:
	=>(ID a=Option1 b=ID)
	|
	(ID d=Option2 e=ID)
	;

Option:
	(=>ID a=Option1 b=ID)
	|
	(ID d=Option2 e=ID)
	;

Option:
	(ID =>a=Option1 b=ID)
	|
	(ID d=Option2 e=ID)
	;

Option:
	(ID a=Option1 =>(b=ID))
	|
	(ID d=Option2 e=ID)
	;

Option:
	(ID a=Option1 b=ID)
	|
	=>(ID d=Option2 e=ID)
	;

Option:
	(ID a=Option1 b=ID)
	|
	(=>ID d=Option2 e=ID)
	;

Option:
	(ID a=Option1 b=ID)
	|
	(ID =>(d=Option2) e=ID)
	;

Option:
	(ID a=Option1 b=ID)
	|
	(ID d=Option2 =>(e=ID))
	;

We can see that for the ambiguous case (x == y) the option that appears first in the rule is the option chosen.

In Antlr3 the production to the right of the predicate is attempted if and only if the syntactic predicate first accepts the next portion of the input stream. Although ordered, the predicates are checked first, with parsing of a clause continuing if and only if the predicate is satisfied

Option:
	(ID Option1 ID)
	|
	(=>ID Option2 ID)
	;
	
Option1:
	'=='|'+=';
	
Option2:
	'=='|'-=';

Option:
	(ID Option1 ID)
	|
	(ID =>Option2 ID)
	;
	
Option1:
	'=='|'+=';
	
Option2:
	'=='|'-=';

1273 [main] INFO  clipse.emf.mwe.utils.GenModelHelper  - Registered GenModel 'https://www.euclideanspace.com/experiment/Mydsl' from 'platform:/resource/com.euclideanspace.experiment/model/generated/Mydsl.genmodel'
warning(200): ../com.euclideanspace.experiment/src-gen/com/euclideanspace/experiment/parser/antlr/internal/InternalMydsl.g:119:1: Decision can match input such as "RULE_ID '==' RULE_ID" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input

So it is not juse a case of putting the syntactic predicate before the option we want to choose. We must understand how the parser scans the grammar so we know where to cut off unwanted options.

reference

EuclideanSpace

home

If you would like to implement your language by starting with a working grammar, which you can get working without delving into complexities such as syntactic predicates, you may want to consider a grammar generator here (Xgener) . You can then customise it and delve into the more complcated stuff later. This will produce an Xbase-like grammar which can be customised (but not the other capabilities of Xbase).