By Susumu Kuno
Communications of the ACM,
November 1966,
Vol. 9 No. 11, Pages 810-823
10.1145/365876.365915
Comments
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 language as is generated by G and whose rules are all of the form Z→ cY1 ··· Ym (m ≥ 0) where Z and Yi 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, &khgr;) assigned to a given sentence &khgr; by the predictive analyzer, however, are usually different from the structural descriptions SD(G, &khgr;) 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, 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(Gs, &khgr;) to SD(G, &khgr;) 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
The full text of this article is premium content
No entries found
Log in to Read the Full Article
Need Access?
Please select one of the options below for access to premium content and features.
Create a Web Account
If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.
Join the ACM
Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.
Subscribe to Communications of the ACM Magazine
Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.
Purchase the Article
Non-members can purchase this article or a copy of the magazine in which it appears.
