Parsing Directed Acyclic Graphs with Range Concatenation Grammars

Pierre Boullier 1 Benoît Sagot 1
1 ALPAGE - Analyse Linguistique Profonde à Grande Echelle ; Large-scale deep linguistic processing
Inria Paris-Rocquencourt, UPD7 - Université Paris Diderot - Paris 7
Abstract : Range Concatenation Grammars (RCGs) are a syntactic formalism which possesses many attractive properties. It is more powerful than Linear Context-Free Rewriting Systems, though this power is not reached to the detriment of efficiency since its sentences can always be parsed in polynomial time. If the input, instead of a string, is a Directed Acyclic Graph (DAG), only simple RCGs can still be parsed in polynomial time. For non-linear RCGs, this polynomial parsing time cannot be guaranteed anymore. In this paper, we show how the standard parsing algorithm can be adapted for parsing DAGs with RCGs, both in the linear (simple) and in the non-linear case.
Type de document :
Communication dans un congrès
International Conference on Parsing Technologies (IWPT 2009), 2009, Paris, France. 2009
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00616690
Contributeur : Benoît Sagot <>
Soumis le : mardi 23 août 2011 - 23:01:14
Dernière modification le : samedi 9 juin 2018 - 10:30:06
Document(s) archivé(s) le : vendredi 25 novembre 2011 - 12:03:18

Fichier

iwpt09rcg.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00616690, version 1

Collections

Citation

Pierre Boullier, Benoît Sagot. Parsing Directed Acyclic Graphs with Range Concatenation Grammars. International Conference on Parsing Technologies (IWPT 2009), 2009, Paris, France. 2009. 〈inria-00616690〉

Partager

Métriques

Consultations de la notice

121

Téléchargements de fichiers

100