Can someone show me how to eliminate left recursion from this grammar using rules?

1
votes

I am trying to remove left recusion from a grammar, and I can do this SOMETIEMES. I obviously don't know the rules, because I only know how to do it by trial and error. The rules I see are like this: The rules that I found on Wikipedia

S --> SX | SSb | XS | a
X --> Xb | Sa | b

So, I know in this particular example, that I can first remove immediate left recursion from the S rule and then after that I get this:

S --> XSS' | aS'
S' --> XS' | SbS' | epsilon
X --> Xb | Sa | b

Then, from here I can merge the S production into the X production to get:

 X --> Xb | XSS' | aS'a | b

and then I can remove immediate left recursion from there to get my final answer. BUT, can someone please explain the rules to me, because I did not follow them to arrive at my final answer. I kind of got lucky. I need to know how to remove left recursion from any given grammar. Any help would be greatly appreciated. Thank you.

1
compiler-constructioncontext-free-grammar

1 Answers

1
votes
  1. Find the bodies of all nonterminal A production with left recursion and delete them.
  2. Add them to a new non-terminal A ’
  3. For each non-terminal A’ product:
    • Delete the first recursive call A
    • Add an A’ call at the end
  4. You add epsilon production to the non-terminal A’
  5. For all the remaining non-terminal production A, add A’ to the end

Example: A -> Ab | Bb | a

  1. A -> Bb | a
  2. A’-> Ab
  3. A’-> bA’
  4. A’-> bA’ | e
  5. A -> BbA’ | aA’

Result: A -> BbA’ | aA’ A’-> bA’ | e