Access Restriction

Author Loeck, Jacques
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Compiler compilers ♦ Bounded-context parsing ♦ Metacompilers ♦ Bounded-context syntatic analysis ♦ Pushdown automata ♦ Formal languages ♦ Generators ♦ Parser construction ♦ Compiler writing systems ♦ Context-free grammars ♦ Syntatical analyzer construction ♦ Translator writing systems
Abstract 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.
Description Affiliation: MBLE Research Lab., Brussels, Belgium (Loeck, Jacques)
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 13
Issue Number 5
Page Count 11
Starting Page 297
Ending Page 307

Open content in new tab

   Open content in new tab
Source: ACM Digital Library