An attribute computed only from the attributes of a node’s children is:

Synthesised, and evaluable during LR parsing

Inherited, and needs a top-down pass

Synthesised, and evaluable during LR parsing

Synthesised, but needs a separate pass

Inherited, and evaluable during LR parsing

A function refers to a variable it does not declare. Static and dynamic scoping give the same answer when:

The enclosing definition and the most recent caller that defines it are the same

The program is compiled rather than interpreted

Which of the following are true of L-attributed definitions? (More than one may be correct.)

Every S-attributed definition is L-attributed

They can be evaluated in a single left-to-right traversal

Every S-attributed definition is L-attributed

They can be evaluated in a single left-to-right traversal

An inherited attribute may depend on a sibling to its right

Syntax-Directed Translation, Runtime Environments and Intermediate Code

Once a parse tree exists, the rest of the front end is bookkeeping attached to it. Syntax-directed translation hangs attributes on the grammar's symbols and rules for computing them on its productions, and the one distinction that decides most questions is the direction information flows. A synthesised attribute is computed from a node's children — the value of an expression, the type of a subtree — and can always be evaluated bottom-up in a single pass, which is exactly what an LR parser does as it reduces. An inherited attribute flows the other way, from a parent or a left sibling, and the standard example is a type declaration: in int a, b, c the type sits at the top and has to be pushed down to each name. The reason this matters is a clean rule: a grammar whose attributes are all synthesised is S-attributed and can be evaluated during LR parsing with no extra pass, while inherited attributes need the L-attributed discipline — each one depending only on the parent and on siblings to its left — to be evaluatable in one left-to-right sweep. Runtime environments then answer where a name lives while the program runs, and the examinable content is almost entirely about activation records and what makes recursion work: each call gets its own frame on the stack, so each recursive invocation has its own copy of the locals, and the frame is what a saved return address and the caller's frame pointer live in. Intermediate code is where the marks come back to counting. Three-address code gives each instruction at most one operator, so an expression becomes a sequence of assignments to temporaries, and the two things questions ask are how many instructions it takes and how many registers are needed to evaluate it — the second having an answer that surprises people, because a balanced expression tree needs more registers than a deep lopsided one.

Synthesised, Inherited, and Which Parser Can Cope

The two attribute directions, and what each costs
Aspect	Synthesised	Inherited
Computed from	The node’s children	The parent or a left sibling
Evaluation order	Bottom-up, one pass	Top-down or left-to-right
A typical example	The value or type of an expression	The declared type pushed onto each name
Grammar class	S-attributed	L-attributed, if each depends only on the left
Evaluable during LR parsing?	Yes — on each reduce	Not in general

🎯 Why S-attributed grammars are free and inherited ones are not

An LR parser reduces a production only once every symbol on its right-hand side has been parsed — which means every child is finished at exactly the moment the parent is created. So a synthesised attribute can be computed right there, in the reduce action, with no extra traversal: the values it needs are sitting on the parser stack. An inherited attribute needs information from above or from the left, which at reduce time may not exist yet, so in general it requires either a separate pass over the tree or a restriction. L-attributed is that restriction: each attribute may depend on the parent and on siblings strictly to its left, which is exactly the order a left-to-right traversal supplies, so an L-attributed grammar can be evaluated during top-down parsing in one sweep. The practical reading is that S-attributed ⊂ L-attributed, and a question asking which parser can evaluate a translation scheme is really asking which of these two classes it falls in.

Activation Records, and What Makes Recursion Work

Each call pushes an activation record — a frame — holding the parameters, the local variables, the saved return address and a link to the caller's frame. That is the entire mechanism behind recursion: a recursive call gets a new frame, so its locals are fresh and independent of the caller's, and returning pops the frame and restores the caller's view. Static allocation cannot do this, because a single fixed location per variable would be shared by every invocation, which is why languages without a stack discipline cannot support recursion.

⚠️ Static and dynamic scope differ only when a name is not local

