Parsing Directed Acyclic Graphs with Range Concatenation Grammars - Archive ouverte HAL Access content directly
Conference Papers Year : 2009

Parsing Directed Acyclic Graphs with Range Concatenation Grammars

(1) , (1)
1

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.
Fichier principal
Vignette du fichier
iwpt09rcg.pdf (146.27 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00616690 , version 1 (23-08-2011)

Identifiers

  • HAL Id : inria-00616690 , version 1

Cite

Pierre Boullier, Benoît Sagot. Parsing Directed Acyclic Graphs with Range Concatenation Grammars. International Conference on Parsing Technologies (IWPT 2009), 2009, Paris, France. ⟨inria-00616690⟩
59 View
82 Download

Share

Gmail Facebook Twitter LinkedIn More