Next: Problems with Existing Up: A Semantic-Head-Driven Generation Algorithm Previous: Introduction

Applicability of the Algorithm

As was the case for the Earley-based generator, the new algorithm assumes that the grammar is a unification-based or logic grammar with a phrase-structure backbone and complex nonterminals. Furthermore, and again consistent with previous work, we assume that the nonterminals associate to the phrases they describe logical expressions encoding their possible meanings. We will describe the algorithm in terms of an implementation of it for definite-clause grammars (DCG) although we believe the underlying method to be more broadly applicable.

A variant of our method is used in Van Noord's BUG (Bottom-Up Generator) system, part of MiMo2, an experimental machine translation system for translating international news items of Teletext, which uses a Prolog version of PATR-II similar to that of Hirsh [7]. According to Martin Kay (personal communication) the STREP machine translation project at the Center for the Study of Language and Information uses a version of our algorithm algorithm to generate with respect to grammars based on head-driven phrase-structure grammar (HPSG). Finally, Calder, Reape and Zeevat [1] report on a generation algorithm for unification categorial grammar that appears to be a special case of ours.

Gertjan van Noord
Thu Nov 24 18:39:44 MET 1994