NARROWING GRAMMAR - THEORY, IMPLEMENTATION, AND APPLICATIONS

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 it 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