Skip to Main content Skip to Navigation
Conference papers

Grammars for Document Spanners

Liat Peterfreund 1, 2, 3
3 VALDA - Value from Data
DI-ENS - Département d'informatique - ENS Paris, Inria de Paris
Abstract : We propose a new grammar-based language for defining information-extractors from documents (text) that is built upon the well-studied framework of document spanners for extracting structured data from text. While previously studied formalisms for document spanners are mainly based on regular expressions, we use an extension of context-free grammars, called extraction grammars, to define the new class of context-free spanners. Extraction grammars are simply context-free grammars extended with variables that capture interval positions of the document, namely spans. While regular expressions are efficient for tokenizing and tagging, context-free grammars are also efficient for capturing structural properties. Indeed, we show that context-free spanners are strictly more expressive than their regular counterparts. We reason about the expressive power of our new class and present a pushdown-automata model that captures it. We show that extraction grammars can be evaluated with polynomial data complexity. Nevertheless, as the degree of the polynomial depends on the query, we present an enumeration algorithm for unambiguous extraction grammars that, after quintic preprocessing, outputs the results sequentially, without repetitions, with a constant delay between every two consecutive ones.
Document type :
Conference papers
Complete list of metadata
Contributor : Liat Peterfreund Connect in order to contact the contributor
Submitted on : Friday, January 8, 2021 - 4:27:40 PM
Last modification on : Tuesday, January 11, 2022 - 11:16:06 AM
Long-term archiving on: : Friday, April 9, 2021 - 7:21:53 PM


Files produced by the author(s)


  • HAL Id : hal-03104144, version 1



Liat Peterfreund. Grammars for Document Spanners. ICDT 2021 - 24th International Conference on Extending Database Technology, Mar 2021, Nicosia / Virtual, Cyprus. ⟨hal-03104144⟩



Les métriques sont temporairement indisponibles