My grammar appears to have a case of indirect left recursion, looked at some of the other similar question, cannot quite make a mental connection between them and my grammar, I can't get my head around how to solve it.
A ::= A' a
| A
| b
A' ::= c
| A
A'
is called from A
but A'
is c
or A
, this is causing the left recursion, how could this be rearranged to an equivalent grammar while eliminating the left recursion?
You have the following productions:
1: A -> A' a
2: A -> A
3: A -> b
4: A' -> c
5: A' -> A
First note that production #2 makes this grammar ambiguous, and is actually kind of pointless. Let's remove it.
1: A -> A' a
3: A -> b
4: A' -> c
5: A' -> A
The "Left recursion" article on Wikipedia contains an (unsourced) algorithm to eliminate all left recursion, including indirect left recursion. Let's ignore this specific algorithm and focus on the idea instead: first turn indirect recursion to direct recursion through substitution, then resolve direct recursion by adding a tail non-terminal.
For instance, we can substitute A'
in production #1 by replacing it with
6: A -> c a (see #1 and #4)
7: A -> A a (see #1 and #5)
The grammar becomes as follows:
4: A' -> c
5: A' -> A
6: A -> c a
7: A -> A a
and we've already turned all indirect recursion into direct recursion. All that remains is to remove the direct recursion for A
:
4: A' -> c
5: A' -> A
6: A -> c a T
8: T -> epsilon
9: T -> a T