An algorithm for coding efficient arithmetic operations

Publisher Website
Google Scholar
Abstract
Most existing formula transbttion schemes yield inefficient coding. A method is described which reduces the mmfl)er of store and fetch operai>ions, evaluates constant sub- expressions during compilation, t~tl(( recognizes m~my equiwdent subexpressions. Most previously published algorithms for formula trans- lation depend uport a left-to-right scan of the formula, during which each symbol encountered either causes generation of coding or is saved on a list until it can be correctly interpreted in context. An exception is the GAT translator, which scans from right to left. In coding arith- metic operators for machines with accumulators (i.e., one- or two-address machines), right-to-left scans potcntiMly generate more efficient eoding than left-to-right scans. The reason can be seen by considering the formula x := (u 0~ v)/(y 0~ z), where the O's a.re orbit,tory arithmetic operators, each inn- plemented by a single machine instruction. The symbolic coding for a typical one-~Mdress machine generated by both Iypes of scan is shown t)elow: Left4o-right Right-to-left CLA u

This publication has 4 references indexed in Scilit: