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