Analysis of Functional Programs using Attribute Grammars

technical reportAn attribute grammar combines the standard context-free grammar that defines the syntax of a programming language with attributes that define semantic aspects of the language. This information makes attribute grammars very useful for performing the semantic analysis of programs. Functional programming languages have their syntax based upon function applications and compositions thereof. This class of programming languages is attractive due to its clear, simple svntax, range of applicability and deterministic execution behavior under parallel execution. At present, the use of functional programming languages is limited due to a lack of effective compilation and optimization techniques for efficient execution. By directing the descriptive power of attribute grammars toward functional programming language compilation, it is possible to develop optimization information leading to efficient compilation and execution of functional programming languages. This is demonstrated here by the development of a system to optimize programs written in the functional programming language called FEL (Functian-Equation Language). A difficulty with attribute grammars lies in developing an efficient method of representing and calculating the semantic attributes of a program. This problem is solved by using logic programming system techniques in Prolog Prolog allows very powerful programs to be written quickly and easily, with the code automaticallv given a template. In addition, Prolog contains logical variables which allow natural data sharing among disjoint parts of an arbitrary data structure without having to pass the data explicitly to the various locations. Through these features it is possible to develop an efficient system for using attribute grammars to perform program analysis