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

can left-factoring remove all non-determinism?

---

I think so, I can shift all the symbols to next steps that are causing non-determinism.

I have one more question. While searching something on internet, I have found that all the deterministic grammars are unambiguous. I have alsi read that some grammars are inherently ambiguous. Little confused.

I have read somewhere before that removal of non determinism does not guarantee removal of ambiguity.

?

---

Yes, determinism guarantees unambiguity. And language of some grammar is inherently ambiguous- meaning we cannot remove ambiguity from such grammars.

---

what about LR(k) grammars?? they also need deterministic grammar right?

---

See answer now, it wasnt correct earlier..

---

Thanx a lot arjun sir. In LL(k) or LL(1) we get conflict in the parsing table when first of two different productions having same LHS symbol have common symbol and hence in that case it wont be parsed by ll1. right?

---

We look as First for LL(1) only - the 1 and first mean the same here. For LL(2) and on, it becomes more hard but even for any k, LL(k) parser is not possible for all DCFLs.

---

@ Arjun sir

When we left factor a grammar and make it deterministic, it doesnt make the grammar unambiguous if it was  ambiguous. Then how can we say that every deterministic grammar is unambiguous?? Its confusing :(

---

isnt left factoring done to remove left recursion ?

---

No, to remove non determinism

---

@vishal

then how do you remove left recurssion ?

---

A->Aa/b =>

A->bA'

A'->aA'/epsilon

Thats how.

---

@vishal

isnt this method called left factoring ?

---

No, it is removing left recursion.

Left factoring is removing non-determinism or common prefixes.

e.g. A-->aP/aQ/aR, all three have common prefix, so we remove it by left factoring.

A-->aA'

A'-->P/Q/R.

hope that helps.

---

Someone explain the above question by @sushmitha

---

When we left factor a grammar and make it deterministic, it doesnt make the grammar unambiguous if it was  ambiguous. Then how can we say that every deterministic grammar is unambiguous?? Its confusing :(

By removing Left Factor( It is done to avoid back-tracing by the parser. ), we make the productions as Deterministic but not the Grammar.

Eg :-

S → aA | a BC

A → bab

B → b

C → ab

By removing Left Factoring, it is looking as

S → aD

D → A | BC

A → bab

B → b

C → ab

 

Now it is left factored ( Note that, there is NO BACK-TRACING ) , but is it Unambiguous Grammar ?

NO, due to abab can be derived in two ways.

Derivation 1 :-

S ---> a D 

     ---> a A

     ---> a bab

Derivation 2 :-

S ---> a D 

     ---> a BC

     ---> a b C

     ---> a b ab

---

@Shaik+Masthan

Means Doing left factoring doesn't convert Non-deterministic CFG to Deterministic CFG. right

Its productions that become deterministic not the Language/Grammar ?

If that would have been the case then Then Language would get change bcoz Non-deterministic CFG generates NCFL and Deterministic CFG generates DCFL.

But that should not happen ..language of grammar after left factoring should be same as before

---

Means Doing left factoring doesn't convert Non-deterministic CFG to Deterministic CFG. right

yes..

Answer 2

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 3

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 4

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

Answer 5

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

can you give me example.

even if we remove left recursion,left factoring still there ambiguity

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)

Answer 7

LL(1)  grammar  should be unambigous

even by eliminating leftfactoring we cannot eliminate the ambiguity

so ambigous will always there even if we convert the ambigous grammar into determistic grammar.

example:- s->iEts /iEtses/a                         s->iEtss'/a

                E->b                              =>          s'->epsilon/es

non determistic grammar                              E->b

                                                                  determisticgrammar

so by leftrecursive and factoring will not make the grammar unammbigous ....option d  is correct

Answer 8

answer - C

Comments

I think D should be the answer. As not all CFG can be converted into LL(1) even if after removing left recursion and factoring.