How to deal with endless recursion

Question

Let's take following sample grammar as an example:

Model:
    m+=Main*
;

Main:
    "bla" r=Rule1
    | Rule3
    | Rule2
;

    Rule1:
        i=INT
        | "key" r=Rule2
    ;

    Rule2:
        "b" r=Rule3
    ;

    Rule3:
        "b" (r=Rule1 | r=Rule2)
    ;

When I compile this I get the error message:

error(211): ../org.xtext.example.test/src-gen/org/xtext/example/test/parser/antlr/internal/InternalTest.g:119:1: [fatal] rule ruleMain 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.

As far as I understand this issue this is because the ruleCall for Rule3 can be infinitely long (since Rule3 can call Rule2 which then can call Rule3 again and so on...) as well as the ruleCall for Rule2.
Therefore the parser can't create a lookahead for these infinitely ruleCalls and in rule Main we demand the parser to decide between these infinitely alternatives but the lack of a lookahead results in this error message...
(correct me if I'm wrong)

My question would be how I can solve this problem?
There must be a way to restructure this grammar so that the parser can handle it.

Best regards Raven

Answer 1

If I look your grammar, I see that you have a Rule2 and Rule3 that can be refactor in only one rule. Because you rule2 and 3 start with "b". So It will be the same if your have a 'Rule2 : "b" r=(Rule1 | Rule2) ;'. In my opinion the rule3 is unnecessary. I will refactor your grammar like this :

Model:
    m+=Main*
;

Main:
    "bla" r=Rule1
    | Rule2
;

Rule1:
    i=INT
    | "key" r=Rule2
;

Rule2:
    "b" r=(Rule1 | Rule2)
;