Lesson 5.5 — Attribute grammars: S- and L-attributed definitions, circularity, ordered and reference attribute grammars¶

Techniques: attribute grammars with synthesized and inherited attributes, dependency graphs and evaluation orders, S- and L-attributed definitions and their one-pass evaluation (Knuth 1968, 1971; Lewis, Rosenkrantz & Stearns 1974; Dragon book Ch. 5), the circularity test (Knuth 1968/1971) and its intrinsic exponential complexity (Jazayeri, Ogden & Rounds 1975), ordered attribute grammars with visit sequences (Kastens 1980), reference attribute grammars with demand-driven and circular evaluation (Hedin 2000; Magnusson & Hedin 2007; JastAdd, Ekman & Hedin 2007) · Pebble implements: the reference resolveNames is an L-attributed evaluation in disguise (the scope table is an inherited attribute threaded left to right, the binding of each use a synthesized one); drill attr-eval-order · Prerequisites: Ch 2 (grammars, parse trees), Ch 3 (LR parsing, for S-attributed evaluation), Lesson 5.2 · Time: 4 hours

Everything in Lessons 5.1–5.4 was an algorithm: walk the tree, keep a table, answer lookups. Knuth proposed a different way to specify such analyses: attach attributes to the grammar's symbols and give, for each production, equations that define them in terms of each other — the type of a declaration flows down to the names it declares, the value of an expression flows up from its operands. An attribute grammar (AG) is such a set of equations; an evaluator solves them on each tree. This lesson is the theory behind every "syntax-directed" semantic analysis: when the equations have a solution, how to order their evaluation, which grammars can be evaluated in one pass (the ones a recursive-descent or LR parser can evaluate as it parses), how to detect grammars that are circular, and how modern systems (JastAdd) extend the formalism with references so that name resolution itself becomes an attribute.

1. Problem and motivation¶

The problem. Given a context-free grammar extended with attributes and semantic rules, and a parse tree, compute every attribute instance of the tree so that every rule holds — or decide ahead of time, for all trees, that this is possible and in what order. In a compiler, the attributes are types, symbol tables, bindings, constant values, generated code; the grammar author writes local equations and the system derives the traversal.

S- and L-attributed evaluation¶

