Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Defining Contexts in Context-F...

Defining Contexts in Context-Free Grammars

Alexander Okhotin, Mikhail Barash, Defining Contexts in Context-Free Grammars. TUCS Technical Reports 1025, Turku Centre for Computer Science, 2012.

Abstract:

Conjunctive grammars (Okhotin, 2001) are an extension of the standard context-free grammars with a conjunction operation, which maintains most of their practical properties, including many parsing algorithms. This paper introduces a further extension to the model, which is equipped with quantifiers for referring to the left context, in which the substring being defined does occur. For example, a rule $A \to a \& \triangleleft B$ defines a string $a$, as long as it is preceded by any string defined by $B$. The paper gives two equivalent definitions of the model---by logical deduction and by language equations---and establishes its basic properties, including a transformation to a normal form, a cubic-time parsing algorithm, and another recognition algorithm working in linear space.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tOkBa11a,
  title = {Defining Contexts in Context-Free Grammars},
  author = {Okhotin, Alexander and Barash, Mikhail},
  number = {1025},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2012},
  keywords = {context-free grammars, conjunctive grammars, contexts, context-sensitive grammars, parsing},
  ISBN = {978-952-12-2662-5},
}

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

Edit publication