Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » TMF (Xtext) » error 202 - the decision cannot distinguish between alternative(s)
error 202 - the decision cannot distinguish between alternative(s) [message #853719] Mon, 23 April 2012 09:14 Go to next message
Joel Bobstein is currently offline Joel BobsteinFriend
Messages: 7
Registered: April 2012
Junior Member
I am stuck with the following antlr error when trying to generate the Xtext artifacts from the grammar: error 202 - the decision cannot distinguish between alternative(s)

I have localized the issue and here is a minimal reproducer:

grammar org.example.domainmodel.Domainmodel with
                                      org.eclipse.xtext.common.Terminals

generate domainmodel "You cannot use links until you have posted more than 25 messages."

Domainmodel:
  program=QualifiedVariable
;

QualifiedVariable:
 (qualifier=Qualifier ".")? id=ID 
;

Qualifier:
  ID ('.' ID)*
;


The error message is: error(202): ../org.example.domainmodel/src-gen/org/example/domainmodel/parser/antlr/internal/InternalDomainmodel.g:200:1: the decision cannot distinguish between alternative(s) 1,2 for input such as "'.' RULE_ID EOF EOF"

I don't understand the error message because I don't see how the input "'.' RULE_ID EOF EOF" could ever be produced by this grammar, plus I don't know which are the alternatives called 1 and 2. I suspect there is a problem with left recursivity, but I'm not sure. I have tried to read the file InternalDomainmodel.g but I cant understand it.


Morever: If I add any token after the QualifiedVariable Rule, there is no error raised by antlr. I can't understand why.

QualifiedVariable:
 (qualifier=Qualifier ".")? id=ID "anyToken"
;



Any idea how to fix this please ?
Re: error 202 - the decision cannot distinguish between alternative(s) [message #853888 is a reply to message #853719] Mon, 23 April 2012 12:32 Go to previous messageGo to next message
Henrik Lindberg is currently offline Henrik LindbergFriend
Messages: 2509
Registered: July 2009
Senior Member
When the parser sees the '.' after ID in Qualified Variable or in
Qualifier, there is now way of telling if it should accept it as a
Qualifier, or as a QualifiedVariable. When you add a token after "id =
ID", the parser figures out that by looking ahead, and finding your
"anyToken" it knows which path to take.

QualifiedVariable : qualifier = Qualifier;

Should be enough, or why not use QualifiedName from the standard grammar
as it handles qualified/segmented names and there is built in support
for many features.

Regards
- henrik

On 2012-23-04 11:14, Joel Bobstein wrote:
> I am stuck with the following antlr error when trying to generate the
> Xtext artifacts from the grammar: error 202 - the decision cannot
> distinguish between alternative(s)
>
> I have localized the issue and here is a minimal reproducer:
>
> grammar org.example.domainmodel.Domainmodel with
> org.eclipse.xtext.common.Terminals
>
> generate domainmodel "You cannot use links until you have posted more
> than 25 messages."
>
> Domainmodel:
> program=QualifiedVariable
> ;
>
> QualifiedVariable:
> (qualifier=Qualifier ".")? id=ID ;
>
> Qualifier:
> ID ('.' ID)*
> ;
>
>
> The error message is: error(202):
> ../org.example.domainmodel/src-gen/org/example/domainmodel/parser/antlr/internal/InternalDomainmodel.g:200:1:
> the decision cannot distinguish between alternative(s) 1,2 for input
> such as "'.' RULE_ID EOF EOF"
>
> I don't understand the error message because I don't see how the input
> "'.' RULE_ID EOF EOF" could ever be produced by this grammar, plus I
> don't know which are the alternatives called 1 and 2. I suspect there is
> a problem with left recursivity, but I'm not sure. I have tried to read
> the file InternalDomainmodel.g but I cant understand it.
>
>
> Morever: If I add any token after the QualifiedVariable Rule, there is
> no error raised by antlr. I can't understand why.
>
> QualifiedVariable:
> (qualifier=Qualifier ".")? id=ID "anyToken"
> ;
>
>
> Any idea how to fix this please ?
>
Re: error 202 - the decision cannot distinguish between alternative(s) [message #859273 is a reply to message #853888] Fri, 27 April 2012 14:50 Go to previous messageGo to next message
Joel Bobstein is currently offline Joel BobsteinFriend
Messages: 7
Registered: April 2012
Junior Member
Henrik Lindberg wrote on Mon, 23 April 2012 08:32
When the parser sees the '.' after ID in Qualified Variable or in
Qualifier, there is now way of telling if it should accept it as a
Qualifier, or as a QualifiedVariable.


Thank you for the answer. I understand your explanation, but I still don't get it.
In the example, the only program accepted is a QualifiedVariable. So how could the parser not know which rule to apply ?

If the input is for example "a.b", it can only be

QualifiedVariable:
qualifier="a." name="b"

Because the grammar is not ambiguous and the whole program has to be a QualifiedVariable.
If the parser wanted to use the rule Qualifier after the dot, it would lead to a dead end, wouldn't it ? So imo there is no other way to parse this with this grammar.

So why doesn't the parser know which path to chose, and is there any way to get this right ?


For the alternatives you proposed, I can't use them as this is a simplified reproducer, for which I would like to find a direct solution.
Re: error 202 - the decision cannot distinguish between alternative(s) [message #859346 is a reply to message #859273] Fri, 27 April 2012 15:33 Go to previous messageGo to next message
Henrik Lindberg is currently offline Henrik LindbergFriend
Messages: 2509
Registered: July 2009
Senior Member
It is important to understand how parsing works. First, the lexer
arranges all tokens in a stream unaware of the grammar. The parser sends
a trained monkey along the stream of produced tokens to see which path
to take.

When faced with two paths that accept the same sequence this is an
ambiguity and the (unguided) parser does not know what to do.

Since your example was simplified it is not possible to give you
concrete advice, but in general you can resolve ambiguities in four ways
- simplify your grammar, using left factoring, using syntactic
predicates, or turning on backtracking.

a) Simplifying the grammar would mean something like what I proposed
earlier; combining multiple rules/objects into one and move complexity
elsewhere (validation, data type conversion, etc.). This is usually the
best choice as it give you more control over error messages, and reduces
grammar complexity (faster parsing, easier to understand, fewer grammar
elements to deal with throughout the environment, etc.). Remember
"syntax is not everything" - try to be forgiving in the parser (this
will help you a lot later as you will have more context than just
"syntax error" and a bunch of unparsed text when you want to do quick
fixes and similar).

b) A syntactic predicate is a tag read by the trained monkey telling the
monkey to accept the input on the path it is on and not search for other
paths. A syntactic predicate is introduced with the '=>' operator.
e.g. =>('A' 'B') tells the monkey that if it finds an 'A' followed by a
'B' then the monkey is on the right path and can return home to get a
banana :).

c) Left factoring is how you handle Expressions like a + b, a * b, but
can be used to handle ambiguities that can be resolved by precedence.
There is a formula to follow for how these rules are written. Look at
Expression examples (you can look at the pp.xtext grammar in
cloudsmith/geppetto at github, if you can't find some other simpler
example). In general, you start with the lowest precedence and make a
rule call to the next higher rule in precedence.

