GATE CS 2024 Set 2 Q19 — Syntax-directed Translation

We need to identify the FALSE statements among the given options.

• Statement A (TRUE): According to standard compiler design terminology, an attribute grammar is defined as a Syntax-Directed Definition (SDD) in which the semantic rules have no side effects.
• Statement B (FALSE): An $L$-attributed definition is defined such that the dependency graph of its attributes has no cycles, and the dependencies only flow from left to right. Consequently, the attributes of any $L$-attributed definition can always be evaluated in a depth-first (specifically, a left-to-right pre-order/post-order) traversal. Therefore, the claim that they cannot always be evaluated in depth-first order is false.
• Statement C (TRUE): Synthesized attributes of a node depend only on the attributes of its children. In a bottom-up parser, the children of a node are reduced before the node itself. Thus, their values are already present on the parser stack, allowing synthesized attributes to be evaluated on-the-fly during bottom-up parsing.
• Statement D (FALSE): To evaluate inherited attributes in an $L$-attributed definition during bottom-up parsing, we typically insert marker non-terminals to perform semantic actions before a reduction. However, inserting these marker non-terminals can introduce shift-reduce or reduce-reduce conflicts, making the modified grammar non-LR(1). Thus, not all $L$-attributed definitions based on an LR(1) grammar can be evaluated during bottom-up parsing.

Since the question asks for the FALSE statements, the correct options are B and D.