GATE CS 2020 Q33 — Syntax-directed Translation

To determine whether the rules are $L$-attributed, let us recall the definition of an $L$-attributed Syntax-Directed Definition (SDD):

For a production $X \rightarrow Y_1 Y_2 \dots Y_n$, an inherited attribute of a symbol $Y_k$ on the right-hand side can only depend on:

1. Inherited attributes of the head non-terminal $X$.
2. Any attributes (synthesized or inherited) of the symbols $Y_1, Y_2, \dots, Y_{k-1}$ that lie to the left of $Y_k$.

Synthesized attributes of the head $X$ can depend on any attributes of the children on the right-hand side.

Analysis of Rule 1: $A \rightarrow PQ$

• $P.i = A.i + 2$: The inherited attribute $P.i$ depends on $A.i$ (inherited attribute of the head $A$). This is valid.
• $Q.i = P.i + A.i$: The inherited attribute $Q.i$ depends on $P.i$ (attribute of $P$, which is to the left of $Q$) and $A.i$ (inherited attribute of the head $A$). This is valid.
• $A.s = P.s + Q.s$: The synthesized attribute of the head $A$ depends on the attributes of its children. This is valid.

Since all dependencies satisfy the conditions, Rule 1 is $L$-attributed.

Analysis of Rule 2: $A \rightarrow XY$

• $X.i = A.i + Y.s$: The inherited attribute $X.i$ depends on $Y.s$ (synthesized attribute of $Y$). Since $Y$ lies to the right of $X$, this dependency on a right sibling is invalid for an $L$-attributed definition.

Thus, Rule 2 is not $L$-attributed.

Therefore, only Rule 1 is $L$-attributed. The correct option is B.