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.

Original languageEnglish
Pages (from-to)73-85
Number of pages13
JournalTheoretical Computer Science
Volume719
DOIs
StatePublished - 6 Apr 2018

    Research areas

  • Conjunctive grammars, Context-free grammars, Context-sensitive grammars, Parsing, Space complexity, SPECIFICATIONS, BOOLEAN GRAMMARS, COMPLEXITY, ONE-SIDED CONTEXTS, TRELLIS AUTOMATA, TIME

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 33856828