GATE CS 2024 Set 2 Q.29: Syntax-Directed Translation

Which of the following statements is/are FALSE?

An attribute grammar is a syntax-directed definition (SDD) in which the functions in the semantic rules have no side effects

The attributes in a L-attributed definition cannot always be evaluated in a depth-first order

Synthesized attributes can be evaluated by a bottom-up parser as the input is parsed

All L-attributed definitions based on LR(1) grammar can be evaluated using a bottom-up parsing strategy

Official answer and solution

Solution

Check standard properties of attribute grammars, S-attributed definitions, and L-attributed definitions.

Note that the question asks which statements are FALSE:

(A) is TRUE: By definition, an attribute grammar is an SDD without side effects in its semantic rules.
(B) is FALSE: In any L-attributed SDD, an inherited attribute of a symbol on the RHS depends only on the inherited attributes of the parent and the attributes of symbols strictly to its left on the RHS. Therefore, the attributes of any L-attributed SDD can always be evaluated in a depth-first (left-to-right) traversal of the parse tree.
(C) is TRUE: S-attributed definitions (containing only synthesized attributes) can always be evaluated on the fly by a bottom-up LR parser during reduction steps.
(D) is FALSE: Evaluating inherited attributes in an L-attributed definition during bottom-up LR(1) parsing requires introducing marker nonterminals, which can introduce shift/reduce or reduce/reduce conflicts so that the modified grammar is no longer LR(1) (unlike LL(1) grammars, for which every L-attributed SDD can be evaluated bottom-up).

Therefore, (B) and (D) are the FALSE statements.

Final answer

Options (B), (D)

Common trap

Selecting the TRUE statements (A) and (C) instead of the FALSE statements.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.