Loading article…
コンピュータサイエンスにおいて、抽象意味グラフ（ASG）または項グラフとは、形式言語またはプログラミング言語の式を、その式のサブタームを頂点とするグラフで表現する抽象構文の一形式である。ASGは、式やプログラムの構文構造を表現するために使用される抽象構文木（AST）よりも高い抽象度を持つ。
ASG は、共通の部分項 (「共通部分式」とも呼ばれる) を含むことができるため、AST よりも複雑で簡潔です。[ 1 ]抽象意味グラフは、コンパイラが抽象構文木に対して共通部分式の除去を実行した結果を格納するための中間表現としてよく使用されます。AST は木であるため、共通の項を表現することはできません。ASG は通常、有向非巡回グラフ (DAG)ですが、一部のアプリケーションでは、サイクルを含むグラフが許可される場合があります。たとえば、サイクルを含むグラフは、関数型プログラミング言語で一般的に使用される非ループ反復構造としての再帰式を表現するために使用される場合があります。これらのタイプのグラフの可変性は、グラフ書き換えの分野で研究されています。
用語グラフという命名法は、書き換え規則の指定による式の変換と処理を伴う用語グラフ書き換えの分野に関連しており、[ 2 ]一方、抽象意味グラフは、言語学、プログラミング言語、型システム、コンパイルについて議論する際に使用されます。
抽象構文木は、適切な木構造ではノードが複数の親を持つことが不可能なため、部分式ノードを共有することはできません。この概念的な単純さは魅力的ですが、冗長な表現が生じ、結果として同一の項の計算が非効率的に重複する可能性があります。そのため、ASGは、構文解析によって抽象構文木を構築するための中間言語として、後続のコンパイル段階でよく使用されます。
抽象意味グラフは、通常、抽象構文木から拡張と抽象化のプロセスを経て構築されます。拡張の例としては、変数が使用されている識別子ノードからその変数の宣言を表すノードへのエッジであるバックポインタの追加が挙げられます。抽象化には、構文解析にのみ関連し、意味論には関係のない詳細の削除が含まれます。
例えば、コードのリファクタリングを考えてみましょう。入力引数を取る関数の実装を表すために、受け取ったパラメータには、参照できるようにソースコード内で慣例的に任意の固有の名前が付けられます。この概念的実体の抽象的な表現である「関数引数」インスタンスは、関数シグネチャで言及される可能性が高く、実装コード本体内でも1回以上言及されるでしょう。関数全体が、そのヘッダーまたは「シグネチャ」情報と実装本体の両方の親であるため、ASTでは、引数実体の複数の使用箇所や出現箇所を同じノードで識別することはできません。これは、ASGのDAGの性質によって解決されます。任意のコード要素に対して単一の固有のノード識別子を持つことの重要な利点は、各要素のプロパティが定義上一意に格納されることです。これにより、任意のプロパティインスタンス化に対して存在の接点が正確に1つ存在するため、リファクタリング操作が簡素化されます。開発者がコード要素の「名前」（この例では「関数引数」）などのプロパティ値を変更することにした場合、ASGは本質的にその値を1箇所にのみ公開するため、そのようなプロパティの変更は暗黙的に、容易に、そして即座にグローバルに伝播されます。
項グラフの概念は、部分項の共有と破棄に配慮した、帰納的に生成された構文の洗練を符号化する。