属性文法

属性文法とは

属性文法（Attribute Grammar）は、形式文法の生成に関連する属性を規定する方法です。この手法では、特定の言語の構文を解析したり、コンパイラを開発する際に、属性の評価が抽象構文木の各ノードで行われます。属性は、合成属性と継承属性の2つに分けられ、言語処理においては非常に重要な役割を果たします。

属性のタイプ

合成属性

合成属性は、属性評価の結果として生成されるものであり、他の属性の値を使用する可能性があります。たとえば、子ノードの値を集約して、親ノードに合成することが要件となる場合が多いです。

継承属性

一方で、継承属性は親ノードから引き継がれる属性です。これにより、構文木の下層から上層への属性伝達が可能となります。どちらの属性も、言語の意味論的なチェックや情報の伝達に寄与しています。

属性文法の活用

属性文法を利用する手法には、特に構文解析ツール（例：yaccやその互換ツールのBisonなど）が含まれます。yaccはLALR(1)のパーサを生成できるツールであり、構文規則に「セマンティックアクション」としてコードを入力することで、構文解析の結果をC言語のコードに組み込むことができます。このようにして、子ノードからの情報が親ノードに対して合成され、より効率的な処理が可能となります。

この手法を使用することで、具象構文木を生成する以外にも、簡単な言語やターゲット向けにネイティブコードや中間言語の生成も行なえます。

属性文法の種類

L属性文法

L属性文法は、抽象構文木を左から右に評価する形式です。この評価手法は一種のトップダウン解析を行い、多くのプログラミング言語がこの形式を基にしています。また、narrowコンパイラのようにL属性文法に特化したコンパイラも存在します。

S属性文法

S属性文法は継承属性を保有しない属性文法です。これは、トップダウン解析やボトムアップ解析の両方で使用可能で、yaccはこのS属性文法に則って開発されています。

LR属性文法

LR属性文法は、ボトムアップ解析の文脈で使用される属性文法です。この手法はL属性文法のサブセットであり、S属性文法のスーパーセットでもあります。yaccは部分的にこのLR属性文法に基づいています。

ECLR属性文法

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.

これらの文献では、属性文法の進化や応用についてさらに詳しい知見を得ることができます。

もう一度検索