Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » TMF (Xtext) » eliminating left recursion
eliminating left recursion [message #1730695] Wed, 27 April 2016 17:03 Go to next message
Danny Quizzo is currently offline Danny QuizzoFriend
Messages: 16
Registered: April 2016
Junior Member
I saw several posts, and read
typefox.io/parsing-expressions-with-xtext
and
/Xtext/documentation/301_grammarlanguage.html (Assigned Actions)

but I am having some problems with LL recursions
[fatal] rule ruleCompare_expr has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2. Resolve by left-factoring or using syntactic predicates or using backtrack=true option.
[fatal] rule ruleMath_expr has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2. Resolve by left-factoring or using syntactic predicates or using backtrack=true option.

My current grammar is

Expression:
or_ex+=And_expr ('||' or_ex+=And_expr )+ ;
And_expr:
and_ex+=Subtract_expr ('&&' and_ex+=Subtract_expr)+ ;
Subtract_expr:
('!!')*'!(' not_ex+=Expression ')'
| ('!!')*'(' not_ex+=Expression ')'
| not_ex+=Compare_expr;
Compare_expr:
comp+=Math_expr (operator+=('>=' | '<=' | '==' | '!=' | '>' | '<') comp+=Math_expr)+ |
comp+= '(' Compare_expr ')' | // clearly this is one problem, but trying to move compare to a terminal did not help
Math_expr:
math+=Term (operator+=('+' | '-' | '*' | '/' | '%') math+=Term)+ |
math+=Term
;

There is more problems as I go , but I maybe with some guidelines on the current issues, I will be able to solve them by myself?

thank you for your help
Re: eliminating left recursion [message #1730824 is a reply to message #1730695] Thu, 28 April 2016 18:41 Go to previous messageGo to next message
Jan Koehnlein is currently offline Jan KoehnleinFriend
Messages: 760
Registered: July 2009
Location: Hamburg
Senior Member
Hmmm, you're mixing up a lot of things.

1) the pattern for assigned actions is like

AndExpr:
   OrExpr //  next rule with higher precedence, no assignment
   ({AndExpr.left=current} // assigned action to create the AndExpr object
     'operator' 
     right=OrExpression)*;

OrExpression...


For associativity, precedence etc. see the documentation

2) You usually want a separate AST node for each '!'

NotExpr:
     CompareExpr // next rule with higher precedence, no assignment
    | {NotExpression}  // unassigned action as ! is not an infix operator
       '!' operand=NotExpr;


3) You assign the '(' in Compare_expr.
4) You lacked the 'returns Expression' on each rule, making the recursion possible.
5) You shouldn't have any LL* issues yet.

So a better version of your grammar would be

Evaluation:
	{Evaluation} expr=Expression?;
	
Expression:
	Or_expr;

Or_expr returns Expression:
	And_expr ({Or_expr.left=current} '||' right=And_expr)*;

And_expr returns Expression:
	Not_expr ({And_expr.left=current} '&&' right=Not_expr)*;

Not_expr returns Expression:
	{Not_expr} '!' operand=Not_expr | Compare_expr;

Compare_expr returns Expression:
	Math_expr ({Compare_expr.left=current} operator=('>=' | '<=' | '==' | '!=' | '>' | '<') right=Math_expr)*;

Math_expr returns Expression:
	Term ({Math_expr.left=current} operator=('+' | '-' | '*' | '/' | '%') right=Term)*;
	
Term returns Expression:
	'(' Expression ')'
	| Number;


Maybe you have a look at the arithmetics example shipped with Xtext.



