What is the correct classification of SDT rules in GATE CS 2025 Set-2 Q22?

Option C is correct. Rule 1 (R→AB) is neither S-attributed nor L-attributed because R.i (a synthesized attribute) depends on A.i which is an inherited attribute. Rule 2 (P→CD) is not S-attributed but is L-attributed because D.i is inherited from C.i (left sibling), satisfying L-attributed conditions. Rule 3 (Q→EF) is both S-attributed and L-attributed since Q.i is synthesized from E.i and F.i only.

What is an S-attributed SDT?

An S-attributed SDT uses only synthesized attributes. A synthesized attribute of a non-terminal on the left-hand side is computed using only the attributes of the symbols on the right-hand side. There are no inherited attributes involved. S-attributed SDTs can be evaluated bottom-up.

Why is Rule 1 (R→AB) neither S-attributed nor L-attributed?

In Rule 1, R.i = A.i + 1 computes a synthesized attribute of R using A.i which is an inherited attribute — not purely synthesized, so it's not S-attributed. For L-attributed, A.i = B.i means A's inherited attribute depends on B which is to its RIGHT in the production. This violates the L-attributed constraint, making Rule 1 neither S-attributed nor L-attributed.

S-attributed L-attributed SDT Rules | GATE CS 2025 Set-2 Q22 Compiler Design

Q: What is an L-attributed SDT?

An L-attributed SDT allows both synthesized and inherited attributes, with the constraint that an inherited attribute of a symbol on the right-hand side can only depend on attributes of symbols to its LEFT in the production, or inherited attributes of the left-hand side non-terminal. L-attributed SDTs can be evaluated in a single left-to-right traversal of the parse tree.

Computer Sciences > GATE 2025 SET-2 > Syntax Directed Translation

Given the following syntax directed translation rules:
Rule 1: R→AB {B.i = R.i1; A.i=B.i; R.i=A.i+1;}
Rule 2: P→CD {P.i = C.i+D.i; D.i=C.i+2;}
Rule 3: Q→EF {Q.i = E.i+F.i;}
Which ONE is the CORRECT option among the following?

Rule 1 is S-attributed and L-attributed; Rule 2 is S-attributed and not L-attributed; Rule 3 is neither S-attributed nor L-attributed

Rule 1 is neither S-attributed nor L-attributed; Rule 2 is S-attributed and L-attributed; Rule 3 is S-attributed and L-attributed

Rule 1 is neither S-attributed nor L-attributed; Rule 2 is not S-attributed and is L-attributed; Rule 3 is S-attributed and L-attributed

Rule 1 is S-attributed and not L-attributed; Rule 2 is not S-attributed and is L-attributed; Rule 3 is S-attributed and L-attributed

Correct : c

The correct answer is Option C.
To classify each rule, recall the two definitions:
S-attributed: Only synthesized attributes are used. Every attribute on the LHS is computed solely from RHS attributes - no inherited attributes involved.
L-attributed: Inherited attributes of a RHS symbol can only depend on attributes of symbols to its left in the production, or on inherited attributes of the LHS. Synthesized attributes of the LHS can use any RHS attribute.
Rule 1 - R → AB { B.i = R.i1; A.i = B.i; R.i = A.i + 1; }
A.i is an inherited attribute that depends on B.i - but B is to the right of A in the production. This violates the L-attributed rule. Also, R.i (synthesized) depends on A.i which is inherited - violating S-attributed. So Rule 1 is neither S-attributed nor L-attributed.
Rule 2 - P → CD { P.i = C.i + D.i; D.i = C.i + 2; }
D.i is an inherited attribute that depends on C.i - C is to the left of D, so L-attributed is satisfied. However, P.i (synthesized) depends on D.i which is an inherited attribute - violating pure S-attributed. So Rule 2 is not S-attributed but is L-attributed.
Rule 3 - Q → EF { Q.i = E.i + F.i; }
Q.i is synthesized using only E.i and F.i - both synthesized RHS attributes. No inherited attributes used anywhere. This is purely S-attributed, and since every S-attributed SDT is also L-attributed, Rule 3 is both S-attributed and L-attributed.
This matches Option C exactly.

Similar Questions

Related Topics

Similar Questions

Related Topics

Question Options

Sign in to ExamPrev