Home » Compiler Design » Compiler design miscellaneous » Question

Compiler design miscellaneous

  1. 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
    1. it is left recursive
    2. it is right recursive
    3. it is ambiguous
    4. it is not context-free
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).



Your comments will be displayed only after manual approval.