Attribute Grammars

5th February 2010 (Absent)

These are lecture notes from my Computer Science course, not a general reference for "Attribute Grammars"

An attribute grammar, at its simplest, is a grammar with attributes attached to it. Previously we’ve discussed transforming the abstract syntax tree by explicitly traversing the tree. But instead we can do this shorter, implementation-independent specification. The ‘attributes’ in an attribute grammar could be anything - information about a programming language construct e.g. current symbol table, type.

Definition

Given a context free grammar, an attribute grammar:

Associates with each grammar symbol X a set of attributes Att(X)
Each grammar rule has a set of attribute equations that have expressions in some meta-language.

There’s an example of an attribute grammar for declared type on slide 53.

Attributes have dependencies. For example the grammar rule (and attribute):

exp0 -> exp1 + exp2       exp0.type = if exp1.type = Int and exp2.type = Int
							then Int else error

has an obvious set of dependencies. The attribute of exp0 (here, its type) is dependent on the attributes (again, types) of exp1 and exp2. You can draw this as one graph superimposed on another (see slide 54) which is called a dependency graph.

You can also have a dependency graph of an entire grammar rule. That’s the union of the dependency graphs of all the attribute equations associated with the grammar rule.

Well-defined Attribution

An attribution (that is, the mapping of attributes of all tree nodes to values such that the attribute equations of the grammar are fulfilled) of a parse-tree is well-defined if

For every attribute a of every tree node X there is one defining attribute equation X.a = exp.
The dependency graph of the parse tree is acyclic (I imagine there’s big issues if it isn’t…).

Without this, you might get two conflicting equations for some tree node.

Computing Attributes

To compute attributes (based on the dependency graphs) you can do it in the order indicated by the dependency graph, and for a lazy functional programming language (Haskell) that can be done in one go. But other languages need more complex stuff:

Synthesised attribute equations are ones where X0.a = exp belongs to a grammar rule X0 -> X1 ... Xn and exp contains only attributes of X1 ... Xn (Huh?).
If not synthesised, then the attribute is inherited.

Some terminology

S-attributed attribute grammars are full of synthesised attributes.
L-attributed attribute grammars is full of inherited attributes I think.

The attribute grammar for Identification in the slides is an L-attributed grammar. The attribute grammar for Type Checking in the slides is an S-attributed grammar.

You can union, and compose attribute grammars together. This is useful in compiler construction. For example unions allow you to describe different aspects of the compiler in different trees. Composition allows you to do something involving abstract syntax trees and concrete syntax trees. Check the slides, I might be wrong.

The lecture notes go on to talk about different implementations of attribute computation:

Traversal(s) of the syntax tree, storing attributes with nodes if needed to be stored (some are inherited/synthesised and so don’t need to be stored at the actual nodes they start at).
Compute attributes when you parse. A recursive-descent parser can do L-attributed grammars easily. An LR parser can do S-attributed grammars easily, but struggles with inherited attributes.

Slide 61+ has some more examples of attribute grammars. They’re not as complicated as they sound, though writing them from scratch probably requires a bit of intuition.

Slide 63+ explains and demonstrates attribute grammars with side effects. Wow, they sound messy. Basically the grammar has a global symbol table too. A state, if you like.

Summary

Using attribute grammars you can specify different semantic phases with nice separate specifications and still get some nice implementations.
The dependency graph is important for using attribute values.
If you restrict the grammar then you can get better implementations where you know how many traversals are required and in what order.

No one likes attribute grammars, everyone uses Yacc/Bison instead. That’s because they’re only decent if you don’t use side effects, and loads of languages use side effects nowadays. Lazy functional languages go well with attribute grammars. Guess that’s why we’re learning about them - the lecturer likes Haskell.