Question

I have stumbled upon a very curious case: Consider

1)       S -> Ax
2) & 3)  A->alpha|beta
4)       alpha-> b
5) & 6)  beta -> epsilon | x

Now I checked and this grammar doesn't defy any rules of LL(1) grammars. But when I construct the parsing table, there are some collisions.

First Sets
S => {b,x}
A=>{b,x,epsilon}
alpha=>{b}
beta=> {x,epsilon}

Follow sets
S=> {$}
A => {x}
alpha => {x}
beta => {x}

Here is the parsing table **without considering** the RHS's which can produce 
epsilons
          x        b      $
S         1        1
A         3        2
alpha              b
beta      6

So far so good, but when we do consider RHS's that can derive epsilon, we get collisions in the table!

So is this LL(1) or not?

No correct solution

OTHER TIPS

So is this LL(1) or not?

First(A) contains x, and Follow(A) contains x. Since A can derive empty, and there is an intersection between First(A) and Follow(A), it is not LL(1).

I am really sorry, its a blunder on my part.

Actually it doesn't satisfy all the rules of LL(1) grammars

beta-> epsilon | x

hence first(x)^follow(beta) should be disjoint but thats not the case!!

Sorryy!!

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top