A1 Refereed original research article in a scientific journal

Two-sided context specifications in formal grammars




AuthorsBarash M, Okhotin A

PublisherELSEVIER SCIENCE BV

Publication year2015

JournalTheoretical Computer Science

Journal name in sourceTHEORETICAL COMPUTER SCIENCE

Journal acronymTHEOR COMPUT SCI

Volume591

Issue2

First page 134

Last page153

Number of pages20

ISSN0304-3975

DOIhttps://doi.org/10.1016/j.tcs.2015.05.004(external)


Abstract

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(n(4)), where n is the length of the input string. (C) 2015 Elsevier B.V. All rights reserved.




Last updated on 2024-26-11 at 17:51