The augmented predictive analyzer for context-free languages—its relative efficiency
Susumu Kuno · Communications of the ACM · 1966
It has been proven by Greibach that for a given context-free grammar G, a standard-form grammar G s , can be constructed, which generates the same language as is generated by G and whose rules are all of the form Z → cY 1 ··· Y m ( m ≥ 0) 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 G s . The structural descriptions SD ( G s , χ ) assigned to a given sentence χ by the predictive analyzer, however, are usually different from the structural descriptions SD ( G, χ ) assigned to the same sentence by the original context-free grammar G from which G s is derived. In Section 1, an algorithm, originally due to Abbott is described, which converts a given context-free grammar into an augmented 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 ( G s , χ ) to SD ( G, χ ) 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