In a compiler implementing type checking, the rule 'Expr → Expr₁ + Expr₂' computes the type of the parent Expr from the types of its two children. This is an example of:
AAn inherited attribute, because type information flows from the expression node to its children
BA synthesized attribute, because the parent's value is computed from its children's values
CA synthesized attribute, because type checking always flows upward in the AST
DAn inherited attribute, because the grammar rule defines the parent's type
A synthesized attribute is computed from the attributes of children and flows upward to the parent. Here the parent Expr's type is computed from Expr₁.type and Expr₂.type — a classic synthesized attribute. Option A reverses the direction: inherited attributes flow downward from parent to children. Option C has the right answer but the wrong reasoning; synthesized attributes flow up, but not all upward-flowing information is about type checking specifically.
Question 2 Multiple Choice
A grammar rule declares 'int x, y, z;' where the type 'int' must be propagated to each variable in the declarator list. This type-propagation attribute is most naturally represented as:
AA synthesized attribute computed bottom-up from the variable names
BAn inherited attribute passed down from the type specifier to each variable
CA synthesized attribute, because the type is determined once and flows to later uses
DAn inherited attribute that flows from z back toward x through the sibling list
The type 'int' is known at the type-specifier node (a parent or left sibling) and needs to flow DOWN to each variable in the list — this is a classic inherited attribute. Synthesized attributes flow upward from children; inherited attributes flow downward from parents or from left siblings. Option D describes an impossible direction: inherited attributes can flow from parents or left siblings (in L-attributed grammars) but not from right siblings back to left ones.
Question 3 True / False
A grammar where nearly every attribute is synthesized (S-attributed) can be evaluated in a single top-down pass over the parse tree.
TTrue
FFalse
Answer: False
S-attributed grammars are evaluated in a single BOTTOM-UP pass, not top-down. Because synthesized attributes flow upward (children to parent), you must evaluate children before their parents. In a bottom-up traversal, you process leaves first and work toward the root — which is exactly the right order. A top-down (root-first) pass would try to compute parents before their children's values are known.
Question 4 True / False
In an L-attributed grammar, an attribute on a node can depend on the attributes of its right siblings.
TTrue
FFalse
Answer: False
L-attributed grammars allow inherited attributes to depend only on the PARENT's attributes and on LEFT siblings' attributes (already processed in a left-to-right traversal). Dependence on right siblings would require knowing those attributes before they've been processed, violating the left-to-right evaluation order. This restriction is precisely what allows L-attributed grammars to be evaluated in a single left-to-right pass — making them compatible with top-down parsing.
Question 5 Short Answer
What is the practical difference between a synthesized and an inherited attribute, and why does this distinction affect how you can evaluate a grammar in a single pass?
Think about your answer, then reveal below.
Model answer: A synthesized attribute is computed from a node's children and flows upward to the parent; it can be evaluated in a single bottom-up pass because children are always ready before their parents. An inherited attribute is computed from a node's parent or left siblings and flows downward; it requires that context above or to the left already be processed. When a grammar mixes both, the evaluation order must respect all dependencies — which may require multiple passes or a carefully constrained dependency structure (like L-attributed grammars) to ensure a single pass remains possible.
The distinction directly determines pass structure. Pure synthesized (S-attributed): one bottom-up pass. Mixed with inherited but L-attributed: one left-to-right pass. Arbitrary inherited attributes with cycles or right-sibling dependencies: multiple passes or might be unevaluable. Compiler designers care because one-pass evaluation is fast and simple; multi-pass evaluation adds complexity.