Another Facet of LIG Parsing

Another Facet of LIG Parsing Pierre Boullier INRIA-Rocquencourt BP 105 78153 Le Chesnay Cedex, France Pierre. Boullier@inria. fr Abstract In this paper 1 we present a new pars- ing algorithm for linear indexed grammars (LIGs) in the same spirit as the one de- scribed in (Vijay-Shanker and Weir, 1993) for tree adjoining grammars. For a LIG L and an input string x of length n, we build a non ambiguous context-free grammar whose sentences are all (and exclusively) valid derivation sequences in L which lead to x. We show that this grammar can be built in (9(n 6) time and that individ- ual parses can be extracted in linear time with the size of the extracted parse tree. Though this O(n 6) upper bound does not improve over previous results, the average case behaves much better. Moreover, prac- tical parsing times can be decreased by some statically performed computations. 1 Introduction The class of mildly context-sensitive languages can be described by several equivalent grammar types. Among these types we can notably cite tree adjoin- ing grammars (TAGs) and linear indexed grammars (LIGs). In (Vijay-Shanker and Weir, 1994) TAGs are transformed into equivalent LIGs. Though context-sensitive linguistic phenomena seem to be more naturally expressed in TAG formalism, from a computational point of view, many authors think that LIGs play a central role and therefore the un- derstanding of LIGs and LIG parsing is of impor- tance. For example, quoted from (Schabes and Shieber, 1994) "The LIG version of TAG can be used for recognition and parsing. Because the LIG for- malism is based on augmented rewriting, the pars- ing algorithms can be much simpler to understand 1See (Boullier, 1996) for an extended version. 87 and easier to modify, and no loss of generality is in- curred". In (Vijay-Shanker and Weir, 1993) LIGs are used to express the derivations of a sentence in TAGs. In (Vijay-Shanker, Weir and Rainbow, 1995) the approach used for parsing a new formalism, the D-Tree Grammars (DTG), is to translate a DTG into a Linear Prioritized Multiset Grammar which is similar to a LIG but uses multisets in place of stacks. LIGs can be seen as usual context-free grammars (CFGs) upon which constraints are imposed. These constraints are expressed by stacks of symbols as- sociated with non-terminals. We study parsing of LIGs, our goal being to define a structure that ver- ifies the LIG constraints and codes all (and exclu- sively) parse trees deriving sentences. Since derivations in LIGs are constrained CF derivations, we can think of a scheme where the CF derivations for a given input are expressed by a shared forest from which individual parse trees which do not satisfied the LIG constraints are erased. Unhappily this view is too simplistic, since the erasing of individual trees whose parts can be shared with other valid trees can only be performed after some unfolding (unsharing) that can produced a forest whose size is exponential or even unbounded. In (Vijay-Shanker and Weir, 1993), the context- freeness of …

Content truncated to 500 words