The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+28 votes

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


asked in Compiler Design by Veteran (69k points) | 2.9k views
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

7 Answers

+32 votes
Best answer

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.

So, option D is correct.

answered by Boss (9.3k points)
edited by
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

then how do you remove left recurssion ?
A->Aa/b =>



Thats how.

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.



hope that helps.
+7 votes

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

answered by Veteran (14.1k points)
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.
+6 votes
LL(1) properties:

1. Un ambiguous

2. Not left recursive

3. Deterministic

I think C does not make the CFG unambiguous all the time.
answered by Junior (801 points)
+3 votes
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).


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.
answered by Active (1.1k points)
can you give me example.

even if we remove left recursion,left factoring still there ambiguity
+2 votes
Answer is d . Removing left recursion and left factoring is necessary but not sufficent condition for LL(1)
answered by Veteran (10.6k points)
0 votes
answer - C
answered by Boss (9.3k points)
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.
0 votes
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)
answered by (239 points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,687 questions
40,231 answers
38,800 users