GATE 2024 CS2 Q.29: solution and answer

Official answer: B, DSource: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

1. We need the FALSE statements, so test each option against the definitions.

2. (A) An attribute grammar is an SDD whose semantic rules are functions with no side effects. This is the standard definition, so (A) is TRUE.

3. (B) In an L-attributed definition, an inherited attribute of a symbol depends only on the inherited attributes of its parent and on attributes of symbols to its left. A left-to-right depth-first traversal of the parse tree therefore always finds every value it needs already computed. So the attributes can always be evaluated in depth-first order. The claim that they cannot always be is FALSE.

4. (C) A bottom-up parser can compute a synthesized attribute at each reduction from the attributes of the right-hand-side symbols already on the stack. This is how S-attributed definitions work, so (C) is TRUE.

5. (D) Evaluating an L-attributed definition bottom-up needs rewriting: each inherited attribute needs a marker nonterminal $M\to \epsilon$ inserted before the symbol. This rewriting is guaranteed to work only for LL(1) grammars. For an LR(1) grammar the markers can introduce conflicts. Example: take $S\to aAc\mid aBd$, $A\to e$, $B\to e$, which is LR(1), and suppose $A$ and $B$ each have an inherited attribute. After inserting markers, $S\to a{M}_{1}Ac\mid a{M}_{2}Bd$ with $M_1\to \epsilon$ and $M_2\to \epsilon$. After shifting $a$ with lookahead $e$, the parser must reduce by $M_1\to \epsilon$ or by $M_2\to \epsilon$ and cannot decide. This is a reduce-reduce conflict. So not all L-attributed definitions on LR(1) grammars can be evaluated bottom-up, and (D) is FALSE.

6. The false statements are (B) and (D).