The efficient evaluation of attribute grammars

Knuth's attribute grammars are a powerful, natural way of specifying translations such as those involved in compiling programming languages, but until now efficient implementation has been possible only for restricted classes of attribute grammars. We present a method of constructing, for any attribute grammar, a recursive procedure which performs the specified semantic evaluation. These "treewalk evaluators" are produced by analysing the data dependencies of the attribute grammar to find an acceptable evaluation strategy. The resulting evaluators are efficient in the sense that they make no use of nondeterminism or searching through the parse tree and may be generated as directly executing machine code rather than requiring an interpreter. Our construction is therefore suitable for use in a practical compiler-writing system