Skip to Main content Skip to Navigation

Another Facet of LIG Parsing (extended version)

Pierre Boullier 1 
Abstract : In this paper we present a new parsing algorithm for linear indexed grammars (LIGs) in the same spirit as the one described in (Vijay-Shanker et 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 ${\cal O}(n^6)$ time and that individual parses can be extracted in linear time with the size of the extracted parse tree. Though this ${\cal O}(n^6)$ 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.
Document type :
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 1:51:55 PM
Last modification on : Thursday, February 3, 2022 - 11:14:19 AM
Long-term archiving on: : Thursday, March 24, 2011 - 1:07:11 PM


  • HAL Id : inria-00073833, version 1



Pierre Boullier. Another Facet of LIG Parsing (extended version). [Research Report] RR-2858, INRIA. 1996. ⟨inria-00073833⟩



Record views


Files downloads