属性文法

属性文法は、意味情報処理によって形式文法を補完する形式的な手法である。意味情報は、文法の終端記号および非終端記号に関連付けられた属性に格納される。属性の値は、文法の生成規則に関連付けられた属性評価規則の結果である。属性は、抽象構文木内の任意の場所から他の任意の場所へ、制御された形式的な方法で情報を転送することを可能にする。 ^[1]

各意味関数は、1つの生成規則にのみ出現するシンボルの属性を扱います。つまり、意味関数のパラメータと結果は、特定の規則に含まれるシンボルの属性です。意味関数が規則の左側にあるシンボルの属性の値を定義する場合、その属性は合成属性と呼ばれます。そうでない場合は、継承属性と呼ばれます。^[2]したがって、合成属性は意味情報を構文木の上方に渡す役割を果たし、継承属性は親ノードから構文木の下方に値を渡すことを可能にします。

算術式の評価などの単純なアプリケーションでは、属性文法は、構文解析だけでなく、実行されるタスク全体を直接的に記述するために使用できます。一方、複雑なシステムでは、例えばコンパイラなどの言語翻訳ツールを構築する場合、構文定義では明示的に与えられていない言語の規則を表す文法に関連する意味チェックを検証するために使用できます。また、パーサーやコンパイラが構文木を特定のマシン用のコードに直接変換したり、中間言語に変換したりするためにも使用できます。

歴史

属性文法はドナルド・クヌースとピーター・ウェグナーによって発明されました^[3]。ドナルド・クヌースが全体の概念を考案したとされていますが、ピーター・ウェグナーはクヌースとの会話の中で継承属性を考案しました。初期のアイデアのいくつかは^[3]、IMPの著者であるエドガー・T・「ネッド」・アイアンズ^[4]の研究に遡ります。

例

以下は、整数の乗算と加算で構成される言語を記述できる単純な文脈自由文法です。

 Expr → Expr + Term  Expr → Term  Term → Term * Factor  Term → Factor  Factor → "(" Expr ")" Factor → integer

以下の属性文法は、文法で記述された式の結果を計算するために使用できます。この文法は合成値のみを使用するため、S属性文法であることに注意してください。

 Expr ₁ → Expr ₂ + Term [ Expr ₁ .value = Expr ₂ .value + Term .value ] Expr → Term [ Expr .value = Term .value ] Term ₁ → Term ₂ * Factor [ Term ₁ .value = Term ₂ .value * Factor .value ] Term → Factor [ Term .value = Factor .value ] Factor → "(" Expr ")" [ Factor .value = Expr .value ] Factor → integer [ Factor .value = strToInt( integer .str) ]

合成属性

合成属性は、子の属性の値から計算されます。子の値は最初に計算する必要があるため、これはボトムアップ伝播の例です。^[5]合成属性を正式に定義するために、形式文法を次のように定義します。 $G=\langle V_{n},V_{t},P,S\rangle$

$V_{n}$ 非終端記号の集合である
$V_{t}$ 終端記号の集合である
$P$ は生成規則の集合である
$S$ は、区別される、または開始のシンボルです

次に、非終端記号の文字列と属性名が与えられた場合、次の 3 つの条件がすべて満たされると、は合成属性になります。 $A$ $a$ $Aa$

$A\rightarrow \alpha \in P$ （ieは文法のルールの1つです） $A\rightarrow \alpha$
$\alpha =\alpha _{1}\ldots \alpha _{n},\forall i,1\leq i\leq n:\alpha _{i}\in (V_{n}\cup V_{t})$ （つまり、ルール本体内のすべてのシンボルは非終端記号か終端記号のいずれかです）
$Aa=f(\alpha _{j_{1}}.a_{1},\ldots ,\alpha _{j_{m}}.a_{m})$ ここで（つまり、属性の値はルール本体のシンボルからいくつかの値に適用される関数です） $\{\alpha _{j_{1}},\ldots ,\alpha _{j_{m}}\}\subseteq \{\alpha _{1},\ldots ,\alpha _{n}\}$ $f$

