Search code examples
parsingrecursioncompiler-constructiongrammarleft-recursion

Indirect left recursion in my grammar?


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?


Solution

  • 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