用語グラフ

項グラフは、頂点が項である一般化されたグラフとして形式言語の式を表現したものだ^[^明確化^]。^[1]項グラフは、共通の部分式 (つまり、有向非巡回グラフの構造をとることができる) だけでなく、巡回/再帰的な部分式 (巡回有向グラフ) も表現できるため、式ツリーよりも強力な表現形式である。

抽象構文木は、各ツリーノードが 1 つの親しか持てないため、共有部分式を表すことができません。この単純さは、同一の用語の重複した計算により効率性を犠牲にしています。このため、用語グラフは、構文解析による抽象構文木の構築の後続のコンパイル段階で中間言語としてよく使用されます。

「項グラフ書き換え」という語句は、形式言語の表現を変換するためのグラフ書き換え法について議論するときによく使用されます。^[2]グラフ文法の観点から見ると、項グラフは通常のグラフではなく、n項単語が最初に特定のサブグラフを持ち、2番目に別のサブグラフを持つ、というように続くハイパーグラフであり、グラフ理論で研究される通常の無向グラフには存在しない区別です。

項グラフはプログラミング言語研究の重要なトピックです。項グラフの書き換え規則はコンパイラの操作的意味を形式的に表現できるためです。項グラフは、化学計算や生物学計算、並行モデルなどのグラフィカル計算をモデル化できる抽象マシンとしても使用されます。項グラフは、一階述語論理で量化されたステートメントを表現するのに適しているため、自動検証や論理プログラミングを実行できます。記号プログラミングソフトウェアは項グラフのもう 1 つのアプリケーションであり、グループ、体、環などの抽象的な代数構造を表現して計算を実行できます。

TERMGRAPHカンファレンス^[3]は、項グラフの書き換えとその応用に関する研究に特化しています。

項グラフは型推論にも使用され、グラフ構造は型の統一の実装に役立ちます。^[4]

参照

参考文献

^ Plump D. (Hartmut Ehrig、G. Engels、Grzegorz Rozenberg 編) (1999)。グラフ文法とグラフ変換によるコンピューティングのハンドブック: アプリケーション、言語、ツール。第 2 巻。World Scientific。pp. 9–13。ISBN 9789810228842。{{cite book}}: CS1 maint: multiple names: authors list (link)
^ バレンドレット;ファン・エーケレン。グラウアートケナウェイ。プラスマイヤー;スリープ (1987)。「項グラフ書き換え」。PARLE Parallel Architectures and Languages Europe (コンピュータサイエンスの講義ノート)。コンピューターサイエンスの講義ノート。259：141-158。土井：10.1007/3-540-17945-3_8。ISBN 978-3-540-17945-0。
^ 「TERMGRAPH 2013」.
^ Fritz Henglein (1988)。型推論と半統合。1988 ACM LISP および関数型プログラミング会議論文集、pp. 184-197。doi : 10.1145/62678.62701

[Plump1999-1] Plump D. (Hartmut Ehrig、G. Engels、Grzegorz Rozenberg 編) (1999)。グラフ文法とグラフ変換によるコンピューティングのハンドブック: アプリケーション、言語、ツール。第 2 巻。World Scientific。pp. 9–13。ISBN 9789810228842。{{cite book}}: CS1 maint: multiple names: authors list (link)

[Barendregt1987-2] バレンドレット;ファン・エーケレン。グラウアートケナウェイ。プラスマイヤー;スリープ (1987)。「項グラフ書き換え」。PARLE Parallel Architectures and Languages Europe (コンピュータサイエンスの講義ノート)。コンピューターサイエンスの講義ノート。259：141-158。土井：10.1007/3-540-17945-3_8。ISBN 978-3-540-17945-0。

[3] 「TERMGRAPH 2013」.

[4] Fritz Henglein (1988)。型推論と半統合。1988 ACM LISP および関数型プログラミング会議論文集、pp. 184-197。doi : 10.1145/62678.62701