GATE CS 2024 Set 2 | Question 29

MSQ · 1 mark

Which of the following statements is/are FALSE?

  1. Option A: An attribute grammar is a syntax-directed definition (SDD) in which the functions in the semantic rules have no side effects
  2. Option B: The attributes in a L-attributed definition cannot always be evaluated in a depth-first order (correct)
  3. Option C: Synthesized attributes can be evaluated by a bottom-up parser as the input is parsed
  4. Option D: All L-attributed definitions based on LR(1) grammar can be evaluated using a bottom-up parsing strategy (correct)

Answer

(B), (D)

Explanation

The question asks for the false statements.

  • A is true. That is the usual definition: the semantic rules of an attribute grammar just compute attribute values, without printing, updating tables or other side effects.
  • B is false. In an L-attributed definition an inherited attribute depends only on the parent and on siblings to its left, so a single left-to-right depth-first traversal always works, computing inherited attributes on the way down and synthesized ones on the way up.
  • C is true. An LR parser computes a synthesized attribute when it reduces by a production, keeping the values on its stack.
  • D is false. Inserting marker nonterminals to compute inherited attributes is guaranteed to work for LL grammars, but in an LR(1) grammar the markers can create parsing conflicts, so not every such definition can be evaluated bottom-up.

Answer: B, D