Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » TMF (Xtext) » Left recursion
Left recursion [message #645269] Thu, 16 December 2010 10:47 Go to next message
adrian  is currently offline adrian Friend
Messages: 93
Registered: August 2009
Member
Hi all
I have a lefet recursive problem in my grammar :First my grammar is somthing like this :

ArrayAccess returns mydsl::ArrayAccess :
codeElement+=Expression '['index=INT ']'

;

FieldAccess returns mydsl::FieldAccess :
expression=Expression '.' field=ID
;

Expression returns mydsl::Expression :
FieldAccess|ArrayAccess

to eliminate the left recursion I try this syntax :

FieldAccess returns mydsl::FieldAccess :
FieldAccess2 ({mydsl::FieldAccess.expression=current} '.' field=ID)*
;
FieldAccess2 returns mydsl::FieldAccess :
expression=ArrayAccess'.' field=ID
;

ArrayAccess returns mydsl::ArrayAccess :
ArrayAccess2 ({mydsl::ArrayAccess.codeElement+=current} '['index=INT']')*
;

ArrayAccess2 returns mydsl::ArrayAccess :
codeElement+=FieldAccess '['index=INT']'

;

But I still have the recursion
Any idea how the resolve this problem?
thanks in advance
Re: Left recursion [message #645363 is a reply to message #645269] Thu, 16 December 2010 18:33 Go to previous messageGo to next message
Henrik Lindberg is currently offline Henrik LindbergFriend
Messages: 2509
Registered: July 2009
Senior Member
Have you looked at the Expression example?
- henrik

On 12/16/10 11:47 AM, piko wrote:
> Hi all I have a lefet recursive problem in my grammar :First my grammar
> is somthing like this :
> ArrayAccess returns mydsl::ArrayAccess : codeElement+=Expression
> '['index=INT ']'
> ;
>
> FieldAccess returns mydsl::FieldAccess : expression=Expression '.'
> field=ID ;
>
> Expression returns mydsl::Expression :
> FieldAccess|ArrayAccess
>
> to eliminate the left recursion I try this syntax :
>
> FieldAccess returns mydsl::FieldAccess : FieldAccess2
> ({mydsl::FieldAccess.expression=current} '.' field=ID)*
> ;
> FieldAccess2 returns mydsl::FieldAccess : expression=ArrayAccess'.'
> field=ID
> ;
> ArrayAccess returns mydsl::ArrayAccess : ArrayAccess2
> ({mydsl::ArrayAccess.codeElement+=current} '['index=INT']')*
> ;
>
> ArrayAccess2 returns mydsl::ArrayAccess : codeElement+=FieldAccess
> '['index=INT']'
> ;
>
> But I still have the recursion
> Any idea how the resolve this problem?
> thanks in advance
>
Re: Left recursion [message #645371 is a reply to message #645269] Thu, 16 December 2010 18:39 Go to previous messageGo to next message
Lorenzo Bettini is currently offline Lorenzo BettiniFriend
Messages: 1812
Registered: July 2009
Location: Firenze, Italy
Senior Member
On 12/16/2010 11:47 AM, piko wrote:
> Hi all I have a lefet recursive problem in my grammar :First my grammar
> is somthing like this :
> ArrayAccess returns mydsl::ArrayAccess : codeElement+=Expression
> '['index=INT ']'
> ;
>
> FieldAccess returns mydsl::FieldAccess : expression=Expression '.'
> field=ID ;
>
> Expression returns mydsl::Expression :
> FieldAccess|ArrayAccess
>
> to eliminate the left recursion I try this syntax :
>
> FieldAccess returns mydsl::FieldAccess : FieldAccess2
> ({mydsl::FieldAccess.expression=current} '.' field=ID)*
> ;
> FieldAccess2 returns mydsl::FieldAccess : expression=ArrayAccess'.'
> field=ID
> ;
> ArrayAccess returns mydsl::ArrayAccess : ArrayAccess2
> ({mydsl::ArrayAccess.codeElement+=current} '['index=INT']')*
> ;
>
> ArrayAccess2 returns mydsl::ArrayAccess : codeElement+=FieldAccess
> '['index=INT']'
> ;
>
> But I still have the recursion
> Any idea how the resolve this problem?
> thanks in advance
>

Hi Pico

I have a similar grammar structure in my DSL... I'll try to reproduce
here a snippet of code (I didn't test the snippets, but my grammar works):

never mind the [ecore::...] parts...

LanguageExpression:
TerminalExpression
({CompoundExpression.mainExpression = current}
op='.'
subExpression=SubExpression)*
;

TerminalExpression returns LanguageExpression:
VariableReference |
IndexedVariable
;

VariableReference:
'$' varRef=[VariableDeclaration]
;

IndexedVariable:
'$' varRef=[VariableDeclaration] '[' index=ArrayIndex ']'
;

SubExpression:
{Indexed} feature=[ecore::ENamedElement] '[' index=INT ']' |
{Feature} feature=[ecore::ENamedElement]
;

this way in my DSL (but again, what I write here is a copy and paste
with some adjustments which I didn't test), I can write

$C

$C[1]

$C[1].foo

$C.foo[1]

$C.foo[1][1]

$C.foo[1][1].bar

$C.foo[1][1].bar[1]

hope this helps...

cheers
Lorenzo
--
Lorenzo Bettini, PhD in Computer Science, DI, Univ. Torino
ICQ# lbetto, 16080134 (GNU/Linux User # 158233)
HOME: http://www.lorenzobettini.it MUSIC: http://www.purplesucker.com
http://www.myspace.com/supertrouperabba
BLOGS: http://tronprog.blogspot.com http://longlivemusic.blogspot.com
http://www.gnu.org/software/src-highlite
http://www.gnu.org/software/gengetopt
http://www.gnu.org/software/gengen http://doublecpp.sourceforge.net


Re: Left recursion [message #646053 is a reply to message #645371] Tue, 21 December 2010 18:11 Go to previous messageGo to next message
Vincent  is currently offline Vincent Friend
Messages: 7
Registered: December 2010
Junior Member
My problem is also something like it, but I don't get it to work. I added it here, so different kinds of recursion-problems are together in one thread.

I want to make a call to a function, but when it's declared without arguments, I also want to call it without "( )". This gives serious problems and while it seems to be a recursion-problem, I cannot translate this solution to my problem.

function A ( );
function B (var w, var x);
y = 5 + A;
z = 8 + B (A / 2, A);


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

generate myDsl "http://www.xtext.org/example/mydsl/MyDsl"

Program:
	declarations+=FunctionDeclaration+
	assignments+=Assignment+
	;

FunctionDeclaration returns Variable:
	'function' name=ID ('(' ('var' var+=ID ('var' var+=ID)*)? ')')? ';' ;

FunctionReference:
	declaration=[Variable] ('(' (sequence+=Sequence (',' sequence+=Sequence)*)? ')')?
;

Assignment:
	name=ID '=' sequence+=Sequence ';'
	;

Sequence: Addition ( {Sequence.expressions+=current} expressions+=Addition)*;

Addition returns Expression: 
	Multiplication ( {Op.values+=current} operator=('+'|'-') values+=Multiplication)*;

Multiplication returns Expression: 
	Term ( {Op.values+=current} operator=('*'|'/') values+=Term)*;
	
Term returns Expression:
	Atom | Parens;
	
Atom: 
	value+=INT | (references += FunctionReference) ;

Parens returns Expression: 
	'(' Addition ')';
	


It gives an error "Decision can match input such as "RULE_ID '('" using multiple alternatives: 1, 2". I suppose I have to use actions, but don't know how.
Re: Left recursion [message #646074 is a reply to message #646053] Tue, 21 December 2010 21:19 Go to previous messageGo to next message
Meinte Boersma is currently offline Meinte BoersmaFriend
Messages: 434
Registered: July 2009
Location: Leiden, Netherlands
Senior Member
Funny thing is: you're already using actions, such as
{Op.values+=current}
(which is an assigned action).

The basic problem with your grammar is that you introduce left-recursion through the FunctionReference by calling the Sequence rule again. Backtracking {c|sh}ould help a bit in this case, but I'm not sure and haven' tried.


Re: Left recursion [message #646192 is a reply to message #645269] Wed, 22 December 2010 15:59 Go to previous messageGo to next message
Vincent  is currently offline Vincent Friend
Messages: 7
Registered: December 2010
Junior Member
Thanks again, Meinte. I meant there are no actions in FunctionReference.

Backtracking is on, but i could not find any documentation on it. So I'm now a dumb user who has clicked the button and complaints nothing happened.

error(211): [fatal] rule rule__FunctionReference__Group__1__Impl has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2.  Resolve by left-factoring or using syntactic predicates hereor using backtrack=true option.
warning(200): Decision can match input such as "'(' RULE_ID" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
warning(200): Decision can match input such as "'(' '('..')'" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input


I see a similar problem

Left-factoring is described here and here, but I think I tried that already in a few forms or I misunderstand it.

I hoped Henrik would post the final solution for his problem.
Re: Left recursion [message #646206 is a reply to message #646192] Wed, 22 December 2010 16:43 Go to previous messageGo to next message
Meinte Boersma is currently offline Meinte BoersmaFriend
Messages: 434
Registered: July 2009
Location: Leiden, Netherlands
Senior Member
You can't put actions in FunctionReference because that would only be useful inside the optional group, but then the current is already created because of the 'declaration=[Variable]' bit.

The real problem is that a '(' after a token pointing to a Variable can belong to both the optional parameter group as well as to a Sequence, so the grammar really has left-recursion at that point.

You could try and make ',' an (infix, left-associative) operator (which you then disallow outside a function call) and make function references a real (prefix) operator as well. By giving that prefix operator the 2nd-highest precedence (after parentheses), something like 'f a+b, c' would be invalid (because , is not allowed outside of a function call) forcing the user to write 'f(a+b, c)'. (I haven't tried this or given it more thought, though.)


Re: Left recursion [message #646389 is a reply to message #645269] Thu, 23 December 2010 16:28 Go to previous messageGo to next message
adrian  is currently offline adrian Friend
Messages: 93
Registered: August 2009
Member
Hi Lorenzo,
thanks for your help
That doesn t work for me because 'field' is an ID in my metamodel not an Expression and for example the expression : a.b.c[1] must be evaluated as :
ArrayAccess 1
----FieldAccess c
-------FieldAccess b
------------Name a
and the expression : a[3].b.c must be evaluated as :
FieldAccess c
----Fieldaccess b
-------ArrayAccess 3
------------Name a
Re: Left recursion [message #646470 is a reply to message #646389] Fri, 24 December 2010 14:57 Go to previous message
Lorenzo Bettini is currently offline Lorenzo BettiniFriend
Messages: 1812
Registered: July 2009
Location: Firenze, Italy
Senior Member
On 12/23/2010 05:28 PM, piko wrote:
> Hi Lorenzo,
> thanks for your help That doesn t work for me because 'field' is an ID
> in my metamodel not an Expression and for example the expression :
> a.b.c[1] must be evaluated as :
> ArrayAccess 1
> ----FieldAccess c
> -------FieldAccess b
> ------------Name a
> and the expression : a[3].b.c must be evaluated as :
> FieldAccess c
> ----Fieldaccess b
> -------ArrayAccess 3
> ------------Name a

then probably you should have an array access both for field and for
name? That's what I meant with my grammar, where I had to have an array
access rule for two kinds of elements...

hope this helps
Lore

--
Lorenzo Bettini, PhD in Computer Science, DI, Univ. Torino
ICQ# lbetto, 16080134 (GNU/Linux User # 158233)
HOME: http://www.lorenzobettini.it MUSIC: http://www.purplesucker.com
http://www.myspace.com/supertrouperabba
BLOGS: http://tronprog.blogspot.com http://longlivemusic.blogspot.com
http://www.gnu.org/software/src-highlite
http://www.gnu.org/software/gengetopt
http://www.gnu.org/software/gengen http://doublecpp.sourceforge.net


Previous Topic:New line and white space problems
Next Topic:Is it a bug of resolving the model?
Goto Forum:
  


Current Time: Fri Apr 26 00:33:18 GMT 2024

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

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

Back to the top