Under static (lexical) scope, a free name resolves by looking outward through the enclosing text of the program, so the answer is fixed at compile time and can be read off the source. Under dynamic scope, it resolves by looking down the call stack to the most recent frame that defines it, so the answer depends on who called whom and can differ between two executions of the same function. Almost every real language is statically scoped. The examinable form is always the same: a small program where a function refers to a name it does not declare, called from two different places — and the two disciplines give different answers precisely because one reads the program and the other reads the stack. If the name is local, both agree, so the first thing to check is whether the name is actually free.

Three-Address Code, Counted

a = bc + bc − d, before and after eliminating the common subexpression
Naive	After CSE
`t1 = b * c`	`t1 = b * c`
`t2 = b * c`	`t2 = t1 + t1`
`t3 = t1 + t2`	`t3 = t2 - d`
`t4 = t3 - d`	`a = t3`
`a = t4`	—
5 instructions	4 instructions

🧠 A balanced expression tree needs MORE registers than a lopsided one

This is the counterintuitive result, and it comes straight from the Sethi–Ullman labelling: a leaf needs 1 register, and a node whose two subtrees need a and b registers needs max(a, b) if a ≠ b, and a + 1 if they are equal. So (a+b)*(c+d) — two subtrees each needing 2 — needs 3 registers, because after evaluating the left side into a register you must hold it while evaluating the right side, which itself needs two. But the left-deep chain ((a+b)+c)+d needs only 2, because at every step one operand is a leaf and can be loaded into the second register and consumed immediately, so nothing accumulates. Both figures were computed. The lesson is that register pressure is driven by how many partial results must be held simultaneously, which is a property of the tree's shape rather than its size — and it is why a compiler may deliberately reassociate an expression.

Key takeaways

A synthesised attribute comes from the children and can be evaluated on each LR reduce, no extra pass.
An inherited attribute comes from the parent or a left sibling — the declared-type-onto-each-name case.
S-attributed ⊂ L-attributed; L-attributed is evaluable in one left-to-right sweep.
Each call gets its own activation record, which is the entire mechanism behind recursion.
Static scope resolves a free name through the enclosing text; dynamic scope through the call stack.
Three-address code gives each instruction at most one operator, so an expression becomes a temp sequence.
a = bc + bc − d takes 5 instructions naively and 4 after common subexpression elimination.
Sethi–Ullman: (a+b)*(c+d) needs 3 registers while ((a+b)+c)+d needs 2 — shape, not size.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

