翻訳と辞書
Words near each other
・ セザール・フランク
・ セザール・フランクの楽曲一覧
・ セザール・リッツ
・ セザール・ルミンスキ
・ セザール・ルワガサナ
・ セザール・ロベルト・ロドリゲス
・ セザール賞
・ セザーレ・ラッテス
・ セザーレ・ラテス
・ セザー・フェレイラ
セシィ-ウルマン法
・ セシィ–ウルマン法
・ セシウム
・ セシウム133
・ セシウム134
・ セシウム135
・ セシウム137
・ セシウムさん
・ セシウムさん事件
・ セシウムさん騒動


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

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

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「セシィ–ウルマン法」の詳細全文を読む




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.