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 |
|
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 |
Henrik Lindberg Messages: 2509 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 |
|
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 |
Henrik Lindberg Messages: 2509 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
|
|
| | |
Goto Forum:
Current Time: Wed Sep 25 17:31:56 GMT 2024
Powered by FUDForum. Page generated in 0.05712 seconds
|