Self doubt

Question

If the productions were:

S-> AC | BD

A -> a

B -> a

C-> c

D-> d

 

For considering whethr this grmmar is LL(k)  where, k>=2  , is left factoring essential?

I think no because based on atleast 2 lookaheads, it would decide which production to take. In above example, only 1 lookahead is same.

Comments

Yes, You are right because in LL(2) decision will be taken based on $2$ look-aheads.

Answer 1

yes !!your query seems to be true......
But i got a query while i read ur query.....

consider this S1:

S2:

 If a grammar is not LL(1), it is not LL(k) for any k.

QUERY: Aren't these two statements contradicting..... Please Explain?!

Comments

@Smriti.

There can be many reasons for grammar not being LL(1) such as left recursive or ambigious.

Here, in my example, I am concerned of only left factoring i.e. the amount of lookahead.

 

For your example, both statements are correct.

---

is left factoring even needed for LL(1) or LL(2) or LL(k) grammar?

---

@Sreshtha.

Its required for LL(1) since 1 lookahed is same and it wont be able to decide which production to choose based on that lookahead.

Its not required for LL(k) where k>=2

Answer 2

Left factoring is required for the grammer you've given.If first() set of RHS of two productions with the same LHS is equal then the grammer is non determinstic and while constructing LL(1) parsing table there will be conflicts as two productions will be mapped to the same cell in the parsing table. And while choosing a production for generating the ip string, the complier has to choose one among two productions and thus the non determinism. Hence non determinism is removed by left factoring. And lookahead is concerned with terminal symbols, not non terminals. Try to construct a table for the same grammer you've added. The resultant table will be non deterministic.

Comments

@Kaushik. I know that LL(1) will require left factoring. But not for LL(2)