Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » TMF (Xtext) » Ambiguous grammar
Ambiguous grammar [message #1767135] Sat, 01 July 2017 19:52 Go to next message
Carsten Wrobel is currently offline Carsten WrobelFriend
Messages: 9
Registered: May 2017
Junior Member
Hi,

I have a problem with an ambiguous Xtext grammar, and can't seem to find the right solution to solve it.

I have tried using syntactic predicates, but wasn't able to disambiguate this way.

An alternative solution could be to use the backtrack option which actually prevents errors when generating xtext artifacts. However, my understanding is that some Antlr warnings will be suppressed when using this option and therefore I am reluctant to use it. I would prefer a solution with some kind of refactoring in stead. Any recommendations/suggestions would be appreciated.

The problem is related to this rule:
Reuse:
{Reuse} ('edit' ref=DotExpression | 'add' add=ReUseAble)
;
And the parser gives these errors:
Decision can match input such as "'edit'" using multiple alternatives: 1, 2
Decision can match input such as "'add'" using multiple alternatives: 1, 2

The whole xtext grammar file is shown below, but only the first 5 rules are relevant for this problem.

grammar org.xtext.example.mydsl4.MyDsl with org.eclipse.xtext.common.Terminals

import "http://www.xtext.org/example/mydsl4/MyDsl"
import "http://www.eclipse.org/emf/2002/Ecore" as ecore


Robot:
'Robot' name=ID
(links += Link | joint+=Joint)*
;

ReUseAble:
Link | Visual | Inertial | Collision
;

Link:
{Link} 'Link' name=ID
(('def' (inertial=Inertial | visual+=Visual | collision+=Collision)*)
| ('reuse' link=[Link] reuse+=Reuse*)
)?
;

Reuse:
{Reuse} ('edit' ref=DotExpression | 'add' add=ReUseAble)
;


DotExpression returns Ref:
ReUsableRef ({DotExpression.ref=current} "." tail=[ReUseAble])*
;

ReUsableRef returns Ref:
{ReUsableRef} reuseable=[ReUseAble]
;

Inertial:
{Inertial} 'Inertial' (name=ID)?
inertia=Inertia
mass=Mass
(origin=Origin)?
;

Inertia:
{Inertia} 'Inertia' (name=ID)?
'ixx' ixx=URDFAttrSignedNumeric
'ixy' ixy=URDFAttrSignedNumeric
'ixz' ixz=URDFAttrSignedNumeric
'iyy' iyy=URDFAttrSignedNumeric
'iyz' iyz=URDFAttrSignedNumeric
'izz' izz=URDFAttrSignedNumeric
;


Visual:
{Visual} 'Visual' (name=ID)?
'Geometry' geometry+=Geometry*
(origin=Origin)?
('Material' material=Material)?

;

Origin:
{Origin} 'Origin' (name=ID)?
'x' x=URDFAttrSignedNumeric
'y' y=URDFAttrSignedNumeric
'z' z=URDFAttrSignedNumeric
('roll' roll=URDFAttrSignedNumeric)?
('pitch' pitch=URDFAttrSignedNumeric)?
('yaw' yaw=URDFAttrSignedNumeric)?
;

Mass:
{Mass} 'Mass' (name=ID)?
'massKilogram' massKilogram=URDFAttrSignedNumeric
;

Collision:
'Collision' name=ID
'Geometry' geometry+=Geometry*
(origin=Origin)?
;

Geometry:
Box | Cylinder | Mesh | Sphere

;

Box:
'Box' (name=ID)?
'height' height=URDFAttrNumeric
'length' length=URDFAttrNumeric
'width' width=URDFAttrNumeric
;

Cylinder:
'Cylinder' (name=ID)?
'radius' radius=URDFAttrNumeric
'length' length=URDFAttrNumeric
;

Mesh:
'Mesh' (name=ID)?
'pathToFile' pathToFile=URDFAttrSTRING
//('scale' dimension=Box)?
;

Sphere:
'Sphere' (name=ID)?
'radius' radius=URDFAttrNumeric
;

Material:
Texture | Color
;


Texture:
'Texture' (name=ID)?
'pathToFile' pathToFile=URDFAttrSTRING
;


// RGBA values must be floats between 0 and 1 incl
Color:
'Color' (name=ID)?
'red' red=URDFAttrFloat
'green' green=URDFAttrFloat
'blue' blue=URDFAttrFloat
'alpha' alpha=URDFAttrFloat
;

Joint:
'Joint' name=ID
//'ChildOf' childOf=[Link]
//'ParentOf' parentOf=[Link]
//'Type' type=JointType
(('def' 'ChildOf' childOf=[Link]
'ParentOf' parentOf=[Link]
'Type' type=JointType)
( origin=Origin | axis=Axis | limit=Limit | calibration=Calibration | dynamics=Dynamics | safetycontroller=SafetyController)* |
//HOW TO REUSE: CHANGE PARENT AND CHILD LINKS??
('reuse' isReuseOf=[Joint]
'ChildOf' childOf=[Link]
'ParentOf' parentOf=[Link]
reuse=Reuse
)
)?
;

enum JointType:
fixed = 'fixed' |revolute = 'revolute' | prismatic = 'prismatic' | continuous = 'continuous'
;

/* Binary values must be 0 or 1 - digitsum must be 1, WHY NEED TO DEFINE ALL THREE?? */
//keyword aliases: 'xyz' or 'x', 'y', 'z'
Axis:
'Axis' (name=ID)?
'x' x=URDFAttrINT
'y' y=URDFAttrINT
'z' z=URDFAttrINT
;

Limit:
'Limit' (name=ID)?
'effort' effort=URDFAttrSignedNumeric
'velocity' velocity=URDFAttrSignedNumeric
'lower' lower=(URDFAttrSignedNumeric)?
'upper' upper=(URDFAttrSignedNumeric)?
;

Calibration:
{Calibration} 'Calibration' (name=ID)?
('rising' rising=URDFAttrSignedNumeric)?
('falling' falling=URDFAttrSignedNumeric)?
;

Dynamics:
{Dynamics} 'Dynamics' (name=ID)?
('friction' friction=URDFAttrSignedNumeric)?
('damping' damping=URDFAttrSignedNumeric)?
;


SafetyController:
'SafetyController' (name=ID)?
'k_velocity' k_velocity=URDFAttrSignedNumeric
('k_position' k_position=URDFAttrSignedNumeric)?
('softLowerLimit' softLowerLimit=URDFAttrSignedNumeric)?
('softUpperLimit' softUpperLimit=URDFAttrSignedNumeric)?
;


//Should we cut Mimic from the spec - NEED TO GET INTERPRETATION OF ATTRS??
/*Mimic:
'Mimic' (name=ID)?
'mimics' mimics=[Joint]
('multiplier' multiplier=URDFAttrSignedNumeric)?
('offSet' offSet=URDFAttrSignedNumeric)?
;*/


/*Constant:
;*/

URDFAttrSignedNumeric:
{URDFAttrSignedNumeric}
(name=ID)?
value = SIGNED_NUMERIC
;

URDFAttrFloat:
value = FLOAT
;

URDFAttrINT:
value = INT
;

URDFAttrNumeric:
value = NUMERIC
;

URDFAttrSTRING:
value = STRING
;

FLOAT returns ecore::EFloat:
INT '.' INT
;

SCIENTIFIC returns ecore::EBigDecimal:
FLOAT 'e' ('+' | '-')? INT
;

SIGNED_NUMERIC:
('-')? (INT | FLOAT | SCIENTIFIC)
;

NUMERIC:
INT | FLOAT | SCIENTIFIC
;

Thanks,
Carsten
Re: Ambiguous grammar [message #1767144 is a reply to message #1767135] Sun, 02 July 2017 06:05 Go to previous messageGo to next message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 14661
Registered: July 2009
Senior Member
here is the smallest grammar showing your problem:

Robot:
'Robot' name=ID
(links += Link)* 
;

ReUseAble: 
Link
;

Link:
{Link} 'Link' name=ID
('reuse' link=[Link] reuse+=Reuse*)?
;

Reuse:
{Reuse} ('add' add=ReUseAble)
;


the problems are


(links += Link)*

and

reuse+=Reuse*

do the new links go into the first += or into the second += ?


Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Re: Ambiguous grammar [message #1767151 is a reply to message #1767144] Sun, 02 July 2017 13:26 Go to previous messageGo to next message
Carsten Wrobel is currently offline Carsten WrobelFriend
Messages: 9
Registered: May 2017
Junior Member
Hi Christian,

Thank you for a quick reply.

A Link can be created in 2 ways:
1. The 'basic' way - without re-using an existing link
2. The 're-use' way using the reuse keyword (assuming at least 1 basic link has
already been defined).

To answer your question - all new links go through the first += but only re-use links goes through the second +=

Thanks,
Carsten
Re: Ambiguous grammar [message #1767154 is a reply to message #1767151] Sun, 02 July 2017 13:44 Go to previous messageGo to next message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 14661
Registered: July 2009
Senior Member
But how to differ them?

Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Re: Ambiguous grammar [message #1767161 is a reply to message #1767154] Sun, 02 July 2017 19:59 Go to previous messageGo to next message
Carsten Wrobel is currently offline Carsten WrobelFriend
Messages: 9
Registered: May 2017
Junior Member
In the model, new ReUse based links can be separated from other links by having a reference to a ReUse type which is not null. For the other type of links this reference will be null.

As I see it, this issue only applies to ReUse based links.

The ambiguity occurs AFTER a ReUse link is created and the user either starts to add new features/attributes or change existing features/attributes which have been inherited from the parent-link.

Thanks,
Carsten
Re: Ambiguous grammar [message #1767164 is a reply to message #1767161] Sun, 02 July 2017 20:16 Go to previous messageGo to next message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 14661
Registered: July 2009
Senior Member
you can try to use a predicate to solve the ambiguity

Link:
{Link} 'Link' name=ID
('reuse' link=[Link] =>('add' reuse+=Reuse)*)?
;

Reuse:
{Reuse} (add=ReUseAble)
;


Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Re: Ambiguous grammar [message #1767172 is a reply to message #1767164] Mon, 03 July 2017 07:29 Go to previous messageGo to next message
Ed Willink is currently offline Ed WillinkFriend
Messages: 7655
Registered: July 2009
Senior Member
Hi

You can indeed use a predicate to bias the ambiguity to one solution. However IMHO this is just kicking the can down the road until you have a user who complains that he wanted alternative B whilst your predicate imposed alternative A. The ambiguity is a GOOD diagnostic warning you that you have a BAD grammar that if implemented is probably going to cause problems for your users. You need to redesign your grammar so that whatever the users need to express can be expressed unambiguously. (I am surprised to see this warning coming from Xtext, it is the kind of check that I normally expect from stronger LALR tools; Google for "shift reduce conflict" and read about "reduce reduce conflict"s.).

Regards

Ed Willink
Re: Ambiguous grammar [message #1767342 is a reply to message #1767172] Tue, 04 July 2017 19:03 Go to previous message
Carsten Wrobel is currently offline Carsten WrobelFriend
Messages: 9
Registered: May 2017
Junior Member
Thanks Ed.

Agree. I have tried to solve the problem using predicates but haven't found a good solution, so I'll have to re-design the grammar a bit. Thanks for the Google search reference.

Regards
Carsten
Previous Topic:How to maka a rule LL(*) while preserving semantics?
Next Topic:Adding a library to an Xbase DSL
Goto Forum:
  


Current Time: Tue Mar 19 03:33:13 GMT 2024

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

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

Back to the top