CODEWITHSUNDEEP
recursionantlrgrammarantlr4
dub stylee
dub stylee

Reputation: 3342

ANTLR4 mutual left recursion grammar

I have read many questions here on StackOverflow about mutual left-recursion issues in LL(k) parsers. I found the general algorithm for removing left-recursion:

A : Aa | b ;

becomes

A : bR ;
R : (aA)? ;

However, I cannot figure out how to apply it to my situation. I have

left_exp: IDENT | exp DOT IDENT ;
exp     : handful
        | of
        | other rules
        | left_exp ;

The "handful of other rules" all contain regular recursion, such as exp : exp PLUS exp, etc. and have no issues. The issue is with left_exp and exp being mutually recursive.

I thought about just adding IDENT and exp DOT IDENT to the exp rules, but there are some situations where the other valid exp rules do not apply, where left_exp would be valid.

EDIT

I also have the following rule, which calls for a left expression followed by assignment. 

assign_statement: left_exp ( COLON IDENT )? EQUAL exp SEMI ;

Since a regular expression is only a left expression if it is followed by DOT IDENT, it seems that I can't just add 

| IDENT
| exp DOT IDENT

to my expression definition, because then assignment would accept any other valid expression on the left side, rather than only one of those two.

Upvotes: 2

Views: 781

Answers (1)

Mike Lischke
Mike Lischke

Reputation: 53317

The approach I apply usually goes like this:

A: Aa | b;

becomes:

A: b (a)*;

Or in general: all alts without left recursion followed by all alts with a (removed) left recursion with unlimited occurences (expressed via the kleene operator). Example:

A: Aa | Ab | c | d | Ae;

becomes:

A: (c | d) (a | b | e)*;

You can check this easily by continuosly replacing A:

A: Aa | b;
A: (Aa | b)a | b;
A: Aaa | ba | b;
A: (Aa | b)aa | ba | b;
A: Aaaa | baa | ba | b;

etc.

In your example however you have an indirect left recursion (via 2 rules). This is not accepted by ANTLR. A solution is to move the alts from left_exp to the exp rule and then apply the algorithm I described above.

Upvotes: 1

Related Questions