410 views
0 votes
0 votes
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.

2 Answers

0 votes
0 votes

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

0 votes
0 votes

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.

edited by

Related questions

1 votes
1 votes
1 answer
1
Tauhin Gangwar asked Feb 5, 2017
537 views
Is this grammar is left factored if yes ??? plz explain how
0 votes
0 votes
0 answers
2
gateexplore asked Nov 17, 2023
81 views
0 votes
0 votes
1 answer
4
Sajal Mallick asked Oct 13, 2023
155 views
Does Follow and First operation always apply on non left recursive grammar?