The gap between context-sensitive languages and context-free languages (types 1 and 2 in the Chomsky hierarchy) has been a rich area of research in formal language theory for the past five decades, giving rise to such mildly context-sensitive mechanisms as tree-adjoining grammars and, more recently, the second author’s conjunctive and Boolean grammars. Barash and Okhotin provide a thorough and eminently readable description of a new formalism that effectively and intuitively captures the notion of one-sided context.

The authors introduce two new (but equivalent) operators representing what they call “left context” and “extended left context.” These, along with the conjunction operator (from Okhotin’s conjunctive grammars) and the usual disjunction operator from context-free grammars, permit simple and intuitively clear specifications of many non-context-free conditions such as the declare-before-use requirement of many modern programming languages. In a separate publication, Barash has even provided a grammar for a simple typed language to illustrate how this new approach allows one to specify common semantic restrictions such as declaration before use and matching of formal and actual parameters in a function invocation [1].

In a presentation that parallels the usual explication of context-free languages, the authors discuss parse trees, alternative formulations (via deduction systems and language equations), normal forms, ambiguity, and parsing algorithms, concluding with a cubic parsing algorithm for general grammars with one-sided context and a quadratic algorithm for unambiguous grammars.

A number of fascinating unsolved questions are posed in the conclusion. For example, it is not yet know whether grammars with one-sided context are any more expressive than conjunctive grammars or whether the notion of inherent ambiguity applies to any of the languages generated by grammars with one-sided context.

A lengthy and comprehensive bibliography traces the development of language classes that contain the context-free languages. This paper is highly recommended for anyone interested in formal language theory or programming languages and their specification.