Context-Sensitive Parsing This paper presents a canonical form for context-sensitive derivations and a parsing algorithm which finds each context-sensitive analysis once and only once. The amount of memory required by the algorithm is essentially no more than the required to store a single complete derivation. In addition, a modified version of the basic algorithm is presented which blocks infinite analyses for grammars which contain loops. The algorithm is also compared with several previous parsers for context-sensitive grammars and general rewriting systems, and the difference between the two types of analyses is discussed. The algorithm appears to be complementary to an algorithm by S. Kuno in several respects, including the space-time trade-off and the degree of context dependence involved. CACM July, 1970 Woods, W. A. context-sensitive grammars, context-sensitive parsing, formal grammars, formal language theory, parsing, parsing algorithms, recognition algorithms 3.42 5.22 5.23 CA700707 JB February 10, 1978 4:43 PM 2030 5 2030 2030 5 2030 2030 5 2030