d) Backtracking, finally, makes the parser backtrack - it will try each
path in the order specified in the grammar, and select the first path
that succeeds, backtracking on failure to the preceding branch point and
trying next path. Backtracking can lead to surprising results and should
be your last option.

Hope that helps you.

Regards
- henrik

On 2012-27-04 16:50, Joel Bobstein wrote:
> Henrik Lindberg wrote on Mon, 23 April 2012 08:32
>> When the parser sees the '.' after ID in Qualified Variable or in
>> Qualifier, there is now way of telling if it should accept it as a
>> Qualifier, or as a QualifiedVariable.
>
>
> Thank you for the answer. I understand your explanation, but I still
> don't get it.
> In the example, the only program accepted is a QualifiedVariable. So how
> could the parser not know which rule to apply ?
>
> If the input is for example "a.b", it can only be
>
> QualifiedVariable:
> qualifier="a." name="b"
>
> Because the grammar is not ambiguous and the whole program has to be a
> QualifiedVariable. If the parser wanted to use the rule Qualifier after
> the dot, it would lead to a dead end, wouldn't it ? So imo there is no
> other way to parse this with this grammar.
>
> So why doesn't the parser know which path to chose, and is there any way
> to get this right ?
>
>
> For the alternatives you proposed, I can't use them as this is a
> simplified reproducer, for which I would like to find a direct solution.
Re: error 202 - the decision cannot distinguish between alternative(s) [message #865457 is a reply to message #859346] Mon, 30 April 2012 12:07 Go to previous messageGo to next message
Joel Bobstein is currently offline Joel BobsteinFriend
Messages: 7
Registered: April 2012
Junior Member
It does help. The problem is not solved yet, but your explanation makes it more concrete. Thanks a lot for sharing your expertise on the matter.
Re: error 202 - the decision cannot distinguish between alternative(s) [message #865947 is a reply to message #865457] Mon, 30 April 2012 16:57 Go to previous messageGo to next message
Henrik Lindberg is currently offline Henrik LindbergFriend
Messages: 2509
Registered: July 2009
Senior Member
On 2012-30-04 14:07, Joel Bobstein wrote:
> It does help. The problem is not solved yet, but your explanation makes
> it more concrete. Thanks a lot for sharing your expertise on the matter.

It helps to start with terminals and smallest possible grammar and then
add one language feature at a time. This way it is more clear which
language construct is giving your trouble.

- henrik
Re: error 202 - the decision cannot distinguish between alternative(s) [message #869888 is a reply to message #865947] Fri, 04 May 2012 16:11 Go to previous message
kon f is currently offline kon fFriend
Messages: 152
Registered: March 2012
Senior Member
I was also facing the same issue. It's difficult to get ambiguity right away from the grammar. I used the antlrworks jar to visualise the ambiguity. Just start antlrworks:

java -jar antlrworks-1.4.3.jar


and open the InternalMyDSL.g file (you can find the path if you hit Control+Shift+R in Eclipse and type in the file name). And as last step, click the play button. The rules on the left, that are marked red need some attention Smile

Here are two links that helped me:

dslmeinte.wordpress.com/2011/12/05/using-syntactic-predicates-in-xtext-part-1/

stackoverflow.com/questions/6499378/antlr-match-input-using-multiple-alternatives-error

Good luck Smile!
Previous Topic:External parameters for Xtend2
Next Topic:ouverture de modele xmi !
Goto Forum:
  


Current Time: Tue Nov 24 19:28:06 GMT 2020

Powered by FUDForum. Page generated in 0.02068 seconds
.:: Contact :: Home ::.

Powered by: FUDforum 3.0.2.
Copyright ©2001-2010 FUDforum Bulletin Board Software

Back to the top