© 1973 by British Computer Society
Coordinate grammars and parsers*
Applied Mathematics Department, Twente University of Technology, Enschede, Netherlands
This paper deals with the rather classical problem of automatically generated bottom-up parsers for subsets of context-free grammars. Except for LR(k) parsers defined by Knuth, which are the most powerful for left to right translation (but considered as much to costly in space and time for practical purposes), the classical bottom-up parsers such as the precedence of the bounded right context parsers are shown to present a lack of power due to a questionable choice of the stack alphabet. Using the grammar total vocabulary as stack alphabet means that one gives account of the symbol names but not their positions in the grammar production rules.
A new alphabet is thus defined where each symbol is a pair of coordinates which represent all the possible occurrences of every symbol of the old alphabet in the grammar production rules. Such an alphabet is used by Knuth for the LR(k) parser and is explicitly defined and used by Loeckx to generate strings so as to construct a decision table for a bounded right context parser. On this simple basis, a complete algorithm is described which inputs any context-free grammar and outputs, under certain conditions, a decision table for a coordinates parser. The acceptable subset of context free grammars is shown to include strictly the bounded right context grammars subset while strictly included in the LR(k) grammars subset. Furthermore, the constructing algorithm and the resulting parser are not substantially more complex or costly than their analogs for the bounded right context grammars.
Received December 1971.
* A short version of this paper can be found in the proceedings of the third ACM Symposium on the theory of computing, Shaker Heights, Ohio, May 3-5, 1971.
Now at Department d'Informatique Numerique, Institut de Recherche d'Informatique et d'Automatique, 78 Rocquencourt, France.