1
$\begingroup$

This is the original grammar:

S -> ABe
A -> ab | a | ϵ
B -> b

I did try left factoring and this is what I got:

S -> ABe
A -> aX | ϵ
X -> b | ϵ
B -> b 

But it still is not LL(1).

$\endgroup$
  • $\begingroup$ Why don't you inline A, B and X? Are you following some fixed procedure? $\endgroup$ – reinierpost Nov 9 '16 at 16:14
  • $\begingroup$ Why is this not an LL(1)? What definition of LL(1) are you using? $\endgroup$ – randomsurfer_123 Nov 9 '16 at 16:16
  • $\begingroup$ @randomsurfer_123 there are conflicts in parsing table. $\endgroup$ – Asnira Nov 9 '16 at 16:18
  • $\begingroup$ @reinierpost sorry, I dont get what you are saying. $\endgroup$ – Asnira Nov 9 '16 at 16:19
  • 1
    $\begingroup$ Do you have to follow those instructions, or do you just need to find an equivalent LL(1) form? In general, if you have a rule of the form $S \to A\alpha$ where $A$ is nullable, then just eliminating left-recursion and left-factoring is not enough. There's two things you can do: 1. either inline A and B, or 2. eliminate the $\epsilon$ from $A$ so that $S \to ABe \mid Be; A \to a \mid ab$. Either of these options will allow you to finish off your grammar using just recursion elimination and factoring; but without doing at least one of these, you can't get to an amenable form. $\endgroup$ – Lee Nov 9 '16 at 18:25

Your Answer

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

Browse other questions tagged or ask your own question.