3.1 Syntax-directed definitions: attributes, semantic rules, synthesized vs inherited, annotated parse trees, dependency graphs and evaluation order

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

YACC resolves an unmarked shift/reduce conflict by doing what? from Lesson 2.4.7
How is the lookahead of a new LR(1) item computed? from Lesson 2.4.4
Give the postorder of a tree with root + whose children are 3 and *, where * has children 5 and 4. from Lesson 0.2.4

1 · The Story

📖

Notes on the chart

Kabir hands Anaya at the Meaning Desk his family chart for each sentence. Anaya sticks a small note on every box.

Some notes are filled from below. In a budget speech the box for “3 times 5 plus 4” gets the note “19”, computed from the notes of its parts “15” and “4”, which were computed from their parts. Like a family’s total spending, added up from each member’s spending.

Other notes come from above or from the left. In “these figures are in lakh: 3, 5, 4”, the unit is written on the parent box and handed down to every number, the way a manager stamps “confidential” on a folder and every page inside inherits it.

Anaya cannot write a note until the notes it needs are written. She draws arrows from each note to the notes that use it, and fills them in an order that respects every arrow.

2 · Predict First

🤔

In the chart for “float a, b, c”, the word float is on the far left and the names come after it. Can each name’s type be computed only from the name’s own children? Write your guess down. The answer is in the vault.

3 · Core Concept

Attributes and semantic rules

A syntax-directed definition (SDD) is a context-free grammar plus

attributes attached to grammar symbols (val, type, code, …), and
semantic rules attached to productions that say how to compute attribute values, e.g. for E → E₁ + T the rule E.val = E₁.val + T.val. (Subscripts only tell occurrences of the same nonterminal apart.)

Terminals get their attributes from the lexer (for example n.lexval = 3).

Synthesized vs inherited

A synthesized attribute of A at a parse-tree node is computed by a rule of the production at that node, A → α, from attributes of A’s children (and A itself). Information flows up.
An inherited attribute of B at a node is computed by a rule of the production at B’s parent, from attributes of the parent and B’s siblings. Information flows down or sideways.

Terminals have synthesized attributes only (supplied by the lexer).

Annotated parse tree

A parse tree showing the value of every attribute at every node is an annotated parse tree (also called decorated).

Dependency graph and evaluation order

The dependency graph has one node per attribute instance in the parse tree and an edge b → a whenever the rule computing a uses b. Any evaluation order must respect the edges: a topological order of the graph (every edge points forward). If the graph has a cycle, no order exists: the SDD is circular. For the classes of SDDs in the next lesson, cycles are impossible and a simple tree walk finds an order.

The two classic SDDs

Desk calculator (synthesized only)        Declarations (inherited)
L → E n        L.val = E.val              D → T L        L.inh = T.type
E → E₁ + T     E.val = E₁.val + T.val     T → int        T.type = integer
E → T          E.val = T.val              T → float      T.type = float
T → T₁ * F     T.val = T₁.val * F.val     L → L₁ , id    L₁.inh = L.inh
T → F          T.val = F.val                             addType(id.entry, L.inh)
F → ( E )      F.val = E.val              L → id         addType(id.entry, L.inh)
F → n          F.val = n.lexval

Story → compiler term

In the story	In the compiler
a sticky note on a box	an attribute of a node
the rule for writing a note	a semantic rule
a note filled from the parts below	synthesized attribute
“lakh” or “confidential” handed down	inherited attribute
the chart with all notes filled	annotated parse tree
arrows from a note to notes that use it	dependency graph
an order that respects every arrow	topological order

4 · Visual

Diagram: n · lexval=3 · F · val=3 · T · val=3 · * · n · lexval=5 · F · val=5 · T · val=15 · E · val=15 · + · n · lexval=4 · F · val=4 · T · val=4 · E · val=19 · L · val=19

Annotated parse tree of 3 * 5 + 4 (desk calculator, values computed by evaluating the SDD on the real parse tree). Every val is synthesized: it only uses the children.

Diagram: float · T · type=float · id · entry=a · L · inh=float · , · id · entry=b · L · inh=float · , · id · entry=c · L · inh=float · D

Annotated parse tree of float a, b, c: T.type is synthesized; L.inh is inherited, handed down the L-chain; every id gets addType(entry, float).

Diagram: 1 · T.type · 2 · L.inh (top L) · 3 · L.inh (lower L) · 4 · id₁.entry · 5 · id₂.entry · 6 · addType(a) · 7 · addType(b)

Dependency graph for “float a, b”. An edge X → Y means Y’s rule uses X. One valid evaluation order (topological order, computed): T.type, id₁.entry, id₂.entry, L.inh (top), L.inh (lower), addType(b), addType(a).

