Reversible logic grammars for natural language parsing and generation

The use of a single grammar in natural language parsing and generation is most desirable for a variety of reasons, including efficiency, perspicuity, integrity, robustness, and a certain amount of elegance. These characteristics have been noted before by several researchers, but it was only recently that more serious attention started to be paid to the problem of creating a bidirectional system for natural language processing. In this paper we discuss a somewhat more radical version of the problem: given a parser for a language, can we reverse it so that it becomes an efficient generator for the same language? Furthermore, since both the parser and the generator are based upon the same grammar, are there any normalization conditions upon the form of the grammar that must be met in order to assure the maximum efficiency of the reversed program? Can other grammars be transformed into the normal form? We describe the results of an experiment with PROLOG-based logic grammar which has been derived from a substantial-coverage string grammar for English. We present an alogorithm for automated inversion of a unification parser into an efficient unification generator, using the collections of minimal sets of essential arguments for predicates. We discuss the scope of the present version of the algorithm and then point out several possible avenues for extension. We also outline a preliminary solution to the question of grammar's “normal form” and suggest a handful of normalizing transformations that can be used to enhance the efficiency of the generator. This research interacts closely with a Japanese-English machine translation project at New York University, for which the first implementation of the inversion algorithm has been prepared. Ľutilisation ?une grammaire unique dans ľanalyse et la generation du langage naturel est tres souhaitable pour une multitude de raisons, dont ľefficacite, la clarte, ľintegrite, la solidite et une certaine dose ?elegance. Ces caracteristi-ques ont deja ete constatees par plusieurs chercheurs; cependant, ce n'est que tout recemment qu'une attention plus serieuse a ete portee au probleme de la creation ?un systeme bidirectionnel de traitement du langage naturel. Dans cet article, ľauteur discute ?un aspect un peu plus radical du probleme qui concerne la possibilitye?inverser le parseur ?un langage afin qu'il devienne un generateur efficace dans le měme langage. En outre, comme le parseur et le generateur sont fonction de la měme grammaire, existe-t-il des conditions de normalisation de la forme de grammaire qu'il faut respecter afin de s'assurer de ľefficacite du programme inverse? Y a-t-il ?autres gramaires qui peuvent ětre transformers en forme normale?Ľauteur decrit les resultats ?une experience avec une grammaire logique basee sur PROLOG qui est derivee ?une grammaire en chaines de langue anglaise. II propose un algorithme pour ľinversion automatique ?un parseur ?unification en generateur ?unification efficace, aľaide des ensembles minimaux ?arguments essentiels pour predicats. II discute de la portee de la version actuelle de ľalgorithme et souligne diverses possibilityes de developpement. II elabore egalement une solution preliminaire a la question de la «forme normale» de la grammaire et suggere un certain nombre de transformations qui peuvent servir a accroitre ľefficacite du generateur. Cette recherche est realisee en etroite collaboration avec un projet de traduction-machine du japonais vers ľanglais pour lequel la premiere mise en oeuvre de ľalgorithme ?inversion a ete realisee. Mots cles: traitement du langage naturel, analyse, generation, grammaire logique, grammaire reversible, arguments essentiels, predicat inverse, direction des calculs.