On the Relative Efficiencies of Context-Free Grammar Recognizers

A number of diverse recognition procedures
that have been proposed for parsing sentences with 
respect to a context-free grammar are described in this
paper by means of a common device.  Each procedure 
is defined by giving an algorithm for obtaining a nondeterministic
Turing Machine recognizer that is 
equivalent to a given context-free grammar.  The formalization
of the Turing Machine has been chosen 
to make possible particularly simple description of
the parsing procedures considered.  An attempt has 
been made to compare recognition efficiencies for the
procedures defined.  For a few simple grammars 
and sentences a formal comparison has been made.  Empirical
comparison of the recognition of more realistic 
programming languages such as LISP and ALGOL has been
made by means of a program which simulates the 
Turing Machine on the Univac M-460 computer.  Several
algorithms for producing grammars equivalent to 
a given context-free grammar have been considered, and
the increase in recognition efficiency they afford 
has been empirically investigated.

CACM May, 1965

Griffiths, T. V.
Petrick, S. R.

CA650506 JB March 7, 1978  2:38 PM

1046	4	1265
1062	4	1265
1086	4	1265
1105	4	1265
1121	4	1265
1132	4	1265
1139	4	1265
1139	4	1265
1139	4	1265
1140	4	1265
1151	4	1265
1234	4	1265
1234	4	1265
1263	4	1265
1263	4	1265
1265	4	1265
1265	4	1265
1265	4	1265
1265	4	1265
1265	4	1265
1270	4	1265
1323	4	1265
1358	4	1265
1379	4	1265
1380	4	1265
1453	4	1265
1464	4	1265
1484	4	1265
1491	4	1265
1496	4	1265
1498	4	1265
1613	4	1265
1614	4	1265
1665	4	1265
1781	4	1265
1781	4	1265
1781	4	1265
1824	4	1265
1825	4	1265
1860	4	1265
2083	4	1265
2126	4	1265
2178	4	1265
2179	4	1265
2252	4	1265
2325	4	1265
2341	4	1265
2546	4	1265
2546	4	1265
464	4	1265
2645	4	1265
2652	4	1265
2684	4	1265
2769	4	1265
2842	4	1265
2929	4	1265
2934	4	1265
584	4	1265
3069	4	1265
631	4	1265
653	4	1265
669	4	1265
679	4	1265
680	4	1265
691	4	1265
720	4	1265
759	4	1265
761	4	1265
763	4	1265
763	4	1265
795	4	1265
799	4	1265
945	4	1265
949	4	1265
989	4	1265
1265	5	1265
1265	5	1265
1265	5	1265
1350	5	1265
1399	5	1265
1659	5	1265
1768	5	1265
1781	5	1265
1945	5	1265
2110	5	1265
404	5	1265
464	5	1265
3094	5	1265
3184	5	1265
631	5	1265
635	5	1265
823	6	1265
123	6	1265
196	6	1265
914	6	1265
915	6	1265
917	6	1265
919	6	1265
984	6	1265
989	6	1265
990	6	1265
990	6	1265
1007	6	1265
1012	6	1265
1012	6	1265
1046	6	1265
1084	6	1265
1098	6	1265
1122	6	1265
1131	6	1265
1138	6	1265
1139	6	1265
1139	6	1265
1140	6	1265
1141	6	1265
1141	6	1265
1149	6	1265
1198	6	1265
1200	6	1265
1215	6	1265
1223	6	1265
1223	6	1265
1225	6	1265
1225	6	1265
1265	6	1265
1265	6	1265
1265	6	1265
1265	6	1265
1265	6	1265
1265	6	1265
1265	6	1265
1265	6	1265
1303	6	1265
1323	6	1265
1336	6	1265
1350	6	1265
1358	6	1265
1366	6	1265
1396	6	1265
1399	6	1265
1421	6	1265
1455	6	1265
1460	6	1265
1462	6	1265
1463	6	1265
1467	6	1265
1468	6	1265
1477	6	1265
1477	6	1265
1487	6	1265
1491	6	1265
1491	6	1265
1496	6	1265
1496	6	1265
1531	6	1265
1535	6	1265
1565	6	1265
1601	6	1265
1602	6	1265
1613	6	1265
1614	6	1265
1626	6	1265
1641	6	1265
1671	6	1265
1697	6	1265
1781	6	1265
1781	6	1265
1787	6	1265
1788	6	1265
205	6	1265
224	6	1265
249	6	1265
288	6	1265
316	6	1265
381	6	1265
398	6	1265
11	6	1265
2179	6	1265
2645	6	1265
404	6	1265
410	6	1265
463	6	1265
464	6	1265
483	6	1265
483	6	1265
3184	6	1265
3188	6	1265
584	6	1265
584	6	1265
600	6	1265
669	6	1265
680	6	1265
680	6	1265
680	6	1265
691	6	1265
763	6	1265
763	6	1265
799	6	1265