Two-sided context specifications in formal grammars

Mikhail Barash, Alexander Okhotin

Результат исследований: Научные публикации в периодических изданияхстатьярецензирование

7 Цитирования (Scopus)


In a recent paper (M. Barash, A. Okhotin, "An extension of context-free grammars with one-sided context specifications", Inform. and Comput., 2014), the authors introduced an extension of the context-free grammars equipped with an operator for referring to the left context of the substring being defined. This paper proposes a more general model, in which context specifications may be two-sided, that is, both the left and the right contexts can be specified by the corresponding operators. The paper gives the definitions, presents several examples of grammars and establishes a basic normal form theorem. This normal form, in particular, leads to a simple parsing algorithm working in time O(n4), where n is the length of the input string.

Язык оригиналаанглийский
Страницы (с-по)134-153
Число страниц20
ЖурналTheoretical Computer Science
СостояниеОпубликовано - 2 авг 2015

Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)


Подробные сведения о темах исследования «Two-sided context specifications in formal grammars». Вместе они формируют уникальный семантический отпечаток (fingerprint).