tailieunhanh - Báo cáo khoa học: "Another Facet of LIG Parsing"

In this paper 1 we present a new parsing algorithm for linear indexed grammars (LIGs) in the same spirit as the one described 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 individual parses can be extracted in linear time with the size of the extracted parse tree. Though this O(n. | Another Facet of LIG Parsing Pierre Boullier INRIA-Rocquencourt BP 105 78153 Le Chesnay Cedex France Abstract In this paper1 we present a new parsing algorithm for linear indexed grammars LIGs in the same spirit as the one described 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 O n6 time and that individual parses can be extracted in linear time with the size of the extracted parse tree. Though this ỡ n6 upper bound does not improve over previous results the average case behaves much better. Moreover practical 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 adjoining 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 understanding of LIGs and LIG parsing is of importance. For example quoted from Schabes and Shieber 1994 The LIG version of TAG can be used for recognition and parsing. Because the LIG formalism is based on augmented rewriting the parsing algorithms can be much simpler to understand rSee Boullier 1996 for an extended version. and easier to modify and no loss of generality is incurred . In Vijay-Shanker and Weir 1993 LIGs are used to express the derivations of a sentence in TAGs. In Vijay-Shanker Weir and Rambow 1995 the approach used for parsing a new formalism the D-Tree Grammars DTG is to translate a DTG into a Linear Prioritized Multiset .