5 · Worked Examples

Example 1 Easy

Draw the annotated parse tree of 3 * 5 + 4 for the desk calculator.

Solution

See the first figure. Bottom-up: F.val = 3, T.val = 3; F.val = 5; T.val = 3 × 5 = 15; E.val = 15; F.val = T.val = 4; E.val = 15 + 4 = 19. Like Anaya totalling a family’s spending from each member up.

Example 2 Medium

For float a, b, c, which attributes are inherited, and in which order are the addType calls made?

Solution

T.type is synthesized (from the keyword). L.inh at every L node is inherited: it comes from T.type (at D) or from the parent L. The calls, in evaluation order: addType(a, float), addType(b, float), addType(c, float). The unit stamped at the top reaches every name, as with Anaya’s “lakh”.

Example 3 GATE

An SDD has E → E₁ # T {E.val = E₁.val × T.val}, E → T {E.val = T.val}, T → T₁ & F {T.val = T₁.val + F.val}, T → F {T.val = F.val}, F → n {F.val = n.lexval}. Evaluate 2 # 3 & 5 # 6 & 4.

Solution

First read the structure from the grammar, not from the symbols: & is at the deeper level T (binds tighter), # at E, both left associative. So the tree groups (2 # (3 & 5)) # (6 & 4). Then apply the rules: # multiplies, & adds: (2 × (3 + 5)) × (6 + 4) = 16 × 10 = 160. Computed on the real parse tree.

6 · Shortcuts

⚡

Structure first, meaning second: decide grouping from the grammar levels and associativity, then apply each rule’s arithmetic, which may be anything (# could mean ×). Valid when: every “evaluate this expression with this SDD” question.

⚡

Synthesized or inherited? Look at the production where the rule is written: computing the left side → synthesized; computing a symbol on the right side → inherited. Valid when: classifying attributes in a given SDD.

7 · GATE Traps

⚠️

Unusual operator meanings (# = ×, & = +) never change the parse tree; only the grammar does.
Terminals have only synthesized attributes.
A rule for X.i written at production A → … X … makes X.i inherited, even if it uses only A’s inherited attributes.
A dependency graph with a cycle has no evaluation order.
Dependency edges point from the used attribute to the computed one.

8 · Memory Hook

🧠

Synthesized climbs up, inherited comes down (or from the left). Evaluate in an order that follows every arrow.

9 · Connect the Dots

Some SDDs can be evaluated during parsing, in a single walk. Which ones, and by which parser? The next lesson defines two classes of definitions and matches them with bottom-up and top-down parsers.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markSynthesized

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

(A) inherited
(B) synthesized
(C) circular
(D) a lexval

Q2NAT2 marksEvaluation

An SDD has E → E₁ * T {E.val = E₁.val + T.val}, E → T {E.val = T.val}, T → T₁ + F {T.val = T₁.val × F.val}, T → F {T.val = F.val}, F → n {F.val = n.lexval}. Evaluate 2 * 3 + 4 * 5.

Numerical answer: ________

Q3MSQ1 markInherited

In D → T L {L.inh = T.type}, L → L₁ , id {L₁.inh = L.inh; addType(id.entry, L.inh)}, T → int {T.type = integer}, which attributes are inherited?

(A) L.inh
(B) L₁.inh
(C) T.type
(D) id.entry

Q4MCQ1 markDependency graph

If the dependency graph of an annotated parse tree has a cycle, then:

(A) any order works
(B) no evaluation order exists
(C) the attributes are all synthesized
(D) the grammar is ambiguous

Q5NAT1 markEvaluation

An SDD has N → N₁ d {N.val = N₁.val × 10 + d.lexval}, N → d {N.val = d.lexval}. What is N.val at the root for the digits 4 2 7?

Numerical answer: ________

11 · Rule Card

SDD = grammar + attributes + semantic rules per production.
Synthesized: computed at the node’s own production from children; flows up.
Inherited: computed at the parent’s production from parent/siblings; flows down or sideways.
Terminals: synthesized only (lexval).
Annotated parse tree shows all attribute values.
Dependency graph: edge b → a if a uses b; evaluate in topological order; cycle ⇒ no order.

12 · Concept Ledger

syntax-directed definition (SDD)attributesemantic rulesynthesized attributeinherited attributelexvalannotated parse treedependency graphtopological ordercircular SDD

13 · Answer Vault

Answer Vault

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

Warm-up

Shifting.
From FIRST(βa) for the item [A → α•Bβ, a].
3 5 4 * +: children first, then the node.

Predict First

No. A name has no child that knows the type. The type must be handed down from the declaration node and across from the type keyword: an inherited attribute.