Optimal code generation for expression trees
AV Aho, SC Johnson - Journal of the ACM (JACM), 1976 - dl.acm.org
AV Aho, SC Johnson
Journal of the ACM (JACM), 1976•dl.acm.orgThis 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.
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.
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.