### 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(n4), where n is the length of the input string.

Original language | English |
---|---|

Pages (from-to) | 134-153 |

Number of pages | 20 |

Journal | Theoretical Computer Science |

Volume | 591 |

DOIs | |

Publication status | Published - 2 Aug 2015 |

### Fingerprint

### Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Theoretical Computer Science*,

*591*, 134-153. https://doi.org/10.1016/j.tcs.2015.05.004