Peter T Breuer and Jonathan P Bowen
1992, 27pp.
A free type definition may be remolded into a simple functional program which enumerates all the terms of the associated grammar. This is the starting point for a reliable method of compiling decompilers.
The technique produces efficient functional code and handles quite general synthetic and inherited attribute grammar descriptions (which correspond loosely to algebraically constrained and parametrized types in the functional programming terminology). Its efficiency derives from a close relationship between functionality and notation, and may also suggest a natural way to extend the popular list comprehension syntax.
The theory developed here guarantees the correctness of a decompiler for an Occam-like language, and, via a known correspondence between attribute grammars and logic programs, of a corresponding Prolog decompiler. Whilst enumerating grammars completely may be Halting Problem hard in general, it is shown here, with the aid of methods of abstract interpretation, that most grammars can be enumerated by the technique presented.