6

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.)

Community
  • 1
  • 1
ravinggenius
  • 816
  • 1
  • 6
  • 14
  • 1
    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 May 25 '11 at 03:25
  • 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 May 25 '11 at 04:06
  • Treetop is not an LALR(1) parser but a recursive descent parser. – Kathy Van Stone May 25 '11 at 13:40

1 Answers1

4

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).

Community
  • 1
  • 1
Kathy Van Stone
  • 25,531
  • 3
  • 32
  • 40
  • Please pardon my ignorance, but how does your example solve the problem? Is it because r_tail is optional? What if the left side was made optional; would it still work? – ravinggenius May 25 '11 at 04:16
  • @Raving Genius: I need something more specific than the one you gave, as you gave something that doesn't need recursion at all (as mentioned in my answer). The other one was just an example of removing left recursion. Can you include example of text it should be matching? – Kathy Van Stone May 25 '11 at 13:39
  • @Raving Genius: To be more specific about my example, r_tail being optional makes it a valid variant of the left recursion (it is equivalent to the rules where r_tail matches the empty string). – Kathy Van Stone May 25 '11 at 20:37
  • Thank you. That does answers my question. – ravinggenius May 25 '11 at 21:04