Access Restriction

Author Kuno, Susumu
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Abstract 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
Description Affiliation: Harvard Univ., Cambridge, MA (Kuno, Susumu)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 9
Issue Number 11
Page Count 14
Starting Page 810
Ending Page 823

Open content in new tab

   Open content in new tab
Source: ACM Digital Library