Eclipse Community Forums: TMF (Xtext) » Decision and expression

Home

Home » Modeling » TMF (Xtext) » Decision and expression

Decision and expression [message #1506064]

Wed, 10 December 2014 09:53

Eclipse User

Hello forum,

I want to parse following input: a=[1+2+3] or a=[1+2+3:4+5.6]

-----------------------------------
Model: id=ID '=' add=Element;

Element: '[' (range1d=Addition | range2d=Range ) ']';
Range: left=Addition ':' right=Addition;

Addition returns Expression:
Multiplication ({Addition.left=current} '+' right=Addition)?;

Multiplication returns Expression:
Primary ({Multiplication.left=current} '*' right=Multiplication)?;

Primary returns Expression:
litteral = NumberLiteral |
'(' Addition ')';

NumberLiteral: value=INT;
-----------------------------------

When I compile this grammar, I get an error:
[fatal] rule ruleElement 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.

If I remove one of the two decisions in Element rule, I do not have compilation error. I do not understand why. Solution I used to solve this problem is to merge Element and Rule into a single rule using two actions:

-----------------------------------
Element: '[' Addition ( {Scalar.size=current} | ( {Range.left=current} ':' right=Addition)) ']';
-----------------------------------

Now everything works fine. But I still do not understand what I did wrong in my first implementation. Can someone explain this ?

Best regards,

Grégoire.

[Updated on: Wed, 10 December 2014 09:55] by Moderator

Re: Decision and expression [message #1508635 is a reply to message #1506064]

Fri, 12 December 2014 10:34

Eclipse User

Up !

Hello forum,

I found another very similar case , with same workaround... but still not understand what I did wrong ! Can someone explain ?

Regards,

Grégoire.

Re: Decision and expression [message #1513196 is a reply to message #1506064]

Tue, 16 December 2014 04:56

Eclipse User

Hello again,

I am still stuck on this issue !

The shortest example is :

Model: id=ID '=' add=Element;
Element: range1d=Range1D | range2d=Range2D;
Range1D: '[' expr=Addition ']';
Range2D: '[' left=Addition ':' right=Addition ']';
Addition returns Expression: Primary ({Addition.left=current } '+' right=Addition)?;
Primary returns Expression: litteral = INT;

I did the following tests (each starting from snippet above):
- If I modify rule Addition to
Addition returns Expression:Primary ({Addition .left=current } '+' right=Primary)?;
=> Grammar compile.

- If I modify rule Range2D to:
Range2D: '@' left=Addition ':' right=Addition '@';
=> Grammar compile.

At this point my conclusion is the conjunction between recursive Expression AND identical starting sequence for Range1D and Range2D breaks the decision in Element rule.

Of course I can merge Element, Range1D and Range2D as shown in my previous post. But I guess it is not a scalable solution for maintenance since it leads to a lot of code duplication when adding new rules in the grammar:

Item1 = Element | Triplet
Triplet: [ expr1 : expr2 : expr3 ]
Item2 : Range1D
Item3 : Range2D
Element = Range1D | Range2D

I did another test: I tried to "isolate" Expression behind intermediate rules:

Element: range1d=Range1D | range2d=Range2D;
Range1D: '[' expr=UnTruc1 ']';
Range2D: '[' left=UnTruc1 ':' right=UnTruc1 ']';
UnTruc1: truc=UnTruc2;
UnTruc2: truc=Addition;
Addition returns Expression: Primary ({Addition.left=current } '+' right=Addition )?;

This has no effect, still got the same issue.

So if someone can explain, it would be great !

Regards,

Grégoire.

Re: Decision and expression [message #1514338 is a reply to message #1506064]

Wed, 17 December 2014 03:03

Eclipse User

Hi Gregoire,

your grammar is recursive for the rule Addition but the decision point
range1d | range2 requires to look for the ':' to decide which path to
go. Since the recursive Addition is used before the colon in rule Range,
it is not possible to decide how many tokens should be read before the
parser could dive into range1d or range2d respectively. Thus the
validation issue. Your solution to use an action and left factor your
grammar looks right to me.

Best,
Sebastian
--
Looking for professional support for Xtext, Xtend or Eclipse Modeling?
Go visit: http://xtext.itemis.com

Re: Decision and expression [message #1514352 is a reply to message #1513196]

Wed, 17 December 2014 03:18

Eclipse User

Your guess is right. The recursive Expression and the identical starting
sequence for Range1D and Range2d don't play well together. You may
either want to left factor your grammar (recommended) or use a syntactic
predicate:

Element: range2d=Range2D | range1d=Range1D; // longer sequence first
Range1D: '[' expr=Addition ']';
Range2D: =>('[' left=Addition ':') right=Addition ']';

Best,
Sebastian
--
Looking for professional support for Xtext, Xtend or Eclipse Modeling?
Go visit: http://xtext.itemis.com

Re: Decision and expression [message #1514453 is a reply to message #1514338]

Wed, 17 December 2014 05:04

Eclipse User

Hello Sebastian,

Thank you for your reply. I think I understand your explanation.
Regards,

Grégoire.

Previous Topic:	question regarding existence of function in generated superclasses
Next Topic:	Problems with Scoping

Goto Forum:

-=] Back to Top [=-

Current Time: Sat Jul 26 00:25:31 EDT 2025

.:: Contact :: Home ::.

Breadcrumbs

Sign up to our Newsletter