The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+28 votes

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

- Removing left recursion alone
- Factoring the grammar alone
- Removing left recursion and factoring the grammar
- None of the above

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

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

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.

?

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.

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.

+7 votes

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

1. Un ambiguous

2. Not left recursive

3. Deterministic

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

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

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.

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.

+2 votes

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

0 votes

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 278
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,687 questions

40,231 answers

114,269 comments

38,800 users