Skip to Main content Skip to Navigation
Conference papers

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
UPD7 - Université Paris Diderot - Paris 7, Inria Paris-Rocquencourt
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/inria-00616690
Contributor : Benoît Sagot Connect in order to contact the contributor
Submitted on : Tuesday, August 23, 2011 - 11:01:14 PM
Last modification on : Thursday, February 11, 2021 - 2:38:02 PM
Long-term archiving on: : Friday, November 25, 2011 - 12:03:18 PM

File

iwpt09rcg.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨inria-00616690⟩

Share

Metrics

Record views

227

Files downloads

354