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

Help

Home

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

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

Decision and expression [message #1506064]

Wed, 10 December 2014 14:53

Grégoire Avot

Messages: 7
Registered: December 2014

Junior Member

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 14:55]

Report message to a moderator

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

Fri, 12 December 2014 15:34

Grégoire Avot

Messages: 7
Registered: December 2014

Junior Member

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.

Report message to a moderator

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

Tue, 16 December 2014 09:56

Grégoire Avot

Messages: 7
Registered: December 2014

Junior Member

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.

Report message to a moderator

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

Wed, 17 December 2014 08:03

Sebastian Zarnekow

Messages: 3118
Registered: July 2009

Senior Member

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

Report message to a moderator

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

Wed, 17 December 2014 08:18

Sebastian Zarnekow

Messages: 3118
Registered: July 2009

Senior Member

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

Report message to a moderator