How to deal with Treetop left-recursion

Question

I have a grammar file for a new general-purpose programming language I'm trying to build. I'm trying to make the language robust and natural to use (it is heavily inspired by Ruby, among others), and in doing so I have introduced some left-recursive rules.

I've seen some examples that seem to indicate the following left-recursive rule:

rule l_recurse
  l_recurse / 'something else'
end

can be made non-left-recursive by changing it to:

rule r_recurse
  'something else' / r_recurse
end

To me this looks like it would have the a different problem and would still fail. Am I right, or will this "just work"?

The specific left-recursions I'm trying to (find and) eliminate are found in this grammar file. I'm not sure which rules are affected, but at least some were pointed out to have left-recursion. (By the way I have tried to eliminate the specific range issue he mentioned by tightening up range's rule.)

Why do you want to remove the left recursion. For LALR(1) parser I thought left recursion was what you would want to try for. I was going to put this as an answer but if you really want to know how to transform immediate left recursion (your example) to right recursion look at the wikipedia page on left recursion. It will show you how to transform the grammar to right recursion and what the effect is on your language. — ditkin
I want to remove left recursion because the grammar library I'm using (Treetop) does not allow for left recursion. Is there a LALR parser in Ruby I could use instead? — ravinggenius
Treetop is not an LALR(1) parser but a recursive descent parser. — Kathy Van Stone

Kathy Van Stone Kathy Van Stone · Accepted Answer · 2011-05-25T03:19:33

The particular case

rule l_recurse
  l_recurse / 'something else'
end

simplifies to

rule l_recurse
   'something_else'
end

(and so does the right recursion rule) so I need to see your specific example to find out what you want to know. The answer to this question gives the general rule for left recursion elimination.

One of the typical easy-to-remove left recursion cases is lists:

rule l_list
    item | l_list ',' item
end

and that can be changed to right recursion

rule r_list
    item r_tail?
end

rule r_tail
    ',' r_list
end

(which is a special case of the general recursion elimination).

How to deal with Treetop left-recursion

1 Answers