Constructing functional programs for grammar analysis problems
Johan T. Jeuring, Doaitse Swierstra · 1995
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 result of this transformation is a program that avoids unnecessary computations in the computation of a fixed point.Constructor classes, which me used to abstract from the notions bottom-up and top-down, are an essential ingredient of the latter derivation.1