• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

An Extension of Context-Free Grammars with One-Sided Context Specifications

Mikhail Barash, Alexander Okhotin, An Extension of Context-Free Grammars with One-Sided Context Specifications. Information and Computation 237, 268–293, 2014.

http://dx.doi.org/10.1016/j.ic.2014.03.003

Abstract:

The paper introduces an extension of context-free grammars equipped with an operator for referring to the left context of the substring being defined. For example, a rule A \to a \And \lhd B defines a symbol a, as long as it is preceded by a string defined by B. The conjunction operator in this example is taken from conjunctive grammars (Okhotin, 2001), which are an extension of ordinary context-free grammars that maintains most of their practical properties, including many parsing algorithms. This paper gives two equivalent definitions of grammars with left contexts-by logical deduction and by language equations-and establishes their basic properties, including a transformation to a normal form and a cubic-time parsing algorithm, with a square-time version for unambiguous grammars.

BibTeX entry:

@ARTICLE{jBaOk14a,
  title = {An Extension of Context-Free Grammars with One-Sided Context Specifications},
  author = {Barash, Mikhail and Okhotin, Alexander},
  journal = {Information and Computation},
  volume = {237},
  publisher = {Elsevier},
  pages = {268–293},
  year = {2014},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 3

Edit publication