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