A Semantic-Head-Driven Generation Algorithm for Unification-Based Formalisms

A Semantic-Head-Driven Generation Algorithm for Unification-Based Formalisms Stuart M. Shieber," Gertjan van Noord, t Robert C. Moore," and Fernando C. N. Pereira.* "Artificial Intelligence Center SRI International Menlo Park, CA 94025, USA tDepartment of Linguistics Rijksuniversiteit Utrecht Utrecht, Netherlands Abstract We present an algorithm for generating strings from logical form encodings that improves upon previous algorithms in that it places fewer restric- tions on the class of grammars to which it is ap- plicable. In particular, unlike an Earley deduction generator (Shieber, 1988), it allows use of seman- tically nonmonotonic grammars, yet unlike top- down methods, it also permits left-recursion. The enabling design feature of the algorithm is its im- plicit traversal of the analysis tree for the string being generated in a semantic-head-driven fashion. 1 Introduction The problem of generating a well-formed natural- language expression from an encoding of its mean- ing possesses certain properties which distinguish it from the converse problem of recovering a mean- ing encoding from a given natural-language ex- pression. In previous work (Shieber, 1988), how- ever, one of us attempted to characterize these differing properties in such a way that a sin- gle uniform architecture, appropriately parame- terized, might be used for both natural-language processes. In particular, we developed an archi- tecture inspired by the Earley deduction work of Pereira and Warren (1983) 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 rea- sonably successful along certain dimensions. It is quite simple, general in its applicability to a range of unification-based and logic grammar for- malisms, and uniform, in that it places only one restriction (discussed below) on the form of the lin- guistic analyses allowed by the grammars used in generation. In particular, generation from gram- mars with recursions whose welbfoundedness relies on lexical information will terminate; top-down generation regimes such as those of Wedekind (1988) or Dymetman and Isabelle (1988) lack this property, discussed further in Section 3.1. Unfortunately, the bottom-up, left-to-right pro- cessing regime of Earley generation--as it might be called--has its own inherent frailties. Efficiency considerations require that only grammars pos- sessing 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 at- tempt to resolve these problems in a satisfactory manner. Although we believe that this algorithm could be seen as an instance of a uniform archi- tecture for parsing and generation--just as the extended Earley parser (Shieber, 1985b) and the bottom-up generator were instances of the general- ized Earley deduction architecture= our efforts to date have been aimed foremost toward the devel- opment of the algorithm for generation alone. We will have little to say about its relation to parsing, leaving such questions for later research.1 2 Applicability of the Algo- rithm As does the Earley-based generator, the new algo- rithm …

Content truncated to 500 words