A Technique for Generating Almost Optimal
Floyd-Evans Productions for Precedence Grammars

A technique is developed for generating almost optimal Floyd-Evans productions 
given a precedence grammar. A graph formulation is used for the problem of 
merging productions.  The productions generated correspond to the minimum cost 
inverse-arborescence of that graph.  The validity of the technique is
demonstrated for weak precedence grammars defined here, but the productions
mechanically generated for any precedence grammar can often be modified in 
such a way that correct, almost optimal parsers are obtained.

CACM August, 1970

Ichbiah, J. D.
Morse, S. P.

translator writing systems, syntactic analysis, Floyd-Evans
productions, precedence grammars, translator optimization,
merger algorithm, minimum cost inverse-arborescence, graph theory

4.12 5.23 5.32

CA700806 JB February 10, 19783:38 PM

1379	4	2015
1665	4	2015
1693	4	2015
1768	4	2015
1781	4	2015
1787	4	2015
1824	4	2015
1825	4	2015
1836	4	2015
1836	4	2015
1861	4	2015
1945	4	2015
2015	4	2015
2015	4	2015
2060	4	2015
2061	4	2015
2091	4	2015
2110	4	2015
2127	4	2015
2179	4	2015
2187	4	2015
2317	4	2015
2545	4	2015
2546	4	2015
2698	4	2015
2698	4	2015
2708	4	2015
2733	4	2015
3045	4	2015
1477	5	2015
1781	5	2015
2015	5	2015
2015	5	2015
2015	5	2015
2179	5	2015
2423	5	2015
1337	6	2015
1477	6	2015
1491	6	2015
1825	6	2015
2015	6	2015
2015	6	2015
2110	6	2015
3184	6	2015