In: A.W. Roscoe (editor), A Classical Mind: Essays Dedicated to C.A.R. Hoare, pp. 17-35, Prentice Hall 1994.

Authors: Richard S. Bird and Oege de Moor
>

Abstract

We derive Earley's algorithm for context-free language recognition from a declarative specification. The main techniques employed are a categorical theory of datatypes, and a relational algebra to deal with program inversion and nondeterminism.

BIBTEX:

           @inproceedings{acm94bird, 
           author = "Richard S. Bird and De Moor, Oege", 
           title = "Relational program derivation and context-free language recognition", 
           booktitle = "A Classical Mind: Essays dedicated to {C. A. R. Hoare}", 
           editor = "A. W. Roscoe", 
           year = "1994", 
           pages = "17--35",
           publisher = "Prentice Hall"}