Compiler design miscellaneous

Compiler design miscellaneous

Easy Questions

Compiler Design

Compiler design miscellaneous
  1. In the correct grammar above, what is the length of the derivation (number of steps starting from S) to generate the string albm with l ≠ m?








  1. View Hint View Answer Discuss in Forum

    It is very clear from the previous solution that the no. of steps required depend upon the no. of a' s & b ' s which ever is higher & exceeds by 2 due to S " AC CB & C"!
    So max(l, m) + 2
    Hence (a) is correct option.

    Correct Option: A

    It is very clear from the previous solution that the no. of steps required depend upon the no. of a' s & b ' s which ever is higher & exceeds by 2 due to S " AC CB & C"!
    So max(l, m) + 2
    Hence (a) is correct option.

  1. Which one of the following grammars generates the language L = {ai bj} i ≠ j]?








  1. View Hint View Answer Discuss in Forum

    In the language language L = {ai bj | i ≠ j} The expression i ≠ j indicates that language L is a language in which number of a ≠ number of b. Here, we need to search for a language in which number of a ≠ number of b.
    Considering the options:
    Options (a)
    S → AC | CB
    C → aCb | a| b
    A → aA | ∈
    B → Bb | ∈
    (a), S → (C) B → a(b) → aBb → ab
    Here, the number of a = number of b, hence, it is not the required grammar.
    Option (b)
    S → as | Sb | a | b
    S → as → abB
    Here, number of a = number of b, hence it is not the required grammar.
    Option (c)
    S → AC | CB
    C → aC b| ∈
    A → aA | ∈
    B → Bb | ∈
    S(C)B → acbB → ab
    Here, number of a = number of b, hence it is not the required grammar.
    Option (d)
    S → AC | CB
    C → aC b| ∈
    A → aA | a
    B → Bb | b
    Consider the production
    S → AC | CB
    Applying, C → ∈
    We get S → A|B
    Now, applying A or B, S generates a^n.b^n. So, L = {ai bj | i ≠ j}
    Now, consider the production, S → AC | CB. If the production C → acb is applied then, it generates a^n,b^n.
    Now, applying either A or B it will give that number of a ≠ number of b.

    Correct Option: D

    In the language language L = {ai bj | i ≠ j} The expression i ≠ j indicates that language L is a language in which number of a ≠ number of b. Here, we need to search for a language in which number of a ≠ number of b.
    Considering the options:
    Options (a)
    S → AC | CB
    C → aCb | a| b
    A → aA | ∈
    B → Bb | ∈
    (a), S → (C) B → a(b) → aBb → ab
    Here, the number of a = number of b, hence, it is not the required grammar.
    Option (b)
    S → as | Sb | a | b
    S → as → abB
    Here, number of a = number of b, hence it is not the required grammar.
    Option (c)
    S → AC | CB
    C → aC b| ∈
    A → aA | ∈
    B → Bb | ∈
    S(C)B → acbB → ab
    Here, number of a = number of b, hence it is not the required grammar.
    Option (d)
    S → AC | CB
    C → aC b| ∈
    A → aA | a
    B → Bb | b
    Consider the production
    S → AC | CB
    Applying, C → ∈
    We get S → A|B
    Now, applying A or B, S generates a^n.b^n. So, L = {ai bj | i ≠ j}
    Now, consider the production, S → AC | CB. If the production C → acb is applied then, it generates a^n,b^n.
    Now, applying either A or B it will give that number of a ≠ number of b.

  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. What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammer with no epsilon-and unit-production (i.e. of type A → ε and A → a) to parse a string with n tokens?








  1. View Hint View Answer Discuss in Forum

    Let the grammar is:
    A → BC
    B → aa
    C → bb
    now let the string w = aabb then
    A → BC(reduction 3)
    → aaC (reduction 2)
    → aabb (reduction 1)
    n = 4 and number of productions are 3 so n - 1

    Correct Option: B

    Let the grammar is:
    A → BC
    B → aa
    C → bb
    now let the string w = aabb then
    A → BC(reduction 3)
    → aaC (reduction 2)
    → aabb (reduction 1)
    n = 4 and number of productions are 3 so n - 1