Compiler design miscellaneous


Compiler design miscellaneous

  1. Consider the following two statements :
    P : Every regular grammar is LL (1).
    Q : Every regular set has a LR (1) grammar.
    Which of the following is true?









  1. View Hint View Answer Discuss in Forum

    A regular grammar can also be ambiguous also. For example, consider the following grammar,
    S → aA/a
    A → aA/ ε
    In above grammar, string 'a' has two leftmost derivations.
    (1) S → aA (2) S → a
    S → a (using A → e)
    And LL(1) parses only unambiguous grammar, so statement P is False.
    Statement Q is true is for every regular set, we can have a regular grammar which is unambiguous so it can be parse by LR parser.
    So option C is correct Answer.

    Correct Option: C

    A regular grammar can also be ambiguous also. For example, consider the following grammar,
    S → aA/a
    A → aA/ ε
    In above grammar, string 'a' has two leftmost derivations.
    (1) S → aA (2) S → a
    S → a (using A → e)
    And LL(1) parses only unambiguous grammar, so statement P is False.
    Statement Q is true is for every regular set, we can have a regular grammar which is unambiguous so it can be parse by LR parser.
    So option C is correct Answer.


  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. View Hint View Answer Discuss in Forum

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

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



  1. Which one of the following is a top-down parser?









  1. View Hint View Answer Discuss in Forum

    Top-down parsing is a technique to analyze unknown data relationship. This is done by hypothesizing general parser tree structures and then considering whether the known fundamental structures are compatible with the hypothesis that was made earlier. Recursive descent parser is a top down parser.

    Correct Option: A

    Top-down parsing is a technique to analyze unknown data relationship. This is done by hypothesizing general parser tree structures and then considering whether the known fundamental structures are compatible with the hypothesis that was made earlier. Recursive descent parser is a top down parser.


Direction: Consider the CFG with {S, A, B} as the non-terminal alphabet, {a, b} as the terminal alphabet, S as the start symbol and the following set of production rules

  1. For the correct answer strings to Q. above, how many derivation trees are there?









  1. View Hint View Answer Discuss in Forum

    The string received is aabbab. We can total 2 derivation trees: Leftmost derivation and rightmost derivation.

    Correct Option: B

    The string received is aabbab. We can total 2 derivation trees: Leftmost derivation and rightmost derivation.



  1. Which of the following strings is generated by the grammar?









  1. View Hint View Answer Discuss in Forum

    Let solve out to get the string generated by the grammar.
    S → aB
    S → aaBB
    S → aabB
    S → aabbS
    S → aabbaB
    S → aabbab
    We get the string as aabbab.

    Correct Option: C

    Let solve out to get the string generated by the grammar.
    S → aB
    S → aaBB
    S → aabB
    S → aabbS
    S → aabbaB
    S → aabbab
    We get the string as aabbab.