6.9k views

Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?

1. Removing left recursion alone
2. Factoring the grammar alone
3. Removing left recursion and factoring the grammar
4. None of the above
| 6.9k views
+5
S->Sa/a  here to convert into LL(1) need to be remove left recursive

for this S->ab/a here to convert LL(1) remove left factoring

then if i take a grammer which not having both left recursive and left factoring for example S->AB/a ;A->a,B->epsilon  then but still not parse by LL(1) bcz it is ambiguous so for that we have to be fulfill all three condition then we can convert into LL(1) surely  so D
+4
$S->A | B$
$A-> a$
$B-> a$

The above mentioned grammar has neither left recursion nor common prefixes, still it's not LL(1).

(D) is the correct option!
0
there is nothing so complicated they asked only ;

if we take any random CFG then what happens?

LL(1) parser not parse all D_CFG like ambiguous and left recursive CFG's etc. so we easily say option ( D ) should be correct.
+2
LL(1) parser does not parse left recursive, ambiguous, non-deterministic grammar because they create conflict in parsing table for sure but these are necessary but not sufficient condition because even a DCFG is free from left recursion, ambiguous, non-determinism still for some reason the parsing table may contain conflict, and no matter how much we try, conflicts in LL(1) parsing table can never be removed for some grammars..

S->Sa/a  here to convert into LL(1) need to be remove left recursive

for this S->ab/a here to convert LL(1) remove left factoring

then if i take a grammer which not having both left recursive and left factoring for example S->AB/a ;A->a,B->epsilon  then but still not parse by LL(1) bcz it is ambiguous so for that we have to be fulfill all three condition then we can convert into LL(1) surely  so D
by Junior (515 points)

A grammar can be LL(1) if it is unambiguous, not left recursive and deterministic.

Options A and B remove left recursion and non-deteminism, but none of them disambiguates the grammar.

So, Option D

by Loyal (6.9k points)