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.
Given a context free grammar, an attribute grammar:
- Associates with each grammar symbol
Xa set of attributes
- 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.
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
aof every tree node
Xthere 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.
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 = expbelongs to a grammar rule
X0 -> X1 ... Xnand
expcontains only attributes of
X1 ... Xn(Huh?).
- If not synthesised, then the attribute is inherited.
- 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.
- 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.