MEMOIZING PURELY FUNCTIONAL TOP-DOWN BACKTRACKING LANGUAGE PROCESSORS

Language processors may be implemented directly as functions. In a pro gramming language that supports higher-order functions, large processo rs can be built by combining smaller components using higher-order fun ctions corresponding to alternation and sequencing in the BNF notation of the grammar of the language to be processed. If the higher-order f unctions are defined to implement a top-down backtracking parsing stra tegy, the processors are modular and, owing to the fact that they rese mble BNF notation, are easy to understand and modify. A major disadvan tage of this approach is that the resulting processors have exponentia l time and space complexity in the worst case owing to the reapplicati on of processors during backtracking. This paper shows how a technique called memoization can be used to improve the efficiency of such proc essors whilst preserving their modularity. We show that memoized funct ional recognizers constructed for arbitrary non-left-recursive grammar s have O(n(3)) complexity where n is the length of the input to be pro cessed. The paper also shows how the initial processors could have bee n memoized using a monadic approach, and discusses the advantages of r eengineering the definitions in this way.