Left recursive rules of Xtext

Question

I faced a recursive rule problem in Xtext. The simplified version is as follow:

grammar my.mavenized.HeroLanguage with org.eclipse.xtext.common.Terminals

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

Atomic:
    Map |
    FunctionCall |
    value=ID;

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

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

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

And Xtext gives me this 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.

Sebastian Zarnekow Sebastian Zarnekow · Accepted Answer · 2014-02-10T07:28:15

You Map contains a list of MapEntrys which end with an Atomic. An Atomic in turn is either a FunctionCall or a plain ID. The Tail of a FunctionCall looks like the beginning of the next MapEntry, though. Since that tail is infinitely deep nested, it is not possible to decide which path to follow. That's what your error message stems from. You could use a predicate to convince the parser about on or the other path to go, e.g.

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

If that is not possible for your use case, you may want to enable backtracking, though that's not recommended.

Left recursive rules of Xtext

1 Answers