Compiler design miscellaneous

Compiler design miscellaneous

Easy Questions

Compiler Design

Compiler design miscellaneous
  1. Consider two binary operators ­ ↑ and ↓ with the precedence of operator ↓ being lower than that of operator ­↑ . Operator ↑­ is right associative while operator ↓ is left associative. Which one of the following represents the parse tree for expression (7 ↓ 3 ↑­ 4 ­↑ 3 ↓ 2)?








  1. View Hint View Answer Discuss in Forum

    Let us consider the given expression (7 ↓ 3­ ↑ 4­ ↑ 3 ↓ 2). Since the precedence of ­↑ is higher, the subexpression (3­ ↑ 4 ↑ ­3) will be evaluated first. In this subexpression, 4­ ↑
    3 would be evaluated first because ­↑ is right to left associative. So the expression is evaluated
    as ((7 ↓ (3­ ↑ (4­ ↑ 3))) ↓ 2). Also, note that among the two ¯ operators, first one is evaluated before the second one because the associativity of ↓ is left to right.

    Correct Option: B

    Let us consider the given expression (7 ↓ 3­ ↑ 4­ ↑ 3 ↓ 2). Since the precedence of ­↑ is higher, the subexpression (3­ ↑ 4 ↑ ­3) will be evaluated first. In this subexpression, 4­ ↑
    3 would be evaluated first because ­↑ is right to left associative. So the expression is evaluated
    as ((7 ↓ (3­ ↑ (4­ ↑ 3))) ↓ 2). Also, note that among the two ¯ operators, first one is evaluated before the second one because the associativity of ↓ is left to right.

  1. An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts, if and only, if








  1. View Hint View Answer Discuss in Forum

    LALR parser is reduced form of CLR or LR(1) parser, LALR parser uses the LR(1) items of CLR parser & of any shift reduce conflicts are there then it is due to LR(1) parser.

    Correct Option: B

    LALR parser is reduced form of CLR or LR(1) parser, LALR parser uses the LR(1) items of CLR parser & of any shift reduce conflicts are there then it is due to LR(1) parser.

  1. Which of the following describes a handle (as applicable to LR-parsing) appropriately?








  1. View Hint View Answer Discuss in Forum

    It is a production p that may be used for reduction in afuture step along with a position in the sentential form where, the right hand side of the production may befound. A “handle” of a string is a substring that matches the RHS of a production and whose reduction to the nonterminal (on the LHS of the production) represents one step along the reverse of a rightmost derivation toward reducing to the start symbol. If S → * αAw → * αbw, then A → β in the position following a is a handle of αβw. In such a case, it is suffice to say that the substring β is a handle of αβw, if the position of β and the corresponding production are clear. Consider the following grammar: E → E + E | E * E | (E) | id and a right-most derivation is as follows: E → E + E → E + E * E → E + E * id3 → E + id2 * id3 → id1 + id2 * id3

    Correct Option: D

    It is a production p that may be used for reduction in afuture step along with a position in the sentential form where, the right hand side of the production may befound. A “handle” of a string is a substring that matches the RHS of a production and whose reduction to the nonterminal (on the LHS of the production) represents one step along the reverse of a rightmost derivation toward reducing to the start symbol. If S → * αAw → * αbw, then A → β in the position following a is a handle of αβw. In such a case, it is suffice to say that the substring β is a handle of αβw, if the position of β and the corresponding production are clear. Consider the following grammar: E → E + E | E * E | (E) | id and a right-most derivation is as follows: E → E + E → E + E * E → E + E * id3 → E + id2 * id3 → id1 + id2 * id3

  1. Which of the following statements are true?
    1. There exist parsing algorithms for some programming languages whose complexities ar less than θ (n3).
    2. A programming language which allows recursive can be implemented with static storage allocation.
    3. No L-attributed definition can be evaluated in the framework of bottom-up parsing.
    4. Code improving transformations can be performed at both source language and intermediate code level.








  1. View Hint View Answer Discuss in Forum

    The time bounds for the parser are the same as those of the recognizer, while the space bound goes up to n 3 in general in order to store the parse trees. In fact it would probably be most efficient to implementthe algorithm to do just a look-ahead of 1. To implement the full look-ahead for any k would be more costly inprogramming effort and less efficient overall since so few programming languages need the extra lookahead. Improving transformations are performed on a target-specific representation of the program. for both existing and proposed architectures, to gather trace information for code improvements are often applied to a high-level intermediate language though it can be applied to the source level also but it can impact the effectiveness of code improvements
    I. Statement is true since there are some parsers which take O(n log2n) time for parsing.
    II. Completely false, since there is no use of stack which is required for recursion.
    III. False
    IV. True since both types of optimizations are applied

    Correct Option: B

    The time bounds for the parser are the same as those of the recognizer, while the space bound goes up to n 3 in general in order to store the parse trees. In fact it would probably be most efficient to implementthe algorithm to do just a look-ahead of 1. To implement the full look-ahead for any k would be more costly inprogramming effort and less efficient overall since so few programming languages need the extra lookahead. Improving transformations are performed on a target-specific representation of the program. for both existing and proposed architectures, to gather trace information for code improvements are often applied to a high-level intermediate language though it can be applied to the source level also but it can impact the effectiveness of code improvements
    I. Statement is true since there are some parsers which take O(n log2n) time for parsing.
    II. Completely false, since there is no use of stack which is required for recursion.
    III. False
    IV. True since both types of optimizations are applied

Direction: For the grammar below, a partial LL (1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2 and E3. ε is the empty string, $ indicates end of input and | separates alternate right hand sides of productions.
S → a A b B | b A a B | ε
A → S
B → S

  1. The FIRST and FOLLOW sets for the non-terminals A and B are








  1. View Hint View Answer Discuss in Forum

    First (S) = First (aAbB) ∪ First (bAaB) ∪ ∈ = {a} ∪ {b} ∪ ∈
    = {a,b,∈}
    First (A) = First S = {a,b,∈}
    First (B) = First S = {a,b,∈}
    Follow (S) = {$} ∪ follow (A) ∪ follows (B)
    Follow (A) = {a, b}
    Follow (B) = Follow (S) = {$, a, b}

    Correct Option: A

    First (S) = First (aAbB) ∪ First (bAaB) ∪ ∈ = {a} ∪ {b} ∪ ∈
    = {a,b,∈}
    First (A) = First S = {a,b,∈}
    First (B) = First S = {a,b,∈}
    Follow (S) = {$} ∪ follow (A) ∪ follows (B)
    Follow (A) = {a, b}
    Follow (B) = Follow (S) = {$, a, b}