Linear-space recognition for grammars with contexts

A1 Originalartikel i en vetenskaplig tidskrift (referentgranskad)

Interna författare/redaktörer

Publikationens författare: Barash M, Okhotin A
Publiceringsår: 2018
Tidskrift: Theoretical Computer Science
Tidskriftsakronym: THEOR COMPUT SCI
Volym: 719
Artikelns första sida, sidnummer: 73
Artikelns sista sida, sidnummer: 85
Antal sidor: 13
ISSN: 0304-3975


Grammars with contexts are an extension of context-free grammars equipped with operators for referring to the left and the right contexts of a substring being defined. These grammars are notable for still having a cubic-time parsing algorithm, as well as for being able to describe some useful syntactic constructs, such as declaration before use. It is proved in this paper that every language described by a grammar with contexts can be recognized in deterministic linear space. (C) 2017 Elsevier By. All rights reserved.


Conjunctive grammars, Context-free grammars, Context-sensitive grammars, Parsing, Space complexity

Senast uppdaterad 2019-15-12 vid 03:12