Eclipse Community Forums: TMF (Xtext) » eliminating left recursion

Home » Modeling » TMF (Xtext) » eliminating left recursion

eliminating left recursion [message #1730695]

Wed, 27 April 2016 13:03

Eclipse User

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 14:41

Eclipse User

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.

Re: eliminating left recursion [message #1730916 is a reply to message #1730824]

Fri, 29 April 2016 14:42

Eclipse User

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 17:02

Eclipse User

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 17:03] by Moderator

Re: eliminating left recursion [message #1730945 is a reply to message #1730926]

Sat, 30 April 2016 10:26

Eclipse User

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 10:44

Eclipse User

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 10:46

Eclipse User

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

Re: eliminating left recursion [message #1730951 is a reply to message #1730948]

Sat, 30 April 2016 11:05

Eclipse User

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 12:02

Eclipse User

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 12:11

Eclipse User

Please share a complete grammar and test model and have a look at the
grammars and hints we gave you eg regarding not

Re: eliminating left recursion [message #1730958 is a reply to message #1730954]

Sat, 30 April 2016 13:00

Eclipse User

Eg have a look at
https://dslmeinte.wordpress.com/2011/03/21/pre-and-postfix-operators-in-xtext/

Re: eliminating left recursion [message #1731073 is a reply to message #1730958]

Mon, 02 May 2016 13:06

Eclipse User

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 13:23

Eclipse User

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.

Re: eliminating left recursion [message #1731082 is a reply to message #1731078]

Mon, 02 May 2016 13:42

Eclipse User

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 13:42

Eclipse User

so !! is not the same as not not ?!?

Re: eliminating left recursion [message #1731085 is a reply to message #1731083]

Mon, 02 May 2016 13:46

Eclipse User

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 13:51

Eclipse User

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 13:55

Eclipse User

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);

Re: eliminating left recursion [message #1731105 is a reply to message #1731088]

Mon, 02 May 2016 15:44

Eclipse User

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:

-=] Back to Top [=-

Current Time: Wed Jul 23 17:02:13 EDT 2025

.:: Contact :: Home ::.

Breadcrumbs

Sign up to our Newsletter