Left recursion [message #645269] |
Thu, 16 December 2010 05:47  |
Eclipse User |
|
|
|
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 #646053 is a reply to message #645371] |
Tue, 21 December 2010 13:11   |
Eclipse User |
|
|
|
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 #646206 is a reply to message #646192] |
Wed, 22 December 2010 11:43   |
Eclipse User |
|
|
|
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.)
|
|
|
|
|
Powered by
FUDForum. Page generated in 0.28296 seconds