An Augmented Pattern Matcher as a Tool to Synthesize Conceptual Descriptions of Programs

Abstract :

In this paper, we present a pattern matcher specially developed for the parsing of LISP functions. Its main features are patterns defined by context-free grammars, parametrized patterns, multi-step matching, as well as dynamic synthesis of new patterns.

We have designed a model for the conceptual description of functions, which abstracts the computations performed by a function, but is still complete enough to be executable. It constitutes a key for the understanding of the function.

The augmented pattern matcher is used by our system PRISME to analyze LISP functions and to synthesize conceptual descriptions. We are currently working on the extension of the system in order to handle programs and to use the conceptual descriptions as guide to program verification and optimization.

Keywords : augmented grammars, code parsing, conceptual program understanding, pattern matching language, program descriptions.

Ce papier est disponible en version Postcript ou sur demande .