CODEWITHSUNDEEP
parsingcompiler-constructioncontext-free-grammar
ishan3243
ishan3243

Reputation: 1928

Curious case LL(1) or not?

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?

Upvotes: 0

Views: 68

Answers (2)

ishan3243
ishan3243

Reputation: 1928

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!!

Upvotes: 0

user142162
user142162

Reputation:

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

Upvotes: 2

Related Questions