A decompiler accepts low-level object code and produces the high-level source code that compiles into the object code. This paper describes a technique for constructing decompilers using attribute grammars and functional programming.

Given the grammars for the source and object languages, the authors show how to augment the source language grammar with attributes--values passed up and down the parse tree while it is being constructed--so that the grammar efficiently generates only acceptable source code.

A decompiler is an implementation of an attribute grammar as a functional program. Some care is required when implementing infinite attributes (such as the set of “if” statements); an enumeration over a set of infinite attributes should result in all possible combinations. Defining list-manipulating operations with the proper interleaving behavior results in a straightforward translation from an attribute grammar to a functional program.

Computability and abstract execution arguments show, among other things, that desirable general decompilation algorithms also solve the halting problem, and so do not exist, and that, for a properly behaved attribute grammar, the associated decompiler properly generates the infinity of source codes.

This work represents a useful first step toward decompilation; it will be interesting to see how it can be extended, for example, to deal with optimized object code or to recover the original source code’s type structures. A familiarity with attribute grammars and functional programming speeds the reading along, but is not necessary for the diligent reader. There are several small errors (mostly typos) throughout the paper.