How many three-address instructions are needed for a = bc + bc − d after common subexpression elimination?
Numerical answer — type the value.
Show answer
Answer: 4
t1 = b * c, t2 = t1 + t1, t3 = t2 - d, a = t3 — four. The naive translation takes five, because it computes b * c twice into separate temporaries. The saving is exactly one instruction, and noticing where it comes from matters: CSE does not remove the addition or the subtraction, only the recomputation of an operand that was already available. Answering 5 means the elimination was not applied; answering 3 usually means the final copy into a was dropped, which three-address code does need unless the last operation can target a directly.
What is the minimum number of registers needed to evaluate (a+b)*(c+d) with no spilling to memory?
Numerical answer — type the value.
Show answer
Answer: 3
Three. By the Sethi–Ullman rule, a leaf costs 1 and a node whose subtrees cost a and b costs max(a, b) when they differ and a + 1 when they are equal. Here both subtrees cost 2 and are equal, so the answer is 3: evaluate a+b into one register, hold it, and the right subtree needs two more of its own. The instructive comparison is the left-deep chain ((a+b)+c)+d, which needs only 2 — at every step one operand is a leaf, loaded and consumed immediately, so nothing accumulates. A balanced tree therefore costs more registers than a lopsided one of the same size, which is the opposite of most people's expectation and is why register pressure is a property of the tree's shape.
An attribute computed only from the attributes of a node’s children is:
1. Inherited, and needs a top-down pass
2. Synthesised, and evaluable during LR parsing
3. Synthesised, but needs a separate pass
4. Inherited, and evaluable during LR parsing
Show answer
Answer: B — Synthesised, and evaluable during LR parsing
Synthesised, and evaluable during LR parsing. An LR parser reduces a production only after every symbol on its right-hand side is complete, so at the instant the parent node is created all its children are finished and their attribute values are on the stack — the computation happens in the reduce action, with no extra traversal (which rules out option C). Option D has it backwards: inherited attributes need information from the parent or from the left, which at reduce time may not exist yet. A grammar with only synthesised attributes is called S-attributed, and being S-attributed is exactly the condition for one-pass evaluation during bottom-up parsing.
Recursion requires activation records to be allocated:
1. Statically, one per function
2. On a stack, one per call
3. On the heap, one per program
4. In registers only
Show answer
Answer: B — On a stack, one per call
On a stack, one per call. A recursive function is active several times at once, and each activation needs its own parameters and locals — so the storage must be per call, not per function. Static allocation gives one fixed location per variable, shared by every invocation, so the inner call would overwrite the outer call's locals: that is precisely why languages with purely static allocation cannot support recursion, which is the historical point behind this question. The frame also carries the saved return address and a link to the caller's frame, which is what lets the return restore the caller's view exactly.
A function refers to a variable it does not declare. Static and dynamic scoping give the same answer when:
1. The program has no recursion
2. The enclosing definition and the most recent caller that defines it are the same
3. The program is compiled rather than interpreted
4. Never
Show answer
Answer: B — The enclosing definition and the most recent caller that defines it are the same
Static scope looks outward through the enclosing text; dynamic scope looks down the call stack for the most recent frame that defines the name. When those two happen to identify the same declaration, the disciplines agree — which is why the difference only becomes visible in a program deliberately constructed so that the caller is not the enclosing scope. Option D is wrong and worth rejecting on sight: for a name declared in the immediately enclosing function that is also the caller, the two coincide trivially. Option C confuses the resolution rule with the implementation strategy; static scoping is a language property and holds whether or not a compiler is involved.
Which of the following are true of L-attributed definitions? (More than one may be correct.)
1. Every S-attributed definition is L-attributed
2. They can be evaluated in a single left-to-right traversal
3. An inherited attribute may depend on a sibling to its right
4. They suit top-down parsing
Show answer
Answer: A — Every S-attributed definition is L-attributed; B — They can be evaluated in a single left-to-right traversal; D — They suit top-down parsing
A, B and D. S-attributed means every attribute is synthesised, which satisfies the L-attributed condition vacuously — hence the containment in A, and it is why S-attributed ⊂ L-attributed. The defining restriction is that each inherited attribute depends only on the parent and on siblings strictly to its left, which is exactly the order a single left-to-right sweep makes available (B) and exactly what a predictive top-down parser produces as it descends (D). C is false and is the restriction itself: a dependence on a right sibling cannot be satisfied in one left-to-right pass, because that sibling has not been visited yet — allowing it is what would force a second traversal.
In int a, b, c; the declared type reaching each of a, b and c is an example of:
1. A synthesised attribute
2. An inherited attribute
3. A terminal attribute
4. A semantic error
Show answer
Answer: B — An inherited attribute
Inherited. The type int is recognised near the top of the declaration and must be handed down to each name in the list — information flowing from a parent, or from a left sibling, rather than up from children. That is the definition of an inherited attribute, and it is the textbook example precisely because a synthesised attribute could not do it: the names have no way to compute the type from their own subtrees. It is also why declaration grammars are the standard motivation for L-attributed definitions — the type reaches each name from its left, so one left-to-right sweep suffices.
A three-address instruction contains at most:
1. Three operators
2. One operator
3. Three temporaries
4. Two instructions
Show answer
Answer: B — One operator
One operator. The name counts addresses — typically one destination and two operands, hence "three-address" — not operators, and the single-operator restriction is what makes the form useful: every instruction maps closely onto one machine operation, and an expression tree of any depth becomes a flat sequence of assignments to temporaries. Option A is the natural misreading of the name and is worth correcting deliberately. That flatness is exactly what the optimisations in the next chapter work on: a linear sequence is what lets you ask which values are available, which are live, and which computations repeat.