Eclipse Community Forums: TMF (Xtext) » Pb with recursive rule invocation

Help

Home

Home » Modeling » TMF (Xtext) » Pb with recursive rule invocation

Show: Today's Messages :: Show Polls :: Message Navigator

Pb with recursive rule invocation [message #1829435]

Fri, 03 July 2020 11:37

Yannick DAVELUY

Messages: 39
Registered: July 2020

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

Report message to a moderator

Re: Pb with recursive rule invocation [message #1829449 is a reply to message #1829435]

Fri, 03 July 2020 19:33

Ed Willink

Messages: 7655
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

Report message to a moderator

Re: Pb with recursive rule invocation [message #1829452 is a reply to message #1829449]

Fri, 03 July 2020 21:17

Yannick DAVELUY

Messages: 39
Registered: July 2020

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

Report message to a moderator

Re: Pb with recursive rule invocation [message #1829481 is a reply to message #1829452]

Sat, 04 July 2020 18:56

Ed Willink

Messages: 7655
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

Report message to a moderator

Re: Pb with recursive rule invocation [message #1829501 is a reply to message #1829481]

Sun, 05 July 2020 19:11

Yannick DAVELUY

Messages: 39
Registered: July 2020

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

Report message to a moderator

Re: Pb with recursive rule invocation [message #1829530 is a reply to message #1829501]

Mon, 06 July 2020 08:34

Ed Willink

Messages: 7655
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

Report message to a moderator

Re: Pb with recursive rule invocation [message #1829534 is a reply to message #1829530]

Mon, 06 July 2020 09:32

Ed Willink

Messages: 7655
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

Report message to a moderator

Previous Topic:	Error in running workflow
Next Topic:	Exporting LSP from a DSL written in Xtext

Goto Forum:

-=] Back to Top [=-

[ Syndicate this forum (XML) ] [

]

Current Time: Thu Apr 25 15:18:04 GMT 2024

.:: Contact :: Home ::.

Breadcrumbs

Sign up to our Newsletter