26,980 views
67 votes
67 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

10 Answers

Best answer
74 votes
74 votes

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.

edited by
10 votes
10 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
7 votes

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

6 votes
6 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.
Answer:

Related questions

26 votes
26 votes
4 answers
1
40 votes
40 votes
3 answers
2
Kathleen asked Sep 17, 2014
19,885 views
Consider the grammar shown below. $S \rightarrow C \ C$$C \rightarrow c \ C \mid d$This grammar isLL(1)SLR(1) but not LL(1)LALR(1) but not SLR(1)LR(I) but not LALR(1)