An algorithm for the construction of bounded-context parsers
By Jacques Loeck
Communications of the ACM,
Vol. 13 No. 5, Pages 297-307
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
Purchase the Article
Create a Web Account
If you are an ACM member, Communications subscriber, Digital Library subscriber, or use your institution's subscription, please set up a web account to access premium content and site
features. If you are a SIG member or member of the general public, you may set up a web account to comment on free articles and sign up for email alerts.