By Jacques Loeck
Communications of the ACM,
May 1970,
Vol. 13 No. 5, Pages 297-307
10.1145/362349.362359
Comments
An algorithm is described which accepts an arbitrary context-free grammar and constructs a bounded-context parser for it whenever such a parser exists.
In the first part of the paper the definition of a context-free grammar and the working of a bounded-context parser are recalled. The notion of reduction class for a context-free grammar is then introduced and its connection with the structure of a bounded-context parser is indicated. Next, pushdown automata which generate the different reduction classes of a context-free grammar are defined. Finally, the algorithm is described; it essentially carries out an exhaustive study of all possible runs of the pushdown automata generating the reduction classes.
In the second part, the utility of the algorithm is discussed in the light of the experience gained from its use in compiler design. The algorithm is claimed to be particularly useful in the simultaneous design of a language and a compiler for it.
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.
