An Algorithm for the Construction Of Bounded-Context Parsers

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 discuss
ed 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.

CACM May, 1970

Loeckx, J.

bounded-context parsing, bounded-context syntactic analysis, parser 
construction, syntactical analyzer construction, generators, compiler 
compilers, compiler writing systems, translator writing systems metacompilers,
context-free grammars, formal languages, pushdown automata

4.12 5.22 5.23

CA700505 JB February 13, 1978  1:58 PM

1379	4	2061
1491	4	2061
1496	4	2061
1542	4	2061
1683	4	2061
1683	4	2061
1693	4	2061
1693	4	2061
1768	4	2061
1781	4	2061
1781	4	2061
1781	4	2061
1787	4	2061
1787	4	2061
1836	4	2061
1836	4	2061
1945	4	2061
1945	4	2061
1945	4	2061
2015	4	2061
2060	4	2061
2060	4	2061
2061	4	2061
2061	4	2061
2061	4	2061
2061	4	2061
2061	4	2061
2061	4	2061
2082	4	2061
2091	4	2061
2091	4	2061
2152	4	2061
2179	4	2061
2179	4	2061
2179	4	2061
2340	4	2061
2356	4	2061
2546	4	2061
2546	4	2061
2603	4	2061
2698	4	2061
2698	4	2061
2708	4	2061
2708	4	2061
2824	4	2061
2982	4	2061
2986	4	2061
3045	4	2061
3045	4	2061
3093	4	2061
1140	5	2061
1141	5	2061
1477	5	2061
1491	5	2061
1825	5	2061
2061	5	2061
2061	5	2061
2061	5	2061
773	5	2061