Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » TMF (Xtext) » [Xtext 2.3.1] : Unexpected non-LL(*) decisions due to recursive rule invocations
[Xtext 2.3.1] : Unexpected non-LL(*) decisions due to recursive rule invocations [message #1199631] Wed, 20 November 2013 23:16 Go to next message
Didier Garcin is currently offline Didier Garcin
Messages: 39
Registered: April 2013
Member
I'm intrigued by the errors returned during generation of infrastructure.

First :
ruleType_definition has non-LL(*) decision due to recursive rule invocations reachable from alts 4,6.


This error message complains about these rules :

Type_definition:
	  Enumeration_type_definition
	| Real_type_definition
	| Record_type_definition
	| Derived_type_definition  // Alt 4
	| Integer_type_definition
	| Array_type_definition    // Alt 6
	| Access_type_definition
	| Interface_type_definition
	;

Derived_type_definition:
      _ABSTRACT_? _LIMITED_? _NEW_ Subtype_indication ((_AND_ interfaceList = Interface_list)? recordExtentionPart = Record_extension_part)?
    ;

Array_type_definition:
    _ARRAY_ 
    "(" 
    constrainedIndex+=Index_subtype_definition ("," constrainedIndex+=Index_subtype_definition)*
    |
    unconstrainedIndex+=Discrete_subtype_definition ("," unconstrainedIndex+=Discrete_subtype_definition)*
    ")"
     _OF_ componentDefinition=Component_definition
    ;

terminal _ABSTRACT_: ('a' | 'A') ('b' | 'B') ('s' | 'S') ('t' | 'T') ('r' | 'R') ('a' | 'A') ('c' | 'C') ('t' | 'T') ;
terminal _ARRAY_: ('a' | 'A') ('r' | 'R') ('r' | 'R') ('a' | 'A') ('y' | 'Y') ;
terminal _LIMITED_: ('l' | 'L') ('i' | 'I') ('m' | 'M') ('i' | 'I') ('t' | 'T') ('e' | 'E') ('d' | 'D') ;
terminal _NEW_: ('n' | 'N') ('e' | 'E') ('w' | 'W') ;


For this is not logic.
How could alt 4 and 6 be ambiguous. Because 1-lookahead(Derived_type_definition) = {_ABSTRACT_, _LIMITED_, _NEW_}, 1-lookahead(Array_type_definition) = {_ARRAY_}.

It seems lexical elements are not considered as lexemes but as part of syntactic rules as if _ABSTRACT_, _LIMITED_, _NEW_ and _ARRAY_ were macros of substitution.

I have error messages as this :
Multiple token rules can match input such as "'r'": RULE__RANGE_, RULE__RECORD_, RULE__REM_, RULE__RENAMES_, RULE__RETURN_, RULE_IDENTIFIER


If this hypothesis is true, how to do in order to obtain the traditional behaviour ?

Thanks all
Re: [Xtext 2.3.1] : Unexpected non-LL(*) decisions due to recursive rule invocations [message #1199963 is a reply to message #1199631] Thu, 21 November 2013 03:12 Go to previous messageGo to next message
Henrik Lindberg is currently offline Henrik Lindberg
Messages: 2500
Registered: July 2009
Senior Member
On 2013-21-11 24:16, Didier Garcin wrote:
> I'm intrigued by the errors returned during generation of infrastructure.
>
> First :
> ruleType_definition has non-LL(*) decision due to recursive rule
> invocations reachable from alts 4,6.
>
>
> This error message complains about these rules :
>
> Type_definition:
> Enumeration_type_definition
> | Real_type_definition
> | Record_type_definition
> | Derived_type_definition // Alt 4
> | Integer_type_definition
> | Array_type_definition // Alt 6
> | Access_type_definition
> | Interface_type_definition
> ;
>
> Derived_type_definition:
> _ABSTRACT_? _LIMITED_? _NEW_ Subtype_indication ((_AND_
> interfaceList = Interface_list)? recordExtentionPart =
> Record_extension_part)?
> ;
>
> Array_type_definition:
> _ARRAY_ "(" constrainedIndex+=Index_subtype_definition (","
> constrainedIndex+=Index_subtype_definition)*
> |
> unconstrainedIndex+=Discrete_subtype_definition (","
> unconstrainedIndex+=Discrete_subtype_definition)*
> ")"
> _OF_ componentDefinition=Component_definition
> ;
>
> terminal _ABSTRACT_: ('a' | 'A') ('b' | 'B') ('s' | 'S') ('t' | 'T')
> ('r' | 'R') ('a' | 'A') ('c' | 'C') ('t' | 'T') ;
> terminal _ARRAY_: ('a' | 'A') ('r' | 'R') ('r' | 'R') ('a' | 'A') ('y' |
> 'Y') ;
> terminal _LIMITED_: ('l' | 'L') ('i' | 'I') ('m' | 'M') ('i' | 'I') ('t'
> | 'T') ('e' | 'E') ('d' | 'D') ;
> terminal _NEW_: ('n' | 'N') ('e' | 'E') ('w' | 'W') ;
>
>
Using terminals for keywords is not good because the lexer does not
backtrack (by default, and you do not want to turn that on).
IIRC there is support for case independent keywords in Xtext.
You will also find that the generated UI does not do a good job wrt to
code completion when using terminals as keywords. I went down that path;
it hurts.

> For this is not logic.
> How could alt 4 and 6 be ambiguous. Because
> 1-lookahead(Derived_type_definition) = {_ABSTRACT_, _LIMITED_, _NEW_},
> 1-lookahead(Array_type_definition) = {_ARRAY_}.
>
> It seems lexical elements are not considered as lexemes but as part of
> syntactic rules as if _ABSTRACT_, _LIMITED_, _NEW_ and _ARRAY_ were
> macros of substitution.
> I have error messages as this :
> Multiple token rules can match input such as "'r'": RULE__RANGE_,
> RULE__RECORD_, RULE__REM_, RULE__RENAMES_, RULE__RETURN_, RULE_IDENTIFIER
>
> If this hypothesis is true, how to do in order to obtain the traditional
> behaviour ?
>

In order to really help with this, the entire grammar must be included.

However, one guess (something that has bit me) is forgetting optional
rule calls at the beginning - do you by any change have rules reachable
from alt 4 and 6 that start with _NEW_ (the Derived_type_definition have
two optional rule calls at the beginning and may thus start with _NEW_).

Also note, the problem is not at the point where it is considering alt 4
and 6 for the *first* time, but when it is *recursing* to
Type_definition - if no rule reachable from Type_definition recurses
back to Type_definition the reasoning is different; then you can think
about only the very first case.

Hope that helps

Regards
- henrik
Re: [Xtext 2.3.1] : Unexpected non-LL(*) decisions due to recursive rule invocations [message #1201331 is a reply to message #1199963] Thu, 21 November 2013 17:43 Go to previous messageGo to next message
Didier Garcin is currently offline Didier Garcin
Messages: 39
Registered: April 2013
Member
Thank you, Henrik for your answer.

I've followed your suggestion concerning the keywords : I have commented their definition as terminals to insert their literal in the grammar.
And there is a great benefit to have done this job : significantly less warnings at the end.

Quote:
However, one guess (something that has bit me) is forgetting optional
rule calls at the beginning - do you by any change have rules reachable
from alt 4 and 6 that start with _NEW_ (the Derived_type_definition have
two optional rule calls at the beginning and may thus start with _NEW_).


However, the previous modification of my grammar as said before doesn't solve this error (
[fatal] rule ruleType_definition has non-LL(*) decision due to recursive rule invocations reachable from alts 4,6
).

(If I understand exactly what you mean) my answer to me is no because considering absence of common elements of the 1-lookaheads.

Quote:
Also note, the problem is not at the point where it is considering alt 4
and 6 for the *first* time, but when it is *recursing* to
Type_definition - if no rule reachable from Type_definition recurses
back to Type_definition the reasoning is different; then you can think
about only the very first case.


I've checked Type_definition, Derived_type_definition (alt 4), Array_type_definition (alt 6) are not referenced anywhere else. So, no circuit and recursion are possible.

To go further

I wonder if there is a way to access internal data of the parser generator as developers take care to trace for their own use. Perhaps, it will move me on a track (directly translated from a french expression, hoping it is understandable).

Second, I was intrigued too about start rule. Indeed, there is no explicit start rule in a xtext grammar. I wonder how Xtext does to select the good start-rule if there is no source (i.e root non-terminal) - because of cycles - in the dependency graph or when they are several ones. This later case means the grammar is indeed invalid.
What would be the behaviour of the parser generator ?

[Updated on: Thu, 21 November 2013 17:54]

Report message to a moderator

Re: [Xtext 2.3.1] : Unexpected non-LL(*) decisions due to recursive rule invocations [message #1201378 is a reply to message #1201331] Thu, 21 November 2013 18:14 Go to previous messageGo to next message
Henrik Lindberg is currently offline Henrik Lindberg
Messages: 2500
Registered: July 2009
Senior Member
On 2013-21-11 18:43, Didier Garcin wrote:
> Thank you, Henrik for your answer.
>
> I've followed your suggestion concerning the keywords : I have commented
> their definition as terminals to insert their literal in the grammar.
> And there is a great benefit to have done this job : significantly less
> warnings at the end.
>
> Quote:
>> However, one guess (something that has bit me) is forgetting optional
>> rule calls at the beginning - do you by any change have rules
>> reachable from alt 4 and 6 that start with _NEW_ (the
>> Derived_type_definition have two optional rule calls at the beginning
>> and may thus start with _NEW_).
>
>
> However, the previous modification of my grammar as said before doesn't
> solve this error ([fatal] rule ruleType_definition has non-LL(*)
> decision due to recursive rule invocations reachable from alts 4,6).
>
> (If I understand exactly what you mean) my answer to me is no because
> considering absence of common elements of the 1-lookaheads.
>
> Quote:
>> Also note, the problem is not at the point where it is considering alt
>> 4 and 6 for the *first* time, but when it is *recursing* to
>> Type_definition - if no rule reachable from Type_definition recurses
>> back to Type_definition the reasoning is different; then you can think
>> about only the very first case.
>
>
> I've checked Type_definition, Derived_type_definition (alt 4),
> Array_type_definition (alt 6) are not referenced anywhere else. So, no
> circuit and recursion are possible.
>
Can you post the entire grammar?
Otherwise it will all be speculation about what could possibly be wrong.

> I wonder if there is a way to access internal data of the parser
> generator as developers take care to trace for their own use. Perhaps,
> it will move me on a track (directly translated from a french
> expression, hoping it is understandable).

There is an ANTLR tool / IDE that can help with getting an understanding
of what the grammar does.

- henrik
Re: [Xtext 2.3.1] : Unexpected non-LL(*) decisions due to recursive rule invocations [message #1201539 is a reply to message #1201378] Thu, 21 November 2013 20:03 Go to previous messageGo to next message
Didier Garcin is currently offline Didier Garcin
Messages: 39
Registered: April 2013
Member
Yes, I'm using AntlrWorks.

The arrows say nothing else.

[Updated on: Thu, 21 November 2013 20:22]

Report message to a moderator

Re: [Xtext 2.3.1] : Unexpected non-LL(*) decisions due to recursive rule invocations [message #1201712 is a reply to message #1201539] Thu, 21 November 2013 22:04 Go to previous message
Didier Garcin is currently offline Didier Garcin
Messages: 39
Registered: April 2013
Member
No Message Body

[Updated on: Thu, 21 November 2013 22:12]

Report message to a moderator

Previous Topic:[Xtext 2.4.1] Resolve cross references without 'name' in target file
Next Topic:[General question] : Xtext interoperability
Goto Forum:
  


Current Time: Thu Oct 02 02:27:42 GMT 2014

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

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