Since a few years several authors have been working on the tactical generation problem in logic- or unification-based grammar formalisms such as  and  (or linguistic theories that use similar formalisms such as LFG , UCG  and CUG ). In most natural language generation systems there are two different parts: the strategic part, `deciding what to say', and the tactical part, that is, `how to say it'. For a discussion of this division of labour see for example , and also .
A bidirectional unification grammar defines relations between strings and an abstract representation that is sometimes called the logical form. The parsing problem is to determine the corresponding logical form(s) for a given string; similarly the (tactical) generation problem is to determine the corresponding string(s) for a given logical form. This conceivement of the generation problem is different from the approaches of Buseman  and Saint-Dizier . In these two works the generation method relies on the parsing of a control structure by a specialized grammar in order to construct a syntactic representation. Moreover it is different from the approach of  in that I assume a clear distinction between the declarative definition of the relation between strings and logical forms (the grammar) and the different processes that are used to compute this relation (the parser and/or the generator).
None of the `early' approaches to the tactical generation problem in this context (such as ,  and ) were entirely satisfactory for general purposes. In section 2 I will summarize some of the criticisms.
Because of these criticisms other approaches were investigated, some of which turned out to be very similar in nature. For example the work reported in  can be seen as variations on one `theme': the head driven bottom-up approach. In this approach the order of processing is geared towards the logical form of the input (head driven) and the information available in lexical entries (bottom-up). In section 3.1 I will define a simple version of such a generator: BUG1, to explain the properties of head-driven bottom-up generation. The shortcomings of BUG1 are discussed together with some possible extensions. Furthermore I clarify the relation between BUG1 and the simple left-corner parser as described in .
Throughout this paper I will define examples and algorithms using the programming language . I thus assume that readers have some knowledge of ; excellent introductions within the NLP context are .
In this paper I will hardly touch upon lexical issues. In fact I will assume that a lexical entry is just a unification grammar rule, accidentally without any daughters. For a more realistic approach see for example  and . I will assume that such approaches can be incorporated in the framework described here.