Eclipse Community Forums: TMF (Xtext) » Strange left recursive rules

Help

Home

Home » Modeling » TMF (Xtext) » Strange left recursive rules(Cannot find recursive problems)

Show: Today's Messages :: Show Polls :: Message Navigator

Strange left recursive rules [message #1241708]

Sat, 08 February 2014 11:20

Xi Lin

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.

Report message to a moderator

Re: Strange left recursive rules [message #1241713 is a reply to message #1241708]

Sat, 08 February 2014 11:30

Xi Lin

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.

Report message to a moderator

Re: Strange left recursive rules [message #1242092 is a reply to message #1241713]

Sun, 09 February 2014 01:52

Henrik Lindberg

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

Report message to a moderator

Re: Strange left recursive rules [message #1242712 is a reply to message #1242092]

Mon, 10 February 2014 01:55

Xi Lin

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.

Report message to a moderator

Re: Strange left recursive rules [message #1242752 is a reply to message #1241708]

Mon, 10 February 2014 03:33

Henrik Lindberg

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

Report message to a moderator

Re: Strange left recursive rules [message #1242790 is a reply to message #1242752]

Mon, 10 February 2014 04:59

Xi Lin

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.

Report message to a moderator

Re: Strange left recursive rules [message #1243177 is a reply to message #1242790]

Mon, 10 February 2014 16:24

Henrik Lindberg

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

Report message to a moderator

Re: Strange left recursive rules [message #1243456 is a reply to message #1243177]

Tue, 11 February 2014 02:10

Xi Lin

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.

Report message to a moderator

Re: Strange left recursive rules [message #1243654 is a reply to message #1243456]

Tue, 11 February 2014 09:04

Lorenzo Bettini

Messages: 1812
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

HOME: http://www.lorenzobettini.it
TDD Book: https://leanpub.com/tdd-buildautomation-ci
Xtext Book: https://www.packtpub.com/application-development/implementing-domain-specific-languages-xtext-and-xtend-second-edition

Report message to a moderator