Automated Inversion of Logic Grammars for Generation

AUTOMATED INVERSION OF LOGIC GRAMMARS FOR GENERATION Tomek Strzalkowski and Ping Peng Courant Institute of Mathematical Sciences New York University 251 Mercer Street New York, NY 10012 ABSTRACT We describe a system of reversible grammar in which, given a logic-grammar specification of a natural language, two efficient PROLOG programs are derived by an off-line compilation process: a parser and a generator for this language. The centerpiece of the system is the inversion algorithm designed to compute the generator code from the parser's PRO- LOG code, using the collection of minimal sets of essential arguments (MSEA) for predicates. The sys- tem has been implemented to work with Definite Clause Grammars (DCG) and is a part of an English-Japanese machine translation project currently under development at NYU's Courant Insti- tute. INTRODUCTION The results reported in this paper are part of the ongoing research project to explore possibilities of an automated derivation of both an efficient parser and an efficient generator for natural language, such as English or Japanese, from a formal specification for this language. Thus, given a grammar-like descrip- tion of a language, specifying both its syntax as well as "semantics" (by which we mean a correspondence of well-formed expressions of natural language to expressions of a formal representation language) we want to obtain, by a fully automatic process, two pos- sibly different programs: a parser and a generator. The parser will translate well-formed expression of the source language into expressions of the language of "semantic" representation, such as regularized operator-argument forms, or formulas in logic. The generator, on the other hand, will accept well-formed expressions of the semantic representation language and produce corresponding expressions in the source natural language. Among the arguments for adopting the bidirec- tional design in NLP the following are perhaps the most widely shared: • A bidirectional NLP system, or a system whose inverse can be derived by a fully automated pro- cess, greatly reduces effort required for the sys- tem development, since we need to write only one program or specification instead of two. The actual amount of savings ultimately depends upon the extend to which the NLP system is made bidirectional, for example, how much of the language analysis process can be inverted for gen- eration. At present we reverse just a little more than a syntactic parser, but the method can be applied to more advanced analyzers as well. • Using a single specification (a grammar) underly- ing both the analysis and the synthesis processes leads to more accurate capturing of the language. Although no NLP grammar is ever complete, the grammars used in parsing tend to be "too loose", or unsound, in that they would frequently accept various ill-formed strings as legitimate sentences, while the grammars used for generation are usu- ally made "too tight" as a result of limiting their output to the "best" surface forms. A reversible system for both parsing and generation requires a finely balanced grammar which is sound and as complete as possible. • A reversible grammar …

Content truncated to 500 words