Sethi–Ullman algorithm: Difference between revisions

Revision as of 01:51, 19 December 2006

Revision as of 05:27, 31 December 2006

Line 1:

When [[Code generation|generating code]] for arithmetic expressions, the [[compiler]] has to decide which is the best way to translate the expression in terms of number of instructions used as well as number of registers needed to evaluate a certain subtree (especially if free registers are scarce). The so called '''Sethi-Ullman algorithm''' (also known as '''Sethi-Ullman numbering''') fulfills the property of producing code which needs the least number of instructions possible as well as the least number of storage references (under the assumption that at the most [[commutativity]] and [[associativity]] apply to the operators used, but distributive laws likei.e. <math>a * b + a * c = a * (b + c)</math> do not hold). Please note that the algorithm succeeds as well if neither [[commutativity]] nor [[associativity]] hold for the expressions used, and therefore arithmetic transformations can not be applied.

==Simple Sethi-Ullman algorithm==