GATE CSE 2003 | Question: 16

Question

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

• A. Removing left recursion alone
• B. Factoring the grammar alone
• C. Removing left recursion and factoring the grammar
• D. None of the above

Comments

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

---

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

---

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.

---

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

Answer 1

$LL(1)$ parser is top down parser.

For top down parsers, the grammar should be unambiguous, deterministic and should not be left recursive.

All the $3$ conditions must be satisfied for $LL(1)$ parsers.

Now, even if all $3$ conditions are satisfied we cannot get an $LL(1)$ or even $LL(k)$ (for any $k$) grammar for even a $DCFG. $This is because there are $DCFLs $ which does not have an $LL(k)$ grammar (see ref below). On the other hand for any $DCFL,$ we can always have an $LR(1)$ grammar.

http://mathoverflow.net/questions/31733/can-i-have-an-ll-grammar-for-every-deterministic-context-free-language

So, Option $D$ is correct.

Comments

indra kumar sahu

Amcodes

Please read this explanation by @arjun sir…..

https://gatecse.in/lr-parsing-part-2-language-of-ll-and-lr-grammars/ 

imp points-

language of any LL(k) grammar is guaranteed to be a DCFL.

But since language of LL(k) is a strict subset of the language of LL(k+1), for any finite kk, there exist SOME DCFL which cannot be generated by ANY LL(k) grammar.

But  it cannot generate all DCFLs.

LL(1)  can generate all regular languages. since regular grammer has right  linear grammer(also left linear) 

 

Hence 

LL(1) always deterministic unambiguous CFG---YES

Deterministic Unambiguous CFG always LL(1) ---No since it cannot generate all dcfl

 

---

So, even if the CFG is unambiguous, left factored, and left recursion is removed, still, we can’t be assured that given CFG is LL(1) grammar because LL(1) can’t parse all possible DCFLs.

Please correct if I’m wrong.

---

@ankit3009

It should be $LL(1)$ as all the languages generated by it will be $DCFL$ although it can’t generate all the $DCFL$ because of (LL(k) is a strict subset of the language of LL(k+1), for any finite k, there exist SOME DCFL which cannot be generated by ANY LL(k) grammar).

check this ->  https://gateoverflow.in/906/gate-cse-2003-question-16?show=389684#c389684

Answer 2

LL(1) properties:

1. Un ambiguous

2. Not left recursive

3. Deterministic

I think C does not make the CFG unambiguous all the time.

Answer 3

D. Removing left recursion and factoring the grammar do not suffice to convert an arbitrary CFG to LL(1) grammar.

Comments

why not C?Could u give me an example?

---

If the Grammar is ambiguous, option C would fail. Removing Left factoring / Left recursion doesn't remove ambiguity in the grammar.

Answer 4

Yes Option D is correct.

But even if the grammar satisfies all three conditions: non left recursive, deterministic and unambiguous even then it may not be LL(1).

E.g.

S -> aAa / ^

A -> abS / ^

Here ^ is epsilon.

This grammar satisfies all three conditions but still not LL(1) because predict set for S -> aAa and S -> ^  is not disjoint.

Comments

@Abhrajyoti00

That’s what i mentioned :) 

it is clearly not left factored.

---

@Pranavpurkar Oh you mean not left factored = not removed left factor? 

---

@Abhrajyoti00

Yes!

Answer 5

Answer is d . Removing left recursion and left factoring is necessary but not sufficent condition for LL(1)

Answer 6

An ambiguous grammar can't be LL(1).

Removing left recursion and factoring the grammar not always guarantees the un-ambiguity of grammar.

i.e.  Ans (D)