RR-3668 : On TAG and Multicomponent TAG Parsing

Abstract : The notion of mild context-sensitivity is an attempt to express the formal power needed to define the syntax of natural languages. However, all incarnati- ons of mildly context-sensitive formalisms are not equivalent. On the one hand, near the bottom of the hierarchy, we find tree adjoining grammars and, on the other hand, near the top of the hierarchy, we find multicomponent tree adjoining grammars. This paper proposes a polynomial parse time method for these two tree rewriting formalisms. This method uses range concatenation grammars as a high-level intermediate definition formalism, and yields several algorithms. Range concatenation grammar is a syntactic formalism which is both powerful, in so far as it extends linear context-free rewriting systems, and efficient, in so far as its sentences can be parsed in polynomial time. We show that any unrestricted tree adjoining grammar can be transformed into an equivalent range concatenation grammar which can be parsed in O(n6) time, and, moreover, if the input tree adjoining grammar has some restricted form, its parse time decreases to O(n5). We generalize one of these algorithms in order to process multicomponent tree adjoining grammars. We show some upper bounds on their parse times, and we introduce a hierarchy of restricted forms which can be parsed more efficiently. Our approach aims at giving both a new insight into the multicomponent adjunction mechanism and at providing a practical implementation scheme.

Résumé : La notion de formalismes faiblements contextuels correspond à une tentative pour exprimer le pouvoir formel dont on a besoin pour définir la syntaxe des langues naturelles. Cependant, toutes les incarnations de ces formalismes ne sont pas équivalentes. D'un côté, en bas de la hiérarchie, on trouve les grammaires d'arbres adjoints et, d'un autre côté, vers le haut de cette hiérarchie, on trouve les grammaires d'arbres adjoints ensemblistes. Ce rapport propose une méthode d'analyse pour ces deux formalismes de réécriture d'arbres. Cette méthode, qui se décline en plusieurs algorithmes, utilise les grammaires à concaténation d'intervalles comme formalisme de définition intermédiaire de haut niveau. La grammaire à concaténation d'intervalles est un formalisme syntaxique qui est à la fois puissant, puisqu'il étend les systèmes de réécriture non contextuels linéaires et efficace, puisque ses phrases peuvent être analysées en temps polynomial. Nous montrons que toute grammaire d'arbres adjoints, sans restrictions, peut être analysée en temps O(n6) et que, de plus, si la grammaire d'arbres adjoints source a une certaine forme restreinte, le temps d'analyse diminue en O(n5). On généralise l'un de ces algorithmes au traitement des grammaires d'arbres adjoints ensemblistes. On montre des bornes supérieures pour le temps d'analyse des grammaires d'arbres adjoints ensemblistes et l'on introduit une hiérarchie de formes restreintes qui bénéficient d'un temps d'analyse moindre. Le but de notre approche est double¸: proposer une nouvelle façon d'appréhender le méchanisme d'adjonction ensembliste et fournir un schéma d'implantation réaliste.

RR-3668 - On TAG and Multicomponent TAG Parsing