---
Get professional support from the Xtext committers at www.typefox.io
Re: eliminating left recursion [message #1730916 is a reply to message #1730824] Fri, 29 April 2016 18:42 Go to previous messageGo to next message
Danny Quizzo is currently offline Danny QuizzoFriend
Messages: 16
Registered: April 2016
Junior Member
thank you for your answer, I am studying it at the moment. I might have some follow ups
One question:
Why did you do
Evaluation:
{Evaluation} expr=Expression?;
Re: eliminating left recursion [message #1730926 is a reply to message #1730695] Fri, 29 April 2016 21:02 Go to previous messageGo to next message
tly . is currently offline tly .Friend
Messages: 8
Registered: August 2014
Junior Member
He used

Evaluation:
{Evaluation} expr=Expression?;


as a toplevel rule. 'Expression?' means that Expression is matched 0 or 1 times. this way you wont get a parser error if you dont type in anything Razz

[Updated on: Fri, 29 April 2016 21:03]

Report message to a moderator

Re: eliminating left recursion [message #1730945 is a reply to message #1730926] Sat, 30 April 2016 14:26 Go to previous messageGo to next message
Danny Quizzo is currently offline Danny QuizzoFriend
Messages: 16
Registered: April 2016
Junior Member
but why do you have to do {Evaluation}, I mean if I don't do that I get a warning ' may be consumed without object instantiation
but I am not sure what it means
Re: eliminating left recursion [message #1730947 is a reply to message #1730945] Sat, 30 April 2016 14:44 Go to previous messageGo to next message
Ed Willink is currently offline Ed WillinkFriend
Messages: 6510
Registered: July 2009
Senior Member
Hi

It means that a rule can be parsed/used without having any impact on the
parsed model - no object creation, no property assignment. This could be
awkward for the serializer since it cannot correlate the tree with
source easily. However IMHO, perhaps 90% of these warnings could be
suppressed by automatic synthesis of the unambiguous action. But for now
you have to do it manually.

Regards

Ed Willink


On 30/04/2016 15:26, Danny Quizzo wrote:
> but why do you have to do {Evaluation}, I mean if I don't do that I
> get a warning ' may be consumed without object instantiation
> but I am not sure what it means
Re: eliminating left recursion [message #1730948 is a reply to message #1730945] Sat, 30 April 2016 14:46 Go to previous messageGo to next message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 13186
Registered: July 2009
Senior Member
Danny Quizzo <forums-noreply@xxxxxxxx> wrote:
> but why do you have to do {Evaluation}, I mean if I don't do that I get a
> warning ' may be consumed without object instantiation
> but I am not sure what it means
>

It forces xtext to create an object although xtext by default does this
only if you have at least on assignment


Need professional support for Xtext, Xpand, EMF?
Go to: https://www.itemis.com/en/xtext/
Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Re: eliminating left recursion [message #1730951 is a reply to message #1730948] Sat, 30 April 2016 15:05 Go to previous messageGo to next message
Danny Quizzo is currently offline Danny QuizzoFriend
Messages: 16
Registered: April 2016
Junior Member
Thank you very much for your answers. I tried to follow some of the suggested code here, and am now running into two problems
My subtract_expr has to have this ('!!')* option,see my original code
Subtract_expr:
('!!')*'!(' not_ex+=Expression ')'
| ('!!')*'(' not_ex+=Expression ')' 
| not_ex+=Compare_expr; 

I understand the suggested structure and tried to do the following, which is of course a left recursion
Sub_expr returns Expression:
	('!!')*'!'not_ex+=Sub_expr|
	('!!')* not_ex+=Sub_expr
    | not_ex+=Comp_expr;
 

I tried to reason that I can also do
Sub_expr returns Expression:
	('!!')*'!'not_ex+=Sub_expr|
       ('!!')* not_ex+=Comp_expr;

but I am getting warning(200): ../com.grammatech.prog_model/src-gen/org/example/domainmodel/parser/antlr/internal/InternalDomainmodel.g:1609:2: Decision can match input such as "'!!' '!'" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
would it be appropriate to do => in front of the comp_expr in this case?
Re: eliminating left recursion [message #1730953 is a reply to message #1730951] Sat, 30 April 2016 16:02 Go to previous messageGo to next message
Danny Quizzo is currently offline Danny QuizzoFriend
Messages: 16
Registered: April 2016
Junior Member
Another follow up
Math_expr returns Expression:
	Term ({Math_expr.left=current} operator=('+' | '-' | '*' | '/' | '%') right=Term)*;


My term is

Term returns Expression:
 	(unary+=('+' | '-' | '~' | '!'))* atom+=Atom (trailer+=Trailer)* 
      | (unary+=('+' | '-' | '~'))*  '('expr+= Math_expr ')' |// the difference here is the lack of !
     | '(' Expression ')'


So clearly the 2nd one is causing a LL recursion, but is it ok to just not include it since/ math expr can be a term and a term can just be the first line ? in that case what do I do with the fact that the 2nd unary should not include!
Finally, isn't the first line in term will cause a confusion with the '!' for subtract_expr who also has ! in it?
Re: eliminating left recursion [message #1730954 is a reply to message #1730953] Sat, 30 April 2016 16:11 Go to previous messageGo to next message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 13186
Registered: July 2009
Senior Member
Please share a complete grammar and test model and have a look at the
grammars and hints we gave you eg regarding not


Need professional support for Xtext, Xpand, EMF?
Go to: https://www.itemis.com/en/xtext/
Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Re: eliminating left recursion [message #1730958 is a reply to message #1730954] Sat, 30 April 2016 17:00 Go to previous messageGo to next message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 13186
Registered: July 2009
Senior Member
Eg have a look at
https://dslmeinte.wordpress.com/2011/03/21/pre-and-postfix-operators-in-xtext/


Need professional support for Xtext, Xpand, EMF?
Go to: https://www.itemis.com/en/xtext/
Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Re: eliminating left recursion [message #1731073 is a reply to message #1730958] Mon, 02 May 2016 17:06 Go to previous messageGo to next message
Danny Quizzo is currently offline Danny QuizzoFriend
Messages: 16
Registered: April 2016
Junior Member
Thank you very much for your answer, and for that link.

First I am attaching my full grammar based on the comments I got in this thread as well as stuff that I was able to understand from the pre and postfix post.
Domainmodel :
    (elements+=Object)*;
Object :
	expressions += Expression

Expression:
	Or_expr;

Or_expr returns Expression:
	And_expr ({Or_expr.left=current} '||' right=And_expr)*;
	
And_expr returns Expression:
	Subtract_expr ({And_expr.left=current} '&&' right=Subtract_expr)*;

Subtract_expr returns Expression:
	{Subtract_expr} ('!!')*'!' operand=Subtract_expr
	//('!!')* not_ex+=Subtract_expr
	not_ex+=Compare_expr;

Compare_expr returns Expression:
	Math_expr ({Compare_expr.left=current} operator=('>=' | '<=' | '==' | '!=' | '>' | '<') right=Math_expr)*;

Math_expr returns Expression:
      Term ({Math_expr.left= current} operator=('+' | '-' | '*' | '/' | '%') right=Term)*;

Term returns Expression: 
 	(unary+=('+' | '-' | '~' | '!'))* atom+=Atom (trailer+=Trailer)* |
   // (unary+=('+' | '-' | '~'))*  expr+=Math_expr  |
     '(' Expression ')'

Atom:
      INT 
    | FLOAT 
    | id;

Trailer:
	'[' (index+=Expression)?']'|
	'.' name=id (=>trailer+=Trailer)*;


Based on the pre postfix post I think the '(' Expression ')' is in the right place.
I also think that I am doing the atom and trailer correctly

I read the hints about the '!' but I find them confusing

So at the moment I have 3 problems that I am not sure how to address,

1) since I need both

	{Subtract_expr} ('!!')*'!' operand=Subtract_expr
       and
	('!!')* not_ex+=Subtract_expr


I am not sure how to do this and to avoid a LL recursion. I cannot just move Subtract_expr to a terminal

2) there is an ambiguaity between
{Subtract_expr} ('!!')*'!' operand=Subtract_expr
and
 	(unary+=('+' | '-' | '~' | '!'))* atom+=Atom (trailer+=Trailer)* |


due to the '!' string , and I do not think forcing the grammar to go to the atom line with => , is appropriate

3)

 	(unary+=('+' | '-' | '~' | '!'))* atom+=Atom (trailer+=Trailer)* |
       (unary+=('+' | '-' | '~'))*  expr+=Math_expr  |


there is some overlap between the first line and the 2nd line due to the unary. I think that since a subtract can get '!' the entire 2nd line
(unary+=('+' | '-' | '~'))* expr+=Math_expr |
can just be deleted
Re: eliminating left recursion [message #1731078 is a reply to message #1731073] Mon, 02 May 2016 17:23 Go to previous messageGo to next message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 13186
Registered: July 2009
Senior Member
Hi,

i still do not understand why you do the !! stuff is and why you dont handle ( recursion) this strange way.
and i have no idea what you want to do with the Term thing.


Need professional support for Xtext, Xpand, EMF?
Go to: https://www.itemis.com/en/xtext/
Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Re: eliminating left recursion [message #1731082 is a reply to message #1731078] Mon, 02 May 2016 17:42 Go to previous messageGo to next message
Danny Quizzo is currently offline Danny QuizzoFriend
Messages: 16
Registered: April 2016
Junior Member
I am writing a domain specific lang, so the '!!' is just a string that can be written in my lang
I can have !!(X+Y) in my language as well as !!! as well as !!!!!.

I am not sure what you mean with :
why you dont handle ( recursion) this strange way

the term can either be
a list of these symbols unary+=('+' | '-' | '~' | '!'))* with an atom, or it can be
'+' | '-' | '~' with another math expression , and clearly since subrtact expression already has ! in it, I think this entire line redundant

the problem is that
both
! subrtact_expr
and also
subrtact_expr should be valid I have two issues
fist the LL recursion in subtract expr and second that
! subrtact_expr
and ... '!'))* atom+=Atom cause some ambiguity
Re: eliminating left recursion [message #1731083 is a reply to message #1731082] Mon, 02 May 2016 17:42 Go to previous messageGo to next message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 13186
Registered: July 2009
Senior Member
so !! is not the same as not not ?!?

Need professional support for Xtext, Xpand, EMF?
Go to: https://www.itemis.com/en/xtext/
Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Re: eliminating left recursion [message #1731085 is a reply to message #1731083] Mon, 02 May 2016 17:46 Go to previous messageGo to next message
Danny Quizzo is currently offline Danny QuizzoFriend
Messages: 16
Registered: April 2016
Junior Member
None of them are actual Xtext not, all of them are just the string '!'
so it can either be
'!' 1
'!!!' 3
'!!!!!' 5

My DSL will deal with all of them as what they are
Re: eliminating left recursion [message #1731087 is a reply to message #1731085] Mon, 02 May 2016 17:51 Go to previous messageGo to next message
Danny Quizzo is currently offline Danny QuizzoFriend
Messages: 16
Registered: April 2016
Junior Member
am I being clear?
for example
terminal SL_COMMENT: 
    '//' !('\n'|'\r')* ('\r'? '\n')?;

vs.

terminal SL_COMMENT: 
    '//' '!'('\n'|'\r')* ('\r'? '\n')?;

The ! is just a string in the 2nd one
Re: eliminating left recursion [message #1731088 is a reply to message #1731087] Mon, 02 May 2016 17:55 Go to previous messageGo to next message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 13186
Registered: July 2009
Senior Member
i dont get that. and i have not the time. but you can have a look at

Domainmodel :
    (elements+=Object ";")*;
Object :
	expressions += Expression
;


Expression:
	Disjunction
;

Disjunction returns Expression
    :   Conjunction ({BinaryExpression.left=current} operator='||' right=Conjunction)*
    ;
    
Conjunction returns Expression
    :   Comparison ({BinaryExpression.left=current} operator='&&' right=Comparison)*
    ;
    
Comparison returns Expression
    :   Addition ({BinaryExpression.left=current} operator=('='|'!='|'<'|'<='|'>'|'>=') right=Addition)?
    ;
    
Addition returns Expression:
	Multiplication (({Plus.left=current} '+' | {Minus.left=current} '-') right=Multiplication)*;

Multiplication returns Expression:
    UnitaryMinus (({Multi.left=current} '*' | {Div.left=current} '/') right=UnitaryMinus)*;
    
 UnitaryMinus returns Expression:
    PrimaryExpression | ({UnitaryMinus} ('-'|"!"|"~") expr=UnitaryMinus);   
PrimaryExpression returns Expression:
	'(' Expression ')' |
	{NumberLiteral} value=Atom trailer+=Trailer*;


Atom:
      INT 
    | FLOAT 
    | ID;

Trailer:
	'[' (index+=Expression)?']'|
	'.' name=ID (=>trailer+=Trailer)*;


FLOAT: INT ("." INT);	


Need professional support for Xtext, Xpand, EMF?
Go to: https://www.itemis.com/en/xtext/
Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Re: eliminating left recursion [message #1731105 is a reply to message #1731088] Mon, 02 May 2016 19:44 Go to previous message
Danny Quizzo is currently offline Danny QuizzoFriend
Messages: 16
Registered: April 2016
Junior Member
While I extremely appreciate your input, I am really lost with the above suggestions.
I understand you are busy, so I would appreciate any help from anyone
Previous Topic:Packaging xtext project
Next Topic:Providing type for keywords
Goto Forum:
  


Current Time: Wed Nov 13 18:06:45 GMT 2019

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

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

Back to the top