Formal Parsing Systems Automatic syntactic analysis has recently become important for both natural language data processing and syntax-directed compilers. A formal parsing system G = (V,u,T,R) consists of two finite disjoint vocabularies, V and T, a many-many map, u, from V onto T, and a recursive set R of strings in T called syntactic sentence classes. Every program for automatic syntactic analysis determines a formal parsing system. A directed production analyzer (I,T,X,p) is a nondeterministic pushdown-store machine with internal vocabulary I, input vocabulary T, and all productions of p in the form: (Z,a) -> aY1 ... Ym where Z, Yi are elements of the set I and a is an element of the set T. Every context-free language can be analyzed by a directed production analyzer. The Kuno-Oettinger multiple-path syntactic analyzer for English is a concrete example of a directed production analyzer and of a working parsing algorithm. The connection between structures assigned by the analyzer and those of a conventional phrase structure grammar is examined in this paper. CACM August, 1964 Greibach, S. A. CA640818 JB March 9, 1978 6:30 PM 1012 5 1012 1012 5 1012 1012 5 1012 1225 5 1012 1350 5 1012 1945 5 1012 823 6 1012 914 6 1012 915 6 1012 917 6 1012 984 6 1012 989 6 1012 990 6 1012 1012 6 1012 1012 6 1012 1012 6 1012 1084 6 1012 1098 6 1012 1122 6 1012 1138 6 1012 1139 6 1012 1141 6 1012 1200 6 1012 1223 6 1012 1225 6 1012 1265 6 1012 1265 6 1012 1336 6 1012 1396 6 1012 1399 6 1012 1455 6 1012 1477 6 1012 1487 6 1012 1491 6 1012 1496 6 1012 483 6 1012 584 6 1012 669 6 1012 680 6 1012 680 6 1012 680 6 1012 763 6 1012