Home » Modeling » TMF (Xtext) » error 202 - the decision cannot distinguish between alternative(s)
|
| Re: error 202 - the decision cannot distinguish between alternative(s) [message #853888 is a reply to message #853719] |
Mon, 23 April 2012 12:32   |
 Henrik Lindberg
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 |
Joel Bobstein
Messages: 7
Registered: April 2012 |
Junior Member |
|
|
Henrik Lindberg wrote on Mon, 23 April 2012 08:32When 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 |
Henrik Lindberg
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.
|
|
| | | |
Goto Forum:
Current Time: Thu Apr 25 16:08:24 GMT 2024
Powered by FUDForum. Page generated in 0.03360 seconds |
] 
Search
Help
Register
Login
Home
