## 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