Portal de Periódicos da CAPES

Optimal Code Generation for Expression Trees

1976; Association for Computing Machinery; Volume: 23; Issue: 3 Linguagem: Inglês

10.1145/321958.321970

1557-735X

Alfred V. Aho, S. C. Johnson,

Evolutionary Algorithms and Applications

This paper discusses algorithms which transform expression trees into code for register machines. A necessary and sufficient condition for optimality of such an algorithm is derived, which applies to a broad class of machines. A dynamic programming algorithm is then presented which produces optimal code for any machine in this class; this algorithm runs in time linearly proportional to the size of the input.