Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » TMF (Xtext) » Pb with recursive rule invocation
Pb with recursive rule invocation [message #1829435] Fri, 03 July 2020 11:37 Go to next message
Yannick DAVELUY is currently offline Yannick DAVELUYFriend
Messages: 14
Registered: July 2020
Junior Member
Hello,


Since I added ArrayValue in my grammar, I have the following errors:
Quote:

error(211): ../org.xtext.example.mydsl/src-gen/org/xtext/example/mydsl/parser/antlr/internal/InternalMyDsl.g:144:2: [fatal] rule ruleType has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2. Resolve by left-factoring or using syntactic predicates or using backtrack=true option.
error(211): ../org.xtext.example.mydsl/src-gen/org/xtext/example/mydsl/parser/antlr/internal/InternalMyDsl.g:180:2: [fatal] rule ruleValueType has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2. Resolve by left-factoring or using syntactic predicates or using backtrack=true option.



This is my simplified grammar with the reproducible problem
grammar org.xtext.example.mydsl.MyDsl with org.eclipse.xtext.common.Terminals

generate myDsl "http://www.eclipse.org/example/mydsl/MyDsl"

Model:
	'model' name=ID
	(type+=Type ';')*
	;

Type:
	AnnotationType|ValueType;
	
ValueType:
	PrimitiveType|ArrayType;

ArrayType:
	(annotation+=Annotation)*
	type=[Type] '['']'  name=ID;
	
PrimitiveType:
	(annotation+=Annotation)*
	'PrimitiveType'  name=ID;
	
AnnotationType:
	(annotation+=Annotation)*
	'AnnotationType' type=[ValueType] name=ID;

Annotation:
	{Annotation} =>'@'type=[AnnotationType] '(' value=Value ')';

Value:
	ArrayValue | IntegerValue;
	
ArrayValue:
	{ArrayValue}  '['']''{'(item+=Value (',' item+=Value)*)?'}';

IntegerValue:
	{IntegerValue} value=INT;


I tried to add syntactic predicates and use left-factoring without success.
Do you have any idea on how to solve this issue ?

Thanks

Yannick
Re: Pb with recursive rule invocation [message #1829449 is a reply to message #1829435] Fri, 03 July 2020 19:33 Go to previous messageGo to next message
Ed Willink is currently offline Ed WillinkFriend
Messages: 6874
Registered: July 2009
Senior Member
Hi

ANTLR, hence Xtext, cannot cope with left recursive rules (unlke LALR tools where left recursion is preferred.) You need to rewrite as right recursion, (or with XText contrive the reciursion to use a * cardinality).

You perhaps did not intend "int[] a [] b [] c [] d [] e" to be a valid ArrayType. This is where the left recursion is. The left recursion which elaborates the suffix of type, must be rewritten as a right recursion that elaborates the prefix of type-name.

Regards

Ed Willink
Re: Pb with recursive rule invocation [message #1829452 is a reply to message #1829449] Fri, 03 July 2020 21:17 Go to previous messageGo to next message
Yannick DAVELUY is currently offline Yannick DAVELUYFriend
Messages: 14
Registered: July 2020
Junior Member
Hi Ed,

Thank for your reply.
I don't understand how this grammar could generate an array type like "int[] a [] b [] c [] d [] e".

When I replace the reference from Value to IntegerValue in Annotation Rule the grammar compile without error.
Annotation:
	{Annotation} =>'@'type=[AnnotationType] '(' value=IntegerValue ')';


I'me beginner with xtext, sorry if I missed something.


Yannick
Re: Pb with recursive rule invocation [message #1829481 is a reply to message #1829452] Sat, 04 July 2020 18:56 Go to previous messageGo to next message
Ed Willink is currently offline Ed WillinkFriend
Messages: 6874
Registered: July 2009
Senior Member
Hi

Sorry. I never use the [Type] syntax - I always use the clearer [Type|ID] so I misread [Type] as Type rather than ID as the term. Ignore my comment.

The recursion must be more subtle. You can try successive simplification till it becomes obvious. It is a long time since I attempted to use it, but I understand that some users find AntlrWorks helpful for debugging grammars.

Regards

Ed Willink
Re: Pb with recursive rule invocation [message #1829501 is a reply to message #1829481] Sun, 05 July 2020 19:11 Go to previous messageGo to next message
Yannick DAVELUY is currently offline Yannick DAVELUYFriend
Messages: 14
Registered: July 2020
Junior Member
Hi

With Antlrworks I didn't found where the recursion is.

If I enable the backtrace the grammar compile but I would prefers to solve the problem with syntactic predicate or left refactoring.

I tried to change the grammar in many way without success.

The recursion seems subtle.

Yannick
Re: Pb with recursive rule invocation [message #1829530 is a reply to message #1829501] Mon, 06 July 2020 08:34 Go to previous messageGo to next message
Ed Willink is currently offline Ed WillinkFriend
Messages: 6874
Registered: July 2009
Senior Member
Hi

I can simplify/flatten your grammar somewhat

Model:
	type=(PrimitiveType|ArrayType) ';'
	;

ArrayType:
	(annotation+=Annotation)
	type=ID '<' '>'  name=ID;
	
PrimitiveType:
	(annotation+=Annotation)
	'PrimitiveType'  name=ID;

Annotation:
	'@'type=ID '(' value=(ArrayValue | IntegerValue) ')';
	
ArrayValue:
	'[' ']' '{' item+=(ArrayValue | IntegerValue) '}';

IntegerValue:
	value=INT;



but the problem remains even with backtrack set true.

error(211): ...: [fatal] rule ruleModel has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.


Punctuation is distinct. There are no * or + recursions. Type is an unrecursive root. The only recursion is clear ArrayValue left recurses itself. The Value usage within the double Annotation seems to confuse the tooling into giving a diagnosis at the root of the double usage rather than at the recursion.

If you really want nested array values in annotations then you will have to refactor as a right recursion wrapping arrays round values, rather than tunneling down to array contents. Much simpler to eliminate ArrayValue from within ArrayValue.

Regards

Ed Willink
Re: Pb with recursive rule invocation [message #1829534 is a reply to message #1829530] Mon, 06 July 2020 09:32 Go to previous message
Ed Willink is currently offline Ed WillinkFriend
Messages: 6874
Registered: July 2009
Senior Member
Hi

I suspect that the bulk of the challenges will vanish if you define

Annotations:
	(annotation+=Annotation)+

ArrayType:
       annotations=Annotations? ...

PrimitiveType:
       annotations=Annotations? 'PrimitiveType' ...


avoiding the need for a potentially infinite set of annotations to be parsed and backtracked depending on whether it is followed by 'PrimitiveType' or not. An Annotations production allows the successful annotations parse to be re-used for the alternative attempts.

Regards

Ed Willink
Previous Topic:Error in running workflow
Next Topic:Exporting LSP from a DSL written in Xtext
Goto Forum:
  


Current Time: Wed Oct 21 00:24:06 GMT 2020

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

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

Back to the top