Knuth's paper [Knu68] introduced synthesized attributes (computed from the children, flowing up) and inherited attributes (computed from the parent and siblings, flowing down), proved that both are needed for natural specifications, and defined the dependency graph whose topological orders are the valid evaluation orders. Two restricted classes matter because a parser can evaluate them while it parses: S-attributed grammars (synthesized attributes only; an LR parser evaluates them on its stack at each reduction, as yacc's $$ does), and L-attributed grammars (each inherited attribute depends only on the parent's inherited attributes and on left siblings), which one left-to-right depth-first traversal — for example a recursive-descent parser — evaluates [LRS74; ALSU07, §5.2.4–5.5]. Pebble's name resolution has exactly this shape: the environment is inherited from left to right, each statement's declarations extend it for the next.

Circularity and ordered attribute grammars¶

An AG is circular if some tree has a cycle in its dependency graph: then the equations may have no solution or many. Knuth gave a test for circularity in the original paper and corrected it in 1971 [Knu71c]; Jazayeri, Ogden and Rounds proved that any such test needs exponential time in the worst case — the problem is EXPTIME-complete [JOR75]. Kastens' ordered attribute grammars (OAGs) [Kas80] are a large subclass decided in polynomial time, for which a fixed visit sequence per production evaluates every tree without dynamic scheduling; generators such as LIGA (Eli) and the LRC system used them.

Reference attribute grammars¶

Classic AGs can only pass information along the tree, so name resolution needs an explicit environment attribute copied through every node. Hedin's reference attribute grammars (RAGs) [Hed00] let an attribute's value be a reference to another node, and let rules read attributes of the node referred to: Use.decl() returns the declaration node, and Use.type() can be defined as decl().type(). Evaluation is demand-driven with caching, and circular attributes evaluated to a fixed point [MH07] handle recursive definitions such as nullability or reachability. JastAdd [EH07] generates Java from RAG specifications and is the implementation language of the ExtendJ Java compiler.

2. Definitions and algorithms¶

Definition 5.5.1 (Attribute grammar)

An attribute grammar is a context-free grammar $G = (N, T, P, S)$ together with, for each nonterminal $X$, disjoint finite sets $\mathrm{Syn}(X)$ of synthesized and $\mathrm{Inh}(X)$ of inherited attributes ($\mathrm{Inh}(S) = \emptyset$), and, for each production $p : X_0 \to X_1 \cdots X_n$, one semantic rule $X_k.a = f(\dots)$ for each defining occurrence — each $a \in \mathrm{Syn}(X_0)$ with $k = 0$ and each $a \in \mathrm{Inh}(X_k)$ with $k \ge 1$ — whose arguments are attribute occurrences $X_j.b$ of the same production. (Terminals carry fixed values from the lexer and are omitted from the definitions below.)

Definition 5.5.2 (Attribute instances and the dependency graph of a tree)

For a parse tree $t$, every node $\nu$ labeled $X$ has one attribute instance $\nu.a$ for each $a \in \mathrm{Syn}(X) \cup \mathrm{Inh}(X)$. At a node $\nu$ where production $p$ is applied, the rules of $p$, with $X_0$ read as $\nu$ and $X_k$ as its $k$-th child, define equations between instances. The dependency graph $D(t)$ has the instances as vertices and an edge $\mu.b \to \nu.a$ whenever the equation defining $\nu.a$ has $\mu.b$ as an argument. Every instance is defined by exactly one equation (by the production at its own node for synthesized attributes, at its parent for inherited ones).

Definition 5.5.3 (Non-circular attribute grammar)

An attribute grammar is circular if $D(t)$ has a cycle for some parse tree $t$, and non-circular otherwise.

Definition 5.5.4 (S-attributed and L-attributed)

An AG is S-attributed if every nonterminal has only synthesized attributes. It is L-attributed if, in every production $X_0 \to X_1 \cdots X_n$, every rule defining an inherited attribute $X_k.a$ ($k \ge 1$) has as arguments only inherited attributes of $X_0$ and attributes (inherited or synthesized) of $X_1, \dots, X_{k-1}$. (Rules for $\mathrm{Syn}(X_0)$ are unrestricted, except that they may not use $\mathrm{Syn}(X_0)$ itself.) Every S-attributed grammar is L-attributed.

The running AG: declarations with an inherited type

After the Dragon book's declaration grammar [ALSU07, §5.2, Fig. 5.8], with a synthesized count added. Attributes: $D$: syn $n$; $T$: syn $\mathit{type}$; $L$: inh $\mathit{inh}$, syn $n$.

production	rules
$p_1: D \to T\ L$	$L[2].\mathit{inh} = T[1].\mathit{type}$; $D[0].n = L[2].n$
$p_2: T \to \texttt{int}$	$T[0].\mathit{type} = \mathsf{int}$
$p_3: L \to L\ \texttt{,}\ \texttt{id}$	$L[1].\mathit{inh} = L[0].\mathit{inh}$; $L[0].n = L[1].n + 1$ (and record $\texttt{id} : L[0].\mathit{inh}$)
$p_4: L \to \texttt{id}$	$L[0].n = 1$ (and record $\texttt{id} : L[0].\mathit{inh}$)

It is L-attributed: the only inherited rules are $L[2].\mathit{inh}$ (uses $T[1]$, a left sibling) and $L[1].\mathit{inh}$ (uses $L[0].\mathit{inh}$, the parent's inherited attribute).

Algorithm 5.5.5 (Evaluation in a topological order of the dependency graph)

Input: an AG, a parse tree $t$.
Output: a value for every instance of $t$, or "circular".
Precondition: the semantic functions terminate.
Postcondition: if $D(t)$ is acyclic, every equation holds.
Invariant: every instance removed from the ready queue has all its arguments already evaluated.

function EvaluateTree(t):
    build D(t);  indeg[v] ← number of arguments of v's equation, for every instance v
    ready ← { v | indeg[v] = 0 }                # constants and lexer-provided values
    while ready is not empty:
        v ← remove some element of ready
        evaluate v's equation                    # all arguments are available
        for each edge v → w in D(t):
            indeg[w] ← indeg[w] − 1
            if indeg[w] = 0: add w to ready
    if some instance was never evaluated: return circular

Algorithm 5.5.6 (One-pass evaluation of an L-attributed grammar)

Input: an L-attributed AG, a parse tree $t$ (or a parser producing it top-down, left to right).
Output: every instance of $t$.
Precondition: the AG is L-attributed (Definition 5.5.4).
Postcondition: every equation holds.
Invariant: when Visit(ν) starts, all inherited instances of $\nu$ are evaluated; when it returns, all instances in $\nu$'s subtree and all synthesized instances of $\nu$ are evaluated.

function Visit(ν):                           # ν's inherited attributes are already known
    for each child μ of ν, left to right:
        evaluate every inherited attribute of μ   # uses ν.inh and left siblings only
        Visit(μ)
    evaluate every synthesized attribute of ν

evaluate Inh(root) (there are none);  Visit(root)

Definition 5.5.7 (IO graphs and Knuth's circularity test)

For a nonterminal $X$, an IO graph of $X$ is a set of pairs $(i, s)$ with $i \in \mathrm{Inh}(X)$, $s \in \mathrm{Syn}(X)$, read "$s$ depends (transitively) on $i$". The IO graph of a tree rooted at $X$ is the set of pairs connected by a path in its dependency graph. For a production $p : X_0 \to X_1 \cdots X_n$ and IO graphs $g_1, \dots, g_n$ of $X_1, \dots, X_n$, the graph $D_p[g_1, \dots, g_n]$ is $p$'s local dependencies plus, for each $k$, the edges $X_k.i \to X_k.s$ for $(i, s) \in g_k$.

Algorithm 5.5.8 (Knuth's circularity test, as corrected in 1971)

Input: an attribute grammar.
Output: "circular" or "non-circular".
Precondition: every nonterminal derives at least one terminal string (useless nonterminals removed).
Postcondition: "circular" iff some tree's dependency graph has a cycle (Theorem 5.5.15).
Invariant: every graph in $\mathrm{IO}(X)$ is the IO graph of some tree rooted at $X$.

for each nonterminal X: IO(X) ← ∅
repeat
    changed ← false
    for each production p : X0 → X1 … Xn:
        for each choice (g1, …, gn) with gk ∈ IO(Xk) for every nonterminal Xk:
            H ← Dp[g1, …, gn]
            if H has a cycle: return circular
            g ← { (i, s) | i ∈ Inh(X0), s ∈ Syn(X0), H has a path X0.i ⇝ X0.s }
            if g ∉ IO(X0): IO(X0) ← IO(X0) ∪ {g};  changed ← true
until not changed
return non-circular

Definition 5.5.9 (Ordered attribute grammar, after Kastens 1980)

Let $\mathrm{IDS}(X)$ be the smallest relation on the attributes of each $X$, and $\mathrm{IDP}(p)$ the smallest graph on the occurrences of each production $p$, such that $\mathrm{IDP}(p)$ contains $p$'s local dependencies and, for every occurrence $X_k$ in $p$, the edges of $\mathrm{IDS}(X_k)$; and $\mathrm{IDS}(X)$ contains every edge between two attributes of $X$ that is a path in $\mathrm{IDP}(p)$ for some $p$ with an occurrence of $X$. Partition each $\mathrm{Syn}(X) \cup \mathrm{Inh}(X)$ into sets $A_{X,1}, \dots, A_{X,m_X}$, alternately inherited and synthesized, by repeatedly removing, from the end of the order, the synthesized attributes whose $\mathrm{IDS}$-successors have all been removed, then the inherited ones, and so on. The AG is ordered if, for every production, $\mathrm{IDP}(p)$ plus the edges "every attribute of $A_{X,j}$ before every attribute of $A_{X,j+1}$" for each occurrence is acyclic. Visit $v$ of a node labeled $X$ then computes $A_{X,2v-1}$ (inherited, by the parent) and $A_{X,2v}$ (synthesized, by the node), in a fixed visit sequence per production.

Definition 5.5.10 (Reference attribute grammar)

A reference attribute is an attribute whose value is a node of the tree. In a reference attribute grammar, a rule may read attributes of any node obtained through a reference attribute (not only of the production's own occurrences), and attributes may take parameters (lookup(name)). A circular attribute is declared with a bottom value in a lattice of finite height and is defined as the least fixed point of its equations.

Algorithm 5.5.11 (Demand-driven evaluation with caching and cycle detection, as in JastAdd)

Input: a tree; a request for attribute instance $\nu.a(\text{args})$.
Output: its value, or an error "circular definition" for a non-circular-declared attribute on a cycle.
Precondition: every equation terminates when its arguments are available.
Postcondition: the returned value satisfies the equation; each instance is computed once.
Invariant: inProgress holds exactly the instances on the current chain of pending requests; cache holds only final values.

function Get(ν.a):                              # ordinary attribute
    if ν.a ∈ cache: return cache[ν.a]
    if ν.a ∈ inProgress: error "circular definition"
    inProgress ← inProgress ∪ {ν.a}
    v ← evaluate the equation of ν.a, calling Get on each argument it reads
    inProgress ← inProgress − {ν.a};  cache[ν.a] ← v;  return v

function GetCircular(ν.a):                      # declared circular, bottom ⊥
    if ν.a ∈ cache: return cache[ν.a]
    if ν.a ∈ inProgress: return current[ν.a]     # read the current approximation
    inProgress ← inProgress ∪ {ν.a};  current[ν.a] ← ⊥
    repeat
        old ← current[ν.a]
        current[ν.a] ← evaluate the equation (reads may re-enter and see approximations)
    until current[ν.a] = old
    inProgress ← inProgress − {ν.a};  cache[ν.a] ← current[ν.a];  return current[ν.a]

3. Worked example¶

S- and L-attributed evaluation¶

The tree of int a, b, c for the running AG (terminals omitted; nodes in preorder, as the drill attr-eval-order numbers them):

flowchart TD
  D1(["D1 (p1)"]) --> T2["T2 (p2)"]
  D1 --> L3["L3 (p3)"]
  L3 --> L4["L4 (p3)"]
  L4 --> L5["L5 (p4)"]

Dependencies $D(t)$ (instance ← the instances it reads): D1.n ← L3.n; T2.type ← —; L3.inh ← T2.type; L3.n ← L4.n; L4.inh ← L3.inh; L4.n ← L5.n; L5.inh ← L4.inh; L5.n ← —.

Algorithm 5.5.5 (Kahn's algorithm, smallest ready instance first; generated by the drill's oracle):

step	evaluate	ready afterwards
1	T2.type	L3.inh, L5.n
2	L3.inh	L4.inh, L5.n
3	L4.inh	L5.inh, L5.n
4	L5.inh	L5.n
5	L5.n	L4.n
6	L4.n	L3.n
7	L3.n	D1.n
8	D1.n	—

Algorithm 5.5.6 (one pass): Visit(D1) → child T2: no inherited attributes, Visit(T2) computes T2.type → child L3: compute L3.inh = T2.type, Visit(L3) → L4.inh, Visit(L4) → L5.inh, Visit(L5) computes L5.n = 1 → back in L4: L4.n = 2 → L3.n = 3 → D1.n = 3. The order is T2.type, L3.inh, L4.inh, L5.inh, L5.n, L4.n, L3.n, D1.n — the same as the table here; in general the two algorithms produce different valid orders.

If the language instead wrote the type after the names, as Pascal does (a, b, c : int), the production would be $p_1' : D \to L\ T$ with $L[1].\mathit{inh} = T[2].\mathit{type}$: an inherited attribute that uses a right sibling. The grammar is still non-circular (Algorithm 5.5.5 evaluates T3.type first), but it is not L-attributed, and Algorithm 5.5.6 would evaluate L2.inh before visiting T3 — reading a value that does not exist yet. Pascal compilers therefore collect the names first and assign the type when they reach it: a second pass over the list.

Circularity and ordered attribute grammars¶

A grammar whose circularity depends on the tree:

production	rules
$q_1: S \to A$	$A[1].i = A[1].s$; $S[0].v = A[1].s$
$q_2: A \to B$	$B[1].i = A[0].i$; $A[0].s = B[1].s$
$q_3: B \to \texttt{x}$	$B[0].s = B[0].i$
$q_4: B \to \texttt{y}$	$B[0].s = 0$

Algorithm 5.5.8, one row per production and choice of child graphs:

round	production, children's graphs	$D_p[\dots]$ has a cycle?	graph added to $\mathrm{IO}(X_0)$
1	$q_3$ (no nonterminal children)	no	$\mathrm{IO}(B) \ni \{(i, s)\}$
1	$q_4$	no	$\mathrm{IO}(B) \ni \{\}$
1	$q_2$ with $g_B = \{(i,s)\}$: path $A.i \to B.i \to B.s \to A.s$	no	$\mathrm{IO}(A) \ni \{(i, s)\}$
1	$q_2$ with $g_B = \{\}$	no	$\mathrm{IO}(A) \ni \{\}$
1	$q_1$ with $g_A = \{(i,s)\}$: $A.s \to A.i$ (the rule) and $A.i \to A.s$ (the graph)	yes	stop: circular

The witness is the tree $S(A(B(\texttt{x})))$; the tree $S(A(B(\texttt{y})))$ is fine. A test that kept only the union of the graphs per nonterminal would also report a cycle here — correctly — but on other grammars the union merges dependencies of different trees and reports cycles no tree has; that is why the corrected test keeps sets of graphs [Knu71c], and why it can take exponential time.

For Kastens' construction on the running (declaration) AG: $\mathrm{IDS}(L) = \emptyset$ ($n$ never depends on $\mathit{inh}$), so the backward partition puts $n$ (synthesized) last and $\mathit{inh}$ before it: $A_{L,1} = \{\mathit{inh}\}$, $A_{L,2} = \{n\}$; $T$ has $A_{T,1} = \emptyset$ (no inherited attributes), $A_{T,2} = \{\mathit{type}\}$. Adding "$A_{X,1}$ before $A_{X,2}$" to each production graph creates no cycle, so the grammar is ordered, and every node needs a single visit: the visit sequence of $p_1$ is "visit T, compute L.inh, visit L, compute D.n".

Reference attribute grammars¶

The JastAdd specification of the §7 box resolves use x by an inherited, parameterized attribute lookup(name) whose value is a reference to a Decl node. For the tree { var x /*d1*/; use x; { use x; var x /*d2*/; use x; } use y; }, demand-driven evaluation (Algorithm 5.5.11) of the inner block's second use x:

step	request	equation used	result
1	`Use.decl()` of the inner second `use x`	`lookup("x")`	pending
2	`lookup("x")` at child 2 of the inner block	scan children 1, 0 of the inner block	child 1 is `Decl x (d2)`: d2
3	cache `decl()` = d2		d2

and of the inner block's first use x: the scan of its earlier siblings finds nothing, so the equation asks the inner block's own lookup("x"), which the outer block defines by scanning its earlier children: Decl x (d1). The cache makes each (node, attribute, argument) instance cost one evaluation.

Try it

./course drill attr-eval-order --seed 3 --difficulty medium --solution (an L-attributed grammar: Kahn's order and the one-pass order); --difficulty hard generates grammars that may be neither, and trees that may be circular.

4. Invariants and correctness¶

S- and L-attributed evaluation¶

Theorem 5.5.12 (Well-definedness for acyclic dependency graphs)

If $D(t)$ is acyclic, the equations of $t$ have exactly one solution, and Algorithm 5.5.5 computes it. If $D(t)$ has a cycle, Algorithm 5.5.5 reports "circular".

Proof

Existence and uniqueness, by induction along a topological order $v_1, \dots, v_N$ of $D(t)$ (one exists because the graph is finite and acyclic): the equation of $v_j$ has arguments among $v_1, \dots, v_{j-1}$ only, so given their (unique, by the hypothesis) values it determines the value of $v_j$ uniquely; every instance has exactly one equation (Definition 5.5.2). Algorithm: by the invariant, an instance is evaluated only when all its arguments are, so every computed value satisfies its equation; Kahn's algorithm removes every vertex of an acyclic graph (a vertex that never becomes ready would have an unevaluated predecessor, and following unevaluated predecessors backwards in a finite graph would produce a cycle). Cycle: the vertices of a cycle can never reach in-degree 0 (each keeps its in-edge from the previous one), so they are never evaluated and the algorithm reports "circular".

Theorem 5.5.13 (L-attributed grammars are evaluable in one left-to-right pass)

For an L-attributed AG and any tree $t$, Algorithm 5.5.6 evaluates every instance after all of its arguments. In particular every L-attributed AG is non-circular.

Proof

By induction on the height of the subtree, prove the invariant of the algorithm box. Consider Visit(ν) for a node $\nu$ with production $X_0 \to X_1 \cdots X_n$, where $\nu$'s inherited instances are evaluated. Children, in order: when the loop reaches child $\mu_k$, it evaluates each inherited instance of $\mu_k$; by Definition 5.5.4 its arguments are inherited instances of $\nu$ (evaluated before the call) or instances of $\mu_1, \dots, \mu_{k-1}$ (all evaluated: by the induction hypothesis, Visit(μ_j) returned with $\mu_j$'s subtree and synthesized instances done, and $\mu_j$'s inherited instances were evaluated before it). Then Visit(μ_k) is called with its precondition met, and by the induction hypothesis (smaller subtree) it evaluates the whole subtree. Synthesized instances of $\nu$: evaluated last; their arguments are instances of $\nu$'s children (all done), inherited instances of $\nu$ (done), or other synthesized instances of $\nu$ — excluded by Definition 5.5.4. Leaves: a node with no nonterminal children has only its synthesized equations, whose arguments are its inherited attributes. So every instance is evaluated after its arguments, which means the order is a topological order of $D(t)$, and $D(t)$ is acyclic.

Corollary 5.5.14 (S-attributed grammars are evaluated bottom-up)

For an S-attributed AG, evaluating each node's synthesized attributes when its subtree is complete — the order in which an LR parser performs reductions — evaluates every instance after its arguments.

Proof

An S-attributed grammar is L-attributed with no inherited attributes, so Algorithm 5.5.6 reduces to "visit the children left to right, then evaluate the node's synthesized attributes": a postorder. An LR parser's reductions happen in exactly this postorder (a production is reduced after all its children, left to right). Theorem 5.5.13 applies.

Circularity and ordered attribute grammars¶

Theorem 5.5.15 (Knuth's test decides circularity)

Algorithm 5.5.8 terminates, and answers "circular" if and only if the AG is circular.

Proof sketch (full proof: [Knu71c])

Termination: $\mathrm{IO}(X)$ is a set of subsets of the finite set $\mathrm{Inh}(X) \times \mathrm{Syn}(X)$ and only grows. Invariant (soundness of the graphs): by induction on the rounds, each graph added to $\mathrm{IO}(X_0)$ comes from a production and child graphs that are IO graphs of real subtrees, so it is the IO graph of the tree assembled from them. Hence a cycle in some $D_p[g_1, \dots, g_n]$ is a cycle in the dependency graph of a real tree (paths through a child's IO edges are paths through that child's subtree). Completeness: conversely, every tree's IO graph is eventually in $\mathrm{IO}$ (induction on tree height), and a cycle in $D(t)$ lies within some node's production plus the IO graphs of its children's subtrees (a cycle can only leave the production's occurrences through a child and must come back through the same child, which the child's IO graph summarizes), so the test finds a graph with a cycle. Knuth's 1968 version merged graphs and was not complete; the 1971 correction keeps sets of graphs.

Theorem 5.5.16 (The circularity problem is intrinsically exponential)

Deciding whether an attribute grammar is circular is complete for deterministic exponential time; in particular every algorithm needs time $2^{\Omega(n / \log n)}$ on infinitely many grammars of size $n$.

Proof sketch (full proof: [JOR75, §3–5])

Membership: Algorithm 5.5.8 runs in time exponential in the number of attributes per symbol (there are at most $2^{\lvert \mathrm{Inh}(X) \rvert \cdot \lvert \mathrm{Syn}(X) \rvert}$ IO graphs per nonterminal). Hardness: Jazayeri, Ogden and Rounds reduce the acceptance problem of linear-space writing pushdown acceptors — a machine model whose acceptance problem needs deterministic exponential time — to circularity: attributes encode tape cells, trees encode computations, and a cycle exists iff the machine accepts. The lower bound then follows from the time hierarchy theorem. (Later proofs, e.g. Wu's, reduce from linear-space alternating Turing machines instead, a model introduced only in 1976; membership plus JOR75's hardness is what "EXPTIME-complete" summarizes.)

Proposition 5.5.17 (Ordered grammars are non-circular and are recognized in polynomial time)

If an AG is ordered (Definition 5.5.9), it is non-circular, and every tree is evaluated by the visit sequences. The OAG test runs in time polynomial in the size of the grammar.

Proof sketch (full proof: [Kas80, §3–4])

$\mathrm{IDS}$ over-approximates every tree's IO graphs (it is the union, closed under composition), so an acyclic $\mathrm{IDP}(p)$ plus partition edges orders every production's occurrences consistently with every possible child; a topological order of each augmented $\mathrm{IDP}(p)$ is the visit sequence, and following the visit sequences at every node evaluates each instance after its arguments (induction over visits). The test computes $\mathrm{IDS}$ and $\mathrm{IDP}$ by a fixed point over single graphs (not sets of graphs), which converges in a polynomial number of edge additions, then one partition per nonterminal and one acyclicity check per production. The price of the polynomial test: some non-circular grammars are not ordered.

Reference attribute grammars¶

Proposition 5.5.18 (Demand-driven evaluation is correct)

For an instance whose transitive argument graph is acyclic, Get (Algorithm 5.5.11) terminates, returns the value satisfying its equation, and evaluates each instance at most once. For a circular attribute over a lattice of finite height with monotone equations, GetCircular returns the least fixed point.

Proof

Acyclic case, by induction on the length of the longest argument path from the instance: the equation's arguments are requested through Get; each has a shorter longest path, so by the hypothesis returns its correct value; the equation is then evaluated on correct arguments, cached, and returned. inProgress never triggers, because a repeated request on the pending chain would be a cycle. The cache makes each instance's equation run once. Circular case: the iterates start at $\bot$ and each evaluation applies the monotone equations to the current approximations, so the sequence is an ascending Kleene chain $F^{0}(\bot) \sqsubseteq F^{1}(\bot) \sqsubseteq \cdots$; finite height makes it stabilize at $\mathrm{lfp}(F)$ (Knaster–Tarski/Kleene; [MH07, §3] for the multi-attribute case).

5. Complexity¶

Variables: $N$ attribute instances and $E$ dependency edges of a tree; $\lvert P \rvert$ productions; $a$ the maximum number of attributes per nonterminal; $r$ the maximum number of nonterminals on a right-hand side; $h$ the lattice height of circular attributes.

Technique	Time	Space	Pathological input
Topological evaluation (Alg. 5.5.5)	$\Theta(N + E)$ per tree	$\Theta(N + E)$: the whole graph	none; memory for huge trees
L-attributed one pass (Alg. 5.5.6)	$\Theta(N + E)$, no graph built	$O(\text{tree depth})$ beyond the attributes	none
Knuth's circularity test (Alg. 5.5.8)	$O(\lvert P \rvert \cdot (2^{a^2})^{r})$ graph checks	$O(\lvert N \rvert \cdot 2^{a^2})$ graphs	the grammars of [JOR75]: $2^{\Omega(n/\log n)}$ for any algorithm (Theorem 5.5.16)
OAG test and visit sequences	polynomial, $O(\lvert P \rvert \cdot a^3)$-ish closure per round	$O(\lvert P \rvert a^2)$	none; but some non-circular grammars are rejected
Demand-driven RAG evaluation (Alg. 5.5.11)	$O(\text{instances demanded} + \text{edges})$ with caching; circular attributes: $\times h$ iterations	cache for demanded instances only	uncached parameterized attributes (`lookup(name)` per name per node) can grow to $N \times$ names

Justification. Kahn's algorithm touches each vertex and edge once; the one-pass evaluator visits each node once and each rule once. Knuth's test considers, for each production, every combination of one IO graph per right-hand-side nonterminal, and a nonterminal has at most $2^{\lvert \mathrm{Inh}(X) \rvert \lvert \mathrm{Syn}(X) \rvert} \le 2^{a^2}$ IO graphs. Demand-driven evaluation runs each demanded equation once (the cache) and each circular one at most $h + 1$ times per stabilization. Real scale: JastAdd's ExtendJ compiles Java 8 projects with memoized RAG attributes at speeds comparable to javac within a small factor [EH07].

S- and L-attributed evaluation¶

Syntax-directed translation schemes embed actions at positions in the right-hand side (A → B { action } C); for an L-attributed definition, inherited attributes become actions before a symbol and synthesized ones actions at the end [ALSU07, §5.4]. Recursive-descent parsers evaluate them with parameters (inherited) and return values (synthesized).
Inherited attributes in LR parsers: yacc and Bison let an action read $0, the value below the current right-hand side on the stack — an inherited attribute from the left context — and mid-rule actions add ε-productions to compute them (§7). This works for L-attributed grammars whose inherited values are copies of known stack positions.
Multi-pass and visit-oriented evaluators for grammars that are not L-attributed: alternating left-to-right and right-to-left passes (Bochmann 1976), or Kastens' visits.

Circularity and ordered attribute grammars¶

Strong (absolute) non-circularity [KW76]: test with one merged IO graph per nonterminal — polynomial, sufficient but not necessary; OAG adds the partition and is a subclass of it.
Well-defined circular AGs: instead of rejecting cycles, give circular attributes a lattice and compute least fixed points (Farrow 1986; JastAdd's circular; Lesson 5.7's definite assignment is such a fixed point).

Reference attribute grammars¶

Higher-order attributes (attributes whose values are new trees that are then attributed; Vogt, Swierstra & Kuiper 1989) — used for desugaring inside AG systems (Lesson 5.6).
Collection attributes (gather contributions from all over the tree, e.g., all call sites of a method) and incremental evaluation (Reps, Teitelbaum & Demers 1983 [RTD83]; JastAdd's flushing), which turn AGs into an incremental analysis framework — the ancestor of the query systems of Lesson 5.6.

7. In real compilers¶

S- and L-attributed evaluation¶

Yacc and Bison evaluate S-attributed definitions on the parser's value stack at each reduction and support inherited attributes through $0 and mid-rule actions (Bison manual §3.4.8 "Actions in Mid-Rule" [BISON-Manual]). Every recursive-descent front end evaluates an L-attributed definition implicitly: the reference resolveNames passes the scope table down (inherited) and returns bindings up (synthesized) in one left-to-right walk (solutions/pebble/lib/Sema/Names/src/NameResolution.cpp).

An inherited attribute in Bison 3.8: $0 carries the declared type

Reproduce (bison 3.8.2, clang 23.1.2):

cat > decl.y <<'EOF'
%{
#include <stdio.h>
#include <ctype.h>
#include <string.h>
int yylex(void); void yyerror(const char *s) { fprintf(stderr, "%s\n", s); }
static const char *in = "int a, b; float c; int d;";
%}
%define api.value.type {const char *}
%token TYPE ID
%%
decls : %empty | decls decl ;
decl  : TYPE list ';'                  /* $$ of TYPE is the synthesized type name   */
      ;
list  : ID          { printf("%s: %s\n", $1, $0); }        /* $0 = TYPE: inherited */
      | list ',' ID { printf("%s: %s\n", $3, $0); }        /* still TYPE, below list */
      ;
%%
int yylex(void) {
  static char buf[64][16]; static int n;
  while (*in == ' ') in++;
  if (!*in) return 0;
  if (isalpha((unsigned char)*in)) {
    char *b = buf[n++]; int k = 0;
    while (isalpha((unsigned char)*in)) b[k++] = *in++;
    b[k] = 0; yylval = b;
    return (!strcmp(b, "int") || !strcmp(b, "float")) ? TYPE : ID;
  }
  return *in++;
}
int main(void) { return yyparse(); }
EOF
bison -Wall -o decl.c decl.y && clang-23 -w decl.c -o decl && ./decl

Output (complete):

a: int
b: int
c: float
d: int

What to notice: list never receives the type as an argument; each reduction of list reads $0, the stack slot just below its right-hand side, which always holds the TYPE token's value because list only occurs after TYPE in decl. That is the inherited attribute $L.\mathit{inh} = T.\mathit{type}$ of the running AG, evaluated by an LR parser as Corollary 5.5.14 and the $0 trick allow for this L-attributed grammar.

Circularity and ordered attribute grammars¶

Kastens' OAG construction is implemented in the LIGA attribute evaluator generator of the Eli system; JastAdd sidesteps static circularity tests by evaluating on demand and allowing declared circular attributes (Algorithm 5.5.11), whose generated code iterates to a fixed point (JastAdd2 2.3.6 [JASTADD]).

A circular attribute evaluated to a fixed point by JastAdd 2.3.6

Reproduce (JastAdd2 2.3.6 from Maven Central, javac/java 21.0.10):

mkdir -p jcirc && cd jcirc
curl -sSLO https://repo.maven.apache.org/maven2/org/jastadd/jastadd/2.3.6/jastadd-2.3.6.jar
cat > Gram.ast <<'EOF'
Grammar ::= Prod*;
Prod ::= <Lhs:String> Sym*;
abstract Sym ::= <Name:String>;
T : Sym;
N : Sym;
EOF
cat > Nullable.jrag <<'EOF'
aspect Nullable {
  // A circular attribute: evaluated by fixed-point iteration from the bottom value false.
  syn boolean Grammar.nullable(String nt) circular [false] {
    for (Prod p : getProdList())
      if (p.getLhs().equals(nt) && p.allNullable()) return true;
    return false;
  }
  syn boolean Prod.allNullable() {
    for (Sym s : getSymList()) if (!s.nullable()) return false;
    return true;
  }
  syn boolean Sym.nullable();
  eq T.nullable() = false;
  eq N.nullable() = grammar().nullable(getName());
  inh Grammar Sym.grammar();
  eq Grammar.getProd().grammar() = this;
}
EOF
cat > Main.java <<'EOF'
import gram.ast.*;
public class Main {
  static Prod prod(String lhs, Sym... rhs) {
    List<Sym> l = new List<Sym>();
    for (Sym s : rhs) l.add(s);
    return new Prod(lhs, l);
  }
  public static void main(String[] args) {
    // S -> A B ; A -> a | B ; B -> A | (empty) ; C -> C c
    Grammar g = new Grammar(new List<Prod>()
        .add(prod("S", new N("A"), new N("B")))
        .add(prod("A", new T("a"))).add(prod("A", new N("B")))
        .add(prod("B", new N("A"))).add(prod("B"))
        .add(prod("C", new N("C"), new T("c"))));
    for (String nt : new String[] {"S", "A", "B", "C"})
      System.out.println("nullable(" + nt + ") = " + g.nullable(nt));
  }
}
EOF
mkdir -p gen classes
java -jar jastadd-2.3.6.jar --package=gram.ast --o=gen Gram.ast Nullable.jrag
javac -nowarn -d classes $(find gen -name '*.java') Main.java 2>/dev/null
java -cp classes Main

Output (complete):

nullable(S) = true
nullable(A) = true
nullable(B) = true
nullable(C) = false

What to notice: nullable(A) depends on nullable(B), which depends on nullable(A): a cycle in the attribute dependencies that a Knuth-style test would reject. Declared circular [false], it is instead the least fixed point from false (Algorithm 5.5.11), exactly the nullable computation of Ch 2 — and the left-recursive C → C c correctly stays false (the least, not the greatest, fixed point).

Reference attribute grammars¶

JastAdd generates, for each syn/inh attribute, a Java method with a cache and a cycle check (inProgress in Algorithm 5.5.11); the ExtendJ Java compiler is written this way. The name-analysis pattern — an inherited parameterized lookup(String) defined by each scope, and a reference attribute decl() — is the one the JastAdd tutorials teach [EH07].

Name resolution as a reference attribute in JastAdd 2.3.6

Reproduce (JastAdd2 2.3.6, javac/java 21.0.10):

mkdir -p jnames && cd jnames
curl -sSLO https://repo.maven.apache.org/maven2/org/jastadd/jastadd/2.3.6/jastadd-2.3.6.jar
cat > Lang.ast <<'EOF'
Program ::= Block;
Block : Stmt ::= Stmt*;
abstract Stmt;
Decl : Stmt ::= <ID:String> <Tag:String>;
Use : Stmt ::= <ID:String>;
EOF
cat > Names.jrag <<'EOF'
aspect Names {
  // A reference attribute: the value of Use.decl() is a node of the tree.
  syn Decl Use.decl() = lookup(getID());

  // Inherited: a statement asks its context which declaration a name denotes.
  inh Decl Stmt.lookup(String name);
  eq Block.getStmt(int i).lookup(String name) {
    for (int k = i - 1; k >= 0; k--)          // earlier statements of this block only
      if (getStmt(k) instanceof Decl && ((Decl) getStmt(k)).getID().equals(name))
        return (Decl) getStmt(k);
    return lookup(name);                       // then the enclosing block
  }
  eq Program.getBlock().lookup(String name) = null;

}
EOF
cat > Main.java <<'EOF'
import lang.ast.*;
public class Main {
  public static void main(String[] args) {
    // { var x /*d1*/; use x; { use x; var x /*d2*/; use x; } use y; }
    Block inner = new Block(new List<Stmt>().add(new Use("x")).add(new Decl("x", "d2")).add(new Use("x")));
    Block outer = new Block(new List<Stmt>().add(new Decl("x", "d1")).add(new Use("x")).add(inner).add(new Use("y")));
    Program p = new Program(outer);
    for (Block b : new Block[] {outer, inner})
      for (Stmt s : b.getStmtList())
        if (s instanceof Use) {
          Use u = (Use) s;
          Decl d = u.decl();
          System.out.println("use " + u.getID() + " -> " + (d == null ? "none" : d.getTag()));
        }
  }
}
EOF
mkdir -p gen classes
java -jar jastadd-2.3.6.jar --package=lang.ast --o=gen Lang.ast Names.jrag
javac -nowarn -d classes $(find gen -name '*.java') Main.java 2>/dev/null
java -cp classes Main

Output (complete):

use x -> d1
use y -> none
use x -> d1
use x -> d2

What to notice: the output lists the outer block's uses, then the inner block's. The inner block's first use x resolves to d1 because its lookup only scans earlier siblings (declare-before-use, as in Pebble) and then delegates to the enclosing block; the second finds d2. No symbol table exists anywhere: the "table" is the set of lookup equations, one per scope construct, evaluated on demand and cached (Proposition 5.5.18).

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
S- and L-attributed evaluation	S: bottom-up only; L: plus left-to-right inherited information (Theorem 5.5.13) — enough for declarations, types and name resolution in declare-before-use languages	$\Theta(N + E)$, one pass, no graph · runs inside the parser	Errors at the node whose equation fails, in source order	Lowest: parser actions or recursive-descent parameters	yacc/Bison actions, recursive-descent front ends, `pebblec`
Circularity test and ordered attribute grammars	Any non-circular AG (Theorem 5.5.12); OAG: a polynomially testable subclass with static visit sequences (Proposition 5.5.17)	Test: exponential in general (Theorem 5.5.16), polynomial for OAG · evaluation $\Theta(N + E)$	The generator reports circular or unordered grammars before any program is compiled	High (a generator)	AG-based compiler generators (Eli/LIGA, LRC, Silver)
Reference attribute grammars	Remote attribute access and references: name and type analysis without copying environments; circular attributes for fixed points (Proposition 5.5.18)	Demand-driven, cached · only demanded instances	Cycles detected at run time on the demanded path	Medium (JastAdd generates the evaluator)	JastAdd/ExtendJ, Modelica compilers (JModelica), language workbenches

Choose L-attributed specifications (implemented as a recursive-descent or visitor walk) when the language resolves names declare-before-use and types flow in one direction — that is Pebble. Choose an AG generator with a static circularity or OAG test when many people maintain one large semantic specification and you want the tool to guarantee an evaluation order. Choose reference AGs when analyses need to follow references across the tree (name, type and flow analyses of an object-oriented language) and you want declarative, modular aspects with on-demand evaluation.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
S- and L-attributed evaluation	`ag-classify`, `ag-topo-order`	`attr-eval-order` (easy, medium)	`ag-s-l`	E1 (the resolver is an L-attributed walk)
Circularity and ordered attribute grammars	`knuth-test-cycle`, `circularity-complexity`	`attr-eval-order --difficulty hard` (circular trees)	`ag-circularity`	—
Reference attribute grammars	`rag-lookup`, `rag-circular`	— (the JastAdd runs above; a drill would need a RAG engine)	`rag`	—

References¶

See the chapter references.

production	rules
\(p_1: D \to T\ L\)	\(L[2].\mathit{inh} = T[1].\mathit{type}\); \(D[0].n = L[2].n\)
\(p_2: T \to \texttt{int}\)	\(T[0].\mathit{type} = \mathsf{int}\)
\(p_3: L \to L\ \texttt{,}\ \texttt{id}\)	\(L[1].\mathit{inh} = L[0].\mathit{inh}\); \(L[0].n = L[1].n + 1\) (and record \(\texttt{id} : L[0].\mathit{inh}\))
\(p_4: L \to \texttt{id}\)	\(L[0].n = 1\) (and record \(\texttt{id} : L[0].\mathit{inh}\))

production	rules
\(q_1: S \to A\)	\(A[1].i = A[1].s\); \(S[0].v = A[1].s\)
\(q_2: A \to B\)	\(B[1].i = A[0].i\); \(A[0].s = B[1].s\)
\(q_3: B \to \texttt{x}\)	\(B[0].s = B[0].i\)
\(q_4: B \to \texttt{y}\)	\(B[0].s = 0\)

round	production, children's graphs	\(D_p[\dots]\) has a cycle?	graph added to \(\mathrm{IO}(X_0)\)
1	\(q_3\) (no nonterminal children)	no	\(\mathrm{IO}(B) \ni \{(i, s)\}\)
1	\(q_4\)	no	\(\mathrm{IO}(B) \ni \{\}\)
1	\(q_2\) with \(g_B = \{(i,s)\}\): path \(A.i \to B.i \to B.s \to A.s\)	no	\(\mathrm{IO}(A) \ni \{(i, s)\}\)
1	\(q_2\) with \(g_B = \{\}\)	no	\(\mathrm{IO}(A) \ni \{\}\)
1	\(q_1\) with \(g_A = \{(i,s)\}\): \(A.s \to A.i\) (the rule) and \(A.i \to A.s\) (the graph)	yes	stop: circular

Technique	Time	Space	Pathological input
Topological evaluation (Alg. 5.5.5)	\(\Theta(N + E)\) per tree	\(\Theta(N + E)\): the whole graph	none; memory for huge trees
L-attributed one pass (Alg. 5.5.6)	\(\Theta(N + E)\), no graph built	\(O(\text{tree depth})\) beyond the attributes	none
Knuth's circularity test (Alg. 5.5.8)	\(O(\lvert P \rvert \cdot (2^{a^2})^{r})\) graph checks	\(O(\lvert N \rvert \cdot 2^{a^2})\) graphs	the grammars of [JOR75]: \(2^{\Omega(n/\log n)}\) for any algorithm (Theorem 5.5.16)
OAG test and visit sequences	polynomial, \(O(\lvert P \rvert \cdot a^3)\)-ish closure per round	\(O(\lvert P \rvert a^2)\)	none; but some non-circular grammars are rejected
Demand-driven RAG evaluation (Alg. 5.5.11)	\(O(\text{instances demanded} + \text{edges})\) with caching; circular attributes: \(\times h\) iterations	cache for demanded instances only	uncached parameterized attributes (`lookup(name)` per name per node) can grow to \(N \times\) names

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
S- and L-attributed evaluation	S: bottom-up only; L: plus left-to-right inherited information (Theorem 5.5.13) — enough for declarations, types and name resolution in declare-before-use languages	\(\Theta(N + E)\), one pass, no graph · runs inside the parser	Errors at the node whose equation fails, in source order	Lowest: parser actions or recursive-descent parameters	yacc/Bison actions, recursive-descent front ends, `pebblec`
Circularity test and ordered attribute grammars	Any non-circular AG (Theorem 5.5.12); OAG: a polynomially testable subclass with static visit sequences (Proposition 5.5.17)	Test: exponential in general (Theorem 5.5.16), polynomial for OAG · evaluation \(\Theta(N + E)\)	The generator reports circular or unordered grammars before any program is compiled	High (a generator)	AG-based compiler generators (Eli/LIGA, LRC, Silver)
Reference attribute grammars	Remote attribute access and references: name and type analysis without copying environments; circular attributes for fixed points (Proposition 5.5.18)	Demand-driven, cached · only demanded instances	Cycles detected at run time on the demanded path	Medium (JastAdd generates the evaluator)	JastAdd/ExtendJ, Modelica compilers (JModelica), language workbenches

Lesson 5.5 — Attribute grammars: S- and L-attributed definitions, circularity, ordered and reference attribute grammars¶

1. Problem and motivation¶

S- and L-attributed evaluation¶

Circularity and ordered attribute grammars¶

Reference attribute grammars¶

2. Definitions and algorithms¶

3. Worked example¶

S- and L-attributed evaluation¶

Circularity and ordered attribute grammars¶

Reference attribute grammars¶

4. Invariants and correctness¶

S- and L-attributed evaluation¶

Circularity and ordered attribute grammars¶

Reference attribute grammars¶

5. Complexity¶

6. Variants and refinements¶

S- and L-attributed evaluation¶

Circularity and ordered attribute grammars¶

Reference attribute grammars¶

7. In real compilers¶

S- and L-attributed evaluation¶

Circularity and ordered attribute grammars¶

Reference attribute grammars¶

8. Comparison¶

9. Assessment¶

References¶