|
セシィ–ウルマン法（英: Sethi–Ullman algorithm）とは、コンパイラにおいて数式に対応したコードを生成する際に、必要な命令数やレジスタ数を最小にするアルゴリズムである。ただし前提条件として、数式内の各演算に交換法則と結合法則が成り立たなければならない。分配法則は成り立たなくてもよい。交換法則や結合法則が成り立たない場合もこのアルゴリズムを適用可能だが、その場合、数式の変形はできない。 == 単純なセシィ–ウルマン法 == セシィ–ウルマン法は次のように動作する（RISCの場合）。 # 抽象構文木を先頭からか最後尾から見ていく。 ## 定数でない葉ノードについて、1 を割り当てる（すなわち、その変数などを保持するのにレジスタが1つ必要であることを示す）。定数の葉ノードについては、0 を割り当てる。 ## 葉でないノード ''n'' について、''n'' 配下の部分木の評価に必要なレジスタ数を割り当てる。左側の部分木に必要なレジスタ数（''l''）が、右側の部分木に必要なレジスタ数（''r''）と異なる場合、現在見ているノード ''n'' が必要とするレジスタ数は ''max(l,r)'' となる。''l == r'' の場合、現在ノードが必要とするレジスタ数は ''l + 1'' となる。 # コード展開 ## ノード ''n'' の左側の部分木の計算に要するレジスタ数が右側の部分木で必要なレジスタ数より大きい場合、先に左側の部分木を評価する（対応するコードを生成する）。これは、右側を先に評価すると、その結果を保持するためのレジスタが余分に必要となって、レジスタが足りなくなる可能性が大きくなるためである。右側の部分木が左側よりもレジスタ数を多く必要とする場合、同様に右側を先に評価する。両側の必要とするレジスタ数が同じ場合、評価する順序はどちらでもよい。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「セシィ–ウルマン法」の詳細全文を読む スポンサード リンク
|