属性文法
属性文法（ぞくせいぶんぽう、Attribute Grammar）とは、形式文法の生成に関する属性を定義する形式的手法。属性には値を関連付けられる。その言語を構文解析やコンパイラで処理する際に、属性の評価（属性から値を得ること）が抽象構文木上のノードで行われる。
属性は2種類に分類される。合成(sythesized)属性と継承(inherited)属性である。合成属性とは、属性評価の結果として生成されるものであり、継承属性の値を使用することもある。継承属性とは、親ノードから継承される属性である。
いくつかの手法では、合成属性は意味情報を構文解析木の上に渡すのに使われ、継承属性は逆に下に渡すのに使われる。例えば、言語変換ツールを作成する場合、属性文法は構文要素に意味（値）を設定するのに使われる。また、文法（構文規則だけでは明示的に示されない言語の規則）に従って意味論的検証を行うことも可能である。
属性文法は構文木を変換して特定マシン向けのコードを直接生成することもできる（あるいは中間言語を生成する）。
属性文法の強みは、制御された形式的手法で抽象構文木を任意の別の形態に変換できることである[要出典]。
各種属性文法
- L属性文法
- 抽象構文木を左から右に評価していく。L属性文法で評価された属性は一種のトップダウン構文解析である。多くのプログラミング言語はL属性である。narrow コンパイラと呼ばれる特殊なコンパイラは L属性文法に基づいている。
- S属性文法
- 継承属性を持たない属性文法。トップダウン構文解析でもボトムアップ構文解析でも使用可能。yacc は S属性文法に基づいている。
- LR属性文法
- LR法を使った構文解析での属性文法。ボトムアップ構文解析で使用。L属性文法のサブセットであり、S属性文法のスーパーセットである。yacc は部分的に LR属性文法に基づいている。
- ECLR属性文法
- LR属性文法の派生。継承属性間の等価関係を利用して属性評価を最適化している。EC とは equivalence class の略。LR属性文法のスーパーセットである。
外部リンク
- Why Attribute Grammars Matter, The Monad Reader, Issue 4, 2005年7月5日
- Semantics of context-free grammars ドナルド・クヌースによる最初の属性文法に関する論文
- D. E. Knuth: The genesis of attribute grammars. Proceedings of the international conference on Attribute grammars and their applications (1990), 1–12. 歴史に関する情報あり
- Jukka Paakki: Attribute grammar paradigms—a high-level methodology in language implementation. ACM Computing Surveys 27:2 (June 1995), 196–255.