The Augmented Predictive Analyzer for Context-Free
Languages-Its Relative Efficiency

It has been proven by Greibach that for a given
context-free grammar G, a standard-form grammar 
Gs can be constructed, which generates the same languages
as is generated by G and whose rules are all 
of the form Z --> cY(1) ... Y(m), (m >= O) where Z and
Y(i) are intermediate symbols and c a terminal 
symbol.  Since the predictive analyzer at Harvard uses
a standard-form grammar, it can accept the language 
of any context-free Grammar G, given an equivalent standard-form
grammar Gs.  The structural descriptions 
SD(Gs,X) assigned to a given sentence X by the predictive
analyzer, however, are usually different from 
the structural descriptions SD(G,X) assigned to the
same sentence by the original context-free grammar 
G from which Gs is derived.  In Section 1, an algorithm,
originally due to Abbott is described standard-form 
grammar each of whose rules is in standard form, supplemented
by additional information describing its 
derivation from the original context-free grammar. 
A technique for performing the SD(Gs,X) to SD(G,X) 
transformation effectively is also described.  In section
2, the augmented predictive analyzer as a parsing 
algorithm for arbitrary context-free languages is compared
with two other parsing algorithms: a selective 
top-to-bottom algorithm similar to Irons' "error correcting
parse algorithm" and an immediate constituent 
analyzer which is an extension of Sakai-Cocke's algorithm
for normal grammars.  The comparison is based 
upon several criteria of efficiency, covering core-storage
requirements, complexities of the programs 
and processing time.

CACM November, 1966

Kuno,S.

CA661108 JB March 2, 1978  3:11 PM

1225	4	1350
1225	4	1350
1350	4	1350
1350	4	1350
1350	4	1350
1350	4	1350
1350	4	1350
1399	4	1350
1646	4	1350
1659	4	1350
1659	4	1350
1768	4	1350
1781	4	1350
1781	4	1350
1856	4	1350
1945	4	1350
1945	4	1350
1945	4	1350
2050	4	1350
2110	4	1350
2650	4	1350
2698	4	1350
2708	4	1350
3093	4	1350
3094	4	1350
1012	5	1350
1225	5	1350
1265	5	1350
1350	5	1350
1350	5	1350
1350	5	1350
1399	5	1350
1659	5	1350
680	5	1350
1225	6	1350
1265	6	1350
1350	6	1350
1671	6	1350
1697	6	1350