NOTE: A better, more general, and more complete implementation is available as part of the Bop term rewriting language.
H.L. Chau and D.S. Parker
appeared in: J. Logic Programming 14, 253-286, November 1992.
an earlier version appeared in: Proceedings of the Sixth Intnl. Conference on Logic Programming, pp. 199-217, Lisbon, Portugal, Giorgio Levi (ed.), MIT Press, June 1989.
This paper describes Narrowing Grammar, a new kind of grammar that combines concepts from logic programming, rewriting, lazy evaluation, and logic grammar formalisms such as Definite Clause Grammar (DCG). A Narrowing Grammar is a finite set of rewrite rules. The semantics of Narrowing Grammar is defined by a specialized kind of outermost rewriting strategy called NU-narrowing.Narrowing Grammar is directly executable, like many logic grammars. In fact, Narrowing Grammar rules can be compiled to Prolog and executed by existing Prolog interpreters as generators or acceptors. Unlike many logic grammars, Narrowing Grammar also permits higher-order specification and modular composition, and provides lazy evaluation by virtue of its rewriting strategy. Lazy evaluation is important in certain language acceptance situations, such as in coroutined matching of multiple patterns against a stream.
We compare Narrowing Grammar with several established logic grammars: Definite Clause Grammar, Metamorphosis Grammar, Extraposition Grammar and Gapping Grammar, showing how these logic grammars can be transformed to Narrowing Grammar. We also investigate the versatility of Narrowing Grammar in language analysis by applying it to several natural language examples.