Eliminating Indirect Left Recursion

Question

My brain is fried trying to eliminate some left recursion from production rules. I'm building a compiler with JavaCC and I need to use the following 2 production rules:

expression := fragment ( ( + | - | * | / )  fragment )*

fragment := identifier | number | ( + | - ) fragment | expression

But the problem is that fragment is related to expression which is related to fragment, ie: indirect left recursion.

I've looked around the internet and everyone seems to use this algorithm which can be found here. That site doesn't explain direct left recursion elimination which you can find here

I end up with rules like this:

void expression(): {}
{
  fragment()
  (
    (< PLUS >|< MINUS >|< DIVIDE >|< ASTERISKS >)
    fragment()
  )*
}

void k(): {}
{
  (
    ((< PLUS >|< MINUS >|< DIVIDE >|< ASTERISKS >)fragment())*k()
  | fragment()
  )
} 

void fragment(): {}
{
  (
    < ID >k()
  | number()k()
  | (< PLUS >|< MINUS >)fragment()k()
)
}

They're written in the code used for JavaCC so hopefully you can understand them. Basically I introduced a rule K to deal with the recursion except the problem still exists because the first part of K can be reduced to nothing because it's * (0 or more times) which leaves you with K -> k() which is more left recursion!!

I have no idea where to go from here and have lost a lot of hair. Any insights would be appreciated!

You can usually have term, expression and then a terminal symbol, why isn't that good enough here? — user529758
I think that fragment is defined incorrectly. Shouldn't expression appear between literal parentheses, something like fragment := ... '(' expression ')'? Otherwise it makes no sense having expression at the fragment level. Note that I'm not familiar with JavaCC in particular, but that would be the problem in other parser generators. — user1201210
I was thinking the same thing tenterhook. I can't seem to think of a case where that expression in fragment would ever be of use. However the rules are pretty much cast in stone as they were decided my a lecturer. Perhaps I should contact him? H2CO3: Could you explain that a bit more? Do you mean I should create a rule term? What would it include? I actually have seen people using term around the net but I thought it would be better to follow that algorithm. — carlmango11
@carlmango11 I recommend contacting him/her about it. There is no way to resolve expression -> fragment -> expression without adding or removing something from the rules. — user1201210

Nathan Ryan Nathan Ryan · Accepted Answer · 2012-12-22T00:42:34

I suggest rewriting the rule for expression as follows:

expression := ( identifier | number | ( + | - ) fragment ) ( ( + | - | * | / ) fragment )*

Effectively, this is just a substitution of fragment in the original definition, with the Kleene operator conveniently absorbing some terms.

Of course, whatever structure is created from parsing this will be need to be accommodated, if it is supposed to reflect the original rules.

Eliminating Indirect Left Recursion

1 Answers