Definition and Use of Attribute Reevaluation in Attributed Grammars

Abstract

Attributed grammars can be used to specify both the syntax and the semantics of programming languages, and provide an implementation for compilers. We discuss extensions to attributed grammars and a generalization of attribute evaluation that allow code optimization techniques to be efficiently implemented and easily specified. A formal definition of the extended attributed grammars, called time-varying attributed grammars, is given. Time-varying attributed grammars provide a high-level, non-procedural specification of iterative algorithms. Evaluators for time-varying attributed grammars are described and potential problems that can result from the use are discussed. Examples of common code optimization techniques are given using time-varying attributed grammars. Techniques that reduce the overhead of evaluation, and also simplify the specifications of attributed grammars are suggested.