Search code examples
bnfleft-recursion

Removing left recursion

I am feeling quite nostalgic so I've decided to write an adventure game creator that allows complex sentences to be entered by the user.

I have hand rolled a lexer and parser that uses the visitor pattern and it works quite well, until I encountered a left-recursion issue with one of my BNF (Backus-Naur Form) rules:

object          ::= {adjective} noun 
                  | object AND {adjective} noun

After removing the left-recursion by following this wiki entry does this look right?

object      ::= {adjective} noun object2
object2     ::= AND {adjective noun} 
              | !Empty

Edited:

I am hand rolling the lexer and parser using C# by following the guide given here. I an not using any parser generators for this exercise.

Also, I got the BNF rules for the parser from this website.

Solution

  • Is there any reason to prefer left-recursion over right recursion in this case? Wouldn't this be simpler:

    object ::= {adjective} noun |
           {adjective} noun AND object

    If you really want to make your solution work, you need to make object2 right-recursive:

    object      ::= {adjective} noun object2
object2     ::= AND {adjective noun} object2 |
                !Empty