継承された属性

構文木内のノードにおける継承属性は、親ノードまたは兄弟ノードの属性値を用いて定義されます。継承属性は、プログラミング言語構成要素が、それが出現する文脈に依存することを表現するのに便利です。例えば、継承属性を用いることで、識別子が代入文の左側に現れるか右側に現れるかを把握し、その識別子のアドレスと値のうちどちらが必要かを判断することができます。合成属性とは異なり、継承属性は親ノードおよび／または兄弟ノードから値を取得できます。以下の生成規則の例のように、

S → ABC

ここで、A は S、B、C から値を取得できます。B は S、A、C から値を取得できます。同様に、C は S、A、B から値を取得できます。

特殊な属性文法

L属性文法:継承された属性は、抽象構文木を左から右に1回走査するだけで評価できます。
LR 属性文法:継承された属性をボトムアップ構文解析でも評価できるL 属性文法。
ECLR 属性文法: 等価クラスを使用して継承された属性の評価を最適化できる LR 属性文法のサブセット。
S属性文法:合成属性のみを使用し、継承属性を使用しない単純なタイプの属性文法

参照

参考文献

^ クヌース 1968年、134ページ。
^ クヌース 1968年、132ページ。
^ ab DE Knuth: 属性文法の起源.属性文法とその応用に関する国際会議議事録(1990)、LNCS、第461巻、1-12ページ。
^ 「メイン」。
^ クヌース 1968年、130ページ。

属性文法を導入した原著論文：ドナルド・E.・クヌース(1968). 「文脈自由言語の意味論」(PDF) .数学システム理論. 2 (2): 127– 145. doi :10.1007/BF01692511. S2CID 5182310. 2020年5月19日時点のオリジナルよりアーカイブ. 2018年3月23日閲覧.{{cite journal}}: CS1 maint: bot: 元のURLステータス不明（リンク）、

外部リンク

なぜ属性文法が重要なのか、The Monad Reader、第4号、2005年7月5日。（この記事では、属性文法の形式主義が、カタモルフィズムを構成的に記述できるようにすることで、関数型プログラミングにアスペクト指向プログラミングをもたらす仕組みについて解説しています。例に使用されている実装としては、ユトレヒト大学の属性文法システム（ Wayback Machineにアーカイブされた2013-06-05）を参照しています（Lrc: 純粋に機能的な高階属性文法ベースのシステムも参照してください）。）
Haskellと関数型プログラミングに関連した属性文法。
Jukka Paakki: 属性文法パラダイム—言語実装における高水準手法. ACM Computing Surveys 27 :2 (1995年6月), 196–255.
Oxは、 LexおよびYacc仕様を、Oxと C / C++構文の組み合わせで記述された合成属性および継承属性の定義で拡張する属性文法コンパイルシステムです。これらの仕様から、Oxは属性付き構文解析木を構築および修飾する通常のLexおよびYacc仕様を生成します。Oxは、UnixおよびSolarisオペレーティングシステム、 Flex、RE/flex、Bison、BYacc、BtYacc 、およびMSTA（DINO GitHubリポジトリ内）で配布されているLexおよびYaccバージョンで動作します。（SourceForgeリポジトリを参照してください。）
Silver は、ミネソタ大学発の拡張可能な属性文法仕様言語およびシステムです。（GitHub リポジトリも参照してください。）

[FOOTNOTEKnuth1968134-1] クヌース 1968年、134ページ。

[FOOTNOTEKnuth1968132-2] クヌース 1968年、132ページ。

[genesis-3] DE Knuth: 属性文法の起源.属性文法とその応用に関する国際会議議事録(1990)、LNCS、第461巻、1-12ページ。

[4] 「メイン」。

[FOOTNOTEKnuth1968130-5] クヌース 1968年、130ページ。