LI.3.2 S- and L-attributed definitions · GATE 2027 Compiler Design

ACompressed recap

🧾

S-attributed: only synthesized attributes; evaluated bottom-up, for example by an LR parser at each reduction with a value stack. L-attributed: inherited attributes may use only the parent’s inherited attributes and siblings to the left; evaluated in one depth-first left-to-right walk, naturally by recursive descent (parameters down, results up). S ⊂ L. Anything else needs the whole tree and a dependency graph.

BMerged rule card

3.2 S-attributed and L-attributed definitions; which parsers can evaluate which

S-attributed: synthesized only → postorder; LR evaluates on reductions with a value stack.
L-attributed: inherited attrs of Xⱼ depend only on A’s inherited and X₁…Xⱼ₋₁ (and Xⱼ, acyclically).
S-attributed ⊂ L-attributed.
L-attributed: one depth-first left-to-right walk; recursive descent: inherited = parameters, synthesized = return values.
LR + inherited attributes: needs marker nonterminals M → ε.

CInterleaved GATE-style questions

Q1MCQ1 markClassify

A → X Y with X.i = A.i and Y.i = X.s, A.s = Y.s. This SDD is:

(A) S-attributed
(B) L-attributed but not S-attributed
(C) neither
(D) circular

Q2MCQ1 markClassify

A → X Y with X.i = Y.s. This SDD is:

(A) S-attributed
(B) L-attributed
(C) not L-attributed
(D) always circular

Q3NAT1 markValue stack

How many rows (including accept) does the LR value-stack trace for 3 * 5 + 4 with the desk calculator have?

Numerical answer: ________

Q4MSQ1 markParsers

Which can evaluate an S-attributed SDD during parsing?

(A) LR parser
(B) LL parser
(C) recursive-descent parser
(D) none of these

Q5MCQ2 marksClassify

A → B C with C.i = A.s (A.s = C.s). This SDD is:

(A) L-attributed
(B) S-attributed
(C) not L-attributed
(D) both

Q6MCQ1 markRecursive descent

In recursive descent, an inherited attribute is implemented as:

(A) a global variable
(B) a parameter of the nonterminal’s procedure
(C) the procedure’s return value
(D) a token attribute

Q7MSQ2 marksFacts

Which are true?

(A) S-attributed ⊂ L-attributed
(B) Every L-attributed SDD is S-attributed
(C) An L-attributed SDD can be evaluated in one depth-first left-to-right walk
(D) An LR parser evaluates any L-attributed SDD without changes

Q8NAT2 marksValue stack

An LR parser evaluates the desk calculator on 2 + 3 * 4. How many reduce moves does it make?

Numerical answer: ________

Answer Vault

Try the questions first. Open when you are ready to check.

Q1 Answer: (B)1 mark

Inherited attributes from parent and left sibling only; not all synthesized.

(A) is wrong: X.i and Y.i are inherited.
(C) is wrong: All dependencies point left or down.
(D) is wrong: No cycle.