Log In
52 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
in Compiler Design 14.5k 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
$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..

10 Answers

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

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


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



@Shaik Masthan hidden left factors should also be counted right so the grammar you gave seems to be left factored but is not actually right ?

can we say that deterministic unambiguous cfg is always LL(1)?

@ then why every DCFL doesn’t have a LL(1) grammar.



Please read this explanation by @arjun sir….. 

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) 



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

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


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

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

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.
5 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.
can you give me example.

even if we remove left recursion,left factoring still there ambiguity
4 votes
Answer is d . Removing left recursion and left factoring is necessary but not sufficent condition for LL(1)
1 vote
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)
1 vote
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


so by leftrecursive and factoring will not make the grammar unammbigous ....option d  is correct
0 votes
answer - C
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.

Related questions

21 votes
3 answers
Assume that the SLR parser for a grammar G has $n_1$ states and the LALR parser for G has $n_2$ states. The relationship between $n_1$ and $n_2$ is $n_1$ is necessarily less than $n_2$ $n_1$ is necessarily equal to $n_2$ $n_1$ is necessarily greater than $n_2$ None of the above
asked Sep 16, 2014 in Compiler Design Kathleen 6.2k views
31 votes
3 answers
Consider the grammar shown below. $S \rightarrow C \ C$ $C \rightarrow c \ C \mid d$ This grammar is LL(1) SLR(1) but not LL(1) LALR(1) but not SLR(1) LR(I) but not LALR(1)
asked Sep 17, 2014 in Compiler Design Kathleen 10.9k views
42 votes
4 answers
Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statistically linked libraries? Smaller sizes of executable files Lesser overall page fault rate in the system Faster program startup Existing programs need not be re-linked to take advantage of newer versions of libraries
asked Sep 17, 2014 in Compiler Design Kathleen 8k views
30 votes
6 answers
The following program fragment is written in a programming language that allows global variables and does not allow nested declarations of functions. global int i=100, j=5; void P(x) { int i=10; print(x+10); i=200; j=20; print (x); } main() {P(i+j);} If the ... scoping and call by name parameter passing mechanism, the values printed by the above program are $115, 220$ $25, 220$ $25, 15$ $115, 105$
asked Apr 24, 2016 in Compiler Design jothee 5.1k views