Constructing functional programs for grammar analysis problems

Abstract

This paper discusses the derivation of functional programs for grammar analysis problems, such as the Empty problem and the Reachable problem. Grammar analysis problems can be divided into two classes: top-down problems such as Follow and Reachable, which are described in terms of the contexts of nonterminals, and bottom-up problems such as Empty and First, which do not refer to contexts. In a previous paper we derive a program for bottom-up grammar analysis problems. In this paper we derive a program for top-down grammar analysis problems by transforming the specification of an arbitrary top-down problem into a program. The existence of a solution is guaranteed provided some natural conditions are satisfied. Furthermore, we describe a general transformation that applies to both classes of grammar analysis problems. The general transformation avoids unnecessary computations in the computation of a fixed point. Constructor classes, which are used to abstract from the notions bottom-up and top-down, are an essential ingredient of the latter derivation.