-
Consider the grammar with non-terminals N = {S, C, S1}, terminals T = {a, b, i, t, e} with S as the start symbol and the following set of rules
S → iCtSS1 | a
S1 → eS | ε
C → b
The grammar is not LL(1) because
-
- it is left recursive
- it is right recursive
- it is ambiguous
- it is not context-free
- it is left recursive
Correct Option: C
A LL(1) grammar doesn't give to multiple entries in a single cell of its parsing table. It has only single entry in a single cell, hence it should be unambiguous.
Option A is wrong. Grammar is not left recursive. For a grammar to be left recursive a production should be of form A → Ab, where A is a single Non-Terminal and b is any string of grammar symbols.
Option B is wrong. Because a right recursive grammar has nothing to do with LL(1).
Option D is wrong. Because the given grammar is clearly a Context Free Grammar. A grammar is CFG if it has productions of the form A → (V ∪ T) *, where A is a single non-terminal and V is a set of Non-terminals and T is a set of Terminals.
Hence Option C should be the correct one. i.e. the grammar is ambiguous.
But let's see how the grammar is ambiguous. If the grammar is ambiguous then it should give multiple entry in a cell while making its parsing table. And Parse table is made with the aid of two functions: FIRST and FOLLOW.
A parsing table of a grammar will not have multiple entries in a cell( i.e. will be a LL(1) grammar) if and only if the following conditions hold for each production of the form A → α | β
1. FIRST (α) ∩ FIRST(β) = φ
2. If FIRST (α) contains ' ε ' then FIRST(α) ∩ FOLLOW (A) = φ and vice-versa.
Now,
• For the production, S → iCtSS1|a, rule 1 is satisfied,
because FIRST(iCtSS1) ∩ FIRST(a) = {i} ∩ {a} = φ
• For the production, S1 → eS| ε, rule 1 is satisfied,
as FIRST(eS) ∩ FIRST(ε) = {e} ∩ {e} = φ.
But here due to ' ε ' in FIRST, we have to check for rule 2. FIRST(eS) ∩ FOLLOW(S1) = {e} ∩ {e, $} ≠ φ. Hence rule 2 fails in this production rule.
Therefore there will be multiple entries in the parsing table, hence the grammar is ambiguous and not LL(1).