Another Facet of LIG Parsing (extended version) - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1996

Another Facet of LIG Parsing (extended version)

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-2858.pdf (337.63 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00073833 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00073833 , version 1

Citer

Pierre Boullier. Another Facet of LIG Parsing (extended version). [Research Report] RR-2858, INRIA. 1996. ⟨inria-00073833⟩
53 Consultations
45 Téléchargements

Partager

Gmail Facebook X LinkedIn More