On TAG Parsing
Pierre Boullier
Abstract : The subject of tree adjoining grammar parsing inspired many researches but they all failed to beat the O(n6) parse time wall. Thus, some present researches in this field try to identify efficient parser implementations either for the full grammar class, or for linguistically significant subclasses. This paper addresses both issues and proposes a method which uses range concatenation grammars as an intermediate implementation formalism. Range concatenation grammar is a syntactic formalism which is both powerful, in so far as it extends linear contextfree rewriting systems, and efficient, in so far as its sentences can be parsed in polynomial time. We show two methods by which unrestricted tree adjoining grammars can be transformed into equivalent range concatenation grammars which can be parsed in O(n 6) time, and, moreover, if the input tree adjoining grammar has some restricted form, its parse time decreases to O(n5).