Sethi–Ullman algorithm: Difference between revisions

Content deleted Content added
Tezeti (talk | contribs)
destubified; is longer than a stub
Removed cyclic redierect
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 laws like <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==