Van Wijngaarden文法
Van Wijngaarden文法（W-grammarとも呼ばれる）は、文脈自由文法を2段階に拡張した形式文法である。オランダの数学者でありコンピュータ科学者であるAdriaan van Wijngaardenによって考案され、プログラミング言語Algol 68の構文定義に使用された。この文法は、無限の生成規則集合を有限のメタルールで記述できる特徴を持つ。
背景メモ
- **Van Wijngaarden文法**は、オランダの数学者・計算機科学者アドリアン・ファン・ワインガーデン（Adriaan van Wijngaarden）が1960年代に考案した形式文法。最も有名な応用例が、プログラミング言語ALGOL 68の構文定義である。
- 通常の文脈自由文法（BNFなど）を2段階に拡張した「二段階文法（two-level grammar）」であり、ひとつの文法規則が別の文法規則を「メタルール」として参照・生成できる。この仕組みにより、文脈依存（例えば変数の宣言前使用禁止など）も表現可能。
- 理論的にはチューリング完全な表現力を持つが、その複雑さゆえ実用のプログラミング言語処理系での採用は限定的。後発のAttribute Grammarなど理論的基盤として影響を与えた。
- 名前はファン・ワインガーデン本人に由来するが、「Wijngaarden」のオランダ語発音は「ヴァインガールデン」に近い。英語圏では「ヴァン・ワインガーデン」と読まれることが多い。