Back to Search
Start Over
An extension of context-free grammars with one-sided context specifications.
- Source :
-
Information & Computation . Oct2014, Vol. 237, p268-293. 26p. - Publication Year :
- 2014
-
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→a& 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08905401
- Volume :
- 237
- Database :
- Academic Search Index
- Journal :
- Information & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 97161695
- Full Text :
- https://doi.org/10.1016/j.ic.2014.03.003