Compiler Design

Attribute Grammars

An Attribute Grammar is the formal mathematical framework used to specify the semantics of a programming language via a context-free grammar. The idea was introduced by Donald Knuth in 1968 and is the foundational formalism underlying all practical semantic specification in compilers today.

The core idea is that each grammar symbol can have attributes — named values associated with instances of that symbol in the parse tree. Each grammar production has associated semantic rules that define how these attribute values are computed.

Formal Definition

An Attribute Grammar is a triple AG = (G, A, R) where:

G = (N, T, P, S) is a context-free grammar with nonterminals N, terminals T, productions P, and start symbol S.
A = { A(X) | X is a grammar symbol } is a finite set of attributes for each symbol.
R = { R(p) | p is a production in P } is a set of semantic rules for each production.

Types of Attributes

Attributes are divided into two main categories depending on how their values flow through the parse tree:

A synthesized attribute of a nonterminal A in a production A → α is one whose value is computed from attribute values of children of A in the parse tree, and/or attribute values of terminals in the production body.

Direction of Flow: Upward

Information flows from the leaves toward the root.

Common Examples:

E.val in an expression grammar (computed from children E1.val and T.val)
E.type in a type-inference grammar (derived from operand types)
T.place in a three-address code generator (the name of the temporary variable holding the result)
digit.lexval (given directly by the lexical analyzer)

An inherited attribute of a nonterminal B at position j in a production A → X_1 X_2 ... X_n is one whose value is computed from attribute values of A (the parent), and/or attribute values of siblings to the left of B.

Direction of Flow: Downward or Sideways

Information flows from parents to children, or from left siblings to right siblings.

Common Examples:

L.in in a declaration grammar (type inherited from a left sibling)
indent.level in a code pretty-printer (current indentation depth passed down)
scope.level in a semantic analyzer (current scope depth passed to child nodes)

Example: Type Propagation (Inherited Attributes)

Inherited attributes are extremely useful for passing context down the tree. Consider a declaration statement like float x, y, z; where the type (float) must be distributed to all identifiers in the list:

Production Rule	Semantic Rules
D → T L	L.in = T.type (Inherit type into list)
T → int	T.type = integer
T → float	T.type = real
L → L1 , id	L1.in = L.in; addtype(id.entry, L.in)
L → id	addtype(id.entry, L.in)

For the input float x, y, z:

T → float sets T.type = real.
D → T L sets L.in = T.type = real (flows down).
For the list L → L1 , z, addtype(z, real) is called and L1.in = real is passed left.
Similarly, for L1 → L2 , y, addtype(y, real) is called.
Finally, the list reduces to L2 → x, executing addtype(x, real).

Introduction to Semantic Analysis Worked Example: Expression Evaluation