Comparing Two Grammar-Based Generation Algorithms: A Case Study

COMPARING TWO GRAMMAR-BASED GENERATION A CASE STUDY Miroslav Martinovic and Tomek Strzalkowski Courant Institute of Mathematical Sciences New York University 715 Broadway, rm. 704 New York, N.Y., 10003 ALGORITHMS: ABSTRACT In this paper we compare two grammar-based gen- eration algorithms: the Semantic-Head-Driven Genera- tion Algorithm (SHDGA), and the Essential Arguments Algorithm (EAA). Both algorithms have successfully addressed several outstanding problems in grammar- based generation, including dealing with non-mono- tonic compositionality of representation, left-recursion, deadlock-prone rules, and nondeterminism. We con- centrate here on the comparison of selected properties: generality, efficiency, and determinism. We show that EAA's traversals of the analysis tree for a given lan- guage construct, include also the one taken on by SHDGA. We also demonstrate specific and common situations in which SHDGA will invariably run into serious inefficiency and nondeterminism, and which EAA will handle in an efficient and deterministic manner. We also point out that only EAA allows to treat the underlying grammar in a truly multi-directional manner. 1. INTRODUCTION Recently, two important new algorithms have been published ([SNMP89], [SNMP90], [S90a], [S90b] and [$91]) that address the problem of automated genera- tion of natural language expressions from a structured representation of meaning. Both algorithms follow the same general principle: given a grammar, and a struc- tured representation of meaning, produce one or more corresponding surface strings, and do so with a mini- mal possible effort. In this paper we limit our analysis of the two algorithms to unification-based formalisms. The first algorithm, which we call here the Seman- tic-Head-Driven Generation Algorithm (SHDGA), uses information about semantic heads ~ in grammar rules to obtain the best possible traversal of the generation tree, using a mixed top-down/bottom-up strategy. The semantic head of a rule is the literal on the right-hand side that shares the semantics with the literal on the left. The second algorithm, which we call the Essential Ar- guments Algorithm (EAA), rearranges grammar pro- ductions at compile time in such a way that a simple top-down left-to-right evaluation will follow an opti- mal path. Both algorithms have resolved several outstanding problems in dealing with natural language grammars, including handling of left recursive rules, non-mono- tonic compositionality of representation, and deadlock- prone rules 2. In this paper we attempt to compare these two algorithms along their generality and efficiency lines. Throughout this paper we follow the notation used in [SNMP90]. 2. MAIN CHARACTERISTICS OF SHDGA'S AND EAA'S TRAVERSALS SHDGA traverses the derivation tree in the seman- tic-head-first fashion. Starting from the goal predicate node (called the root), containing a structured repre- sentation (semantics) from which to generate, it selects a production whose leg-hand side semantics unifies with the semantics of the root. If the selected production passes the semantics unchanged from the left to some nonterminal on the right (the so-called chain rule), this later nonterminal becomes the new root and the algo- rithm is applied recursively. On the other hand, if no right-hand side literal has the same semantics as the root (the so called non-chain rule), …

Content truncated to 500 words