Skip to main content



      Home
Home » Modeling » TMF (Xtext) » Left recursion
Left recursion [message #645269] Thu, 16 December 2010 05:47 Go to next message
Eclipse UserFriend
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 13:33 Go to previous messageGo to next message
Eclipse UserFriend
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 13:39 Go to previous messageGo to next message
Eclipse UserFriend
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 13:11 Go to previous messageGo to next message
Eclipse UserFriend
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 16:19 Go to previous messageGo to next message
Eclipse UserFriend
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 10:59 Go to previous messageGo to next message
Eclipse UserFriend
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 11:43 Go to previous messageGo to next message
Eclipse UserFriend
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 11:28 Go to previous messageGo to next message
Eclipse UserFriend
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 09:57 Go to previous message
Eclipse UserFriend
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: Thu Jul 03 05:54:50 EDT 2025

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

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

Back to the top