Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » TMF (Xtext) » Strange left recursive rules(Cannot find recursive problems)
Strange left recursive rules [message #1241708] Sat, 08 February 2014 11:20 Go to next message
Xi Lin is currently offline Xi LinFriend
Messages: 21
Registered: January 2014
Junior Member
I faced a recursive rule problem in Xtext. The simplify version is as follow:

Atomic:
    Map |
    FunctionCall |
    value=ID;
    
Map:
    'map' '{'
        (entries+=MapEntry)+
    '}';
    
MapEntry:
    '(' key=Atomic ')' '=>' value=Atomic;
    
FunctionCall:
    name=ID '(' arg=Atomic ')';


And Xtext give me error message:
[fatal] rule ruleAtomic has non-LL(*) decision due to recursive rule invocations reachable from alts 2,3.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.


But i cannot find left recursive problems. Is there some implicit rules in Xtext about the left recursive?

Thanks.
Re: Strange left recursive rules [message #1241713 is a reply to message #1241708] Sat, 08 February 2014 11:30 Go to previous messageGo to next message
Xi Lin is currently offline Xi LinFriend
Messages: 21
Registered: January 2014
Junior Member
The other case is as follow:
Statement:
atomic+=Atomic*;

Atomic:
  '(' Atomic ')' |
  FunctionCall |
  value=ID;

FunctionCall:
  name=ID '(' arg=Atomic ')';


I can understand that this one has ambiguity, but why does Xtext also warning about:
[fatal] rule ruleAtomic has non-LL(*) decision due to recursive rule invocations reachable from alts 2,3.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.
Re: Strange left recursive rules [message #1242092 is a reply to message #1241713] Sun, 09 February 2014 01:52 Go to previous messageGo to next message
Henrik Lindberg is currently offline Henrik LindbergFriend
Messages: 2509
Registered: July 2009
Senior Member
On 2014-08-02 12:30, Xi Lin wrote:
> The other case is as follow:
>
> Statement:
> atomic+=Atomic*;
>
> Atomic:
> '(' Atomic ')' |
> FunctionCall |
> value=ID;
>
> FunctionCall:
> name=ID '(' arg=Atomic ')';
>
>
> I can understand that this one has ambiguity, but why does Xtext also
> warning about:
>
> [fatal] rule ruleAtomic has non-LL(*) decision due to recursive rule
> invocations reachable from alts 2,3. Resolve by left-factoring or using
> syntactic predicates or using backtrack=true option.
>

To get help with problems like these, you need to post your entire grammar.

- henrik
Re: Strange left recursive rules [message #1242712 is a reply to message #1242092] Mon, 10 February 2014 01:55 Go to previous messageGo to next message
Xi Lin is currently offline Xi LinFriend
Messages: 21
Registered: January 2014
Junior Member
Henrik Lindberg wrote on Sat, 08 February 2014 20:52

To get help with problems like these, you need to post your entire grammar.

- henrik


Thanks for your reply.

These two cases are both complete grammar extracted from my whole grammar.

Adding any header like:
grammar my.mavenized.HeroLanguage with org.eclipse.xtext.common.Terminals

generate heroLanguage "http://www.mavenized.my/HeroLanguage"

They can be checked by Xtext tools.
Re: Strange left recursive rules [message #1242752 is a reply to message #1241708] Mon, 10 February 2014 03:33 Go to previous messageGo to next message
Henrik Lindberg is currently offline Henrik LindbergFriend
Messages: 2509
Registered: July 2009
Senior Member
On 2014-08-02 12:20, Xi Lin wrote:
> I faced a recursive rule problem in Xtext. The simplify version is as
> follow:
>
>
On 2014-08-02 12:20, Xi Lin wrote:
> I faced a recursive rule problem in Xtext. The simplify version is as
> follow:
>

Atomic
: Map
| FunctionCall
| value=ID
;

Map
: 'map' '{' (entries+=MapEntry)+ '}'
;

MapEntry
: '(' key=Atomic ')' '=>' value=Atomic
;

FunctionCall
: name=ID '(' arg=Atomic ')'
;

I re-formatted the grammar to make it easier to read.

The problems here are:

* When looking at an Atomic and the next token is ID, it does not know
if this is a Atomic with value = ID, or a FunctionCall since the
function call also starts with an ID.

* Second problem is that LL(*) parsing does not have precedence on
operators and it does not know if to "shift or reduce" (in other parsing
technologies). This is something that must be manually resolved by the
grammar author when using LL. This is called "left factoring". You get
this in the FunctionCall rule which boils down to ID '(' ID

i.e. something like this does not work in a LL parser

Expression
: Expression '+' Expression
| Expression '-' Expression
...
;

Suggest you look at one of the Expression based examples for Xtext.
(There is a formula to follow - it is not as hard as it first looks once
you get the hang of it).

I hope that helps

Regards
- henrik
Re: Strange left recursive rules [message #1242790 is a reply to message #1242752] Mon, 10 February 2014 04:59 Go to previous messageGo to next message
Xi Lin is currently offline Xi LinFriend
Messages: 21
Registered: January 2014
Junior Member
Henrik Lindberg wrote on Sun, 09 February 2014 22:33

The problems here are:

* When looking at an Atomic and the next token is ID, it does not know
if this is a Atomic with value = ID, or a FunctionCall since the
function call also starts with an ID.

* Second problem is that LL(*) parsing does not have precedence on
operators and it does not know if to "shift or reduce" (in other parsing
technologies). This is something that must be manually resolved by the
grammar author when using LL. This is called "left factoring". You get
this in the FunctionCall rule which boils down to ID '(' ID

i.e. something like this does not work in a LL parser

Expression
: Expression '+' Expression
| Expression '-' Expression
...
;


Thanks for you reply.

1. For the first problem, i think that Xtext is working in a greedy match way that it should not be problem. I write a test as follow:

Atomic
:
 FunctionCall
| TheOtherFunctionCall
;

FunctionCall
: 
name=ID '(' arg=Atomic ')'
;

TheOtherFunctionCall
:
name=ID '[' arg=Atomic ']'
;

And it works well. So i think it may not be the core reason?

2. For the second problem, i know about using current to solve that Expression problem. But i still think maybe it is not the cause of problem? Because for the posted problematic grammar, if it enter the FunctionCall rule, it should know how to parse it.

See an example as follow:
getName(xi)

This is a rule of ID '(' ID ')' and only FunctionCall rule can be applied on it and not other Atomic rule can be used in my thought.

In the posted grammar, if i remove Map from Atomic rule, everything is OK. So i think the problem is happened in Map rule and FunctionCall, but i cannot figure out in which case will it be ambiguous.
Re: Strange left recursive rules [message #1243177 is a reply to message #1242790] Mon, 10 February 2014 16:24 Go to previous messageGo to next message
Henrik Lindberg is currently offline Henrik LindbergFriend
Messages: 2509
Registered: July 2009
Senior Member
On 2014-10-02 5:59, Xi Lin wrote:
> Henrik Lindberg wrote on Sun, 09 February 2014 22:33
>> The problems here are:
>>
>> * When looking at an Atomic and the next token is ID, it does not know
>> if this is a Atomic with value = ID, or a FunctionCall since the
>> function call also starts with an ID.
>>
>> * Second problem is that LL(*) parsing does not have precedence on
>> operators and it does not know if to "shift or reduce" (in other
>> parsing technologies). This is something that must be manually
>> resolved by the grammar author when using LL. This is called "left
>> factoring". You get this in the FunctionCall rule which boils down to
>> ID '(' ID
>>
>> i.e. something like this does not work in a LL parser
>>
>> Expression
>> : Expression '+' Expression
>> | Expression '-' Expression
>> ...
>> ;
>
>
> Thanks for you reply.
>
> 1. For the first problem, i think that Xtext is working in a greedy
> match way that it should not be problem. I write a test as follow:
>
>
> Atomic
> :
> FunctionCall
> | TheOtherFunctionCall
> ;
>
> FunctionCall
> : name=ID '(' arg=Atomic ')'
> ;
>
> TheOtherFunctionCall
> :
> name=ID '[' arg=Atomic ']'
> ;
>
> And it works well. So i think it may not be the core reason?
>
> 2. For the second problem, i know about using current to solve that
> Expression problem. But i still think maybe it is not the cause of
> problem? Because for the posted problematic grammar, if it enter the
> FunctionCall rule, it should know how to parse it.
>
> See an example as follow:
>
> getName(xi)
>
> This is a rule of ID '(' ID ')' and only FunctionCall rule can be
> applied on it and not other Atomic rule can be used in my thought.
>
> In the posted grammar, if i remove Map from Atomic rule, everything is
> OK. So i think the problem is happened in Map rule and FunctionCall, but
> i cannot figure out in which case will it be ambiguous.

As I said, you have to go and read up on how it actually works. I read a
great explanation in an ANTLr book ("The Definitive ANTLR reference")
how LL* parser works. It is not immediately intuitive when having worked
with other parser technologies.

Also look at other Xtext based grammars and how various programming
language constructs were implemented (calls, maps, etc).

- henrik
Re: Strange left recursive rules [message #1243456 is a reply to message #1243177] Tue, 11 February 2014 02:10 Go to previous messageGo to next message
Xi Lin is currently offline Xi LinFriend
Messages: 21
Registered: January 2014
Junior Member
Henrik Lindberg wrote on Mon, 10 February 2014 11:24

As I said, you have to go and read up on how it actually works. I read a
great explanation in an ANTLr book ("The Definitive ANTLR reference")
how LL* parser works. It is not immediately intuitive when having worked
with other parser technologies.

Also look at other Xtext based grammars and how various programming
language constructs were implemented (calls, maps, etc).

- henrik


Thanks. I'll read the book to see how it actually works.
Re: Strange left recursive rules [message #1243654 is a reply to message #1243456] Tue, 11 February 2014 09:04 Go to previous messageGo to next message
Lorenzo Bettini is currently offline Lorenzo BettiniFriend
Messages: 1770
Registered: July 2009
Location: Firenze, Italy
Senior Member
On 11/02/2014 03:10, Xi Lin wrote:
> Henrik Lindberg wrote on Mon, 10 February 2014 11:24
>> As I said, you have to go and read up on how it actually works. I read
>> a great explanation in an ANTLr book ("The Definitive ANTLR
>> reference") how LL* parser works. It is not immediately intuitive when
>> having worked with other parser technologies.
>>
>> Also look at other Xtext based grammars and how various programming
>> language constructs were implemented (calls, maps, etc).
>>
>> - henrik
>
>
> Thanks. I'll read the book to see how it actually works.

Hi Xi

there's also a chapter in my Xtext book about left-factoring using an
Expression language:
http://www.packtpub.com/implementing-domain-specific-languages-with-xtext-and-xtend/book

hope this helps
Lorenzo

--
Lorenzo Bettini, PhD in Computer Science, DI, Univ. Torino
HOME: http://www.lorenzobettini.it
Xtext Book:
http://www.packtpub.com/implementing-domain-specific-languages-with-xtext-and-xtend/book


Re: Strange left recursive rules [message #1256266 is a reply to message #1243654] Tue, 25 February 2014 08:56 Go to previous message
Xi Lin is currently offline Xi LinFriend
Messages: 21
Registered: January 2014
Junior Member
Hi Lorenzo,

I read your book and it helps a lot.

Thanks for your great work!
Previous Topic:Cross References in a dynamic language
Next Topic:Editor related issues in xtext
Goto Forum:
  


Current Time: Tue Oct 27 13:18:23 GMT 2020

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

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

Back to the top