Search code examples
compiler-construction

How to make this grammar LL(1)?

I had this grammar at first.

S -> A | B
A -> Aa | epsilon
B -> Bb | epsilon

I eliminated left recursion to have this:

S -> A | B
A -> A'
A' -> aA' | epsilon
B -> B'
B' -> bB' | epsilon

This grammar is not LL(1) as First(A) and First(B) have epsilon in common. I know that common first symbols are usually resolved with factoring. I do not know how to resolve common epsilon in A and B First sets.

Solution

  • The grammar is ambiguous, since an empty string could be produced by either S→A→ε or S→B→ε. In order to make the grammar parseable at all, you need to resolve the ambiguity.

    Probably the simplest would be to add the rule S→ε and then remove it from both A and B, so that their base productions are a and b respectively.