Classes of languages between context-free and context-sensitive ones may be of theoretical interest. From the practical point of view they might be useful also for the parsing of context-free languages. For example, a left-to-right parser for an LR(k) context-free grammar [1] has to look k symbols ahead in order to be able to apply some rule at a given place. This means, in fact, that the parser is based on a contextsensitive grammar derived from the original context-free one.
It seems useful to start directly with some kind of context sensitive grammars instead of context-free ones and make the necessary restrictions only. The parser need not know whether the grammar has previously been transformed, and thus occasionally it may be applied to real noncontext-free languages.
In this paper, right-sensitive grammars are considered, since they are natural extensions of context free ones as far as left-to-right parsing is concerned. Let F 0 ,/'1, and F 2 denote the class of context-free, unilateral context sensitive and context sensitive grammars, respectively. Then by the definitions given in this paper /'0 C F 1 C F 2 and thus, for the corresponding classes of languages ~(F0) _C ~(F1) C if(f2). It can be shown that ~~ ~(F1) , i.e., the class of unilateral contextsensitive languages properly contains the class of context-free ones . It is not known whether ~0(/'2) properly contains ~(F1).
We will call a parser left-to-right if it always performs the leftmost replacement (s) when it is attempting to reduce the input string to the initial symbol of the grammar. This may involve reverse scans so the input string is not always sequentially processed. The parser dealt with in this paper is simply a deterministic version of the general (nondeterministic) language recognition device represented in Fig. . Of course, this very basic parser can be applied as a recognizer only to a restricted class of rightsensitive grammars.
The main result of the present paper is Theorem 3, which gives sufficient conditions for the applicability of this parser. The conditions are of moderate difficulty to test for and the test would normally be done by machine. These conditions are not too