セシィ–ウルマン法

セシィ–ウルマン法（英: Sethi–Ullman algorithm）とは、コンパイラにおいて数式に対応したコードを生成する際に、必要な命令数やレジスタ数を最小にするアルゴリズムである。ただし前提条件として、数式内の各演算に交換法則と結合法則が成り立たなければならない。分配法則は成り立たなくてもよい。交換法則や結合法則が成り立たない場合もこのアルゴリズムを適用可能だが、その場合、数式の変形はできない。
単純なセシィ–ウルマン法.
セシィ–ウルマン法は次のように動作する（RISCの場合）。
例.
数式 formula_1 は、抽象構文木では次のように表される。
 / \
 a *
 / \
 / \ / \
 b c d 3
このアルゴリズムを適用するに当たって、数式の右辺 formula_2 のみを考慮する。すなわち、代入 '=' の右の部分木のみを参照する。
 / \
 + +
 b c d 3
木構造を（とりあえず先頭から）見ていき、各部分木の評価に必要なレジスタを割り当てていく（formula_2 の最後の被加数は定数であることに注意）。
 *2
 / \
 +2 +1
 b1 c1d1 30
この木構造から、'*' の左の部分木の計算には2つのレジスタが必要だが、右の部分木の計算には1つのレジスタだけでよいことが分かる。従って、この式を計算する時点で使っていないレジスタが2つしかない可能性もあるので、先に左側の計算を行うコードを生成する。レジスタを1つしか必要としない右側の部分木を計算するコードを先に生成すると、左側の計算をする間、右の計算結果を保持しておくレジスタが必要となり、全部で3つのレジスタが必要となってしまう。先に左側を計算するには2つのレジスタが必要だが、結果の保持には1つのレジスタがあればよいので、右の計算に必要な1つのレジスタと合わせても、2つのレジスタがあれば全体を計算可能である。
改良版.
セシィ-ウルマン法の改良として、使われている演算の代数的性質を利用して、数式を最初に変換する手法がある。