Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » TMF (Xtext) » Please, need help on indirect left recursive problem(direct and indirect left recursive problem)
Please, need help on indirect left recursive problem [message #810706] Thu, 01 March 2012 13:06 Go to next message
Joe Müller is currently offline Joe MüllerFriend
Messages: 12
Registered: March 2012
Junior Member
Hi@all,

My name is Joe and I coming from Austria. Currently, I'm working on my first xtext example and I read the xtext docu and a lot about how we can avoid left recursive grammar. For the simple cases I was able to remove it and it works but for the non trivial one I have no clue how I should solve it. Please, maybe someone can give me a hint/solution for my problem. Above you can see a simplified abridgement of my code.

Many many thanks in advance,
Joe


Expr returns Expr:
	  ( Const ) 
	| ( Array )
	| ( Struct )
	| ( expr+=Expr '||' expr+=Expr ) //direct left recursive
	| ( expr+=Expr '&&' expr+=Expr ) //direct left recursive
	| ( '(' name+=ID ')' expr+=Expr)
	| ( '(' expr+=Expr ')' )
;

Array:
	  ( '[' (expr+=Expr)? ']' )
	| ( '[' ':' name+=ID ']' )
	| ( expr+=Expr '[' (  name+=ID( ','  name+=ID)* )? ']' ) //indirect left recursive
;

Struct:
	  ('<' expr+=Expr '>')
	| (expr+=Expr '<' expr+=Expr '>' expr+=Expr) //indirect left recursive
;

Const:
	| 'float' 
	| 'double'
	| 'char' 
	| 'true' 
	| 'false' 
;


Re: Please, need help on indirect left recursive problem [message #810928 is a reply to message #810706] Thu, 01 March 2012 17:40 Go to previous messageGo to next message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 14665
Registered: July 2009
Senior Member
Hi,

did you already have a look at http://blog.efftinge.de/2010/08/parsing-expressions-with-xtext.html

~Christian


Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Re: Please, need help on indirect left recursive problem [message #811429 is a reply to message #810928] Fri, 02 March 2012 10:34 Go to previous messageGo to next message
Joe Müller is currently offline Joe MüllerFriend
Messages: 12
Registered: March 2012
Junior Member
Hi Christian,

thanks for the link. This blog explains in an understandable way how I can eliminate direkt left recursive Smile but not how I should cope with indirect left recursive, or?

I have re-designed the grammar as follows, where the direct recursive expressions are eliminated. How should this work for the indirect one?

thanks,
Joe


Expr_or returns Expr:
	Expr_and ( {Expr_or.left=current} '||' right+=Expr_and )*
;

Expr_and returns Expr:
	Expr_rest ( {Expr_and.left=current} '&&' right+=Expr_rest)*
;

Expr_rest returns Expr:
	  ( Const )
	| ( Array )
	| ( Struct )
	| ( '(' name+=ID ')' expr+=Expr_or)
	| ( '(' expr+=Expr_or ')' )
;

Const:
	| 'float' 
	| 'double'
	| 'char' 
	| 'true' 
	| 'false' 
;

Array:
	  ( '[' (expr+=Expr_or)? ']' )
	| ( '[' ':' name+=ID ']' )
	| ( expr+=Expr_or '[' (  name+=ID( ','  name+=ID)* )? ']' ) //indirect left recursive
;

Struct:
	  ('<' expr+=Expr_or '>')
	| (expr+=Expr_or '<' expr+=Expr_or '>' expr+=Expr_or) //indirect left recursive
;

Re: Please, need help on indirect left recursive problem [message #811715 is a reply to message #811429] Fri, 02 March 2012 18:31 Go to previous message
Meinte Boersma is currently offline Meinte BoersmaFriend
Messages: 434
Registered: July 2009
Location: Leiden, Netherlands
Senior Member
Left-recursion == left-recursion, whether it's direct or indirect makes no difference (for Xtext/ANTLR) - the only difference is that the indirect kind is more difficult to spot.

You'd better follow the pattern from Sven's blog completely and make everything either an operator/operation or an atom (i.e. primary). Also, you use += where you're better off using a simple assignment (=).


Previous Topic:Xtext 2.2.1 != Xtext 2.0.1 on Enumeration elements?
Next Topic:handling large files
Goto Forum:
  


Current Time: Fri Apr 26 02:51:40 GMT 2024

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

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

Back to the top