0
$\begingroup$

I need to remove indirect left recursion from the following CFG: remove indirect left recursion from the following CFG. $$A → Ba| b$$ $$B → Cd | e$$ $$C → Df | g$$ $$D → Df | Aa | Cg$$

In the following solution, I have expanded all the non-terminals to get them converted to direct recursion, instead of indirect recursion (if applicable), so that I may apply Rule for removal of direct left recursion:

$$A → Ba → Cda → Dfda → Aafda$$ $$C → Df → Cgf$$ $$D → Df$$ $$D → Cg → Dfg$$ $$D → Aa → Dfdaa$$ So, it becomes: $$A → Aafda| b$$ $$B → Cd | e$$ $$C → Cgf | g$$ $$D → Df | Dfg | Dfdaa | ba | gg$$ So, it becomes (after removal of direct left recursions): $$A → bA'$$ $$A' → afdaA'| eps$$ $$B → Cd | e$$ $$C → gC'$$ $$C' → gfC' | eps$$ $$D → baD' | gg D'$$ $$D'→ fD' | fgD' | fdaaD' | eps$$

My specific Question is: Do I have to follow this way (convert all production rules emanating from all non-terminals or should I do that for only one, e.g. D?

$\endgroup$
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Mar 12 '16 at 5:09
  • $\begingroup$ @D.W., edited my qs with specific doubt $\endgroup$ – Dr. Debasish Jana Mar 13 '16 at 6:34
2
$\begingroup$

You should focus on trying to only modify productions that aren't "good". A production is "good" if it :

  1. Starts with a terminal,
  2. Is an epsilon production, or
  3. Is in the form A->B (followed by a series of terminals and non-terminals) and we can partially order the non-terminals so that A<B. We'd also have to do some extra checks if B being nullable. That is, if B is nullable, we'd have to consider all productions in which B occurs and is nulled. For example, suppose we have the grammar:

    A -> BAa
    B -> b | esp
    

    At first glance, the rule A->BAa might appear good (because we can assert that A<B), but if B is nulled, we end up with the production A->Aa which is bad. This is usually not a big problem, but you've got to make sure you cover all your cases. Note that this doesn't apply to your example, but I'd figure I'd be thorough.

For your grammar:

  • A->Ba is good since we can assert that A<B.

  • b is good because this is a terminal.

  • For similar reasons, all the productions of B and C are also "good", so we shouldn't change them.

  • For D, there are several problems. Obviously, we cannot assert that D<D, and we also can't assert that D<A or D<C (since we assumed that A<B<C<D in our previous step). However, the productions for A, B, and C are all "good", so we can substitute those in and expose the hidden left recursion (as you've done in your work).

In short, you should only worry about modifying "bad" productions and leaving any "good" ones as they are. It's not always possible to do this, but in general, it'll save you work.

$\endgroup$
  • $\begingroup$ Welcome to CS.SE, and thank you for the detailed answer! One question: Would you mind editing your answer to clarify about the nullable check? Do we need to check that B is nullable, or that B isn't nullable? I know you said it doesn't matter for this specific example, but that might be helpful to others with a similar problem in the future. $\endgroup$ – D.W. Mar 13 '16 at 19:34
  • $\begingroup$ There you go :) $\endgroup$ – user979616 Mar 13 '16 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.