The problem of generating a well-formed natural-language expression from an encoding of its meaning possesses certain properties which distinguish it from the converse problem of recovering a meaning encoding from a given natural-language expression. In previous work [19], however, one of us attempted to characterize these differing properties in such a way that a single uniform architecture, appropriately parameterized, might be used for both natural-language processes. In particular, we developed an architecture inspired by the Earley deduction work of Pereira and Warren [15], but which generalized that work allowing for its use in both a parsing and generation mode, merely by setting the values of a small number of parameters.
As a method for generating natural-language expressions, the Earley deduction method is reasonably successful along certain dimensions. It is quite simple, general in its applicability to a range of unification-based and logic grammar formalisms, and uniform, in that it places only one restriction (discussed below) on the form of the linguistic analyses allowed by the grammars used in generation. In particular, generation from grammars with recursions whose well-foundedness relies on lexical information will terminate; top-down generation regimes such as those of Wedekind [21] or Dymetman and Isabelle [4] lack this property, discussed further in Section 3.1.
Unfortunately, the bottom-up, left-to-right processing regime of Earley generation-as it might be called-has its own inherent frailties. Efficiency considerations require that only grammars possessing a property of semantic monotonicity can be effectively used, and even for those grammars, processing can become overly nondeterministic.
The algorithm described in this paper is an attempt to resolve these
problems in a satisfactory manner. Although we believe that this
algorithm could be seen as an instance of a uniform architecture for
parsing and generation-just as the extended Earley parser
[17] and the bottom-up generator were instances
of the generalized Earley deduction architecture-our efforts to date
have been aimed foremost towards the development of the algorithm for
generation alone, so that we will have little to say about its
relation to parsing, leaving such questions for later
research.