Eclipse Community Forums: TMF (Xtext) » Recursion without recursion?

Help

Home

Home » Modeling » TMF (Xtext) » Recursion without recursion?

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

Recursion without recursion? [message #893033]

Mon, 02 July 2012 11:44

Hannes Müller

Messages: 24
Registered: June 2012

Junior Member

Hello everyone,

Ok, I have a problem while defining a dsl where formulas like a * (b / 2) should be written. I get errors all the time and after some hours I don't know how to proceed without help. Does enyone knows what the error message means (see error message below)? Or even better why the errors occur (see code below)? I don't see a left recursion like the ones descriped in the documentation (or in one of the blogs of one of the guys who are responsible for xtext).
----------------------------
The following error message occurs (more than once):

"warning(200): ../org.xtext.scannerdomainmodel/src-gen/org/xtext/example/mydsl/parser/antlr/internal/InternalMyDsl.g:1089:2: Decision can match input such as "'+' RULE_ID" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input"
--------------------------------------
Here is the relevant part of my xtext-file:

RecalculateFormula:
complexFormula = ComplexFormula
;

Operant:
parameter = [ParameterWithRecalculate] | integer = INT
;

SimpleFormulaWithoutBrackets:
leftOperant = Operant (operators += FormulaOperator operants += Operant)*
;

SimpleFormulaWithBrackets:
'('SimpleFormulaWithoutBrackets')'
;

SimpleFormularWithOptionalBrackets:
simpleFormularWithoutBrackets = SimpleFormulaWithoutBrackets | simpleFormulaWithBrackets = SimpleFormulaWithBrackets
;

ComplexFormula:
leftFormula = SimpleFormularWithOptionalBrackets (operators += FormulaOperator formulas += SimpleFormularWithOptionalBrackets)*
;
--------------------------

I have an additional hint:

When I only use the SimpleFormulaWithBrackets rule instead of the SimpleFormularWithOptionalBrackets rule in the ComplexFormula rule it works. But I want optional brackets!
And: If I want to add the following Rule to the operants again those error messages occur:
Operant:
parameter = [ParameterWithRecalculate] | integer = INT //| double = Double
;
Double:
predecimalNumber = INT('.'decimalNumber = INT)?
;

I would be gratefule for any hint.

THX in advance
Hannes

[Updated on: Mon, 02 July 2012 12:10]

Report message to a moderator

Re: Recursion without recursion? [message #893060 is a reply to message #893033]

Mon, 02 July 2012 12:54

Alexander Nittka

Messages: 1193
Registered: July 2009

Senior Member

Hi,

the short answer is that your double definition would also parse an int (as the decimalNumber part is optional), hence the ambiguity.

Alex

Need training, onsite consulting or any other kind of help for Xtext?
Go visit http://xtext.itemis.com or send a mail to xtext@itemis.de

Report message to a moderator

Re: Recursion without recursion? [message #893071 is a reply to message #893060]

Mon, 02 July 2012 13:25

Hannes Müller

Messages: 24
Registered: June 2012

Junior Member

Thx Alexander Smile

,

That is logical and without the optional part it works.

But what is with the rules ...

SimpleFormulaWithoutBrackets:
leftOperant = Operant (operators += FormulaOperator operants += Operant)*
;

SimpleFormulaWithBrackets:
'('SimpleFormulaWithoutBrackets')'
;

The rule SimpleFormulaWithBrackets starts and ends with brackets. Isn't that a not confusable rule because of the not optional brackets (obviously not - but why)? And how do I get optional brackets?

Thx in advance for any answer,
Hannes

[Updated on: Mon, 02 July 2012 13:29]

Report message to a moderator

Re: Recursion without recursion? [message #893141 is a reply to message #893071]

Mon, 02 July 2012 20:37

Alexander Nittka

Messages: 1193
Registered: July 2009

Senior Member

Hi,

The second short answer is: Have you looked at the arithmetics example shipped with Xtext or the grammar for XBase. These address the definition of expressions. There are also a couple of blog posts about expressions in Xtext. I guess you have, because you want a non-recursive definition.
By the way, the error is not a problem of left recursion (otherwise the message would say so). It is a problem of ambiguity, i.e. there are several ways to parse the same input (however with a different semantic structure which often is not wanted).

Not looking at the structure of the expressions you parse, does the following help as inspiration?

SimpleFormula: Operant | "("ComplexFormula")";

ComplexFormula: formulas += SimpleFormula (operators += FormulaOperator formulas += SimpleFormula)*;

Alex

Need training, onsite consulting or any other kind of help for Xtext?
Go visit http://xtext.itemis.com or send a mail to xtext@itemis.de

Report message to a moderator

Re: Recursion without recursion? [message #893220 is a reply to message #893141]

Tue, 03 July 2012 09:22

Hannes Müller

Messages: 24
Registered: June 2012

Junior Member

Hi,

Thx again for the inspiration Smile

I tried you example - the same errors are rising ...

After trying other stuff I watched the tutorial of Sven Efftinge and the Arithmetics example.

And I tried it out: If you let the example run as it is it works.
But if I try to modifiy the last line of the last rule like this (now a Parameter-reference should be allowed as part of the formula) the same errors arrise again

(code)
Expression:
Addition;

Addition returns Expression:
Multiplication (({Plus.left=current} '+' | {Minus.left=current} '-') right=Multiplication)*;

Multiplication returns Expression:
PrimaryExpression (({Multi.left=current} '*' | {Div.left=current} '/') right=PrimaryExpression)*;

PrimaryExpression returns Expression:
'(' Expression ')' | parameter = [ParameterWithRecalculate]
;

(errors)
warning(200): ../org.xtext.scannerdomainmodel.ui/src-gen/org/xtext/example/mydsl/ui/contentassist/antlr/internal/InternalMyDsl.g:648:1: Decision can match input such as "RULE_ID" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
error(201): ../org.xtext.scannerdomainmodel.ui/src-gen/org/xtext/example/mydsl/ui/contentassist/antlr/internal/InternalMyDsl.g:648:1: The following alternatives can never be matched: 2

I don't know what to do anymore Sad

So again I am gratefule for any inspiration ^^
Hannes

Report message to a moderator

Re: Recursion without recursion? [message #893260 is a reply to message #893220]

Tue, 03 July 2012 11:50

Alexander Nittka

Messages: 1193
Registered: July 2009

Senior Member

Hi,

I cannot reproduce the problem with my sample code, neither with a quick test of the arithmetic example.

Could you please post the complete grammar.

Alex

Need training, onsite consulting or any other kind of help for Xtext?
Go visit http://xtext.itemis.com or send a mail to xtext@itemis.de

Report message to a moderator

Re: Recursion without recursion? [message #893288 is a reply to message #893260]

Tue, 03 July 2012 13:14

Hannes Müller

Messages: 24
Registered: June 2012

Junior Member

Hi and thx for taking the time Smile

Here is the code - as long as I comment out the part "parameter = [ParameterWithRecalculate]" in the PrimaryExpression rule brackets can be set but don't have to (like I want it). The code is more or less copied from the Arithmetics project. But after adding the line the known errors occur ...

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

generate myDsl // ... please think of the URI here - momentary I cannot add links

DomainModel:
{DomainModel}
supportedUsers = SupportedUserStates
supportedProgressStates = SupportedProgressStates
supportedActions = SupportedStateChangingActions
measurementsWithParmeters += MeasurementsWithParametersAndStateTransitions+
;

SupportedUserStates:
'user states {'supportedUserStates += SupportedUserState (',' supportedUserStates += SupportedUserState)*'}'
;

SupportedUserState:
name = ID
;

SupportedProgressStates:
'progress states {'supportedProgressStates += SupportedProgressState (',' supportedProgressStates += SupportedProgressState)*'}'
;

SupportedProgressState:
name = ID
;

SupportedStateChangingActions:
'state changing actions {'supportedStateChangingActions += StateChangingAction (',' supportedStateChangingActions += StateChangingAction)*'}'
;

StateChangingAction:
name = ID
;

MeasurementsWithParametersAndStateTransitions:
'supported measurements {'measurementsWithParametersAndStateTransitions += MeasurementWithParametersAndTransition 'end measurement;' (measurementsWithParametersAndStateTransitions += MeasurementWithParametersAndTransition 'end measurement;')* '}'
;

MeasurementWithParametersAndTransition:
measurement = Measurement '{' (parametersWithRecalulate += ParameterWithRecalculate)+ stateTransitions = StateTransitions '}'
;

Measurement:
'measurement' name = ID
;

ParameterWithRecalculate:
// new parameter should be declared or know parameter which already has some formulas
(('parameter' name = ID) | ('known parameter' paramWithRecal = [ParameterWithRecalculate]))
'state depending recalculates {' (recalculates += Recalculate)+ '}'
;

Recalculate:
userState += [SupportedUserState] '&' progressState += [SupportedProgressState]
('&&' userState += [SupportedUserState] '&' progressState += [SupportedProgressState])* '==>' (recalculateFormula = RecalculateFormula | resusedRecalculateFormula = [RecalculateFormula]) ';'
;

RecalculateFormula:
('reusable formula 'name = ID':')? complexFormula = Expression//ComplexFormula
;

Expression:
Addition;

Addition returns Expression:
Multiplication (({Plus.left=current} '+' | {Minus.left=current} '-') right=Multiplication)*;

Multiplication returns Expression:
PrimaryExpression (({Multi.left=current} '*' | {Div.left=current} '/') right=PrimaryExpression)*;

PrimaryExpression returns Expression:
'(' Expression ')' | number = Number //| parameter = [ParameterWithRecalculate]
;

Number:
predecimalNumber = INT '.' decimalNumber = INT
;

StateTransitions:
'state transitions {' (stateTransitions += StateTransition ';')+'}'
;

StateTransition:
stateTransitionConditions += StateTransitionContition ('&&' stateTransitionConditions += StateTransitionContition)* '==>' userStateNEW = [SupportedUserState] '&' progressStateNEW = [SupportedProgressState]
;

StateTransitionContition:
userStateOLD = [SupportedUserState] '&' progressStateOLD = [SupportedProgressState] '&' stateChangingAction = [StateChangingAction]
;

Report message to a moderator

Re: Recursion without recursion? [message #893384 is a reply to message #893288]

Tue, 03 July 2012 19:07

Alexander Nittka

Messages: 1193
Registered: July 2009

Senior Member

Hi,

problem is the rule Recalculate. There is an alternative
(recalculateFormula = RecalculateFormula | resusedRecalculateFormula = [RecalculateFormula])

a) The first one is a definition of a RecalculateFormula which may be an Expression as the first part ('reusable formula 'name = ID':')? is optonal. However, an Expression may be a an ID (paramter= [ParameterWithRecalculate]).
b) The second is a reference to a RecalculateFormula via an ID.

Hence the ambiguity. The parser cannot decide whether use the recalculateFormula feature or the reuseRecalculateFormula feature when seeing an ID.

The simplest way for disambiguation would be the introduction of a keyword (recalculateFormula = RecalculateFormula | "reuse" resusedRecalculateFormula = [RecalculateFormula]), but this may be impossible if you have no control over the syntax of the language.

Alex

P.S.: White spaces within keywords are not a good idea for several reasons. It may seem nice that you get code completion for "user states {" with one proposal rather than 3, but a) this is what code templates are for where you can even complete the closing bracket in one go, b) your users may not be too happy if they are not even allowed to place the opening bracket on the next line, c) they cause major problems when it comes to lexing (try the follwing model and tell me whether a user will understand the mismatched character error message: "user states { user }"... do you?)

Need training, onsite consulting or any other kind of help for Xtext?
Go visit http://xtext.itemis.com or send a mail to xtext@itemis.de

Report message to a moderator

Re: Recursion without recursion? [message #893759 is a reply to message #893384]

Thu, 05 July 2012 13:19

Hannes Müller

Messages: 24
Registered: June 2012

Junior Member

Thx

It works now and I am happy.

The tread can be closed.

PS: And thanks for the hint -> this "user states{user}" effect is - let's say it that way - unexpected

Report message to a moderator

Previous Topic:	Cross-reference mistake
Next Topic:	Using the AST without eclipse

Goto Forum:

-=] Back to Top [=-

[ Syndicate this forum (XML) ] [

]

Current Time: Tue Apr 23 07:42:18 GMT 2024

.:: Contact :: Home ::.

Breadcrumbs

Sign up to our Newsletter