Can't figure out how to make a grammar LL(1)

Question

Let's say I start with:

$A \rightarrow Ba$

$B \rightarrow dab | cBb | Acb$

Now I want to make this grammar LL(1), so I need to get rid of the left recursion. I'll work with $B \rightarrow Acb$.

I'll replace where $A$ occurs with its production:

$B \rightarrow dab|cBb|Bacb$

And that gives me a direct left recursion, which I rewrite as:

$B \rightarrow dabB' | cBbB'$

$B' \rightarrow acbB' | \epsilon$

At this point this seems like this should be LL(1), so I'm checking: $FIRST$ sets: For $A: \{d,c\}$, $B: \{d,c\}$ and $B': \{\epsilon, a\}$.

$FOLLOW$ sets: $A: \{eof\}$, $B: \{a,b\}$ and $B': \{a,b\}$.

Now I'd like to check $FIRST^+$, but if I do $FIRST^+(B' \rightarrow acbB') = \{a\}$ and then $FIRST^+(B' \rightarrow \epsilon) = \{\epsilon, a, b\}$ which does NOT have a non-empty intersection.

Does it make sense to look at $FIRST^+$ in terms of each production that has the same left hand side? Or, have I made a mistake in calculating $FIRST$ or $FOLLOW$ sets to begin with? Is there an issue with the rule $B \rightarrow cBb$ (not left recursive exactly but does have the $B$ nestled inside).

Answer 1

For context-free grammar to be LL(1), these two requirements have to be met for its every rule $ A \rightarrow \alpha | \beta$:

1. $ FIRST(\alpha) \cap FIRST(\beta) = \emptyset$
2. $ \epsilon \in FIRST(\alpha) \implies FOLLOW(A) \cap FIRST(\beta) = \emptyset$

Does it make sense to look at FIRST+ in terms of each production that has the same left hand side?

No, as you can see, to decide if grammar fits those rules above, we have to calculate $FIRST$ function for the right-hand sides of the grammar's rules, not for the left sides.

For your grammar, we get these results:

$A: FIRST(Ba) = \{c,d\},\space FOLLOW(A) = \{\epsilon\}$

$B: FIRST(dabB') = \{d\},\space FIRST(cBbB') = \{c\}, \space FOLLOW(B)=\{a,b\}$

$B': FIRST(acbB') = \{a\},\space FIRST(\epsilon) = \{\epsilon\},\space FOLLOW(B')=\{a\}$

As you can see, there is a $FIRST/FOLOW$ conflict (violated second requirement from above) in $B'$. You can read here about how to solve this.