Search code examples
parsingrecursioncompiler-constructiongrammarleft-recursion

Resolving left-recursion in my grammar

My grammar has a case of left-recursion in the sixth production rule.

Left recursion

I resolved this by replacing Rule 6 and 7 like this:

Resolved left recursion

I couldn't find any indirect left recursions in this grammar.

The only thing that bothers me is the final production rule, which has a terminal surrounded by two non-terminals.

My two questions are:

  • Is my resolved left recursion correct?
  • Is the final production rule a left recursion? I am not sure how to treat this special case.
Solution

  • Yes, your resolution is correct. You may want to remove the epsilon rule for ease of use, but the accepted strings are correct.

    X -> -
X -> -Z
Z -> +
Z -> +Z
Z -> X + Y
... and Y is of the form 0* 1 (no syntax collisions)

    As a check, note that you could now replace this final rule with two new rules, one for each expansion of X:

    Z -> -  + Y
Z -> -Z + Y

    This removes X entirely from the Z rules, and each Z rule would then begin with a terminal.

    No, your final production rule is no longer left-recursive. X now must resolve to a string beginning with a non-terminal.

    I have to admit, though, I'm curious about what use the language has. :-)