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