# Another Facet of LIG Parsing (extended version)

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.
Keywords :
Type de document :
Rapport
[Research Report] RR-2858, INRIA. 1996
Domaine :

Littérature citée [2 références]

https://hal.inria.fr/inria-00073833
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:51:55
Dernière modification le : vendredi 25 mai 2018 - 12:02:02
Document(s) archivé(s) le : jeudi 24 mars 2011 - 13:07:11

### Identifiants

• HAL Id : inria-00073833, version 1

### Citation

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

### Métriques

Consultations de la notice

## 87

Téléchargements de fichiers