Search code examples
left-recursion

Eliminating left recursion for a specific grammar

I've looked through a million examples/tutorials but I still can't manage to eliminate left recursion for this grammar:

S --> C
C --> Dc|c
D --> Cd|d

Any ideas?

Solution

  • First make the indirect recursion to an immediate one via eliminating D. You only have two nonterminals, so it can be done.

    S --> C
C --> Cdc|dc|c

    Then you can work on making it tail-recursive:

    S --> C
C --> dcC'|cC'
C'--> dcC'

    The trick in the second part is to take all terminals from derived from C (here, dc and c) and give them a tail (C --> dcC'|cC'). This dc and c is the same terminal set that came after Cdc in the first rule set. Then you create a rule for the new nonterminal (the tail) and put it after the terminals from the first rule (ie. this dc comes from Cdc).

    To make it clearer:

    S --> C
C --> Db|f
D --> Ca|c

-->

S --> C
C --> Cab|cb|f

-->

S --> C
C --> cbC'|fC'
C'--> abC'