1
$\begingroup$

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).

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.