TY - JOUR
T1 - Two-sided context specifications in formal grammars
AU - Barash, Mikhail
AU - Okhotin, Alexander
PY - 2015/8/2
Y1 - 2015/8/2
N2 - 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.
AB - 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.
KW - Conjunctive grammars
KW - Context-free grammars
KW - Context-sensitive grammars
KW - Grammars with contexts
KW - Parsing
UR - http://www.scopus.com/inward/record.url?scp=84943659952&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2015.05.004
DO - 10.1016/j.tcs.2015.05.004
M3 - Article
AN - SCOPUS:84943659952
VL - 591
SP - 134
EP - 153
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -